是C#的lambda表达式语法LALR(1)？

Question

我想问的问题在标题中简明扼要.让我举一个问题语法的例子:

identifier_list
    : identifier
    | identifier_list identifier;

lambda_arguments
    : '(' identifier_list ')'
    | identifier;

lambda
    : lambda_arguments '=>' expression

然后我们添加正常的C表达式语法 - 特别是

primary_expression
    : '(' expression ')'
    | identifier
    | lambda;

真正的问题是,这个语法LALR(1)是否可解析,即能够被自动解析器生成器解析？或者它需要手动或GLR解析器？请注意,我希望特别了解此小节,而不是上下文相关的关键字内容或任何其他部分.

我现在想的是,如果解析器看到'(' identifier ')',它有两个有效的解析,所以如果解析器看到identifier,向前看')',它将无法决定哪个解析树失效.这可能只是一个转移/减少冲突,我可以通过分配一些任意优先权(可能是有利的'(' identifier ')')来消除.

编辑:实际上,我正在考虑使用这个语法小节来窃取新语言中的类似功能.我已经在语法形式上有类似于JavaScript的匿名函数,但我的豚鼠吱吱声反馈抱怨它们对于许多用途而言过于冗长,并且指出C#lambda表达式是更理想的解决方案.我担心这个解决方案可能导致模糊不清.所以,真的,我只对那个小节感兴趣.其他东西,如泛型和演员表对我来说都不是问题.

以前版本的语法都是机械可解析的,我不想失去这个属性,而我之前使用机械发生器的经验告诉我,最好先检查这里,而不是试试自己.对于我的手动解析器,我当然可以通过特殊情况'(' identifier向前看比正常情况更进一步.

Answer 1

首先,解析器理论始终是我的弱点之一.我主要从事语义分析工作.

其次,我曾经使用过的所有C#解析器都是手工生成的递归下降解析器.我之前在解析器理论方面具有强大背景的同事之一确实构建了自己的解析器生成器并成功地将C#语法输入其中,但我不知道这样做的恶劣黑客攻击是什么.

所以我在这里说的是以适当的怀疑态度来回答这个问题.

正如您所注意到的,lambdas稍微有些烦恼,因为您必须小心这个带括号的表达式 - 它可能是带括号的表达式,强制转换运算符或lambda参数列表,而lambda参数列表可能有几种不同的形式.但考虑到所有事情,在C#3.0中添加lambda是相对容易的,语法上的; 破解解析器并不是太难 - 正是语义分析是lambdas的熊.

对于前瞻性而言,C#语法中真正令人烦恼的问题是泛型和强制转换.

在语言已经存在之后,C#2中添加了泛型 >>,>以及<运算符,当你将泛型投入混合时,所有这些都会导致奇怪的问题.

经典的问题当然是A ( B < C, D > ( E ) ) 有没有方法的调用A需要两个参数:B < C和D > (E)或一,B<C,D>( E )？

消除歧义的规则是:

如果可以将一系列标记解析为以type-argument-list结尾的简单名称,成员访问或指针成员访问,>则会检查紧跟在结束标记之后的标记.如果是其中之一,( ) ] : ; , . ? == !=则将type-argument-list保留为simple-name,member-access或pointer-member-access的一部分,并且丢弃令牌序列的任何其他可能的解析.否则,type-argument-list不被认为是simple-name,member-access或pointer-member-access的一部分,即使没有其他可能的标记序列解析.

语法的第二个问题可以追溯到C#1.0,​​那就是演员操作符.问题是,(x)-y可能意味着"投-y键入x"或者可能意味着减去y从x.这里的规则是:

括号中的一个或多个标记的序列只有在满足以下条件之一时才被视为强制转换表达式的开头:

令牌序列是类型的正确语法,但不是表达式.

令牌序列是一种类型的正确语法,紧跟在右括号后面的令牌是令牌"〜",令牌"!",令牌"(",标识符,文字或任何关键字,除了as和is.

消除两种情况歧义的规则在理论上涉及潜在的大前瞻,但在实践中,您很少需要备份解析器.

Answer 2

用C#-style lambdas增强的表达式语法不是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
               ;

但是,我没有完整的语法,因为我不知道目标语言需要什么.

Answer 3

是的,这种情况是直接减少/减少冲突.

%token identifier ARROW

%%

program
: expression
| program expression
;

identifier_list
: identifier
| identifier_list identifier;

lambda_arguments
: '(' identifier_list ')'
| identifier;

lambda
: lambda_arguments ARROW expression;

primary_expression
: '(' expression ')'
| identifier
| lambda;


expression : primary_expression


$ yacc -v test.6.y 
conflicts: 1 reduce/reduce

这正是因为不知道下一个符号是)什么减少:我们减少一个lambda_arguments列表还是一个primary_expression？

解析器生成器通过支持lambda列表以错误的方式解决了它.但这意味着永远不会产生带括号的表达式.

这种混乱有几种方法.这可能是最简单的方法,修改后的语法不包含任何冲突:

%token identifier ARROW

%%

program
: expression
| program expression
;

identifier_list
: identifier
| identifier_list identifier
;

lambda_arguments
: '(' identifier identifier_list ')'
| identifier
;

primary_expression
: '(' expression ')'
| '(' expression ')' ARROW expression
| lambda_arguments ARROW expression
| identifier
;

expression : primary_expression

我们将lambda语法折叠成primary_expression,lambda_arguments现在是单个未加密的标识符,或者是至少两个标识符的列表.

此外,lambdas现在有两种语法案例:

| '(' expression ')' ARROW expression
| lambda_arguments ARROW expression

因此必须编写两个语义动作规则.一些逻辑将是常见的,因此可以将其归结为辅助函数,该函数为lambda构建语法树节点.

第一个语法变体的动作必须检查$2右手符号,并检查它是否是由标识符标记组成的简单主表达式.如果是这种情况,则操作会打开表达式,取出标识符并从该标识符构建lambda列表,并使用该列表生成最终作为规则输出的lambda语法节点($$值,在Yacc中计算).如果$2是任何其他类型的表达式,则发出诊断:它是错误的lambda语法,例如( 2 + 2 ) => foo.当然,解析器接受了这一点,这就是调用规则的方式.但它现在被语义上拒绝(在语义上指的是"语义"这个词的低卡路里版本).

第二个变体的动作很简单:像以前一样,使用lambda列表,正文表达式和一个lambda节点.

简单地说,lambda语法如此紧密地集成到表达式语法中,它不能轻易地归结为完全独立的规则,这些规则是通过一个要求lambda减少的生产引入的primary_expression.这是一厢情愿的想法,因为shift-reduce解析器的规则不是函数调用.