如何知道何时在regex解析树中插入连接节点？

Question

我正在做一个有趣的项目，涉及从正则表达式生成解析树。我已经让它大部分工作了，但是我被如何集成连接挂住了。

*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中构建树。)

现在，我花了几个小时寻找一个教程，解释如何做到这一点，但没有任何运气。如果有人能看到如何修改代码，或者能给我指明正确的方向，我将不胜感激。

Answer 1

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

"abcd“加上infix &会是什么样子？它是a&b&c&d。这应该是后缀ab&c&d&还是abcd&？第一个是左关联的，第二个是右关联的。我认为第二种方法更适合解析正则表达式。

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

我将了解如何增强您的代码以添加&...

更新:你的代码在

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

我不能轻松地修复bug并将其扩展到add &，所以我现在放弃了。