8

LALR(1) パーサーでは、文法のルールが解析テーブルに変換され、「これまでにこの入力があり、先読みトークンが X である場合、状態 Y に移行するか、ルール R によって削減されます」と効果的に記述されます。 .

ジェネレーターを使用するのではなく、実行時に解析テーブルを計算し、その解析テーブルを使用して入力を評価する、インタープリター言語 (ruby) で LALR(1) パーサーを正常に構築しました。これは驚くほどうまく機能し、テーブルの生成は非常に簡単で (これには少し驚きました)、自己参照ルールと左右の関連付けがサポートされています。

ただし、理解するのに少し苦労していることの 1 つは、yacc/bison が空のルール定義を概念的に処理する方法です。テーブルを生成する際に各ルールの各シンボルを再帰的に調べ、「空」はレクサーから来るものでも、ルールによって削減されるものでもないため、私のパーサーはそれらを処理できません。では、LALR(1) パーサーは空のルールをどのように処理するのでしょうか? 彼らはそれを特別に扱っていますか、それとも、そのような概念を特に意識する必要さえなくても、有効なアルゴリズムがうまく機能する「自然な」概念ですか?

たとえば、途中に何もないペアの括弧の任意の数に一致できるルールを考えてみましょう:

expr:   /* empty */
      | '(' expr ')'
      ;

次のような入力は、このルールに一致します。

((((()))))

これは、'(' を読み取り、先読みトークンで ')' を確認すると、パーサーが以下を選択することを意味します。

  1. ')' をシフトする (不可)
  2. 他のルールに従って入力を減らす (不可能)
  3. 何か他の...

「シフト」または「縮小」のコアアルゴリズムには完全には適合しません。パーサーは事実上、スタックに何もシフトせず、「何もない」を に還元してからexpr、次のトークン をシフトし')'、 を与え'(' expr ')'、もちろんこれは に還元さexprれます。

私を混乱させているのは「何もシフトしない」ことです。解析テーブルはそのような概念をどのように伝えますか? また、空の値を減らすと値を返す何らかのセマンティック アクションを呼び出すことができるはずであることも考慮してください。そのため、解析テーブルからそれをスキップして、スタックと先読みで単に変換する必要が$$あるというかなり単純なビューシフトは、真に sequenceを生成するのではなく、単に sequence を生成します。'('')''(' expr ')''(' ')'

4

2 に答える 2

9

これについて何日も考えたにもかかわらず、質問を書いているときとその後の議事録でこれを熟考して以来、何かが信じられないほど明白で単純であることに気づきました。

すべてのルールによるリダクションは常に: スタックから X 個の入力を取り出します。ここで、X はルール内のコンポーネントの数です。次に、結果をスタックに戻し、そのリダクション後にテーブルで指定された状態に移動します。

空のルールの場合、「空」が概念でさえあると考える必要はありません。解析テーブルには、「'('スタック上で指定され、先読みに含まれていないものはすべて'('、「空」ルールで削減する」という遷移を含める必要があります。空のルールのコンポーネントのサイズは 0 であるため、スタックから 0 をポップすることはスタックが変更されないことを意味し、何も削減した結果がスタックにシフトされない場合、実際に文法とすべてが明確になります。

Stack       Lookahead    Remaining Input      Action
--------------------------------------------------------------
$           (            ())$                 Shift '('
$(          (            ))$                  Shift '('
$((         )            )$                   Reduce by /* empty */
$((expr     )            )$                   Shift ')'
$((expr)    )            $                    Reduce by '(' expr ')'
$(expr      )            $                    Shift ')'
$(expr)     $                                 Reduce by '(' expr ')'
$expr                                         Accept

それが「うまくいく」理由は、空のルールで削減するには、スタックからゼロのアイテムをポップするだけでよいためです。

于 2011-11-23T13:43:07.250 に答える
5

可能であれば、d11wtqの素晴らしい答えを締めくくる別のビュー：

nullable ルール (ϵ を導出するルール) は、パーサーの構築中に関数FOLLOW(X)andの下で説明されFIRST(X)ます。たとえば、 があり A -> B x、B が ϵ を導出できる場合x、 によって計算されるセットに含める必要がありますFIRST(A)。しかもセットでFOLLOW(B)。

さらに、空のルールは正規LR(1)アイテム セットで簡単に表現できます。

$ファイルの終わりを表す追加の非終端記号があることを想像すると便利です。

文法を見てみましょう：

S -> X | ϵ
X -> id

最初の正規LR(1)アイテム セットについては、最初のLR(0)アイテム セットを取得し、記号「$」を使用して先読みを追加できます。

S -> . X   , '$'
S -> .     , '$'
X -> . id  , '$'

次に、先読み用の 1 つがありidます。

S -> . X   , 'id'
S -> .     , 'id
X -> . id  , 'id'

FIRSTとFOLLOWセットを見てみましょう。

S -> . X   , '$'

FIRST(X)これは「ドット最終」項目ではないため、ここでシフトしたいのですが、セットに先読み記号が含まれている場合のみです$。これは false であるため、テーブル エントリには入力しません。

次：

S -> .     , '$'

これは「ドットファイナル」の項目なので減らしたいところです。reduce のコンテキストを検証するために、次のことを調べます。reduce しFOLLOW(S)たい文法記号の後に、先読みの内容が続くことはありますか? 確かにそう。開始記号は定義上、その後に入力の終わりが続くため、$常に入っています。FOLLOW(S)はい、削減できます。そして、記号 を削減しているSので、削減は実際にはacceptアクションです: 解析は終了します。テーブル エントリにacceptアクションを入力します。

同様に、次の項目セットに対して lookahead で繰り返すことができますid。S-deriving-empty ルールにスキップしましょう。

S -> .     , 'id'

S続くことができますidか？しそうにない。したがって、この削減は適切ではありません。パーサー テーブルのエントリは埋めません。

したがって、空のルールが問題を引き起こさないことがわかります。LR(0)これはすぐに (パーサーの構築方法に応じて) ドット ファイナルまたはアイテムに変わりLR(1)、先読みの考慮とテーブルへの入力に関して、他のドット ファイナル アイテムと同じように扱われます。

于 2012-04-24T00:02:09.073 に答える