左括り出しと左再帰除去

構文解析


言語パーサー勉強会で習ったことメモ。


LL系のパーサーは左側から順にトークンを読んで処理していくので、
まず、

  1. 左側にどんな種類のトークンに何が来るか？
  2. どのトークンの場合は何をする？（どの選言を処理する？）

というのが定まる必要がある。

  • 左括り出し

選言がある式で、左のトークンが重複してると上手く解析できない
そこで、左のトークンの重複をなくすように式変換する。

    • 左括り出し前
     Ex ::= 'a' 'b'
        |   'a' 'c'
        |   'a'
      • 'a' というトークンが来たとき、どの選言を使うのか定まらない（＝何をするか決まらない）
    • 左括り出し後
     Ex  ::= 'a' Ex2
     Ex2 ::= 'b'
         |   'c'
         |   empty

再帰がある式で、左端で再帰していると上手く解析できない
そこで（ｒｙ

     Ex ::= Ex 'b'
        |   'a'
      • 左側でExを再帰的によびだしているので、Exの左端に何が来る？が定まらない
        • いや、人間の頭で考えりゃわかるけど、機械のキモチになると「ExはExで始まる」が無限ループするので・・
    • 左括り出し後
     Ex  ::= 'a' Ex2
     Ex2 ::= 'b' Ex2
         |   empty


うん。純粋に勉強としてオモシロイかった。

何に使ったら嬉しいかは・・・考え中。笑