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 で簡単に構築できます。)

ここ数時間、これを行う方法を説明するチュートリアルを探していましたが、うまくいきませんでした。ぶら下がっている式がいくつあるかを追跡する必要があると言いたいのですが、3 つを作成するようなことをする場合は「&」を挿入しますが、それは非効率的であり、より良い方法があると確信しています。 . 誰かがコードを変更する方法を知っているか、正しい方向に私を向けることができれば、私はそれを高く評価します.

4

1 に答える 1

3

分流場アルゴリズムは、主に、中置演算子から後置演算子への変換を処理するように設計されています。2 つの複雑な点は、正規表現の構文に既に後置演算子 * があることと、中置連結演算子が暗黙的であることです。これらの組み合わせにより、解析が面倒になります。

"abcd" は中置 & でどのように見えますか? a&b&c&dです。これは接尾辞 ab&c&d& または abcd&&& のどちらである必要がありますか? 1 つ目は左結合で、2 つ目は右結合です。正規表現の解析には 2 番目の方が適していると思います。

ここで、a、b、c、または d のそれぞれは、括弧内の正規表現であり、それぞれの後に「*」が続く場合があります。

& を追加するようにコードを拡張する方法について説明します。

更新: コードが間違っています

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

簡単にバグを修正して & を追加するように拡張することはできないので、今のところあきらめています。

于 2012-04-28T10:55:34.177 に答える