コンパイラ設計-ボトムアップパーサー

ボトムアップ解析は、ツリーの葉ノードから始まり、ルートノードに到達するまで上方向に動作します。ここでは、文から開始し、開始記号に到達するために逆の方法で生産規則を適用します。以下の画像は、利用可能なボトムアップパーサーを示しています。

シフトリデュース解析

Shift-reduce解析では、ボトムアップ解析のために2つのユニークなステップを使用します。これらのステップは、シフトステップおよびリデュースステップとして知られています。

シフトステップ：シフトステップは、シフトされたシンボルと呼ばれる次の入力シンボルへの入力ポインタの前進を指します。このシンボルはスタックにプッシュされます。シフトされたシンボルは、解析ツリーの単一ノードとして扱われます。
リデュースステップ：パーサーが完全な文法ルール（RHS）を見つけて、それを（LHS）に置き換えるとき、それはリデュースステップと呼ばれます。これは、スタックの最上部にハンドルが含まれている場合に発生します。削減するために、POP関数がスタック上で実行され、ハンドルからポップされ、LHS非終端記号に置き換えられます。

LRパーサー

LRパーサーは、非再帰的、シフト削減、ボトムアップパーサーです。コンテキストに依存しない幅広いクラスの文法を使用しているため、最も効率的な構文解析手法となります。 LRパーサーはLR（k）パーサーとしても知られています。Lは入力ストリームの左から右へのスキャンを表します。 Rは右端の派生の逆の構築を表し、kは決定を行う先読みシンボルの数を示します。

LRパーサーの構築には、広く使用されている3つのアルゴリズムがあります。

SLR（1）–シンプルLRパーサー：
最小クラスの文法で動作します
少数の州、したがって非常に小さなテーブル
シンプルで高速な構造
LR（1）– LRパーサー：
LR（1）文法の完全なセットで動作します
大きなテーブルと多数の状態を生成します
遅い建設
LALR（1）–先読みLRパーサー：
文法の中間サイズで動作します *状態の数はSLR（1）と同じです

LR解析アルゴリズム

ここでは、LRパーサーのスケルトンアルゴリズムについて説明します。

token = next_token()

repeat forever
   s = top of stack

   if action[s, token] = “shift si” then
      PUSH token
      PUSH si
      token = next_token()

   else if action[s, token] = “reduce A::= β“ then
      POP 2* |β| symbols
      s = top of stack
      PUSH A
      PUSH goto[s,A]

   else if action[s, token] = “accept” then
      return

   else
      error()

LL vs. LR

LL	LR
Does a leftmost derivation.	Does a rightmost derivation in reverse.
Starts with the root nonterminal on the stack.	Ends with the root nonterminal on the stack.
Ends when the stack is empty.	Starts with an empty stack.
Uses the stack for designating what is still to be expected.	Uses the stack for designating what is already seen.
Builds the parse tree top-down.	Builds the parse tree bottom-up.
Continuously pops a nonterminal off the stack, and pushes the corresponding right hand side.	Tries to recognize a right hand side on the stack, pops it, and pushes the corresponding nonterminal.
Expands the non-terminals.	Reduces the non-terminals.
Reads the terminals when it pops one off the stack.	Reads the terminals while it pushes them on the stack.
Pre-order traversal of the parse tree.	Post-order traversal of the parse tree.

Compiler-design-bottom-up-parser

目次

コンパイラ設計-ボトムアップパーサー

シフトリデュース解析

LRパーサー

LR解析アルゴリズム

LL vs. LR