使用C#风格的lambda表达式扩展的表达式文法不是LALR(1),但可能是LALR(2)。因此,可以(尽管可能并不容易)生成等效的LALR(1)文法:请参见下面的编辑。
您将在输入上获得一个reduce/reduce冲突:
( id )
因为id
可以缩减为identifier_list
或expression
(在第二种情况下间接地),而解析器无法根据一个向前看标记(>
)来判断哪个是正确的。
如果基于两个向前看标记,它就能够判断了,因为只有当第二个接下来的标记是=>
时才可能将其缩减为identifier_list
,只要=>
不是语言中的运算符,如果第二个接下来的标记是=>
,则无法将其缩减为expression
。所以我认为这可能是 LALR(2),虽然我不能确定。
当有多个标识符时并不会出现问题,因为在
( id1 id2 )
id1 id2
无法在大多数表达式语言中简化为一个表达式(当然,你所使用的语言可能不同)。当单个未加括号的标识符紧跟着 =>
时,也不会有问题,前提是 `=>' 不是有效的运算符。
编辑
我在原始回答中忽略了一点,即不存在 LALR(2) 语言这样的东西。由 LALR(2) 文法识别的语言也被某些 LALR(1) 文法识别。事实上,有一个构造性证明支持此主张,允许机械地创建这样一个 LALR(1) 文法,以及一个过程来恢复原始解析树。
在这种情况下,生成 LALR(1) 文法甚至更简单,因为如上所述只有一条产生式需要额外的前瞻。解决方法是将规约延迟一个记号。换句话说,在原始文法中包括类似以下内容:
primary: '(' expression ')'
lambda_parameters: '(' id_list ')'
在这里,id_list
和expression
都派生出终端ID
。除了ID
之外,这两个非终端的派生是不重叠的,因此我们可以按照以下方式解决问题:
primary: '(' expression_not_id ')'
| '(' ID ')'
lambda_parameters: '(' id_list_not_id ')'
| '(' ID ')'
现在只需要对expression
和id_list
进行分离,以便单独处理ID
的情况,这并不是很困难。下面是一个简化的例子,可以很容易地扩展;它仅限于加法、乘法和函数应用(我包括这些来证明两个逗号分隔列表不是问题):
primary: primary_not_id | ID ;
term: term_not_id | ID ;
sum: sum_not_id | ID ;
expr: expr_not_id | ID ;
expr_list: expr | expr_list ',' expr ;
arguments: '(' ')' | '(' expr_list ')' ;
ids: ID ',' ID | ids ',' ID ;
parameters: '(' ID ')' | '(' ids ')' ;
primary_not_id: LITERAL
| '(' expr_not_id ')'
| '(' ID ')'
| primary arguments
;
term_not_id: primary_not_id
| term '*' primary
;
sum_not_id: term_not_id
| sum '+' term
;
expr_not_id: sum_not_id
| parameters RIGHT_ARROW expr
;
注意:原文中的语法将多个参数的lambda表达式表示为标识符序列,而不是用逗号隔开:
(a b) => a + b
。我认为实际意图是使用逗号:
(a, b) => a + b
,这也是我在上面的语法中所做的更改。如果你所使用的语言有逗号运算符(例如C系列),这种区别就很重要,因为在这种情况下,一个表达式可能会是
'(' expression_list ')'
,这与lambda参数列表冲突。不加思索的实现会导致在
expression_list
中的第一个
expression
上产生reduce/reduce冲突,这是无法通过有限的前瞻解决的,因为
expression_list
可以是任意长的。
不过,对于这种情况也有解决方法:可以将id_list
与expression_list
分开,类似于以下内容:
id_list: ID
| id_list ',' ID
;
expression_list_not_id_list: expression_not_id
| id_list ',' expression_not_id
| expression_list_not_id_list ',' expression
;
expression_list: expression_list_not_id_list
| id_list
;
我并没有进行完整的语法校对,因为我不知道目标语言需要哪些。