3

解決できない LR(1) 競合のある文法があります。それでも、文法は明確であるべきです。(最初に、、)、{}、 の5 つのトークンを使用した簡略化された文法で問題を示します。,id

EBNF は次のようになります。

      args = ( id ',' )*

expression = id
           | '(' expression ')'
           | '(' args ')' '{}'

文法は明確で、最大 2 つの先読みトークンが必要です。が(シフトされると、次の 5 つの可能性しかありません。

  1. (→再発。
  2. )→ のように縮小し'(' args ')'ます。
  3. id )ない{}→ として減らす'(' expression ')'。
  4. id ) {}→'(' args ')' '{}'
  5. id ,'(' args ')' '{}'→ (最終的に)として削減します。

単純な翻訳では、次の結果 (および競合)が得られます。

   formal_arg: Ident
               {}

  formal_args: formal_arg Comma formal_args
             | formal_arg
             | /* nothing */
               {}

      primary: Ident
             | LParen formal_args Curly
             | LParen primary RParen
               {}

そのため、文法では、決定する先読みの最大 3 つのトークンが必要です。LR(3) 文法は LR(1) 文法に変換できることを知っています。

ただし、この特定のケースで変換を行う方法がよくわかりません。上記の単純化された文法は、より大きなコード本体からの抜粋であることに注意してください。特に、 上記のすべてprimaryをタッチせずに変換することは可能ですか?expr

4

1 に答える 1

1

ここで、これと非常によく似た問題の解決策を提供しました: Is C#'s lambda expression grammar LALR(1)? . 基本的な考え方は、( id )ケースを他の 2 つの可能性 (( expr_not_id )および( list_at_least_2_ids )) から分離することでした。次に、先読みトークンが利用可能になるまで、削減方法に関する決定を( id )延期できます（あなたの場合、それで{十分であると仮定します）。

残念ながら、への変換exprはexpr_not_id非常に簡単でほとんど機械的ですが、間違いなく多くの作品に影響を与えます。また、それはやや醜いです。したがって、最後の文で提示した問題を解決できません。primary触らずに変身できるとは正直思いませんがexpr、以前から驚いていました。

(もう 1 つの明白な解決策は、文法が実際には明確であるため、GLR パーサー ジェネレーターを使用することですが、使用しているパーサー ジェネレーターにその機能があるとは思えません。)

于 2013-06-30T03:40:32.660 に答える