まえがき
こんにちは
これは、独自のLALRアナライザージェネレーターの作成に関する記事の第2部です。 このパートでは、原始的なアップストリームパーサーから最も重要ではないが、最も関連性の高いLALRパーサーへの進化について説明します。 最初の記事を読んでいない人（以下のリンク）は、少なくとも最後のセクションの前半を読むことをお勧めします。 この小さなコードを何度か言及します。
前回の記事のコメントで、数人の人が私のコンパイラコンパイラを書く動機に興味を持っていました。 残念ながら、彼らはこの記事でこの質問に対する答えを見つけられません。 最初は特別な理論なしで記事を書くつもりでしたが、ジェネレーターを書き始めたタスクと目標を正当化して、実装のニュアンスと機能を共有したいと考えました。 つまり、ボリュームはかなりまともです：複数の画面。 しかし、それでもポピュリスト言語で基本理論を説明することに決めたので、記事は3つのパートになりました。 したがって、プレゼンテーションのロジックを壊さないために、まずLR / SLR / LALRアナライザーについて話し、明日は最終版を公開し、最も興味深い部分だと思います。
なぜ進化が必要なのですか？
最後の部分の例のプリミティブコードを見ると、アルゴリズムの複雑さがO（n）として計算されていることがわかります（nは入力文字の数）。 これはアルゴリズムにとって非常に良いマークだとすぐに言います。 たとえば、最速のソートの場合、複雑度はO（n * log（n））です。 しかし、このステートメントはアルゴリズムの複雑さについて何を意味しますか？ ただし、n個の操作ではなく、少なくともC * n（Cは定数）を実行する必要があることを意味します。 この例では、定数は非常に大きく、すべてのルールの長さの合計であり、100、1000、および10000になります。つまり、10文字の文字列の場合、10万回の操作がかかります。 しかし、これはすでに非常に悪いです。
そのため、パーサー自体のアルゴリズムを改善する必要があります。 基本的な考え方は、各記号と着信端末で、この記号と以前のいくつかの記号が畳み込みにつながるルールを知っていることです（すでに最小化された非端末を含む最後のK文字を1つの非端末に置き換えます）。転送、つまり、この端末がどこに位置しているかを判断します。 大まかに言えば、ルールA = 012とB = 021がある場合、行01はルールAのキャリーオーバー、02はルールBのキャリーオーバー、012はルールAのコンボリューションにつながります。このアイデアは、前述の定数Cを1に近づけます。このスキームがFSM（ステートマシン）の概念に非常によく適合することは容易にわかります。 簡単に言えば、これは2次元のテーブルであり、現在の状態番号と受信シンボルによって新しい状態番号を提供します。 そして、最終状態に到達するまで続きます。
FSMの状態
いいでしょう 状態がルールの文字の現在の位置を反映する必要があることは明らかだと思います-上記の例AおよびBで、以前に文字0、1を読み込んだ場合、状態は「Aの3つの規則の最初の2文字をすでに読んだ」と説明できます。 ルールC = 013を追加すると、状態はより限定的ではなくなります：「3 AまたはCの最初の2文字をすでに読み取りました」。 そして、すべてが次の文字に依存します-2または3。2が来ると、「3 Aから3文字を読み取る」状態になり、その後、畳み込みを整理します-012を文字Aに、それぞれ3とCについて-同様に。 それは明らかです。
さらに、どこで開始し、いつ停止するかを決定する必要があります。 この例では、先頭は「3x AまたはBまたはCから0文字を読み取ります」です。 結末も明確です-A / B / Cの3つの可能な「3 of 3」状態 つまり、規則の1つに従って畳み込みが発生すると、停止します。 ただし、プリミティブで機能する場合は、少し複雑にする価値があり、すべてが壊れます。
A = 0 A | 1
今こそ、状態コーディングについて考えるときです。 まあ、私たちは希望と期待を平文で書かないでしょう。 アナライザーは単に私たちを理解しません。 上記で使用した格言の機械表現について考える必要があります。 実際、これらを互いに比較する場合、これは基本です。 ルールとこのルールの現在の位置という2つの定義ポイントのみが含まれます。 また、例からわかるように、状態には複数のそのようなセットを含めることができます。 クラシックのセット自体はアイテムと呼ばれます。 そして、これらは次のようになります。A= 01・2、つまり、ルールA = 012で2文字を読み取ります。
FSMテーブル
FSM自体を設定するだけで、パーサーは実際に準備ができています。 状態間の遷移表は非常に簡単に構築されます-畳み込みは、すべての文字が読み取られたルールを含む状態に遭遇したときに決定されます。 つまり、マーカー（・）は最後にあります。 さらに、テーブル内の列は現在の文字によって設定されるため、折りたたみ可能な文字を追跡できるすべての可能な端末を見つける必要があります。 畳み込みが形成されたが、その後にシンボルが続く場合、それは文法の一般的な論理では決して見つけることができず、これは間違いです。 例：
#start A A = B 2 B = 01
ここでは、畳み込みBの間に、2が後に続くことを確認する必要があり、他の文字はありません。 このセットを計算するロジックは理解できると思いますが、そうでない場合は、以下に疑似アルゴリズムがあります。 この点に加えて、コンボリューションを行う場合、分析がどの親ルールで追跡される必要があるかを考慮する必要があります。 つまり、畳み込みシンボルはいくつかのルールに簡単に参加でき、対応する状態に切り替えるには、この操作が現在どの特定のルールで進行中であるかを明確に知る必要があります。 これは、状態スタックを維持することで解決されます。 シフトするとき（端末を受け取り、状態を変更するとき）、状態番号をスタックにプッシュします。 また、畳み込み中に、スタックからL個の要素を抽出します。ここで、Lは式の右側の長さ（1つの非終端に折りたたまれた要素のセット）です。 そして、同じFSMテーブルによって決定される新しい状態のインデックスを配置します。このインデックスは、最小化されたルールの左側の非終端に等しい列番号と行番号-スタックの一番上の状態です。 面倒に聞こえるかもしれませんが、本当に簡単です。 上記の文法でアルゴリズムの動作を説明します。
0. 0 1. , s0 {A = · B 2}, {0} 2. , = [s0, 0] = s1 {B = 0 · 1} , {0}, 1 3. , = [s1, 1] = s2 {B = 0 1 ·} , {0, 1}, 2 4. , [s2, 2] (2 - ), = [s2, 2] = s3 {A = B · 2}, {B} 5. , = [s3, 2] = s4 {A = B 2 ·} , {B, 2}, EOF ( ) 6. , = [s4, EOF] = s5 {S = A ·}, {A} 7. , = [s5, EOF] = s6 {S}, , ,
畳み込みを理解しましたが、状態間の遷移とそれらがどこから来たかをどのように決定するかはまだ明確ではありません。 そして、すべてが簡単に解決されます-使用可能なすべての文字（端末と非端末）を繰り返し処理し、分析中の現在の状態に適用します。 {A = ...・X ...}という形式のアイテムが含まれる場合（Xはインライン文字）、マーカーを移動し（これはまさにXシンボルの使用です）、新しい状態のアイテムを取得します{A = ... X・.. 。}。 もちろん、Xにこのようなアイテムが複数ある場合、新しい状態には複数のエントリも含まれます。 さらに、このプロセス中に、目的のFSMを構築します：[sOld、X] = sNew。 これは、テーブルのほぼ完成した行です。 畳み込み要素を追加するだけです。
もう一つの重要なポイント。 繰り返しますが、最後の例を見ると、{A = B・2}と[s0、B] = sXのみが開始状態{A =・B 2}から取得できることがわかります。 しかし、これは間違っており、機能しません。 開始状態の入力時に、非端末（B）ではなく、入力端末（0、1、2）のみが取得されるためです。 アルゴリズムの動作を保証するために、可能なターンを考慮する必要があります（動作は畳み込みの反対です）。 つまり、この場合、文法から、Bを展開し、条件付きで{A =・0 1 2}を取得できることがわかります。これは、ロジックに完全に対応しています。 私が説明したことを形式化すると、「状態に{X = ...・Y ...}が含まれる場合、{Y =・...}という形式のアイテムも含まれるはずです」と書くことができます。 この拡張プロセスはクロージャと呼ばれます。
以上で、理論はFSM生成アルゴリズムとFSMベースのアナライザー自体の両方をコンパイルするのに十分です。 構築の擬似コード：
/* , */ function firstTerminal(X) { if (X.type == Terminal) return X; result = []; for (rule in rules) { // X = Y ... if (rule.left == X) { // , first(Y) result[] = first(rule.right[0]) } } return result; } // , function nextTerminal(X) { result = []; for (rule in rules) { // Y = ... X if (rule.right.end(X)) { /* X Y, X , Y */ result[] = nextTerminal(rule.left); } else { // Y = ... X ... if (rule.right.has(X)) { // result[] = firstTerminal(rule.right.next(X)); } } } return result; } // function closeItem(I) { for (item in I) { // Y = ... · X ..., X if (item.markered.type == NonTerminal) { for (rule in rules) { // X = ... if (rule.left == item.markered) { // X = · ... I[] = {rule: rule, marker: 0}; } } } } } // FSM function addReducing(I, FSM) { for (item in I) { // X = ... · if (item.markered == item.end) { // S = A, A - if (item.rule.left == _START_) { // , , FSM[I.index, EOF] = Success; } else { // , for (term in nextTerminal(item.rule.left)) { /* rule : */ FSM[I.index, term] = {operation: Reduce, rule: item.rule}; } } } } } // I X function shiftState(I, X) { result = []; for (item in I) { // Y = ... · X ... if (item.markered == X) { // result[] = {rule: item.rule, marker: item.marker + 1}; } } return closeItem(result); } // function buildFSM() { FSM = {}; // S = · A states = [closeItem({rule: {S = A}, marker: 0})]; for (state in states) { // addReducing(state, FSM); for (X in symbols) { new = states[] = shiftState(state, X); // FSM[state.index, X] = {operation: Shift, index: new.index}; } } }
アルゴリズムコード：
input >> term; accepted = false; /* 0 , , == */ stack = [0]; while (!accepted) { // - stack.top() state = FSM[stack.top(), term]; switch (state) { case Success: accepted = true; break; case Shift: // stack.push(state.index); input >> term; break; case Reduce: // L stack.pop(state.rule.right.length); // state.rule.left - // stack.pop() - , X stack.push(FSM[stack.pop(), state.rule.left]); // {..., Y, ..., Z} {..., X} X = Y ... Z break; default: throw SyntaxError; } }
アルゴリズムのさらなる改善。 一眼レフ（1）
かなり高速で優れたアルゴリズムを取得しましたが、検出が難しい欠陥が1つあります。 それは、折りたたみ可能な非終端記号（nextTerminal関数）の後に来る文字の定義の不完全さにあります。 小さな例：
A = B 2 | C B = C 0 | 1 C = B States: S0: [{S = · A}, {A = · B 2}, {A = · C}, {B = · C 0}, {B = · 1}, {C = · B}] S1: [{S = A ·}], S0 A S2: [{A = B · 2}, {C = B ·}], S0 B ... SX: [{A = B 2 ·}], S2 2
文法は、10 ... 02および10 ... 0の形式の行を記述します。 nextSymbol = [0、2、EOF]。 そして、FSM [S2、2]の場合、規則C = Bに従って畳み込みを行う必要がありますが、規則A = B 2に従って同じ瞬間に、状態S2の同じ端末2によってSXに転送する必要があります。 。 これは悲しいです。 これは、ポイントC = Bの状態S2では、A = C EOFに基づいてEOFのみを待機する必要があり、2または0がないためです。これらは将来のみ表示されます。
はい これは合成の例ですが、実際にはそのようなトラップを持つ文法があります。 また、それほど珍しいことではありません。 予想されるシンボルに応じた、畳み込みを生成するポイントの決定-ソリューションは明らかです。 つまり、{C = B・}は条件付きで{C = B・[EOFを期待]}に変換するか、簡潔にするために{C = B・、EOF}に変換します。 2つのポイントのみが影響を受けます-ポイントの生成（新しい形式のポイントを作成する必要があります）および畳み込みを伴うセルの生成。 つまり、closeItem（）とaddReducing（）の2つの関数のみがあります。
// function closeItem(I) { for (item in I) { // Y = ... · X ..., X if (item.markered.type == NonTerminal) { for (rule in rules) { // X = ... if (rule.left == item.markered) { // X - if (item.nextMarkered == item.end) { // first = item.expect; } else { // first = firstTerminal(item.nextMarkered); } // for (expect in first) { // X = · ... I[] = {rule: rule, marker: 0, expect: expect}; } } } } } } // FSM function addReducing(I, FSM) { for (item in I) { // X = ... · if (item.markered == item.end) { // S = A, A - if (item.rule.left == _START_) { // , , FSM[I.index, EOF] = Success; } else { /* , */ FSM[I.index, item.expect] = {operation: Reduce, rule: item.rule}; } } } }
トップ-LALR（1）
前のアルゴリズムの欠点は肉眼で顕著です-1ポイントと1状態を使用していましたが、現在は複数のポイントと複数の状態が可能で、予想されるシンボルのみが異なります。 したがって、FSMテーブルは大きくなり、そのサイズが大きくなり、対応するテーブルLR（0）を数桁超える可能性があります。 良くない
出口を見つけることは難しくありません-予想されるシンボルのみが異なる状態を組み合わせます。 例：[{A = B、0}、{B = C、0}]および[{A = B、1}、{B = C、1}]。 なぜ安全なのですか？
- 遷移中に新しい状態を構築するとき、期待シンボルを使用しません。したがって、s0とs1がカーネル（期待されるシンボルを除くアイテムの一部）で同じ場合、s0からXから生成されたs2とs1からXから生成されたs3も同じです。 したがって、sn0のs0とs1、sn1のs2とs3を簡単に組み合わせて、それらの間に接続を作成できます。 これは完全に正しいです。
- FSMテーブルの2番目の部分は畳み込みです。 しかし、状態では異なる期待記号が存在するため、定義によってそれらが交差できないことは明らかです。畳み込みは対応する期待記号の1つのセルにのみ記録されます。 そして、それらは簡単に組み合わせることができます。
したがって、最終的には同じLR（0）を取得しますが、文法の制限はありません。
記事の一部
- パート1.基本理論
- パート2. LRジェネレーターの説明
- パート3.作成の機能とLRジェネレーターの可能な機能