6

LL 再帰降下パーサーが次の形式のルールを処理する方法を理解しています。

A = B*;

先読みトークンが B の FIRST セット内の端末と一致するかどうかに基づいて、ループを続行するかどうかをチェックする単純なループを使用します。ただし、テーブル ベースの LL パーサーに興味があります。この形式のルールはそこでどのように機能しますか? 私の知る限り、このような繰り返しを 1 つで処理する唯一の方法は右再帰を使用することですが、右連想構文木が望ましくない場合は結合性が台無しになります。

現在、LL(1) テーブルベースのパーサー ジェネレーターを作成しようとしていますが、目的の解析ツリーの形状を変更せずにこのようなケースを処理する方法がわからないため、知りたいです。

4

2 に答える 2

2

文法

EBNF 文法を単純な BNF に拡張し、それbが端末で<e>あり、空の文字列であると仮定しましょう。

A -> X
X -> BX
X -> <e>
B -> b

この文法はb、任意の長さの terminal の文字列を生成します。

LL(1) テーブル

テーブルを作成するには、最初のセットと次のセットを生成する必要があります ( LL(1) 解析テーブルを作成します)。

最初のセット

First(α)は、文法記号の任意の文字列から派生した文字列を開始する端末のセットですα。

First(A) : b, <e>
First(X) : b, <e>
First(B) : b

フォローセット

Follow(A)非終端記号 のすぐ右側に現れる端子 a の集合ですA。

Follow(A) : $
Follow(X) : $
Follow(B) : b$

テーブル

セットに基づいてテーブルを作成できるようになりました$。入力マーカーの終了です。

+---+---------+----------+
|   |    b    |    $     |
+---+---------+----------+
| A | A -> X  | A -> X   |
| X | X -> BX | X -> <e> |
| B | B -> b  |          |
+---+---------+----------+

パーサー アクションは常に、解析スタックの最上位と次の入力シンボルに依存します。

  1. 解析スタックの上のターミナル:
    1. 入力記号に一致: スタックをポップし、次の入力記号に進みます
    2. 一致なし: 解析エラー
  2. パース スタック上の非ターミナル:
    1. 解析テーブルにはプロダクションが含まれています: プロダクションをスタックに適用します
    2. セルが空です: 解析エラー
  3. $解析スタックの上に:
    1. $は入力記号です: 入力を受け入れます
    2. $は入力シンボルではありません: 解析エラー

サンプル解析

入力を分析してみましょうbb。初期の解析スタックには、開始記号と終了マーカーが含まれていますA $。

+-------+-------+-----------+
| Stack | Input |  Action   |
+-------+-------+-----------+
| A $   | bb$   | A -> X    |
| X $   | bb$   | X -> BX   |
| B X $ | bb$   | B -> b    |
| b X $ | bb$   | consume b |
| X $   | b$    | X -> BX   |
| B X $ | b$    | B -> b    |
| b X $ | b$    | consume b |
| X $   | $     | X -> <e>  |
| $     | $     | accept    |
+-------+-------+-----------+

結論

ご覧のとおり、フォームのルールはA = B*問題なく解析できます。結果として得られる入力の具体的な解析ツリーは次のbbようになります。

解析木

于 2014-12-03T13:22:36.130 に答える