C#的lambda表达式语法是否为LALR(1)?

35

我希望问的问题已经简明地在标题中给出。让我举一个相关语法方面的例子:

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特殊处理,稍微向前查看一点。


4
@EricLippert可能能够回答这个问题。 - Federico Berasategui
这是一个 @JonSkeet 的问题。 - Scott Selby
14
虽然Eric和Jon非常聪明,掌握了很多(有时是内部的)知识,但似乎这个语法问题可以由一个没有“内部知识”的人回答,只要他对语法和解析器有良好的理解(即:比我高出很多)。 - user2246674
LALR(1)、手动编写解析器和GLR并不是唯一的选择。只要文法是明确无歧义的,ANTLR 4就能够生成一个工作的解析器,前提是文法不包含间接或隐藏的左递归。 - Sam Harwell
1
可能是《C#和Java语法是否为LALR(x)?》的重复问题。 - user541686
显示剩余5条评论
4个回答

38
首先,解析器理论一直是我的薄弱点之一。我大多数时间都在工作于语义分析器。
其次,我曾经使用的所有C#解析器都是手动生成的递归下降解析器。我的一位前同事在解析器理论方面有很强的背景,他构建了自己的解析器生成器并成功地将C#语法馈入其中,但我不知道这样做会涉及到什么样的恶意黑客活动。
所以我要说的是要适当怀疑这个答案。
正如你所指出的,Lambda表达式可能会让人感到有些恼火,因为你必须小心处理括号表达式--它可能是一个括号表达式、一个转换操作符或一个Lambda参数列表,并且Lambda参数列表可能有几种不同形式。但总的来说,在C# 3.0中添加Lambda表达式相对容易,语法上的修改不太困难--Lambda表达式的语义分析才是一个麻烦。
就前瞻而言,在C#语法中真正棘手的问题是泛型和转换。
泛型在C# 2中添加,在语言已经具有 >>、> 和 < 运算符之后,当你将泛型引入时,所有这些运算符都可能导致奇怪的问题。
经典问题当然是 A ( B < C, D > ( E ) )。调用方法 A 是否需要两个参数:B < C 和 D > (E),还是一个参数,B(E)?
为了消除歧义的规则如下:如果一系列的标记可以解析为简单名称、成员访问或指针成员访问,且以类型参数列表结尾,则会检查紧随右尖括号 > 标记之后的标记。如果它是 ( ) ] : ; , . ? == != 中的一个,则将类型参数列表保留为简单名称、成员访问或指针成员访问的一部分,而将序列标记的任何其他可能解析舍弃。否则,即使没有序列标记的其他可能解析,也不认为类型参数列表是简单名称、成员访问或指针成员访问的一部分。
语法的第二个问题可以追溯到 C# 1.0,它涉及转换操作符。问题在于 (x)-y 可能意味着“将 -y 强制转换为类型 x”,也可能意味着从 x 中减去 y。这里的规则是:
由括号括起来的一个或多个标记序列仅在以下至少一种情况成立时被视为强制转换表达式的开头:
- 序列标记对于类型而言是正确的语法,但对于表达式却是错误的语法。 - 序列标记对于类型而言是正确的语法,并且直接跟在右括号之后的标记是 “~”,“!”,“(” ,标识符,字面量或任何关键字(除 asis 之外)。
消除歧义的规则在理论上涉及潜在的大量前瞻,但在实践中,您很少需要让解析器回溯太远。

让我想起了我之前的一个问题... https://dev59.com/LWYq5IYBdhLWcg3whRDV - user541686
我很感激您对于一般问题的见解,但我的问题确实非常具体。不过,我很好奇您在Lambda分析的哪个部分遇到了困难,因为我发现它们非常容易实现。 - Puppy
2
@DeadMG:你可能有一个不会每天改变的规范来工作。最难的部分是将现有的匿名方法分析改装成处理推测性Lambda绑定的形式;那段代码充满了全局可变状态,这使得进行推测变得困难。让性能达到可接受的水平也需要相当多的工作,设计一个在典型场景下呈现良好错误消息的算法也是如此。 - Eric Lippert

10

使用C#风格的lambda表达式扩展的表达式文法不是LALR(1),但可能是LALR(2)。因此,可以(尽管可能并不容易)生成等效的LALR(1)文法:请参见下面的编辑。

您将在输入上获得一个reduce/reduce冲突:

( id )

因为id可以缩减为identifier_listexpression(在第二种情况下间接地),而解析器无法根据一个向前看标记(>)来判断哪个是正确的。

如果基于两个向前看标记,它就能够判断了,因为只有当第二个接下来的标记是=>时才可能将其缩减为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_listexpression都派生出终端ID。除了ID之外,这两个非终端的派生是不重叠的,因此我们可以按照以下方式解决问题:

primary:           '(' expression_not_id ')'
       |           '(' ID ')'


lambda_parameters: '(' id_list_not_id ')'
                 | '(' ID ')'

现在只需要对expressionid_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
           ;
注意:原文中的语法将多个参数的lambda表达式表示为标识符序列,而不是用逗号隔开:(a b) => a + b。我认为实际意图是使用逗号:(a, b) => a + b,这也是我在上面的语法中所做的更改。如果你所使用的语言有逗号运算符(例如C系列),这种区别就很重要,因为在这种情况下,一个表达式可能会是'(' expression_list ')',这与lambda参数列表冲突。不加思索的实现会导致在expression_list中的第一个expression上产生reduce/reduce冲突,这是无法通过有限的前瞻解决的,因为expression_list可以是任意长的。

不过,对于这种情况也有解决方法:可以将id_listexpression_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
               ;

我并没有进行完整的语法校对,因为我不知道目标语言需要哪些。


嗯,是的,我完全是想要有 (a, b) - Puppy

5

是的,这种情况是一个明显的reduce/reduce冲突。

%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”现在是一个未括号化的单个标识符或至少两个标识符的列表。
此外,现在有两种语法情况适用于lambda函数:
| '(' expression ')' ARROW expression
| lambda_arguments ARROW expression

因此需要编写两个语义操作规则。其中一些逻辑是通用的,可以委托给一个帮助函数,该函数构建lambda的语法树节点。
对于第一个语法变体,操作需要检查$2右手符号,检查它是否是由标识符令牌组成的简单基本表达式。如果是这种情况,操作就会打开表达式,取出标识符并从该标识符构建lambda列表,并使用该列表生成lambda语法节点,该节点最终成为规则的输出(在Yacc术语中为$$值)。如果$2是任何其他类型的表达式,则发出诊断:这是错误的lambda语法,例如(2+2)=>foo。当然,这被解析器接受,这就是规则被调用的方式。但现在它正在被语义地拒绝(其中"语义"指的是"语义"这个词的低热量版本)。
第二个变体的操作很简单:取出lambda列表、正文表达式并生成lambda节点,就像以前一样。
简而言之,lambda语法与表达式语法紧密集成,不能轻易地将其分配到完全分离的规则中,通过一个将lambda减少为primary_expression的单个产生式调用。这是一厢情愿的想法,因为移位-约简解析器的规则不是函数调用。

我可以简单地禁止(x) => expr,只允许x => expr(x, y) => expr - Puppy
1
你可以禁止它们。很快你会发现一个包含它们的程序。 - Ira Baxter
a) 我很高兴你去做了LALR生成器实验,因为它回答了这个问题。 b) 如果按照你所问的精确问题,我的答案是“不”,所以我很惊讶你把“是”写成了你的第一个词。 c) 事实上,你可以通过语义动作作弊并以此方式实现LALR语法,但对于你的问题,我的答案仍然是“不”,但对于“我能否构建一种基于LALR的解析器来读取某种语言”,我的答案是“是”,因为我们总是可以接受过多的内容并进行(图灵)后处理来清理。所有解析器都在某种程度上是这样工作的。 - Ira Baxter
@IraBaxter:我的修改表明,由于我正在考虑在一种新语言中引入一个类似语法的特性,因此我没有任何使用这个语法的现有程序。因此,像C#中那样的任何现有程序都不是我的问题。 - Puppy
啊,那你可以根据自己的方便定义语法,这个问题就没有意义了。 - Ira Baxter

3
我认为lambda表达式语法问题本身并不有趣,除非你知道整个语言都是LALR(1)。
如果你想知道答案,请将子文法输入到一个 LALR(1) 解析器生成器中。如果它抱怨移位规则或约简冲突,则不是 LALR(1)。一个文法是否是LALR(1)取决于你能否按定义为其构建过渡表。
大多数情况下,人们需要一个完整语言的解析器。
这里有两个有趣的问题。
1)C# 4.5本身是否是LALR(1)语言?(例如,是否存在某些文法是LALR(1)的?注意:特定的文法不是LALR(1)并不意味着没有另一个文法是LALR(1)。)
2)Microsoft发布的任何C#文法(以其许多形式)是否是LALR(1)?
我认为Eric告诉我们1)不正确。这表明2)也不正确。
C++需要无限的前瞻来解决模板,这在很大程度上是由于“>”可能被解释为“模板参数结束”或“大于号”的局部可能性所引起的。由于C#复制了这一点,我预计它在模板解析方面也需要无限的前瞻要求。这绝对不是 LALR(1)。[还有一个混乱的问题,即“>>”是否可以被视为移位运算符,而“> >”则不能被视为移位运算符,这无法在语法中修复,因为它无法看到空格。]
我的公司使用GLR作为其语言处理工具,我们有一个工作良好的C# 4.5文法。 GLR意味着我们不必考虑如何将上下文无关文法转换为LALR(1)兼容形式(例如,弯曲、扭曲、左/右因子、洗牌),或编写特定的向前查找等,因此我们可以专注于处理代码的问题,而不是解析。
这确实意味着强制转换和其他结构在解析时会产生歧义树,但是如果你有类型信息,这些歧义很容易解决。

埃里克只提供了两个C#语言规范中真正模棱两可的例子,这与你的第一个观点无关。我的直觉是,如果您不关心获得漂亮的解析树,那么为C#制作LALR(1)语法将非常简单:例如,您可以给出一个正则表达式“id(\ + id | \ * id)*”来检查简单的表达式语法,但这并不能告诉您太多有关输入的结构信息。如果您不关心结构,LALR(1)非常强大。 - Alex ten Brink
事实上,所有解析器都通过某种方式读取输入,然后对结果进行后处理以克服解析器的缺点。没有其他方法(理想情况下不需要后处理)。因此,您可以使用正则表达式“.+”(因此明显是LALR)解析C#,然后返回并添加结构,但这违背了问题的要点。我认为公平地解释它为,“是否有一个LALR(1)解析器可以捕获整个语言[而不会在某个地方丢失结构]?”对于C#,Eric的示例和模板上的无限前瞻几乎使问题无解:否。 - Ira Baxter

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文,
原文链接