コンパイル。 2：文法

前回の投稿には多くのコードがあり、意見によっては十分な説明がありませんでした。 代わりに、今度は多くの理論がありますが、実際にはほとんど到達しません。

さらに投稿：

1. ショップマシン
2. 正式な文法
3. LR解析

ショップマシン

前回、正規表現の問題を特定し、その上にテキストを解析するためのDFAを構築しました。ブラケットがネストの同じレベルにあるかどうかを判断することは不可能です。 正規表現を使用すると、さらに狭い問題でさえ解決することは不可能です。 {*} *のような文字列をチェックして、数量が{ quantity }と等しいかどうかを確認します。 それとは逆に、そのような正規表現を作成できるとします。 したがって、それからDFAを構築することができます。これにより、適切な行と不適切な行が区別されます。 結果のDFAにN個の状態がある場合、タイプ{ ^{N +1} （つまり " N +1回{ "）の行で、オートマトンはいくつかの状態（「ループ」）で複数回訪問します。 そのため、行の先頭に新しい文字{を追加すると、同じサイクルでもう一度マシンを実行できます-置換に気付かないでしょう。 その結果、マシンは適切なライン{ ^{N + 1} } ^{N + 1と}不適切なライン{ ^{N + M + 1} } ^{N + 1}を区別できなくなります。 （ Mはマシンで検出されたループの長さです。それは{行の先頭に追加されます。）

言い換えれば、DFAは十分なメモリがないため、ネストされた構造を認識できません。覚えているのは1〜N （現在の状態番号）の値だけです。 より大容量のマシンが必要であり、そのメモリは必要に応じて無制限に拡大できます。

現在の状態に加えて、 ストアメモリを備えたオートマトンには、文字を書き込むことができるスタックがあります。 各ステップで、マシンは次の入力文字とスタックの先頭文字を読み取ります。 トリプル（現在の状態、入力シンボル、スタックからのシンボル）に従って、マシンは、読み取りシンボルの代わりに切り替える状態とスタックに書き込むものを選択します。 スタックへの書き込みはオプションです。読み取り文字をそこから単純に消去できます。 そのため、動作中のスタックは拡大と縮小の両方を行うことができます。

用語に関して：自動販売機は店舗の自動販売機とは関係ありません。 奇妙なことに、ストアマシンは、スタックの古典的な実装であるマシンストア（図を参照）にちなんで命名されています。カートリッジの最上部の要素にのみアクセスできます。

これで、元の問題を解決できます。 {と}が行にあるかどうかを確認します。 各{を読み取り、スタックに書き込みます。 各}を読み取り、スタックから{を消去します。

状態1：{
             スタック記号：{EOF（空のスタック）
入力文字：
       {write {{、1にとどまる{}、1にとどまる
       }何も書かないで、行2に収まらない（1）
      EOF文字列が収まらない（2）文字列が収まる（3）


状態2：考慮}
             スタック記号：{EOF（空のスタック）
入力文字：
       {ラインが収まらない（4）ラインが収まらない（4）
       }何も書かないでください。2行目にとどまることはできません（5）
      EOF文字列が収まらない（6）文字列が収まる（7）

注：

1. 行は}で始まります
2. 行の先頭に複数の{がありますが、それらの後には1つではありません}
3. 行は空です
4. 後}行には再び{
5. } {以上（スタックは終了しましたが、入力はありません）
6. }より小さい{ （入力は終了したが、スタックはない）
7. 同様に{と} （スタックと入力は同時に終了しました）

容量の大きいマシンに加えて、構文を設定する新しい方法がまだ必要です-正規表現よりも柔軟です。

正式な文法

任意のネストをサポートする言語構造を決定するために、たとえばネストされたブラケットの上記の問題に対して、文字（「端末」）と変数（「非端末」）で構成される「推論規則」を使用し始めました。

有効： '{'有効 '}';
有効：;

左、コロンの前-変数。 右側には、そこから取得できるテキストがあり、定義されている変数への再帰参照を含む変数を含めることができます。

スペースを節約するために、同じ変数の代替定義を分割できます| ：

有効： '{'有効 '}' |  ;

より意味のある例は、算術式の文法です。

 EXPR：NUM |  EXPR OP EXPR;
 NUM：DIGIT |  NUM DIGIT;
 DIGIT： '0' |  '1' |  '2' |  '3' |  '4' |  '5' |  '6' |  '7' |  '8' |  '9';
 OP： '+' |  '-' |  '*' |  '/';

このタイプの文法はcontext-freeと呼ばれ、変数の定義がコンテキストに依存しないことを示します。たとえば、NUMの前に「0x」が付いていても、常に10進数の文字列に一致します。 実際には、効果的な構文解析メソッドがないため、状況依存文法は使用されません。

したがって、文法に従って、式22+3*4-5は次のように認識されます。

   「2」「2」「+」「3」「*」「4」「-」「5」
 DIGIT DIGIT OP DIGIT OP DIGIT OP DIGIT
  NUM DIGIT OP NUM OP NUM OP NUM
    NUM OP EXPR OP EXPR OP EXPR
     EXPR OP EXPR OP EXPR
            EXPR OP EXPR
                     EXPR

または多分そう：

   「2」「2」「+」「3」「*」「4」「-」「5」
 DIGIT DIGIT OP DIGIT OP DIGIT OP DIGIT
  NUM DIGIT OP NUM OP NUM OP NUM
    NUM OP EXPR OP EXPR OP EXPR
     EXPR OP EXPR OP EXPR
            EXPR OP EXPR
                             EXPR

前者の場合、式は左側の合計と右側の差の積として認識されます。 第二に-算術の規則に従って。 指定された2つを除き、他のオプションも可能です。

単一の式に複数の「解析ツリー」がある場合、疑問が生じます。パーサーはどちらを選択する必要がありますか？

同様の問題は正規表現にありました：「。」、「]」、「。」の行に「quick brown fox」を適用すると、$ 1 =「quick brown」と$ 2 =「fox」、または$ 1 =“迅速な「および$ 2 = "茶色のキツネ」。 正規表現は、「貪欲に」動作することに同意し、左から右に行を読み、各サブ式に可能な限り多くの適切な文字を取り込みます。 （したがって、実際には「クイックブラウン」と「フォックス」が得られます）。

文法にはそのような取り決めはありません。 文法があいまいな分析を可能にする場合、これは悪い、価値のない文法であり、別の文法を考え出す必要があります。 たとえば、左から右にすべてのアクションを実行する市場取引計算機の文法は次のようになります。
EXPR: NUM | EXPR OP NUM ;
NUM: DIGIT | NUM DIGIT ;
DIGIT: '0' | '1' | '2' | '3' | '4' | '5' | '6' | '7' | '8' | '9' ;
OP: '+' | '-' | '*' | '/' ;
現在、EXPR定義では、2番目のオペランドは常に裸の数値であるため、解析は次のようにしかできません。

   「2」「2」「+」「3」「*」「4」「-」「5」
 DIGIT DIGIT OP DIGIT OP DIGIT OP DIGIT
  NUM DIGIT OP NUM OP NUM OP NUM
    NUM OP NUM OP NUM OP NUM
     EXPR OP NUM OP NUM OP NUM
            EXPR OP NUM OP NUM
                     EXPR OP NUM
                             EXPR

代わりに加算よりも乗算の優先順位を維持したい場合、EXPRは積の合計として定義する必要があります 。
EXPR: TERM | EXPR '+' TERM | EXPR '-' TERM ;
TERM: NUM | TERM '*' NUM | TERM '/' NUM ;
NUM: DIGIT | NUM DIGIT ;
DIGIT: '0' | '1' | '2' | '3' | '4' | '5' | '6' | '7' | '8' | '9' ;

'2' '2' '+' '3' '*' '4' '-' '5'
DIGIT DIGIT '+' DIGIT '*' DIGIT '-' DIGIT
NUM DIGIT '+' NUM '*' NUM '-' NUM
NUM '+' TERM '*' NUM '-' TERM
TERM '+' TERM '-' TERM
EXPR '+' TERM '-' TERM
EXPR '-' TERM
EXPR

プログラミング言語では、同様のあいまいさは珍しくありませんが、C ++ではすべてのステップで正しいです。コメンテーターは、C ++コンパイラの最初から最後までの開発に関する素晴らしい記事「珍しい職業」に言及しました。
これは詳細を掘り下げる時期ではありませんが、最も簡単な例はif (1) if (2) foo(); else bar(); if (1) if (2) foo(); else bar(); if (1) { if (2) foo(); else bar(); }ように解釈できますif (1) { if (2) foo(); else bar(); } if (1) { if (2) foo(); else bar(); } if (1) { if (2) foo(); else bar(); } 、またはif (1) { if (2) foo(); } else bar(); if (1) { if (2) foo(); } else bar(); 文法のコンパイラが解釈の1つを禁止することに注意しない場合。
あいまいさのない文法を書くことは重要なスキルです。

LR解析

ストアオートマトンに文法を認識させる方法は？
入力行を1文字ずつ読み取り、読み取った文字をスタックに書き込み（ shift ）ます。 文法規則に一致するスタックの最上部でシーケンス（文字と変数）が収集されるとすぐに、マシンはそのすべてをスタックから押し出し、一致する規則の左側の変数に置き換えます（ 畳み込み ）。 マシンのすべての作業は、一連のシフトと畳み込みです。

興味深い点：マシンは、どのキャラクターがスタックにあるかを本当に気にしません。 それでも同じように、彼はそれらを文法のルールと比較することはできません。 代わりに、現在の状態に基づいて畳み込みに適用するルールを選択します。 彼は、折りたたみ後にどの状態になるかを知るために、スタックが必要です。 これを行うために、シフト中に、彼はシンボルとともに現在の状態をスタックに書き込みます。 畳み込み中に、スタックから消去されたすべての文字の下に書き込まれた状態を取得し、それに応じて次の状態に移行します。

うるさいhabrayuzerは、ストアオートマトンではないことに気付くでしょう。各ステップで、スタックから1つの要素が消去されるのではなく、一度に複数の要素が消去されます。 スタックの一番上の要素ではなく、消去された要素の下の要素を見てください。 さらに、畳み込み中、マシンは入力文字を未読のままにします。 理論的には、このような「拡張」マシンを「標準」ビューに変換して、スタックをクリアするための追加の状態を作成できます。 実際には、両方のオプションの実装はまったく同じです。つまり、サイクル、スタック、および遷移テーブルはまったく同じです。 変換テーブルの下のスペースを節約するために、彼らはその状態を無駄に膨らませることなく「高度な」マシンを使用します。

最後の文法（正しい操作の優先順位を持つ算術式）を認識するには、11の状態のオートマトンが必要です。

状態1：
  桁：シフト、2に移動
状態2：
  スタックから1文字を削除し、そこにDIGITを書き込みます
  スタックの状態が1または7または10の場合、3に進みます
  スタックの状態が4または9の場合、5に進みます
状態3：
  スタックから1文字を削除し、そこにNUMを書き込みます
  スタックの状態が1または10の場合、4に進みます
  スタックの状態が7の場合、9に進みます
状態4：
  桁：シフト、2に移動
  そうでない場合：スタックから1文字を削除し、そこに書き込みますTERM
         スタックの状態が1の場合、6に進みます
         スタックの状態が10の場合、11に進みます
状態5：
  スタックから2文字を削除し、そこにNUMを書き込みます
  スタックの状態が1の場合、4に進みます
  スタックの状態が7の場合、9に進みます
状態6：
   「*」、「/」：シフト、7へ
  それ以外の場合：スタックから1文字を削除し、そこにEXPRを書き込みます
         スタックの状態が1の場合、8に進みます
状態7：
  桁：シフト、2に移動
状態8：
   EOF：式は正常に認識されました
   「+」、「-」：シフト、10に移動
状態9：
  桁：シフト、2に移動
  それ以外の場合：スタックから3文字を削除し、そこに書き込みますTERM
         スタックの状態が1の場合、6に進みます
         スタックの状態が10の場合、11に進みます
状態10：シフトEXPR：EXPR '+' TERMまたはシフトEXPR：EXPR '+' TERM
  桁：シフト、2に移動
状態11：
   「*」、「/」：シフト、7へ
  そうでない場合：スタックから3文字を削除し、そこにEXPRを書き込みます
         スタックの状態が1の場合、8に進みます

このマシンがどこから来たのかは考えません。 UFOがそれを私たちに持ってきたとします。
それがどのように機能するかを見てみましょう：同じ式22+3*4-5通過させましょう：

状態1、入力 "22 + 3 * 4-5"、スタックは空です
 *数字：シフト、2に移動
状態2、入力 "2 + 3 * 4-5"、スタック '2'、（1）
 *スタックから1文字を削除し、そこにDIGITを書き込み、3に進みます
状態3、入力 "2 + 3 * 4-5"、DIGITスタック、（1）
 *スタックから1文字を削除し、そこにNUMを書き込み、4に進みます
状態4、入力 "2 + 3 * 4-5"、スタックNUM、（1）
 *数字：シフト、2に移動
状態2、入力 "+ 3 * 4-5"、スタック '2'、（4）、NUM、（1）
 *スタックから1文字を削除し、そこにDIGITを書き込み、5に進みます
状態5、入力 "+ 3 * 4-5"、DIGITスタック、（4）、NUM、（1）
 *スタックから2文字を削除し、そこにNUMを書き込み、4に進みます
状態4、入力 "+ 3 * 4-5"、スタックNUM、（1）
 *スタックから1文字を削除し、そこにTERMを書き込み、6に進みます
状態6、入力 "+ 3 * 4-5"、スタックTERM、（1）
 *スタックから1文字を削除し、そこにEXPRを書き込み、8に進みます
状態8、入力 "+ 3 * 4-5"、EXPRスタック、（1）
 * '+'：シフト、10に移動
状態10、入力 "3 * 4-5"、スタック '+'、（8）、EXPR、（1）
 *数字：シフト、2に移動
状態2、入力「* 4-5」、スタック「3」、（10）、「+」、（8）、EXPR、（1）
 *スタックから1文字を削除し、そこにDIGITを書き込み、3に進みます
状態3、入力「* 4-5」、DIGITスタック、（10）、「+」、（8）、EXPR、（1）
 *スタックから1文字を削除し、そこにNUMを書き込み、4に進みます
状態4、入力 "* 4-5"、スタックNUM、（10）、 '+'、（8）、EXPR、（1）
 *スタックから1文字を削除し、そこにTERMと書き込み、11に進みます
状態11、入力「* 4-5」、スタックTERM、（10）、「+」、（8）、EXPR、（1）
 * '*'：シフト、7へ
状態7、入力「4-5」、スタック「*」、（11）、TERM、（10）、「+」、（8）、EXPR、（1）
 *数字：シフト、2に移動
状態2、入力「-5」、スタック「4」、（7）、「*」、（11）、TERM、（10）、「+」、（8）、EXPR、（1）
 *スタックから1文字を削除し、そこにDIGITを書き込み、3に進みます
状態3、入力「-5」、DIGITスタック、（7）、「*」、（11）、TERM、（10）、「+」、（8）、EXPR、（1）
 *スタックから1文字を削除し、そこにNUMを書き込み、9に進みます
状態9、入力「-5」、NUMスタック、（7）、「*」、（11）、TERM、（10）、「+」、（8）、EXPR、（1）
 *スタックから3文字を削除し、そこにTERMと書き込み、11に進みます
状態11、入力「-5」、スタックTERM、（10）、「+」、（8）、EXPR、（1）
 *スタックから3文字を削除し、そこにEXPRを書き込み、8に進みます
状態8、入力「-5」、EXPRスタック、（1）
 * '-'：シフト、10に移動
状態10、入力 "5"、スタック '-'、（8）、EXPR、（1）
 *数字：シフト、2に移動
状態2、入力は空、スタックは '5'、（10）、 '-'、（8）、EXPR、（1）
 *スタックから1文字を削除し、そこにDIGITを書き込み、3に進みます
状態3、入力空、DIGITスタック、（10）、「-」、（8）、EXPR、（1）
 *スタックから1文字を削除し、そこにNUMを書き込み、4に進みます
状態4、入力は空、スタックはNUM、（10）、 '-'、（8）、EXPR、（1）
 *スタックから1文字を削除し、そこにTERMと書き込み、11に進みます
状態11、入力は空、スタックTERM、（10）、 '-'、（8）、EXPR、（1）
 *スタックから3文字を削除し、そこにEXPRを書き込み、8に進みます
状態8、入力は空、EXPRスタック、（1）
 * EOF：式は正常に認識されました

実際、オートマトンは、入力文字列が有効な算術式であるかどうかを判断します。 そうでない場合、いずれかの状態では、次の入力シンボルに適したアクションはありません。 その後、マシンは構文エラーを報告します。
同じマシンを使用して式を計算できます。スタック上の各シンボルには、その数学的な値を格納します。 畳み込むとき、スタックから削除されたものに基づいて新しいキャラクターの値を計算します。
操作の優先度を考慮した高度な計算機が得られます：

状態1、入力 "22 + 3 * 4-5"、スタックは空です
 *数字：シフト、2に移動
状態2、入力 "2 + 3 * 4-5"、スタック '2'、（1）
 *スタックから「2」を削除し、そこにDIGIT = 2と書き込み、3に進みます
状態3、入力 "2 + 3 * 4-5"、DIGITスタック= 2、（1）
 *スタックからDIGIT = 2を削除し、そこにNUM = 2を書き​​込み、4に進みます
状態4、入力 "2 + 3 * 4-5"、スタックNUM = 2、（1）
 *数字：シフト、2に移動
状態2、入力 "+ 3 * 4-5"、スタック '2'、（4）、NUM = 2、（1）
 *スタックから「2」文字を削除し、そこにDIGIT = 2と書き込み、5に進みます
状態5、入力 "+ 3 * 4-5"、スタックDIGIT = 2、（4）、NUM = 2、（1）
 *スタックからDIGIT = 2、NUM = 2を削除し、そこにNUM = 22を書き込み、4に進みます
状態4、入力 "+ 3 * 4-5"、スタックNUM = 22、（1）
 * NUM = 22をスタックから削除し、そこに書き込むTERM = 22、6に進む
状態6、入力 "+ 3 * 4-5"、スタックTERM、（1）
 *スタックからTERM = 22を削除し、そこにEXPR = 22と書き込み、8に進みます
状態8、入力 "+ 3 * 4-5"、スタックEXPR = 22、（1）
 * '+'：シフト、10に移動
状態10、入力 "3 * 4-5"、スタック '+'、（8）、EXPR = 22、（1）
 *数字：シフト、2に移動
状態2、入力「* 4-5」、スタック「3」、（10）、「+」、（8）、EXPR = 22、（1）
 *スタックから「3」を削除し、そこにDIGIT = 3と書き込み、3に進みます
状態3、入力 "* 4-5"、スタックDIGIT = 3、（10）、 '+'、（8）、EXPR = 22、（1）
 *スタックからDIGIT = 3を削除し、そこにNUM = 3を書き込み、4に進みます
状態4、入力 "* 4-5"、スタックNUM = 3、（10）、 '+'、（8）、EXPR = 22、（1）
 *スタックからNUM = 3文字を削除し、そこにTERM = 3と書き込み、11に進みます
状態11、入力「* 4-5」、スタックTERM = 3、（10）、「+」、（8）、EXPR = 22、（1）
 * '*'：シフト、7へ
状態7、入力「4-5」、スタック「*」、（11）、TERM = 3、（10）、「+」、（8）、EXPR = 22、（1）
 *数字：シフト、2に移動
状態2、入力「-5」、スタック「4」、（7）、「*」、（11）、TERM = 3、（10）、「+」、（8）、EXPR = 22、（1）
 *スタックから「4」を削除し、そこにDIGIT = 4を書き込み、3に進みます
状態3、入力「-5」、スタックDIGIT = 4、（7）、「*」、（11）、TERM = 3、（10）、「+」、（8）、EXPR = 22、（1）
 *スタックからDIGIT = 4文字を削除し、そこにNUM = 4を書き込み、9に進みます
状態9、入力「-5」、スタックNUM = 4、（7）、「*」、（11）、TERM = 3、（10）、「+」、（8）、EXPR = 22、（1）
 * NUM = 4、 '*'、TERM = 3をスタックから削除し、そこに書き込みTERM = 12、11に移動
状態11、入力「-5」、スタックTERM = 12、（10）、「+」、（8）、EXPR = 22、（1）
 * TERM = 12、 '+'、EXPR = 22をスタックから削除し、そこにEXPR = 34を書き込み、8に進みます
状態8、入力 "-5"、スタックEXPR = 34、（1）
 * '-'：シフト、10に移動
状態10、入力 "5"、スタック '-'、（8）、EXPR = 34、（1）
 *数字：シフト、2に移動
状態2、入力は空、スタックは「5」、（10）、「-」、（8）、EXPR = 34、（1）
 *スタックから「5」を削除し、DIGIT = 5をそこに書き込み、3に進みます
状態3、入力は空、スタックDIGIT = 5、（10）、 '-'、（8）、EXPR = 34、（1）
 *スタックからDIGIT = 5を削除し、そこにNUM = 5と書き込み、4に進みます
状態4、入力は空、スタックNUM = 5、（10）、 '-'、（8）、EXPR = 34、（1）
 * NUM = 5をスタックから削除し、そこに書き込むTERM = 5、11に進む
状態11、入力は空、スタックTERM = 5、（10）、 '-'、（8）、EXPR = 34、（1）
 * TERM = 5、 '-'、EXPR = 34をスタックから削除し、そこにEXPR = 29を書き込み、8に進みます
状態8、入力が空、スタックEXPR = 29、（1）
 * EOF：式は正常に認識され、値= 29

実際のコンパイラのパーサーは同様に設計されており、各畳み込みでのみ式が評価されず、対応するコードが生成されます。

記述された構文解析の方法は昇順と呼ばれます。最小の構造を認識し、それらを結合することから始めます。 反対のトップダウンアプローチがあります。「テキスト全体」の構造から始めて、さらに小さな下位構造を認識して分割します。 2つのアプローチの支持者の間には、結果が緩慢なホリバーがいることが判明しました。それぞれの側は、彼女のアプローチがより自然であり、人による構文の認識に近く、したがってデバッグが容易であると考えています。

次回はバイソンについて知ります。バイソンは文法の観点からLRオートマトンの認識を構築し、それから素晴らしい電卓をコンパイルできます。