2

私はこのような文法を持っています：

「1つ以上のrule1に一致します。ここで、rule1は1つ以上のrule2であり、rule2は1つ以上のrule3などです。それぞれ改行で区切られます」。次の例を見てください。

start:   rule1_list
      ;

rule1_list:   rule1
           |  rule1_list NEWLINE rule1
            ;

rule1:   rule2
     |   rule2 NEWLINE rule3_list
      ;

rule2:   TERMINAL2
      ;

rule3_list:   rule3
          |   rule3_list NEWLINE rule3
          ;

rule3 :  TERMINAL3
      ;

これを行うと、shift / reduceの競合が発生しますが、文法を変更して停止するにはどうすればよいですか？基本的に、新しい行の後で分岐し、次のものがTERMINAL2またはTERMINAL3であるかどうかを確認する必要があります。

4

3 に答える 3

5

LALR（1）ではなく、あいまいな文法、デフォルトでは解析できないyaccモード

長い話を短くするために、%glr-parser次のように宣言を使用してこれを「修正」できます。

%glr-parser
%%
start: rule1_list
. . .
. . .

ロングストーリーのようなミディアムレングスを作るには...

Shift-reduceの競合は、通常、エラーではありません。競合は、通常は必要なシフトを常に実行することで解決されます。ほとんどまたはすべての実際の文法には、shift-reduceの競合があります。また、削減が必要な場合は、優先順位宣言を使用して削減を調整できます。

ただし、真にあいまいな文法では、シフトを実行すると、パーサーが2つのパスのいずれかに送信され、そのうちの1つだけが最終的に文法内の文字列を検出します。この場合、S/Rの競合は致命的なエラーです。

最初のものを分析すると、パーサーが| rule2 NEWLINE rule3_listケース内の改行を検出すると、rule3_listが期待される新しい状態に移行するかrule1: rule2、を使用してrule1を減らすことができます。デフォルトでshiftが選択されているため、常にrule3_listを検索します。

2番目の競合は、に改行が表示されたときに発生します rule3_list: rule3_list . NEWLINE rule3。これで、シフトしてrule3の検索を開始するか、を使用してrule1を減らすことができます| rule2 NEWLINE rule3_list。

その結果、記述されているとおり、端末に「2」と「3」を想定すると、2行の後に3行しか解析できません。優先順位をいじると、「2」行のみを解析でき、「3」行は解析できません。

最後に、yaccで生成されたGLRパーサーを使用することは、ちょっとした悩みの種であることを付け加えておきます。私はそれがうまくいくと思いますが、それは純粋なBFIであり、パーサーは分割し、2つのスタックを保持し、文法に文字列が見つかるまで両方のパスを続行します。悲しいことに、他の修正も問題です。1.文法をLALR（1）として再定式化し、2。スキャナーに先読みを追加し、複合トークンを返します。3 .使用している文法のルールを試してみてください。おそらく、yaccで処理できます。バリエーション。

これが、私が実際にyaccが好きではなく、手書きの再帰下降またはPEGのようなより現代的なものを好む理由です。（Treetopを参照してください。）

改行を単に無視する（推奨される）左再帰ルールで何かを試しました（文法が複雑になり、空白トークンが作成されます...）..そしてこれは「機能」しますが、それがあなたの望むものかどうかはわかりません。 ..

%%
start:   stmtList
      ;

stmtList: /* nothing */ 
      | stmtList '2' threeList;
      ;

threeList: /* nothing */
      | threeList '3'
      ;
%%
int yylex() { int c; do {  c = getchar (); } while (c == '\n'); return c; }
于 2009-11-19T01:17:35.183 に答える
1

あいまいではなく、LALR（1）ではありません

問題は、文法のいくつかの場所で2トークンのルックイーヘッドが必要であり、何をすべきかを決定するためにNEWLINEの後にどのTERMINALが続くかを確認することです。これを修正するためにできることはたくさんあります。

  1. scaanerの改行をスキップします-そうすると、それらはトークンではなくなり、先読みの邪魔になりません

  2. ％glr-parserを使用します。これは、文法に曖昧さを導入した場合、物事を機能させるためにマージ関数が必要になるため、危険な場合があります。特定の競合があいまいさによるものなのか、それとも先読みが必要なだけなのかを判断する良い方法はありません。各競合バイソンレポートを注意深く分析して伝える必要があります。

  3. 文法をリファクタリングして決定を延期するため、先読みはそれほど必要ありません。簡単な選択の1つは、区切り文字ではなくターミネータとして改行をルールに吸収することです。

    start:   rule1_list ;

rule1_list:   rule1
          |  rule1_list rule1
          ;

rule1:   rule2
     |   rule2 rule3_list
     ;

rule2:   TERMINAL2 NEWLINE ;

rule3_list:   rule3
          |   rule3_list rule3
          ;

rule3 :  TERMINAL3 NEWLINE ;

もちろん、これにより文法が変更され、EOFの前の最後のルールの後に改行が必要になります。

于 2009-11-22T20:29:06.990 に答える
0

左再帰を右再帰に変換する必要があると思います。例rule3_list：

rule3_list: TERMINAL3 | TERMINAL3 NEWLINE rule3_list;
于 2009-11-19T01:45:32.957 に答える