如何将此语法转换为LR（1）？

Question

我有一个LR（1）冲突的语法，我无法解决;但是，语法应该是明确的。我将首先用五个令牌简化语法来演示问题：(,),{},,和id。

的EBNF是这样的：

 args = (id ',')* 

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

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

1. (→重复。
2. )→减少为'(' args ')'。
3. id)不是{}→缩小为'(' expression ')'。
4. id){}→降低作为'(' args ')' '{}'
5. id,→降低作为'(' args ')' '{}'（最终）。

一个天真的翻译产生以下结果（和conflicts）：

formal_arg: Ident 
       {} 

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

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

所以，语法要求先行决定的最多三个令牌。我知道一个LR（3）语法为can be transformed LR（1）语法。

但是，我不太了解如何在这种特殊情况下进行转换。请注意，上面的简化语法是从larger body of code中提取的;特别是有可能变换primary而不碰expr以及上述所有内容？

Answer 1

我提供了一个解决方案，这里的问题与此非常相似：Is C#'s lambda expression grammar LALR(1)?。其基本思想是将(id)与其他两种可能性分开（(expr_not_id)和(list_at_least_2_ids)）。那么关于如何减少(id)的决定可以推迟到先行令牌可用（在你的情况下，{，假设这是足够的）。

不幸的是，尽管将expr转换为expr_not_id非常简单且几乎是机械的，但它肯定会涉及大量的制作。另外，它有点难看。所以它不能解决你在最后一句中提出的问题。我并不认为有可能在不碰expr的情况下转换primary，但我之前感到惊讶。

（另一个明显的解决方案，因为语法其实明确的，就是用一个GLR分析器生成，但我不相信你所使用的解析器发电机具有该功能。）