1

我正在从事一个有趣的项目，该项目涉及从正则表达式生成解析树。我已经让它大部分工作了，但我对如何集成连接很感兴趣。

*Main> :l regex.hs 
[1 of 1] Compiling Main             ( regex.hs, interpreted )
Ok, modules loaded: Main.
*Main> toPostfix "a"
"a"
*Main> toPostfix "a|b"
"ab|"
*Main> toPostfix "((a|b)|c)"
"ab|c|"
*Main> toPostfix "((a|b)|c)de"
"ab|c|de"
*Main> toPostfix "((a|b)|c)*de"
"ab|c|*de"
*Main> toPostfix "(ab)*"
"ab*" -- Should be ab&*
*Main> toPostfix "(ab|bc)"
"abbc|" -- Should be ab&bc&|

这是我的代码：

import Data.List
import Control.Monad

data Reg = Epsilon |
           Literal Char |
           Or Reg Reg |
           Concat Reg Reg |
           Star Reg
           deriving Eq


showReg :: Reg -> [Char]
showReg Epsilon        = "@"
showReg (Literal c)    = [c]
showReg (Or r1 r2)     = "(" ++ showReg r1 ++  "|" ++ showReg r2 ++ ")"
showReg (Concat r1 r2)   = "(" ++ showReg r1 ++ showReg r2 ++ ")"
showReg (Star r)       = showReg r ++ "*"


instance Show Reg where
    show = showReg

evalPostfix :: String -> Reg 
evalPostfix = head . foldl comb []
    where
        comb :: [Reg] -> Char -> [Reg]
        comb (x:y:ys) '|'   = (Or y x) : ys
        comb (x:y:ys) '&'   = (Concat y x) : ys
        comb (x:xs) '*'     = (Star x) : xs
        comb xs '@'         = Epsilon : xs
        comb xs s           = (Literal s) : xs


-- Apply the shunting-yard algorithm to turn an infix expression
-- into a postfix expression.
shunt :: String -> String -> String -> String
shunt o p [] = (reverse o) ++ p
shunt o [] (x:xs)
    | x == '(' = shunt o [x] xs
    | x == '|' = shunt o [x] xs
    | otherwise = shunt (x:o) [] xs
shunt o (p:ps) (x:xs)
    | x == '(' = shunt o (x:p:ps) xs
    | x == ')' = case (span (/= '(') (p:ps)) of
        (as, b:bs) -> shunt (as ++ o) bs xs
    | x == '|' = case (p) of
        '(' -> shunt o (x:p:ps) xs
        otherwise -> shunt (p:o) (x:ps) xs
    | x == '*' = shunt (x:o) (p:ps) xs
    | otherwise = shunt (x:o) (p:ps) xs


-- | Convert an infix expression to postfix
toPostfix :: String -> String
toPostfix = shunt [] []


-- | Evaluate an infix expression
eval :: String -> Reg
eval = evalPostfix . toPostfix

特别是，分流功能正在完成所有繁重的工作，是应该进行更改的地方。（这棵树可以很容易地在 evalPostfix 中构建。）

现在，我花了最后几个小时寻找解释如何做到这一点的教程，但没有任何运气。我想说我需要跟踪我有多少悬挂表达式，如果我会做任何会创建三个的事情，请插入一个“&”，但这似乎效率低下，我确信有更好的方法. 如果有人可以看到如何更改代码或可以指出我正确的方向，我将不胜感激。

4

1 回答 1

3

调车场算法主要用于处理中缀运算符到后缀运算符的转换。两个复杂性是正则表达式语法已经有一个后缀运算符 *，并且中缀连接运算符是隐式的。这些组合使解析变得烦人。

“abcd”与中缀 & 看起来如何？这是a&b&c&d。这应该是后缀ab&c&d&还是abcd&&&？第一个是左关联的，第二个是右关联的。我声称第二个更适合解析正则表达式。

现在，a、b、c 或 d 中的每一个都可能是括号中的正则表达式，并且每个都可能后跟一个“*”。

我将看到有关增强您的代码以添加 &...

更新：您的代码错误

*Main> toPostfix' "a|bcd"
"abcd|"

我不能轻易修复错误并将其扩展为添加 &，所以我现在放弃了。

于 2012-04-28T10:55:34.177 回答