YACC语法用于算术表达式，不带括号

Question

我想在YACC中编写算术表达式的规则；其中定义了以下操作：

+   -   *   /   ()

但是，我不希望该语句带有括号。也就是说，a+(b*c)应该有一个匹配的规则，但是(a+(b*c))不应该。

我该如何实现？

---

动机：

在我的语法中，我定义了一个这样的集合：(1,2,3,4)并且我想(5)被视为1元素集合。模糊性导致减少/减少冲突。

Answer 1

这是一个非常小的算术语法。它处理您提到的四个运算符和赋值语句：

stmt:      ID '=' expr ';'
expr:      term | expr '-' term | expr '+' term
term:      factor | term '*' factor | term '/' factor
factor:    ID | NUMBER | '(' expr ')' | '-' factor

定义“ set”文字很容易：

set:       '(' ')' | '(' expr_list ')'
expr_list: expr | expr_list ',' expr

如果我们假设集合文字只能作为赋值语句中的值出现，而不能作为算术运算符的操作数出现，那么我们将为“表达式或集合文字”添加语法：

value:     expr | set

并修改赋值语句的语法以使用该语法：

stmt:      ID '=' value ';'

但是，这导致你提到的减少/减少冲突，因为(5)可能是expr，通过扩展expr→交通term→交通factor→交通'(' expr ')'。

这是解决这种歧义的三种解决方案：

1.明确消除歧义

消除歧义是乏味的，但并不是特别困难；我们只是在每个优先级上定义了两种子表达式，一种可能用括号括起来，而另一种绝对不用括号包围。我们从括号的表达式的简写开始：

paren:     '(' expr ')'

然后为每个子表达式类型X添加一个生产pp_X：

pp_term:   term | paren

并通过允许带括号的子表达式作为操作数来修改现有的生产形式：

term:      factor | pp_term '*' pp_factor | pp_term '/' pp_factor

不幸的是，由于expr_list定义的方式，我们最终仍然会发生转移/减少冲突。面对赋值语句的开头：

a = ( 5 )

完成了5，所以这)是先行标记，解析器不知道(5)a是set（在这种情况下下一个标记将是a ;）还是a paren（仅在下一个标记是操作数时才有效）。这并不是模棱两可的-可以使用LR（2）解析表轻松解析该解析-但是没有多少工具可以生成LR（2）解析器。因此，我们坚持认为expr_list必须具有两个表达式，并添加paren到产生式中来回避问题set：

set:       '(' ')' | paren | '(' expr_list ')'
expr_list: expr ',' expr | expr_list ',' expr

现在，解析器无需在赋值语句之间expr_list和之间进行选择expr；它只是简化(5)为paren并等待下一个标记澄清解析。

最终结果是：

stmt:      ID '=' value ';'
value:     expr | set

set:       '(' ')' | paren | '(' expr_list ')'
expr_list: expr ',' expr | expr_list ',' expr

paren:     '(' expr ')'
pp_expr:   expr | paren
expr:      term | pp_expr '-' pp_term | pp_expr '+' pp_term
pp_term:   term | paren
term:      factor | pp_term '*' pp_factor | pp_term '/' pp_factor
pp_factor: factor | paren
factor:    ID | NUMBER | '-' pp_factor

没有冲突。

2.使用GLR解析器

尽管有可能明确消除歧义，但所得到的语法是肿的，而且不是很清楚，这是不幸的。

Bison可以生成GLR解析器，这将使语法更加简单。实际上，原始语法几乎无需修改即可运行。我们只需要使用Bison %dprec动态优先级声明来指示如何消除歧义：

%glr-parser
%%
stmt:      ID '=' value ';'
value:     expr    %dprec 1
     |     set     %dprec 2
expr:      term | expr '-' term | expr '+' term
term:      factor | term '*' factor | term '/' factor
factor:    ID | NUMBER | '(' expr ')' | '-' factor
set:       '(' ')' | '(' expr_list ')'
expr_list: expr | expr_list ',' expr

如果两个生产均可行，则两个生产中的%dprec声明用于value告诉解析器首选value: set。（它们在只能进行一次生产的情况下不起作用。）

3.修正语言

尽管可以按照指定的方式解析语言，但我们可能没有对任何人做任何帮助。甚至会有人因改变而感到惊讶

a = ( some complicated expression ) * 2

至

a = ( some complicated expression )

突然a变成一个集合，而不是一个标量。

通常情况下，语法不明显的语言也很难被人类解析。（例如，请参见C ++的“最令人烦恼的解析”）。

( expression list )用于创建元组文字的Python 采用一种非常简单的方法：( expression )始终是一个表达式，因此元组必须为空或至少包含一个逗号。为了使后者成为可能，Python允许用尾随逗号编写元组文字。除非元组包含单个元素，否则尾随逗号是可选的。所以(5)是一个表达式，而()，(5,)，(5,6)和(5,6,)是的所有元组（最后两个具有相同的语义）。

Python列表写在方括号之间；在这里，再次允许使用逗号，但由于[5]模棱两可，因此不再需要逗号。所以[]，[5]，[5,]，[5,6]和[5,6,]都列出。