FParsecで左再帰を試してみる

F# のパーサーコンビネーター FParsec を使って、左再帰の文法を書くとどうなるか試してみた。左再帰についての説明は Wikipedia から引用しておく。

左再帰（英: Left recursion）とは、言語（普通、形式言語について言うが、自然言語に対しても考えられ得る）の文法（構文規則）にあらわれる再帰的な規則（定義）の特殊な場合で、ある非終端記号を展開した結果、その先頭（最も左）にその非終端記号自身があらわれるような再帰のことである。

文法はこんなイメージ。足し算、引き算、数値に対応。足し算と引き算について、 expr が一番左に来ているため左再帰となっている。

expr = expr '+' num
     | expr '-' num
     | num

これをコードで書くと以下のようになる。 pAddition , pSubtraction の先頭に pExpression が登場している。

open FParsec

type Expression =
    | Addition of Expression * float
    | Subtraction of Expression * float
    | Term of float

let pExpression, pExpressionRef = createParserForwardedToRef()

let pAddition =
    pExpression .>>. ((spaces >>. pchar '+' >>. spaces) >>. pfloat)
    |>> Addition

let pSubtraction =
    pExpression .>>. ((spaces >>. pchar '-' >>. spaces) >>. pfloat)
    |>> Subtraction

let pTerm = pfloat |>> Term

pExpressionRef.Value <-
    pAddition
    <|> pSubtraction
    <|> pTerm

生成したパーサー pExpression を使って、実際にパースしてみるとどうなるか。

> run pExpression "1-2+3-4";;
Binding session to '/home/gingk/.nuget/packages/fparsec/1.1.1/lib/netstandard2.0/FParsec.dll'...
Binding session to '/home/gingk/.nuget/packages/fparsec/1.1.1/lib/netstandard2.0/FParsecCS.dll'...
Stack overflow.
Repeat 8717 times:
--------------------------------
   at FParsec.Primitives+op_DotGreaterGreaterDot@104[[System.__Canon, System.Private.CoreLib, Version=6.0.0.0, Culture=neutral, PublicKeyToken=7cec85d7bea7798e],[System.__Canon, System.Private.CoreLib, Version=6.0.0.0, Culture=neutral, PublicKeyToken=7cec85d7bea7798e],[System.Double, System.Private.CoreLib, Version=6.0.0.0, Culture=neutral, PublicKeyToken=7cec85d7bea7798e]].Invoke(FParsec.CharStream`1<System.__Canon>)
   at FParsec.Primitives+op_BarGreaterGreater@143[[System.__Canon, System.Private.CoreLib, Version=6.0.0.0, Culture=neutral, PublicKeyToken=7cec85d7bea7798e],[System.__Canon, System.Private.CoreLib, Version=6.0.0.0, Culture=neutral, PublicKeyToken=7cec85d7bea7798e],[System.__Canon, System.Private.CoreLib, Version=6.0.0.0, Culture=neutral, PublicKeyToken=7cec85d7bea7798e]].Invoke(FParsec.CharStream`1<System.__Canon>)
...

結果として、スタックオーバーフローが発生して落ちた。要は無限ループが発生したわけである。まあ当たり前と言えば当たり前ではあるが、実際に確認できてよかった。

ここからは余談。左再帰を避けて実装してみる。

open FParsec

type Expression =
    | Addition of float * Expression
    | Subtraction of float * Expression
    | Term of float

let pExpression, pExpressionRef = createParserForwardedToRef()

let pAddition =
    pfloat .>>. ((spaces >>. pchar '+' >>. spaces) >>. pExpression)
    |>> Addition

let pSubtraction =
    pfloat .>>. ((spaces >>. pchar '-' >>. spaces) >>. pExpression)
    |>> Subtraction

let pTerm = pfloat |>> Term

pExpressionRef.Value <-
    attempt pAddition
    <|> attempt pSubtraction
    <|> pTerm

以下の通り、問題なくパースできた。

> run pExpression "1-2+3-4";;
val it: ParserResult<Expression,unit> =
  Success: Subtraction (1.0, Addition (2.0, Subtraction (3.0, Term 4.0)))

さらに余談。上のコードでは attempt によるバックトラック (巻き戻し) を活用していたが、バックトラックを避けて以下のようにも書ける。

open FParsec

type Expression =
    | Addition of float * Expression
    | Subtraction of float * Expression
    | Term of float

let pExpression, pExpressionRef = createParserForwardedToRef()

let pBinop =
    tuple2 (pchar '+' <|> pchar '-') (spaces >>. pExpression)

pExpressionRef.Value <-
    pipe2
        (pfloat .>> spaces)
        ((eof >>% None) <|> (pBinop |>> Some))
        (fun num opt ->
            match opt with
            | Some(binop) ->
                match binop with
                | ('+', exp) -> Addition (num, exp)
                | ('-', exp) -> Subtraction (num, exp)
                | _ -> failwith "not reachable"
            | None -> Term num)

こちらのほうが効率が良くて良さげ。パース実行結果は以下。

> run pExpression "1-2+3-4";;
val it: ParserResult<Expression,unit> =
  Success: Subtraction (1.0, Addition (2.0, Subtraction (3.0, Term 4.0)))