Compiler-design-top-down-parser
コンパイラ設計-トップダウンパーサー
前の章で、トップダウン解析手法が入力を解析し、ルートノードから解析ノードの構築を開始し、徐々にリーフノードに移動することを学びました。 トップダウン解析のタイプは次のとおりです。
再帰降下解析
再帰降下は、上から解析ツリーを構築するトップダウン解析手法であり、入力は左から右に読み取られます。 すべての端末および非端末エンティティに対して手順を使用します。 この解析手法では、入力を再帰的に解析して解析ツリーを作成します。解析ツリーでは、バックトラッキングが必要な場合と必要でない場合があります。 しかし、それに関連付けられている文法（因数分解されていない場合）は、バックトラッキングを回避できません。 バックトラッキングを必要としない再帰下降解析の形式は、*予測解析*として知られています。
この構文解析手法は、本質的に再帰的なコンテキストフリーの文法を使用するため、再帰的と見なされます。
バックトラッキング
トップダウンパーサーはルートノード（開始記号）から開始し、入力文字列をプロダクションルールと照合して置き換えます（一致する場合）。 これを理解するには、次のCFGの例をご覧ください。
S → rXd | rZd
X → oa | ea
Z → ai入力文字列の場合：トップダウンパーサーであるreadは、次のように動作します。
プロダクションルールのSで始まり、その出力を入力の左端の文字に一致させます。 ‘r’. Sのまさに生成（S→rXd）はそれに一致します。 したがって、トップダウンパーサーは次の入力文字に進みます（つまり、 「e」）。 パーサーは非終端「X」を展開しようとし、その生成を左からチェックします（X→oa）。 次の入力シンボルと一致しません。 したがって、トップダウンパーサーはバックトラックして、Xの次のプロダクションルールを取得します（X→ea）。
これで、パーサーはすべての入力文字を順番に一致させます。 文字列は受け入れられます。
| Back Tracking | Back Tracking | Back Tracking | Back Tracking |
予測パーサー
予測パーサーは、再帰降下パーサーであり、入力文字列を置換するために使用されるプロダクションを予測する機能があります。 予測パーサーはバックトラッキングの影響を受けません。
予測パーサーは、タスクを実行するために、次の入力シンボルを指す先読みポインターを使用します。 パーサーのバックトラッキングを無料にするために、予測パーサーは文法にいくつかの制約を課し、LL（k）文法として知られるクラスの文法のみを受け入れます。
予測解析では、スタックと解析テーブルを使用して入力を解析し、解析ツリーを生成します。 スタックと入力の両方には、スタックが空で入力が消費されることを示す終了記号 $ が含まれています。 パーサーは、解析テーブルを参照して、入力要素とスタック要素の組み合わせを決定します。
再帰降下解析では、パーサーは入力の単一インスタンスに対して複数のプロダクションを選択できますが、予測パーサーでは、各ステップに選択できるプロダクションは最大1つです。 入力文字列に一致するプロダクションがない場合があり、解析手順が失敗する場合があります。
LLパーサー
LLパーサーはLL文法を受け入れます。 LL文法は、文脈自由文法のサブセットですが、簡単な実装を実現するために、簡易版を取得するためのいくつかの制限があります。 LL文法は、両方のアルゴリズム、つまり再帰下降またはテーブル駆動によって実装できます。
LLパーサーはLL（k）として示されます。 LL（k）の最初のLは入力を左から右に解析し、LL（k）の2番目のLは左端の派生を表し、k自体は先読みの数を表します。 通常、k = 1であるため、LL（k）はLL（1）と書くこともできます。
LL解析アルゴリズム
テーブルのサイズはkの値で指数関数的に増加するため、パーサーの説明のために決定論的なLL（1）に固執することがあります。 第二に、与えられた文法がLL（1）ではない場合、通常、与えられたkに対してLL（k）ではありません。
以下は、LL（1）解析のアルゴリズムです。
Input:
string ω
parsing table M for grammar G
Output:
If ω is in L(G) then left-most derivation of ω,
error otherwise.
Initial State : $S on stack (with S being start symbol)
ω$ in the input buffer
SET ip to point the first symbol of ω$.
repeat
let X be the top stack symbol and a the symbol pointed by ip.
if X∈ Vt or $
if X = a
POP X and advance ip.
else
error()
endif
else/*X is non-terminal*/
if M[X,a] = X → Y1, Y2,... Yk
POP X
PUSH Yk, Yk-1,... Y1/*Y1 on top*/
Output the production X → Y1, Y2,... Yk
else
error()
endif
endif
until X = $/*empty stack*/A→α|の場合、文法GはLL（1）です。 βはGの2つの異なる生成物です。
- 端子がない場合、αとβの両方がaで始まる文字列を派生します。
- 最大でαとβのいずれか1つが空の文字列を派生できます。
- β→tの場合、αはFOLLOW（A）の終端で始まる文字列を導出しません。
