コンパイラの仕組み（Chapter5 下向き構文解析）

本
  • 演算子順位法は以下のような文法には適用できない
    • 非終端記号が隣接する形で生成規則の右辺が書かれている文法
    • 省略可能な（生成規則の右辺がεとなっている）非終端記号を含む文法
      • y=abはy=a*bだとするという文法は適用できないはず？（省略がこれしかなければ適用できるのかな？）
  • 上位の構文から下位の構文へと計算を進める構文解析を下向き構文解析(topdown parsing)とよぶ。条件としては以下のようなものがある
    • 入力を一つ読むごとに、それが生成規則のどの構文要素に当たるかが一意にわかること（必須ではないが、構文要素の確定のために先読みが必要なので大変になる）
    • 構文規則が左再帰をもたないこと。（左再帰を持ってしまうと構文要素の確定ができず、無限ループに入ってしまう）
  • 入力を一つ読むごとに、一意にわかるので、先頭に来る可能性のある記号の集合FIRSTを求めておき、その集合に入っているかどうかを考慮すればよい。
  • ただし、εが存在する場合は次の集合を読む必要があるので、次に来る可能性のある文字の集合FOLLOWを作成しておく。ただし、次の文字もεの可能性があるので、簡単ではない。
  • First(α)集合の作り方（αは構文記号）
    1. αが終端記号であれば、First(α)={α}とする
    2. α→ε（α自体が省略可能）であればεをFirst集合に加える
    3. α→βγという生成規則があれば、First(β)をFirst(α)に加える
    4. α→β1β2・・・　βnと合った場合、k
      • k=nは含まないことに注意！k=nになると全体が省略可能と同意となり、α→εと同意になる
    • 上記を繰り返し、どのFirst集合に対する追加が無くなるまで行う
  • Follow(B)の作り方（Ｂは非終端記号）
    1. Bが開始記号であれば、入力終了文字を＄で表すとして、Follow(B)に＄を含める
    2. 生成規則Ａ→αＢβがあれば、First(β）からεを除いたものをFollow(B)に加える。
    3. 生成規則Ａ→αＢがある場合、および生成規則Ａ→αＢβがあって、βが省略可能な場合、Follow(A)をFollow(B)に加える
    4. 上記を繰り返し、どの非終端記号のFollowに対しても要素の追加が無くなるまで繰り返す
  • 非終端記号Ａと終端記号aの組み合わせについて選択する生成規則を示す表を作ることができる。これを構文解析表という。
  • この構文解析表において、どの組み合わせにおいても生成規則が重複しない場合はLL(1)文法(Left-right scan Leftmost derivation grammer)と呼ぶ。
  • ある入力列を読んだ場合、それに適合する可能性のある生成規則はどれとどれである、ということを状態として記録しておき、入力記号の列を読むに従って、それらの状態間で遷移していき、可能性のある生成規則が一つに絞られた段階で、その生成規則に対する照合がすんで、構文要素が一つ確定できるという方法が考えられる。これを実用化したものがLR構文解析系とよぶ