用 C# 风格的 lambda 增强的表达式语法不是 LALR(1),但它可能是 LALR(2)。因此,有可能(尽管不一定是微不足道的)产生等效的 LALR(1) 语法:请参阅下面的编辑。
您将在输入上遇到减少/减少冲突:
( 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
案件,事实证明这并不是很困难。下面是一个简化的例子,可以很容易地扩展;它仅限于加法、乘法和函数应用(我包括在内以证明两个逗号分隔的列表不是问题):
%token ID LITERAL RIGHT_ARROW
%start expr
%%
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
;
注意:OP 中的语法生成具有多个参数的 lambdas 作为标识符序列,不以逗号分隔:(a b) => a + b
。我认为实际意图是使用逗号:(a, b) => a + b
,这就是我在上述语法中所做的。如果您的语言像 C 家族那样具有逗号运算符,则差异很重要,因为在这种情况下,表达式可能是'(' expression_list ')'
,它与 lambda 参数列表冲突。一个幼稚的实现会导致第一个中的减少/减少冲突expression
,因为它可能是任意长的expression_list
,所以无法通过有限的前瞻来解决。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
;
不过,我没有做完整的语法,因为我不知道目标语言需要什么。