3

我有一个无法解决的 LR(1) 冲突的语法；然而，语法应该是明确的。我将首先用五个标记的简化语法来演示这个问题：(、)、{}和。,id

EBNF 看起来像这样：

      args = ( id ',' )*

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

语法是明确的，最多需要两个前瞻标记。当(移位时，只有五种可能：

  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
               {}

因此，语法最多需要三个前瞻标记来决定。我知道 LR(3) 语法可以转换为 LR(1) 语法。

但是，我不太明白在这种特殊情况下如何进行转换。请注意，上面的简化语法是从大量代码中提取的；primary特别是，是否有可能在不触摸和上述所有内容的情况下进行转换 expr？

4

1 回答 1

1

I provided a solution to a problem very similar to this one here: Is C#'s lambda expression grammar LALR(1)?. The basic idea was to separate out the ( id ) case from the other two possibilities ( ( expr_not_id ) and ( list_at_least_2_ids ) ). Then the decision about how to reduce ( id ) can be deferred until the lookahead token is available (in your case, {, assuming that that is sufficient).

Unfortunately, while the transformation of expr into expr_not_id is pretty straightforward and almost mechanical, it definitely touches a lot of productions. Also, it's somewhat ugly. So it fails to solve the problem you present in the last sentence. I don't actually think that it is possible to transform primary without touching expr, but I've been surprised before.

(The other obvious solution, since the grammar is in fact unambiguous, is to use a GLR parser-generator, but I don't believe the parser-generator you are using has that feature.)

于 2013-06-30T03:40:32.660 回答