Cle*_*rer 3 c yacc bison flex-lexer
我执行的语言,有两家运营商之间的冲突| * |和* || *-第一个是"规范"操作,其中两个|-characters环绕的表达,另一个是运营商还是,其中两个表达式三明治2个|-characters.
到目前为止,我能够解析类似的表达式||| a || b | | |- 即单个或三个级别的规范或(规范中任意数量的规范和任何系列的或运算符); 这只适用于表达式的尾部包含|彼此之间有空格的字符 - 即||| a || b | | |可以工作,但||| a || b |||会导致语法错误.我希望能够将最后一个版本解析为a or b内部的三个规范.
我的实现的简约版本(即相关部分):
野牛/ Yacc部分:
%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
Flex部分:
%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 '|'; }
我使用NOR和NOR2状态来确保只有在| -characters之间没有任何内容时才接受OR运算符.
首先,您的语言本质上是模棱两可的.你可以通过各种方式解决歧义 - 下面有一些想法 - 但这种含糊不清通常不是一个好主意,因为它们不仅使语言难以解析机器; 它们使人类难以解析.这个世界充满了计算机语言,其中包含古怪的解析和常见问题解答,解释了为什么你所写的内容并没有达到你的意思.
(在下面,我将使用⌈…⌋而不是|…|for norm,而x‖y不是x||yfor or,以显示表达式如何解析.)
这是一个简单的歧义:
|a|||b|||c|
它可能是:
?a??b??c?
要么
?a??b??c?
所以我们需要能够选择这两种解释中的一种或另一种.
如果我们使用的语法在后,我们需要能够减少每个|这实在是一个?以非终端rnorm,每一个|这是一个?到lnorm.通过LR(1)语法逻辑[注1],我们需要根据紧随其后的令牌输入做出此决定|.
很容易看出第一个|永远是a ?,但这|||是一个挑战.如果我们要选择?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* )*
where TERM是一个名称或常量文字,OPEN是某种形式的开括号,是某种形式CLOSE的紧密括号.
如果有前缀和/或后缀运算符,那么我们就可以改变OPEN到(OPEN | PREFIX)和CLOSE到(CLOSE | POSTFIX).它不会改变我要说的任何内容.
并非所有与正则表达式匹配的字符串都在表达式语言中,但表达式语言中的每个字符串都必须与正则表达式匹配.要将其限制为正确的表达式字符串,我们还需要要求括号正确匹配,而不能用常规语言表示.但这也不重要.
可以将正则表达式重新排列为:
OPEN* TERM ( CLOSE* OPERATOR OPEN* TERM )* CLOSE*
这清楚地表明在第TERM一个之前出现的任何东西都是OPEN; 在最后一个术语之后出现的任何东西都是a CLOSE,而在两个TERMs 之间的任何字符串都包含一个OPERATOR,可能在OPENs 之前,后面跟着CLOSEs.
在您的语言中,bars(|)可以是OPEN或CLOSE,并且其中两个可以是OPERATOR.要求操作员是两个棒是否有任何优势？没有; 加倍这个标准决不会有助于消除解析的歧义.两个TERMs 之间的一串连续条必须包含一个运算符; 拼写操作符||仅表示连续栏的字符串必须长一个栏.
现在,我们来看一下问题中的扫描仪规则.
第一个观察是他们没有真正起作用.或者这可能是第二次观察,因为第一个观察结果是他们看起来太复杂了他们想要完成的事情.状态之间的交替NOR和NOR2意味着序列|s的进入lexed的交替LOR和ROR令牌.例如,表达式:|1||||2|将被定义为|1LORRORLORROR2|.但是这不会允许正确的parse(?1???2?),因为中间的两个|字符被标记为RORLOR,因此不会与表达式生成匹配:
expression LOR ROR expression
当然,这是可以解决的.我们只需要向解析器添加更多制作.但是,yuk!
但目标只是要求两个条形图只有在没有空格分隔的情况下才能被识别为"或"运算符.没有必要这么努力工作.以下就足够了:
[0-9]+ { return NUMBER; }
[|]/[|] { return COMBINING_BAR; }
[|] { return NON_COMBINING_BAR; }
(如果第一个规则具有第二个规则,则第二个规则不适用,因为第一个规则优先,因此具有优先级,但主要是因为flex实际上考虑了规则的长度,包括在确定哪个是最长匹配时的尾随上下文.)
词法的这种风格做的工作,它有可用于在分析下的类似问题++等语言不幸借用其不幸的超载<和>,这可能是模板支架,比较操作,或移位运算.没有一些消除歧义的规则,在C++表达式中开始
A<B<x>>…
它在理论上可能>>是任何一个
在C++ 11之前,它始终是一个右移运算符.从C++ 11开始,它将是两个紧密的模板括号,而>>in 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 what 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算法允许解析器返回包含所有可能的解析树的(压缩的)数据结构.但是,野牛实施确实需要解决模糊问题; 如果不是,则生成错误消息并终止解析.但是,消除歧义的任务很简单,因为它只在必要时才会发生; 也就是说,当解析器可以证明存在歧义时.
我们仍然需要一个规则,让我们决定哪些可能的解析是正确的.在这里,我将使用规则" norm表达必须尽可能长",这是在评论中的讨论中产生的.
为避免混淆,我不打算尝试使用这两种消歧方式.它们不能很好地混合,并且很容易写出表达式语法而不依赖于优先规则.出于说明目的,我只使用三个运算符,其中一个(&&)绑定比绑定更紧密||,另一个(,)绑定得更紧密.因为这是一个GLR语法,所以过早减少没有问题所以我使用分组非终端来简化语法.(实际上,解析器在没有额外减少的情况下会稍快一些,但这可能与可读性无关.)
词法分析器是上面的简单词法分析器,它|根据是否立即跟随另一个词来对s 进行分类|,并为其他终端添加一些规则.大多数野牛文件应该看起来很熟悉:
%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开始和结束,|并且将有一种可能性,其中起始和结束条匹配,以及其他可能性,其中它们围绕较短的表达式.我们将要选择生产bar expression bar,这将通过单位产品冒出来; 因此,我们为所有单位产品提供更高的合并优先权.
或者,我们可以尝试使用空格来消除歧义,就像要求在||没有内部空间的情况下编写运算符一样.上述歧义可以通过以下规则解决:
|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括号必须紧跟在包含的表达式之前,没有空格
正确的范数括号必须紧跟在包含的表达式后面,没有空格
两个没有插入空格的连续条形必须是两个标准括号或一个操作符.
(记住上面的常规语言,最后一条规定消除了两个连续条形是不同类型的标准括号的可能性;它们必须都是打开或两者都要关闭.)
根据该规则,我们最终得到:
||||a| || |||b||| || |c|||| ? ????a?????b?????c????
||||a|| || ||b|| || ||c|||| ? ????a?????b?????c????
||||a||| || |b| || |||c|||| ? ????a?????b?????c????
但是,如上所述,双杠并没有真正获得任何东西.简单地要求它||总是两个标准括号,从来不是标准括号和操作符,我们可以回到写作or单个条:
||||a| | |||b||| | |c|||| ? ????a?????b?????c????
||||a|| | ||b|| | ||c|||| ? ????a?????b?????c????
||||a||| | |b| | |||c|||| ? ????a?????b?????c????
最后,让我们为什么难以使用优先级来修复歧义语法.
优先级声明对于简单的表达式语法很有用,我们只需要定义不同运算符的绑定能力.它们也可以以相对可理解的方式使用,以消除"悬挂其他"语法的歧义.它们有时可以用于其他语法问题,但你需要小心.
优先规则用于解决转移/减少冲突.如果生产和前瞻符号具有已定义的优先关系,并且存在涉及生产和前瞻符号的转移/减少冲突 - 也就是说,语法允许减少生产或转移前瞻符号 - 然后,如果前瞻符号具有更高的优先级,则bison将通过移位来解决移位/减少冲突,否则减少(在比较中考虑关联性).由于它使用优先关系来解决冲突,因此野牛不会将冲突标记为警告.此外,如果实际上没有使用优先关系来解决任何冲突,野牛也不会产生任何警告.使用优先级声明后,您已签署了关于许多可能错误的警告权.
优先级声明的非平凡使用可能会对实际解析的语言产生非显而易见的影响.简而言之,优先权不是灵丹妙药; 你的脚还需要一些防弹保护.