如何解决在野牛中使用相同字符的两个不同操作符之间的模糊冲突

%token NUM
%token OR
%token NORM

%right LOR ROR 
%right NORM
%right OR
%right '|'

%%

expression:
    NUM
    | lnorm expression rnorm %prec NORM
    | expression LOR ROR expression %prec OR

lnorm: '|' | ROR | LOR
rnorm: '|' | LOR

%x NOR NOR2


%%
-?[0-9]+                  { return NUM; }
"|"                       { yy_push_state(NOR); }

<NOR2>.  { yyless(0); yy_pop_state(); return ROR; }
<NOR>"|" { BEGIN(NOR2); return LOR; }
<NOR>.   { yy_pop_state(); yyless(0); return '|'; }

首先,您的语言本质上是模棱两可的.你可以通过各种方式解决歧义 – 下面有一些想法 – 但这种含糊不清通常不是一个好主意,因为它们不仅使语言难以解析机器;它们使人类难以解析.这个世界充满了计算机语言,@R_489_10498@古怪的解析和常见问题解答,解释了为什么你所写的内容并没有达到你的意思.

(在下面,我将使用⌈…⌋而不是| … |代表norm,而x‖y代替x || y代表or,以显示表达式如何解析.)

这是一个简单的歧义：

|a|||b|||c|

它可能是：

⌈a‖⌈b⌋‖c⌋

要么

⌈a⌋‖b‖⌈c⌋

所以我们需要能够选择这两种解释中的一种或另一种.

如果我们在帖子中使用语法,我们需要能够减少每个|这真的是非终端rnorm的⌋,每个|这是一个⌈到lnorm.通过LR(1)语法[注1]的逻辑,我们需要仅根据紧跟在|后面的令牌的输入做出这个决定.

很容易看到第一个|永远是⌈,但是|||是一个挑战.如果我们要选择⌈a⌋‖b‖⌈c⌋作为正确的解析,我们需要在读取| a ||后立即决定.如果相反我们的消歧规则将用于⌈a‖⌈b⌋‖c⌋,我们可以等待一段时间,但我们仍然需要决定何时读取| a ||| b.

但无论我们采用哪种方式,我们都必须将其他一些明确的字符串转换为语法错误.这里有一些字符串,所有字符串都以| a ||| b开头,带有明确的解析：

|a|||b        ⇒ ⌈a⌋‖b
|a|||b||      ⇒ ⌈a‖⌈b⌋⌋
|a|||b||c     ⇒ ⌈a⌋‖b‖c
|a|||b|||c||| ⇒ ⌈a‖⌈b‖⌈c⌋⌋⌋

简而言之,我们无法在我们看到b的时候做出决定.实际上,在我们看到整个输入之前,我们通常无法做出决定,所以即使我们找到一个,也无法使用LR(k)解析器来获得更大的K值.

这种困境是典型的“过早减少”;在这种情况下,我们减少了代表输入的各种令牌为了避免有大量非常相似的产品应对选择的笛卡尔积,一个非终端rnorm.这样的快捷方式通常是不鼓励的,部分原因是它们消除了优先使用消歧的可能性,部分原因是它们可以将LR(1)语法转换为LR(2)或更糟.我们可以很容易地摆脱lnorm和rnorm(以更大的语法为代价),但在这种情况下它无济于事;即使减少了rnorm,我们仍然需要在不迟于我们看到令牌之后减少括号括号表达式.这关闭了常态.而且,如上所述,我们没有足够的信息来做到这一点.

显然,我们要么必须放弃LR(1)解析的想法,要么我们需要拒绝一些明确的表达式(例如,上述四个表达式中的两个).

让我们暂停一下,绕道而行.在包含括号(各种类型)和二元运算符的标准表达式语法中,表达式必须与正则表达式匹配：

OPEN* TERM CLOSE* ( OPERATOR OPEN* TERM CLOSE* )*

其中TERM是名称或常量文字,OPEN是某种形式的左括号,CLOSE是某种形式的近括号.

如果有前缀和/或后缀运算符,那么我们可以将OPEN更改为(OPEN | PREFIX)并将CLOSE更改为(CLOSE | POSTFIX).它不会改变我要说的任何内容.

并非所有与正则表达式匹配的字符串都在表达式语言中,但表达式语言中的每个字符串都必须与正则表达式匹配.要将其限制为正确的表达式字符串,我们还需要要求括号正确匹配,而不能用常规语言表示.但这也不重要.

可以将正则表达式重新排列为：

OPEN* TERM ( CLOSE* OPERATOR OPEN* TERM )* CLOSE*

这清楚地说明在第一个TERM之前出现的任何事情都是开放的;在最后一个术语之后出现的任何东西都是CLOSE,并且两个TERM之间的任何字符串都只包含一个OPERATOR,可能在OPEN之后,然后是CLOSE.

在您的语言中,条形(|)可以是OPEN或CLOSE,其中两个可以是OPERATOR.要求运算符是两个棒是否有任何优势？没有;加倍这个标准决不会有助于消除解析的歧义.两个TERM之间的一串连续条必须包含一个运算符;将运算符拼写为||仅表示连续条形的字符串必须长一个条形.

现在,我们来看一下问题中的扫描仪规则.

第一个观察是他们没有真正起作用.或者这可能是第二次观察,因为第一个观察结果是它们看起来太复杂了,无法实现它们所要完成的任务.状态NOR和NOR2之间的交替意味着| s序列被置于LOR和ROR令牌的交替中.例如,表达式：| 1 |||| 2 |将被列为| 1LORRORLORROR2 |.但这不会允许正确的解析(⌈1⌋‖⌈2⌋),因为中间的两个|字符被标记为RORLOR,因此与表达式@L_874_41@不匹配：

expression LOR ROR expression

当然,这是可以解决的.我们只需要向解析器添加更多制作.但是,yuk！

但目标只是要求两个条形图只有在没有空格分隔的情况下才能被识别为“或”运算符.没有必要这么努力工作.以下就足够了：

[0-9]+   { return numbER; }
[|]/[|]  { return COMBINING_BAR; }
[|]      { return NON_COMBINING_BAR; }

(如果第一个规则具有第二个规则,则第二个规则不适用,因为第一个规则优先,因此具有优先级,但主要是因为flex实际上考虑了规则的长度,@L_874_46@在确定哪个是最长匹配时的尾随上下文.)

lexing的这种风格确实有用,它对解析C和其他语言的类似问题很有用,不幸的是它借用了它不幸的重载<和&gt ;,可以是模板括号,比较运算符或移位运算符.没有一些消歧规则,在C表达式中开始 A< B< X>> … 从理论上说,>>成为任何一个

>两个关闭模板括号@H_616_100@>一个关闭的模板括号,后跟一个大于运算符@H_616_100@>一个右移操作符.

在C 11之前,它始终是一个右移操作符.从C 11开始,它将是两个接近的模板括号,而>>在B< x>> …中将是一个关闭的模板括号,后跟一个大于运算符.

C 11消歧基于一个简单的规则：“如果>可以关闭未闭合的打开模板括号,那么它是一个封闭的模板括号”(即使紧接着另一个>).如果你考虑一下,这是唯一可以在上述LR(1)论证中存活的规则;它允许解析器决定关于哪种类型的令牌>是尽可能早.这可以使用与上述类似的技术来实现.以非常简化的形式：

template_specialization
     : TEMPLATE_NAME '<' template_arguments '>'
template_arguments
     : template_argument
     | template_arguments ',' template_argument
     ;
template_argument
     : type
     | expression_other_than_gt
     ;
expression
     : expression_other_than_gt
     | expression '>' expression
     | expression COMBINING_GT NON_COMBINING_GT expression
     /* I left out @R_607_10112@ is needed to handle >>=,but it is similar */
     ;
expression_other_than_gt
     : ID
     | CONSTANT
     | '(' expression ')'
     | expression '+' expression
     /* and so on,including <,<<,<<= but without >,>>,>>= */
     ;

使用expression_other_than_gt似乎有点难看,很自然地会问是否可以使用优先级声明.我稍后会讨论这个问题,但是现在我要注意,即使可以正确地说明优先权声明,也不容易做到并且难以以可以证明有效的方式做,而如上所述写出制作相对容易.

这让我们用LR(1)解析器解析C模板表达式(假设我们可以识别模板的名称,这个问题超出了本答案的范围).但它需要将一些其他明确的表达式转换为语法错误.例如,完全毫不含糊

TemplateClassA<x > y> anInstanceOfA;

必须写

TemplateClassA<(x > y)> anInstanceOfA;

为了避免第一个>被解释为关闭模板括号.虽然完全是任意的,但这个规则至少很容易解释(“括号比较和转换,如果你将它们用作模板参数”)并且C程序员似乎没有问题,可能是因为它很少出现. (另一方面,为了避免将>>转换为非法的右移令牌,必须在std :: vector< std :: pair< int,int>>中插入额外的空格被认为是主要的疣.)

幸运的是,我们不再局限于LALR(1)了.如今,bison能够使用GLR算法,该算法可以解析任何明确的无上下文语法.不仅如此,它还附带了一些新的GLR工具来处理(某些)模糊的无上下文语法,这正是我们解决这一特定问题所需要的.

与常规LR解析不同,GLR解析被设计为具有歧义.如果它在输入中的某个点发现可能有两个或更多个解析,则它只是尝试所有这些解析.大多数情况下,一些后来的输入将消除除一个替代之外的所有选项,然后GLR解析器执行所有语义操作并继续解析.

从技术上讲,GLR算法允许解析器返回包含所有可能的解析树的(压缩的)数据结构.但是,野牛实施确实需要解决模糊问题;如果不是,则@L_874_41@错误消息并终止解析.但是,消除歧义的任务很简单,因为它只在必要时才会发生;也就是说,当解析器可以证明存在歧义时.

我们仍然需要一个规则,让我们决定哪些可能的解析是正确的.在这里,我将使用规则“规范表达式必须尽可能长”,这是在@L_197_72@中的讨论中产生的.

为避免混淆,我不打算尝试使用这两种消歧方式.它们不能很好地混合,并且很容易写出表达式语法而不依赖于优先级规则.出于说明目的,我只使用三个运算符,其中一个(&&)比||绑定得更紧,另一个(,)绑定得不那么紧.因为这是一个GLR语法,所以过早减少没有问题所以我使用分组非终端来简化语法. (实际上,解析器在没有额外减少的情况下会稍快一些,但这可能与可读性无关.)

词法分析器是上面的简单词法分析器,它根据它们是否紧跟另一个|来进行分类,并为其他终端添加了一些规则.大多数野牛文件应该看起来很熟悉：

%glr-parser
%debug

%token numbER IDENTIFIER
%token AND "&&"
%token COMBINING_BAR NON_COMBINING_BAR

%%
program: /* empty */ | expression '\n' program;

bar: COMBINING_BAR | NON_COMBINING_BAR;
or:  COMBINING_BAR bar;

expression : alternation                 %dprec 2
           | expression ',' alternation  %dprec 1
           ;

alternation: conjunction                 %dprec 2
           | alternation or conjunction  %dprec 1
           ;

conjunction: term                        %dprec 2
           | conjunction "&&" term       %dprec 1
           ;

term       : IDENTIFIER
           | '(' expression ')'
           | bar expression bar
           ;

除了％glr-parser声明之外,唯一的区别是各种表达式规则中的％dprec声明对.当解析器确定在输入中的同一点可能有多个非终端解析时,％dprec(动态精度)用于决定应该优先选择同一个非终端的几个可能的减少中的哪一个.它选择以最大％dprec减少为首的解析.

请注意,这不是(通常)减少/减少冲突.减少对应于先前某些接受决定接受的不同解析,例如,移位和减少.每次减少都有自己的解析器堆栈,但在减少之后,解析器堆栈将是相同的(这是堆栈所必需的 – 解析 – 要合并).在它自己的解析器堆栈中,每次减少(通常)都是无冲突的.

在这种特殊情况下,我们试图解决与“选择最长规范”规则相对应的歧义.如果存在歧义,表达式将以|开头和结尾并且将有一种可能性,其中起始和结束条匹配,以及其他可能性,其中它们围绕较短的表达.我们将要选择生产条表达栏,它将在单元制作中冒出来;因此,我们为所有单位产品提供更高的合并优先权.

或者,我们可以尝试使用空格来消除歧义,就像要求运算符||一样写作没有内部空间.上述歧义可以通过以下规则解决：

|a|| |b|||c| ⇒ ⌈a‖⌈b⌋‖c⌋
|a| ||b|||c| ⇒ ⌈a⌋‖b‖⌈c⌋

虽然这是明确的,但仍然没有真正的可读性.这种技术无济于事：

||||a| || || |b| || || |c||||

这可能是⌈⌈⌈⌈a⌋‖⌈⌈⌈b⌋⌋⌋‖⌈c⌋⌋⌋⌋或⌈⌈⌈⌈a⌋⌋⌋‖⌈b⌋‖⌈⌈⌈c⌋⌋⌋⌋.这些空间只能消除其他可能的⌈⌈⌈⌈a⌋⌋‖⌈⌈b⌋⌋‖⌈⌈c⌋⌋⌋⌋.

一个不同的空白规则,就像在命运多Fort的堡垒中使用的规则,将坚持：

>左边的norm括号必须紧跟在包含的表达式之前,没有空格@H_616_100@>正确的范数括号必须紧跟在包含的表达式后面,没有空格@H_616_100@>两个没有插入空格的连续条形必须是两个标准括号或一个操作符.

(记住上面的常规语言,最后一条规定消除了两个连续条形是不同类型的标准括号的可能性;它们必须都是打开或两者都要关闭.)

根据该规则,我们最终得到：

||||a| || |||b||| || |c|||| ⇒ ⌈⌈⌈⌈a⌋‖⌈⌈⌈b⌋⌋⌋‖⌈c⌋⌋⌋⌋
||||a|| || ||b|| || ||c|||| ⇒ ⌈⌈⌈⌈a⌋⌋‖⌈⌈b⌋⌋‖⌈⌈c⌋⌋⌋⌋
||||a||| || |b| || |||c|||| ⇒ ⌈⌈⌈⌈a⌋⌋⌋‖⌈b⌋‖⌈⌈⌈c⌋⌋⌋⌋

但是,双杠并没有真正获得任何东西.只需要||总是两个标准括号,从来不是一个标准括号和一个操作符,我们可以回到写作或作为一个单独的栏：

||||a| | |||b||| | |c|||| ⇒ ⌈⌈⌈⌈a⌋‖⌈⌈⌈b⌋⌋⌋‖⌈c⌋⌋⌋⌋
||||a|| | ||b|| | ||c|||| ⇒ ⌈⌈⌈⌈a⌋⌋‖⌈⌈b⌋⌋‖⌈⌈c⌋⌋⌋⌋
||||a||| | |b| | |||c|||| ⇒ ⌈⌈⌈⌈a⌋⌋⌋‖⌈b⌋‖⌈⌈⌈c⌋⌋⌋⌋

最后,让我们为什么难以使用优先级来修复歧义语法.

优先级声明对于简单的表达式语法很有用,我们只需要定义不同运算符的绑定能力.它们也可以以相对可理解的方式使用,以消除“悬挂其他”语法的歧义.它们有时可以用于其他语法问题,但你需要小心.

优先规则用于解决转移/减少冲突.如果生产和前瞻符号具有已定义的优先关系,并且存在涉及生产和前瞻符号的转移/减少冲突 – 也就是说,语法允许减少生产或转移前瞻符号 – 然后,如果前瞻符号具有更高的优先级,则bison将通过移位来解决移位/减少冲突,否则减少(在比较中考虑关联性).由于它使用优先关系来解决冲突,因此野牛不会将冲突标记为警告.此外,如果实际上没有使用优先关系来解决任何冲突,野牛也不会产生任何警告.使用优先级声明后,您已签署了关于许多可能错误的警告权.

优先级声明的非平凡使用可能会对实际解析的语言产生非显而易见的影响.简而言之,优先权不是灵丹妙药;你的脚还需要一些防弹保护.