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,向前看')',它将无法决定要关闭哪个解析树。不过,这可能只是一个 shift/reduce 冲突,我可以通过分配一些任意优先级(可能是 favouriing '(' identifier ')')来消除它。

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

我以前的语法版本是机械可解析的,我不想失去这个属性,而我以前使用机械生成器的经验告诉我,最好在这里检查而不是自己尝试。对于我的手动解析器,我当然可以简单地在特殊情况下'(' identifier向前看比正常情况更远一些。

4

4 回答 4

37

首先,解析器理论一直是我的弱点之一。我主要研究语义分析器。

其次,我曾经使用过的所有 C# 解析器都是手动生成的递归下降解析器。我的一位在解析器理论方面拥有深厚背景的前同事确实构建了自己的解析器生成器并成功地将 C# 语法输入其中,但我不知道这样做会带来什么样的骇人听闻的黑客攻击。

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


正如您所注意到的,lambda 有点令人烦恼,因为您必须小心那个带括号的表达式——它可能是一个带括号的表达式、一个强制转换运算符或一个 lambda 参数列表,而 lambda 参数列表可能有几种不同的形式。但考虑到所有因素,在 C# 3.0 中添加 lambda 在语法上相对容易;破解解析器并不太难——语义分析对 lambdas 来说是个难题。

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

泛型是在 C# 2 中添加的,在该语言已经具有 >>,><运算符之后,当您将泛型混入其中时,所有这些都可能导致奇怪的问题。

经典问题当然A ( B < C, D > ( E ) ) 是方法的调用是否A需要两个参数:B < Cand D > (E)or one, B<C,D>( E )?

消除歧义的规则是:

如果可以将标记序列解析为以 type-argument-list 结尾的简单名称、成员访问或指针成员访问,则检查紧跟在结束>标记之后的标记。如果它是其中之一,( ) ] : ; , . ? == !=则类型参数列表作为简单名称、成员访问或指针成员访问的一部分保留,并且丢弃标记序列的任何其他可能的解析。否则,类型参数列表不被视为简单名称、成员访问或指针成员访问的一部分,即使没有其他可能的标记序列解析。

语法的第二个问题可以追溯到 C# 1.0,那就是强制转换运算符。问题是这(x)-y可能意味着“强制-y类型转换x”或者它可能意味着yx. 这里的规则是:

仅当以下至少一项为真时,括号中的一个或多个标记的序列才被视为强制转换表达式的开始:

标记序列对于类型来说是正确的语法,但对于表达式来说却不是。

记号序列是一个类型的正确语法,紧跟在右括号后面的记号是记号“~”、记号“!”、记号“(”、标识符、文字或除asand之外的任何关键字is

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

于 2013-06-04T23:28:41.427 回答
10

用 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_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
           ;

注意:OP 中的语法生成具有多个参数的 lambdas 作为标识符序列,不以逗号分隔:(a b) => a + b。我认为实际意图是使用逗号:(a, b) => a + b,这就是我在上述语法中所做的。如果您的语言像 C 家族那样具有逗号运算符,则差异很重要,因为在这种情况下,表达式可能是'(' expression_list ')',它与 lambda 参数列表冲突。一个幼稚的实现会导致第一个中的减少/减少冲突expression,因为它可能是任意长的expression_list,所以无法通过有限的前瞻来解决。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
               ;

不过,我没有做完整的语法,因为我不知道目标语言需要什么。

于 2013-06-05T04:35:32.633 回答
5

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

%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. 这是一厢情愿的想法,因为 shift-reduce 解析器的规则不是函数调用。

于 2013-06-05T07:34:29.287 回答
3

我不认为 lambda 表达式语法问题本身很有趣,除非你知道语言的其余部分是 LALR(1)。

如果您想知道答案,请将您的子语法提供给 LALR(1) 解析器生成器。如果它抱怨 shift-reduce 或 reduce-reduce 冲突,则不是 LALR(1)。根据定义,语法是否LALR(1) 取决于您是否可以为其构建转换表。

大多数情况下,人们想要一个用于整个语言的解析器。

这里有两个有趣的问题。

1) C# 4.5 完全是一种语言 LALR(1) 吗?(例如,是否有一些语法是 LALR(1)?请注意,不是 LALR(1) 的特定语法并不意味着没有另一个语法。

2) 微软(以多种形式)发布的任何 C# 语法是否为 LALR(1)?

我认为 Eric 告诉我们 1) 不是真的。这表明 2) 也不正确。

C++ 需要无限前瞻来解析其模板,这主要是由于本地可能性“>”被解释为“结束模板参数”或“大于”。由于 C# 复制了这个,我希望它对模板分辨率也有无限的前瞻要求。那绝对不是 LALR(1)。[关于“>>”是否可以被视为移位运算符,而“> >”不能被视为一个额外的混乱,你无法在语法中修复,因为它看不到空格。]

我的公司使用 GLR 作为其语言处理工具,并且我们有一个 C# 4.5 语法可以正常工作。GLR 意味着我们不必考虑如何将上下文无关文法转换为与 LALR(1) 兼容的形式(例如,弯曲、扭曲、左/右因子、随机播放)或代码即席前瞻等。因此我们可以专注于处理代码的问题,而不是解析问题。

这确实意味着强制转换和其他构造在解析时会产生模棱两可的树,但如果您有类型信息,这些很容易解决。

于 2013-06-05T00:36:33.673 回答