左再帰の除去についてプチまとめ

Verilogパーサを書き進めていくと、Verilog構文の左再帰に遭遇します。
Haskell Parsecは再帰下降パーサということで、左再帰の構文をそのまま書くと
stack overflowを起こしてうまく処理を続けられません。
うまいこと左再帰を除去（右再帰に置き換える）する必要があります。
というわけで、ドラゴンブックを読んで仕入れた知識をもとに
うまいこと左再帰を除去してみたので、書いておきます。

左再帰の文法が

    A → Aα | β

のようにあるとき、↓のように置き換えていきます。

    A  → βA'
    A' → αA' | ε

とゆーわけで、Verilogの BNFから、左再帰の部分を抜粋してみます。

<expression>
    ::= <primary>
    ||= <UNARY_OPERATOR> <primary>
    ||= <expression> <BINARY_OPERATOR> <expression>
    ||= <expression> <QUESTION_MARK> <expression> : <expression>
    ||= <STRING>

んー、このままだと、ちょっとわかりにくいので、変形してみます。
とりあえず A, α, βと対応させられるように、ということで。

変形その1

<expression>
    ::= <Beta>
    ||= <expression> <BINARY_OPERATOR> <expression>
    ||= <expression> <QUESTION_MARK> <expression> : <expression>

<Beta>
    ::= <primary>
    ||= <UNARY_OPERATOR> <primary>
    ||= <STRING>

構造が単純になってきました。
が、もうちょっと変形します。

変形その2

<expression>
    ::= <Beta>
    ||= <expression> <Alpha1>
    ||= <expression> <Alpha2>

<Alpha1>
    ::= <BINARY_OPERATOR> <expression>

<Alpha2>
    ::= <QUESTION_MARK> <expression> : <expression>

<Beta>
    ::= <primary>
    ||= <UNARY_OPERATOR> <primary>
    ||= <STRING>

単純な左再帰の文法にしか見えなくなりました。（見えなくなったはず！）

そういうわけで、この文法を右再帰の文法に変形すれば完了、と思います。

変形その3

<expression>
    ::= <Beta> <expression_>
    ||= <Beta> <expression__>

<expression_>
    ::= [<BINARY_OPERATOR> <expression> <expression_>]

<expression__>
    ::= [<QUESTION_MARK> <expression> : <expression> <expression__>]

<Beta>
    ::= <primary>
    ||= <UNARY_OPERATOR> <primary>
    ||= <STRING>

（たぶんこれでよいのではないかなぁ？）

Haskellコード

じゃ、この部分の Haskellコードです。
ソース全体は githubにて。まだまだまだまだ書きかけですが＞＜
http://github.com/kei-os/vparsec/tree/master/Vparsec.hs

lexeme, tryを入れすぎな気もします。
まだまだ Haskell経験が浅いな。

expression :: Parser String
expression = do { a <- optExpression
                ; b <- expression_ <|> expression__
                ; return $ a ++ b }
        <?> "expression"
    where
        optExpression = try(primary)
          <|> try(do { a <- lexeme unaryOperator
                     ; b <- lexeme primary
                     ; return $ a ++ b })
          <|> string'
        expression_
            = try(do { a <- lexeme binaryOperator
                     ; b <- lexeme expression
                     ; c <- lexeme expression_
                     ; return $ a ++ b ++ c })
          <|> string ""
        expression__
            = try(do { a <- lexeme questionMark
                     ; b <- lexeme expression
                     ; c <- colon
                     ; d <- lexeme expression
                     ; e <- lexeme expression__
                     ; return $ a ++ b ++ c ++ d ++ e })
          <|> string ""