LR（0）アナライザーを作成します。 複雑なことについて簡単な言葉で

はじめに

こんにちは

ロシア語では、このアルゴリズムの簡単でわかりやすい説明は見つかりませんでした。 このギャップを埋めることにしました。 まず、それは何ですか？ LR（0）パーサーは、主にパーサーです。 パーサーの目的は、トークンの入力ストリーム（字句アナライザーが入力文字ストリームに基づいて生成する言語の基本要素、トークンの例は数字、コンマ、文字）を処理し、それを特定の形式で指定された言語の説明と比較することです。 比較は、特定のデータ構造（ほとんどの場合ツリー）の構築で構成されます。 さらに、この構造は次の段階であるセマンティック分析に進み、コンパイラはすでにツリーの意味を理解しようとしています。



パーサーには、アップストリームとダウンストリームの2つのクラスがあります。 前者は、入力トークンである葉から始まるツリーを構築しますが、後者は、逆に、ツリーのルートから始まります。 実際、LRは、アナライザーがストリームを左から右（L-「左」）に読み取り、下から上にツリーを構築することを意味します（混乱を起こさずに右を意味する文字Rを入力します）。 インデックス0は、次のトークンをプレビューせず、現在のトークンでのみ機能することを意味します。 このタイプのアナライザーを選択する利点は何ですか？

• 彼は速いです。
• 多くの言語をカバーしています。 つまり、言語を発明して記述した場合、LRアナライザーは高い確率でその言語を処理できます。
• 構文エラーはできるだけ早く検出されます。 前の入力ストリームと一致しない文字が見つかるとすぐに、これに関するエラーを出力できます。

欠点もあります：

• 構造の相対的な複雑さ。
• 言語の記述のあいまいさによって、アナライザーを混乱状態に追い込むことができます。

用語

端末記号 （ terminal ）は、ユーザーがアナライザーに与えることができる記号です。この場合、これらはトークンです。

非終端 記号 （ nonterminal 、 nonterminal ）-言語のオブジェクトを示す記号。 たとえば、記号Aは用語であるとしましょう。 もちろん、複数文字の名前（Aではなくterm）を選択できます。

文脈自由文法 （ CFG ）-フォームのルールのセット ここで、Aは非端末、wは端末と非端末の任意のコレクションです。 この記事では、この文脈のない意味で、単に文法を使用します。

アナライザーを作成する文法の小さな例：



この文法は、0と1の2つの数値に対する不完全な算術演算のセットを記述しています。文法は、言語の記述です。 入力ストリームが私たちの言語に属しているか、どこかで構文エラー（1 + 1の代わりに1+を書いた）かどうかをチェックするために、開始の非終端から始まるこの規則に従って入力ストリームを取得する方法を探しています（Eがあります）。 1 + 1の場合、パスはそのようなEになり、ルール2、E + F、ルール1、F + F、ルール4、T + F、ルール8、1 + F、再び4、1 + T、最後に8番目を適用し、 1 +1。ご覧のとおり、入力文字列を取得できました。これは、構文的に正しいことを意味します。

これで、アナライザーの名前のRという文字を説明できます。 これは、ルールの極右部分から公理に移る、つまり、元の（1）を収集するより単純なルール（7および8）から進むことを意味します。 Lアナライザー（LL）は、ルールの左側の部分から次の分析方向を選択しようとします。



有限状態マシン （ FSM ）についても言及する価値があります。 これは、一連の状態と入力ストリームを持つモデルです。 マシンは初期状態から起動し、現在のシンボルと入力シンボルに基づいて状態を変更します。 つまり、状態0から開始し、aが入力に入ると、オートマトンは状態1になり、bが状態2になります。遷移の仕組みは、表によって与えられます。列は現在の状態、列は入力記号です。

アルゴリズム

アナライザーを機能させるには、いくつかのことが必要です。

• 分析する入力ストリーム自体。
• パーサーステートのスタック（LIFO（Last In First Out）ルールに準拠するデータ構造）は、シートのスタックとして想像するのが最も簡単です-葉をスタックの最後に置き、スタックの要素が必要なときに最初に取得します）。
• アクションテーブル。 彼女は、現在の状態で、入力で現在のキャラクターをどうするかを教えてくれます。
• 変換表 アクションの1つで使用される補助テーブル。

ここでは、アナライザーがどのように機能するかを明確にする必要があります。 現在の状態は、スタックの一番上の状態です。 アクションのテーブルを見てください（インデックスは現在の入力シンボルと現在の状態です）。 このテーブルには4種類のレコードがあります。

• success（accepted）-入力行がこの文法に属していることを意味します。
• void（エラー）-アクションはありません。行き詰まっています。ユーザーは現在のキャラクターを間違えました。
• transfer（shift）-スタックの一番上に、入力文字に対応する状態を配置し、次を読み取ります
• リダクション（reduce）-文法規則を使用して状態を置き換えることができるスタック状態があります。ここでは、遷移テーブルの値を取得します。 最初のインデックスは現在の状態です。 2番目は、ルールの左側です。 つまり、状態のシーケンスを変換したものです。

コード形式では、次のようになります。

1. スタック。 プッシュ （状態[ 0 ] ） ;
2. while （ ！が受け入れられます）
3. {
4. 状態* st =スタック。 トップ （ ） ;
5. 末端項= s [ inp_pos ] ;
6. if （ ！ terms。IsTerm （ term ） ）
7. エラー（ ） ;
8. アクション*アクション= actionTable。 Get （ st、term ） ;
9. if （ ！アクション）
10. エラー（ ） ;
11. スイッチ （アクション- >タイプ（ ） ）
12. {
13. ケース ActionAccept ：
14. 受け入れられた= true ;
15. 休憩 ;
16. case ActionShift ：
17. inp_pos ++ ;
18. スタック。 プッシュ （アクション- >状態（ ） ） ;
19. 休憩 ;
20. ケース ActionReduce ：
21. ルール*ルール=アクション- >ルール（ ） ;
22. スタック。 pop （ルール- >サイズ（ ） ） ;
23. 状態* transferState = transferTable。 Get （スタック。 トップ （ ） 、ルール- >左（ ） ） ;
24. if （ ！ transferState ）
25. エラー（ ） ;
26. スタック。 push （ transferState ） ;
27. 休憩 ;
28. }
29. }

ご覧のとおり、分析自体に複雑なことはありません。 ただし、全体のトリックは、これらのトリッキーなテーブルを作成することです。 まず、パーサーの状態を把握しましょう。 これは、アルゴリズムのかなり重要な部分です。 いいえ、これは単なる数字ではありません。 いくつかの新しい概念を導入する必要があります。

まず、これらはアイテムです。 これは、マーカーという新しいプロパティを持つルールです。 マーカーは、現在期待している要素を示します。 したがって、各ルールはn + 1個のトークンを生成します。nはルールの右側の文字数です。 たとえば、ルール3を使用します。円の中のプラス記号は、マーカーの場所を示します。



たとえば、2番目の段落のマーカーは、現在の文字にマイナス記号が表示されることを示しています。 複数のアイテムを組み合わせると、アイテムのセットになります。 実際には、状態は特定の方法で一緒に組み立てられたアイテムのセットです。



ただし、状態を操作するには、最初にセットを閉じる必要があります。 これは、完全なアナライザーブランチを取得することを意味します。 つまり、セット内にマーカーが非終端点を指すポイントがある場合（そして、この場合、すべての非終端点は左側の部分です）、対応する非終端点を「デプロイ」する必要があります。 これは、左部分がこの非終端であるアイテムを追加するだけで起こり、マーカーは最初の文字を指します。 単独で、再帰的に展開します。新しく追加された段落で最初の文字が非終端記号である場合は、閉じます。 フルセットを取得するまで。 ポイントが1つしかないセット（前の例では3番）を閉じます。



Fを展開すると、ポイント2、3、4が得られます。3と4では、再びFを展開するよう提案されますが、これらのルールは既にセットにあるので、スキップします。 しかし、Tがデプロイされていないため、5と6が得られます。すべて、クロージャーの準備ができました。

1. for （ itemsetのclosed_item ）
2. {
3. if （ closed_item。isClose ）
4. 続ける ;
5. 要素マーカー= closed_item。 マーカー （ ） ;
6. if （マーカー。 タイプ （ ） ！ = ElementNonTerm ）
7. {
8. closed_item。 isClose = true ;
9. 続ける ;
10. }
11. NonTerminal nonTerm =マーカー。 NonTerm （ ） ;
12. item = allitems- > First （ 0 、nonTerm ） ;
13. while （ ！ item。isend （ ） ）
14. {
15. if （ ！ itemset。exists （ item ） ）
16. アイテムセット。 追加 （アイテム） ;
17. アイテム。 next （ 0 、nonTerm ） ;
18. }
19. closed_item。 isClose = true ;
20. }

状態が何であるかを理解したら、それらの構築を開始できます。 最初に、出力の基礎であり、最後に到達する必要がある新しいルールを導入します。





もちろん、最初の状態は、このルールに基づいて、マーカーをEに向けてアイテムを閉じることです。ここで、一時的な有限状態マシンのテーブルの構築を開始します。これは、遷移テーブルとアクションテーブルの基盤として機能します。 マーカーが指すシンボルの基準に従って、状態をグループに分けます。 この例のクロージャでは、Fグループ、Tグループ、0グループ、1グループの4つのグループがあります。 各グループは、新しい状態への移行です。 遷移からの最初のインデックスは、実際にグループ化するシンボル（F、T、0、1）です。 2番目のインデックスは現在の状態です。 そして、テーブル内の値は、渡す状態です。 したがって、4つの新しい状態を取得します。 それらを構築するのは非常に簡単です-各ポイントでグループ内でond位置のマーカーを右に移動し、結果セットを閉じます。 これは新しい状態になります。

1. firstState。 追加 （項目。 最初 （ ） ） ;
2. firstState。 MakeClosure （ ） ;
3. 状態。 add （ firstState ） ;
4. size_t state_idx = 0 ;
5. while （ state_idx < states。size （ ） ）
6. {
7. 状態* st =状態[ state_idx ] ;
8. GroupedItems group = st- > Group （ ） ;
9. for （ groupのgroup_class ）
10. {
11. if （ group_class- > first。 タイプ （ ） == ElementEnd ）
12. 続ける ;
13. State newState （ ＆ items、states。Size （ ） ） ;
14. for （ group_classのgroup_item ）
15. newState。 追加 （ group_item、group_item。MarkerInt （ ） + 1 ） ;
16. newState。 MakeClosure （ ） ;
17. 状態oldState =状態。 検索 （ newState ）
18. if （ ！ oldState ）
19. {
20. 状態。 add （ newState ） ;
21. fsmTable。 Add （ st、group_class- > first、newState ） ;
22. }
23. 他に
24. fsmTable。 Add （ st、group_class- > first、oldState ） ;
25. }
26. state_idx ++ ;
27. }

遷移テーブルは非常に簡単に構築されます-インデックスが非終端であるFSMテーブルから列を転送します。



アクションテーブルはもう少し興味深いものです。 また、パーツはFSMからターミナルインデックス付きの列に転送されますが、元の宇宙船テーブルに記録された状態パラメーターを使用したシフトアクションはテーブルセルに書き込まれます。 次に、入力行の終わりを示す新しい列「$」を追加します。 この列には、受け入れられたイベントを入力します。これは、インデックス状態にアイテムが含まれている場合に書き込まれます 。 これは成功を意味し、主要なルールに変わり、同時に入力ストリームが終了します。 次に、畳み込みアクションがあります。 アイテムがある各州について 、ここでwは端末と非端末の任意の組み合わせで、行全体（もちろん、他のコマンドで占有されていないフリーセルのみを意味します）のreduceコマンドと、このアイテムが属する対応するルールのパラメーターを記述します。

1. fsmTable。 FeedTransferTable （ transferTable ） ;
2. fsmTable。 FeedActionTable （ actionTable ） ;
3. アイテムendItem =アイテム。 GetItem （ 1 、 'S' 、Elements （ "E" 、nonTerms ） ） ;
4. for （ st in states ）
5. if （ st。HaveItem （ endItem ） ）
6. actionTable。 Add （ st、 '$' 、 new Action （ ） ） ;
7. for （ st in states ）
8. {
9. ItemListリスト= st。 GetReducable （ ） ;
10. for （リスト内のlistItem ）
11. actionTable。 Add （ st、 new Action （ listItem。GetRule （ ） ） ） ;
12. }

文学

コンパイラ：原則、テクニック、およびツール、1986年、アルフレッドV.アホ、ラビセティ、ジェフリーD.ウルマン