コンパイル。 5：下方解析

まだ上向きの構文解析を行っています。 他にどんなオプションがありますか？
バイソンを脇に置き、理論に戻ります。

さらに投稿：

1. アイデア
2. 化身
3. ホリバー
4. バックトラッキング

アイデア

上向き解析の一般的な考え方は次のとおりです。入力行を読み取り、一度に1文字ずつスタックにシフトします。 文法規則に一致する組み合わせがスタックの最上部で形成されるとすぐに、それを1つの非終端記号にまとめて続行します。
この方法の重要な特徴は、ルールの折りたたみ中にすべてのコンポーネントを手元に用意し、必要な構造でそれらからツリーを構築したり、計算のために外出先でも使用できることです。

反対のアプローチは、文法の最初のシンボルの展開を開始し、次の入力シンボルに従って展開可能なルールを選択することです。
たとえば、文法に規則がある場合

 OP： '{' OPS '}' //ブロック
     |  EXPR ';'  //式
     |  'if' '（' EXPR '）' OP
     |  'if' '（' EXPR '）' OP 'else' OP
     |  'while' '（' EXPR '）' OP
     |  'exit' ';'  ;

テキストのさらに先にwhileがあることがわかります。その後、 OP: 'while' '(' EXPR ')' OP ;ルールに従って展開しOP: 'while' '(' EXPR ')' OP ;

ストアマシンの場合、このような解析は次のように実装できます。

• 展開中に、ルールの正しい部分をスタックに書き込みます。それに応じてテキストの継続を解析します。
• スタックの最上部に端末があり、入力テキストに同じ端末がある場合、テキストは期待どおりです。 スタックから上位端末を削除し、テキストの次の文字を読み取ります。
• スタックの最上部が非終端の場合、それを展開する必要があります。 入力シンボルに基づいて開発のルールを選択します。

スイープ中にアクションを実行することは無意味であることにすぐに注意します。展開されたルールの右部分はまだ読み取られておらず、読み取られるかどうかはまったくわかりません。 展開するときに、右の部分のシンボルの下のスタックにダミー信号を配置することができます。「ルールが正常に読み取られました。アクションを実行できます」。 しかし、この瞬間までに、右側全体が既にスタックから消去されています！ アクションは何と連携しますか？

しかし、下向き構文解析の主な難しさはこれではなく、開発に適切なルールを選択する方法です。
バイソンには強すぎる文法を思い出してください。

 WORD：S1 'a' 'i' 'l' |  S2 'a' 'l' 'e';
 S1： 's';
 S2： 's';

次の文字が's'とき、どのようにWORDをアンラップしますか？
選択方法は不明ですWORD両方の規則は、正確に's'始まります。

化身

マシンが複数の文字を先読みできるようにすることができます。レビューにより判断すると、このアプローチは人気のLLパーサージェネレーターであるANTLRで使用されました。
技術的な難しさは、スイープの開発が依存する新しいキャラクターごとに、遷移テーブルの次元が増加することです。 したがって、テキストから3文字（スタックから1文字）を読み取るN状態のオートマトンの非圧縮テーブルには、N・256 ⁴要素（数十ギガバイト）が含まれます。
したがって、LLパーシングの適用先は、パーサージェネレーターがテーブルを効率的に圧縮する能力によって正確に決定されます（バイソンが258x14のテーブルを7つの短い1次元配列に圧縮した方法を思い出してください）。

私が理解している限り、すべてがすべての人に問題がないため、長距離先読みのLRパーサーはそうではありません。長距離の検索が不十分であることに起因する競合はLRパーサーではまれです。 バイソンが私たちの文法を認識できるように、2つの同一の畳み込みの中から選択するように頼まなくても十分です。

 WORD： 's' 'a' 'i' 'l' |  「s」「a」「l」「e」;

一方、LLパーサーでは何も変更されていません。以前のように、両方のルールは's'文字に対応しています。 したがって、LL構文解析の文法を「適合」させるために、同じ非終端記号に対するさまざまな規則の一般的な始まりが「補助非終端記号」に取り出されます。

 WORD1： 's' 'a' WORD;
 WORD： 'i' 'l' |  'l' 'e';

このトリックは「左因子分解」と呼ばれます。これは、「共通因子」が均等に開始されるルールから取り出されるかのようです。
これで、 WORD1スイープは一意であり、 WORD 2つのスイープは異なる文字で始まります。

ANTLR miracle-squeezerが必要なだけ先読みできるのに、なぜ因子分解に悩まされ、文法に意味のない非終端記号を生成するのですか？
文法に戻る

 OP： '{' OPS '}' //ブロック
     |  EXPR ';'  //式
     |  'if' '（' EXPR '）' OP
     |  'if' '（' EXPR '）' OP 'else' OP
     |  'while' '（' EXPR '）' OP
     |  'exit' ';'  ;

次のifキャラクターをOPに展開する方法は？ この方法で開始できる2つのルールがあります。 そして、それらの共通部分'if' '(' EXPR ')' OPは任意の長さにすることができるため、パーサーがどれだけ先を見ても、これは彼を救いません。

LLが処理できないもう1つの問題は、左再帰です。 市場取引計算機の文法を覚えておいてください：

 EXPR：NUM |  EXPR OP NUM;

EXPR両方の規則はNUMから始まります。最初の規則は明示的で、2番目の規則は暗黙的です。 ただし、ルールから引き出すことができる一般的な「要因」はありません。 NUMの長さに制限NUMないと仮定した場合、先を見越しても問題が解決しないことは明らかです。

文法を修正するために、その意味から始めます。行の最初のNUMは既製の式であり、他のすべての式には2つのオペランドが含まれます。

 EXPR：NUM EXPR1;
 EXPR1：|  OP NUM EXPR1;

左因数分解と左再帰の排除により、曖昧さのない文法をLL構文解析に適合させることができますが、多くの補助的な非終端記号を追加しても、まったく意味がありません。
たとえば、 EXPR: EXPR OP NUM ;ルールの畳み込みでは、次のようになりEXPR: EXPR OP NUM ; 構文ツリーノードを簡単に作成しました。左の引数-ここにあります（ $1 。 正しい引数はここにあり、 $3です。 EXPR1: OP NUM EXPR1 ;の展開でできることEXPR1: OP NUM EXPR1 ; ？ 左の引数は既に展開されており、スタックから消去されています 。 しかし、 EXPR1を手にしています。正しい引数の後の部分式です。 何か良いもののようです！

重要なことは、左再帰はすべての左結合操作、およびそのほとんどにとって自然なことです。 したがって、上記のような混乱は珍しい好奇心ではなく、典型的なケースです。

一方では、文法をLL形式に還元することは完全に形式的であり、魂のない鉄片に委ねることができます。 一方、特定の文法ではなく、独自の文法に従って動作するオートマトンをデバッグする方法は？
特に、デプロイメントのアクションを記述することは許可されません。すべて同じように、デプロイメントは設定したルールではなく、鉄片が設定した他のルールになるからです。 このようなパーサーが特定の解析ツリーを生成できると便利です。 これを行うには、特定の文法のルールをオートマトンが実際に機能するルールと相関させ、ツリーを再構築して、あるルールから別のルールに移動したノードを「元に戻す」必要があります。

ホリバー

LLの利点に関する議論。 LRは一般に自動解析と同じくらい古いです。 どちらのアプローチにも独自の支持者がいます。 例えば、私から個人的に深く尊敬されていたニクラウス・ワースは、LL分析の積極的な謝罪者であり、Pascalの開発における設計目標の1つはLL（1）分析の可能性でした。 テキストの次の文字を1つだけ見るオートマトン。 LLの「生きている言語」のほとんどは適合しません。たとえば、Cでは、変数または関数の宣言はintで開始でき、行を最後まで読むまで区別できません。

利便性に関して：基本的に、誰もが彼が慣れている楽器を賞賛し、珍しいことを嫌います。
たとえば、「 ANTLR vs. バイソン "：

個人的な好みの面では、LALR文法は構築とデバッグがはるかに簡単だと思います。 欠点は、shift-reduceや（恐ろしい）reduce-reduceのようなやや不可解なエラーに対処する必要があることです。 これらはパーソンを生成するときにBisonがキャッチするエラーであるため、エンドユーザーエクスペリエンスには影響しませんが、開発プロセスを少し面白くすることができます。

その紛争におけるANTLRの利点には、解析自体の品質以外のあらゆるものが含まれます。便利な開発環境、異なる言語でのコード生成、ユーザーフレンドリーな生成コードです。

ANTLRとテーブルパーサーの最大の違いは、便利に生成されるコードです。 実際、特殊な解析スタックの代わりに、呼び出しスタックが使用され、各文法規則の認識が関数呼び出し（再帰規則の場合、再帰関数の場合）として実装されます。 したがって、呼び出しスタックからデバッグする場合、パーサーが現在の状態になった方法がすぐにわかります。 一方、バイソンでは、思い出すように、状態間の遷移のデバッグ印刷をオンにし、遷移の理由を理解するためにマシンの印刷を確認する必要があります。
テーブルの前の再帰的実装の欠点も明らかです。コードの量がはるかに多いため、メモリが消費されます。 生成されたコードに「パッチ」を書くことは不可能です。これは、文法が変更されると変更され、さらに数十の関数が乗算されるためです。

バックトラッキング

スイープごとにルールを事前選択するLLパーサーは、ダウンストリーム解析の唯一のオプションではありません。 別のアイデア：いくつかの適切なルールがある場合、 すべてを試してみますが 、いくつかはします。 たとえば、 fork()などの操作を実行できます。現在の状態でパーサークローンを作成し、各クローンにスキャンオプションの1つを試行させます。 クローンが構文エラーに遭遇すると、クローンは死にます。 すべてのクローンが停止している場合、適切なスキャンオプションは1つではありません。入力テキストに構文エラーがあります。

正しいテキストの場合、このアプローチは多かれ少なかれ受け入れられます。 しかし、エラー検出には問題があります。 まず、検出されたエラーのどれを印刷しますか？ それらのほとんどは、誤って選択されたスキャンの結果であり、プログラムテキストのエラーではありません。 しかし、パーサーの観点からは、すべてが完全に同等です。

第二に、分析が終わることはありません。左再帰規則に従ってスイープを行うたびに、クローンの1つはスイープ前とまったく同じ状態になります。 そのため、各ステップでさらに1つのまったく同じクローンが判明し、無限に続きます。 クローンの1つが分析の終わりに達すると、残りのすべてを殺すことができます。 そして、反対に、他のすべてのクローンが構文エラーに遭遇して死に、無駄なクローンだけが生き続けるのか？

最後に、あいまいな文法をどうするか？ LLおよびLRパーサーは、コンパイル時に競合を検出します。 ここでは、コンパイルなどはありません：パーサーは、ほとんど生の文法、つまり 外出先で解釈します。
そのため、同じテキストに対して1つの分析または別の分析のいずれかが得られることが判明する場合があります。どのクローンが分析をより早く終了する時間があるかによって異なります。

最後の問題は最も独創的な方法で解決されました：あいまいな構文解析の可能性は文法の基本的な問題であり、それらの代わりに構文解析式を使用する必要があることが発表されました。本質的には開発ルール間で厳密な優先順位が与えられるという点でのみ異なります。 たとえば、文法
OP: EXPR ';' | 'if' '(' EXPR ')' OP | 'if' '(' EXPR ')' OP 'else' OP ;
そして
OP: EXPR ';' | 'if' '(' EXPR ')' OP 'else' OP | 'if' '(' EXPR ')' OP ;
-これはまったく同じ曖昧な文法であり、構文解析式
OP: EXPR ';' / 'if' '(' EXPR ')' OP 'else' OP / 'if' '(' EXPR ')' OP
パーサーに「最初にif..elseを認識しようとし、失敗した場合のみif if..elseを認識しif..else 」と明確に伝えelse 。 そして、表現
OP: EXPR ';' / 'if' '(' EXPR ')' OP / 'if' '(' EXPR ')' OP 'else' OP
は、「- else if if else 」を最初に認識することを意味するため、 elseはまったく認識されelse 。

ここで、可能なすべてのスイープを同時にチェックする代わりに、優先度に従って順番にチェックします。 前のスキャンでエラーが発生した場合にのみ、次のスキャンに進みます。 コメンテーターが言及したリンクは、この解析方法の優れた比metaを提供します。

怠zyな象に乗ったことがありますか？ 彼はゆっくり歩き、激しく揺れます。 そして、彼は道路を歩いていませんが、あらゆる方向にさまよい、面白いと思いますが、もしそれらが望ましいものと一致しなければ、象の運転手は「いや、私たちはここにいません」と言います。 だから、すべての選択肢を試した後、ゾウは「ここではない 」と言わなかった時点で自分自身を見つけます。 したがって、パーサーコンビネーターは、オプションのいずれかが機能するまで、オプションのすべての組み合わせも試行します。 そして、各ロールバックの後、彼らは再び同じ仕事をし始めます。 <...>数行のプログラムはすぐに理解されました。 すでに数秒で3行になります。 5行も待たなかった。 覚えておいてください、このようなパーサーコンビネーターは、非常に単純な文法にのみ適しています。

構文解析ループを検出し、許容可能な作業時間を達成し、エラーを特定することは残っています。

ループの方が簡単です。入力テキストを進めることなく、同じ状態に2回いる場合、3回目に、そして好きなだけ同じ状態になります。 入力テキストの各位置について、すでにその位置に行ったすべての状態のリストを保持する必要があることがわかります。同じ状態に2度目になった場合、「いいえ、それで十分です。もう行きません」と言います。

無料のボーナスとして、「ええ、ありました」という目盛りだけでなく、以前の分析の結果（スキャンが発生した/適合しなかった）を覚えている場合、「線形」の動作時間が得られます。 最悪のシナリオは、テキストの各位置にあるすべての可能な状態を訪問する場合です。 テキストの長さがN文字で、 文法でMルールの構文解析式（各非終端記号の代替開発オプションを含む）の場合、操作時間O （ M * N ）が得られます。 ずる賢く目を細めて、 Mが定数であるふりをする場合、そうです、時間は線形です。 比較のために、各状態で事前定義されたアクションを持つ従来のLLパーサーとLRパーサーは、最悪の場合O （ M * N ）でまったく同じです。

 S：|  T1 S;
 T1：T2;
 T2：T3;
 ...
 TM： 't';

ここで、 't'各シフトの後't' LRは't' -> TM -> ... -> T3 -> T2 -> T1 M畳み込みを実行します。 LLは、各't' 「食べる」前に、 MスイープT1 -> T2 -> T3 -> ... -> TM -> 't'ます。
全体の問題は、平均的なケースが最悪のケースとどのように異なるかです。少なくとも「線形象」は、同じ文法でLLよりも多くの解析でスイープを実行します。

メモリ消費のもう1つの問題。 過去のスキャンの結果のM * Nを保存する必要があります。これに加えて、入力テキストをメモリに完全に保存する必要があるという事実に加えて、象は無限に前後に実行する必要があるためです。 これは、ストアで自動化されたパーサーがすでに読み取られたテキストに戻らないため、メモリ要件はテキストのみではなく文法のみに依存するという事実にもかかわらずです。
誰もが「1バイトの歴史」を読みましたか？ さらに、新しいコンパイラの最も自然なアプリケーションの1つは、保存されたメモリが重要なすべてのコンパクトなプラットフォームをサポートすることです。

そして、構文エラーの検出に関して。 実際にpackrat（skopid）という名前を取得した私たちの象は、1回のスキャンが行われなかったときにテキストに間違いがあると結論付けました。 したがって、エラーが検出される位置の前に、エラー自体の場所がはるかに先行する場合があります。構文解析式を想定します

 DECL：DECLVAR / DECLFN;
 DECLVAR：タイプID ';'  ;
 DECLFN：タイプID '（' ARGS '）';

-Cの宣言の構文にリモートに似ています。
入力テキストにTYPE ID '!'として解析できるシーケンスが含まれている場合 、その後、構文エラーはどの位置にありますか？ Packratは最初のスキャンをチェックしますが、機能しません。パーサーはTYPEの先頭にロールバックし、2回目のスキャンを試みます。 彼女も合わない。 TYPE前にエラーが検出されることがTYPEます。 TYPEがハーフラインのハードコア表現である場合はどうなりますか？
少なくとも1回のスキャンで到達できた一番右のものをエラー位置として表示することは論理的です。 パーサーがテキストが正常に解析されることをまだ期待していた最後の位置。
エラーのローカリゼーションがそのように実装されているpackrat実装があると思います。

それだけです、それはシリーズの最後の投稿で、解析を扱っています。
次回は、セマンティクスに移りましょう。そうすれば、おもちゃの言語は本当にプログラミング言語になります。