算术表达式的 YACC 语法，没有括号
YACC grammar for arithmetic expressions, with no surrounding parentheses
我想写YACC中算术表达式的规则；其中定义了以下操作：
+ - * / ()
但是，我不希望语句包含括号。也就是说，a+(b*c) 应该有一个匹配规则，但 (a+(b*c)) 不应该。
我怎样才能做到这一点？
动机：
在我的语法中，我定义了一个这样的集合：(1,2,3,4) 并且我希望 (5) 被视为一个 1 元素集合。歧义导致 reduce/reduce 冲突。
这是一个非常简单的算术语法。它处理您提到的四个运算符和赋值语句：
stmt: ID '=' expr ';'
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
如果我们假设集合文字只能作为赋值语句中的值出现，而不是算术运算符的操作数，那么我们将为“表达式或集合文字”添加语法：
value: expr | set
并修改赋值语句的语法以使用：
stmt: ID '=' value ';'
但这会导致您提到的 reduce/reduce 冲突，因为 (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 的定义方式，我们仍将以 shift/reduce 冲突告终。遇到赋值语句的开头：
a = ( 5 )
完成 5，因此 ) 是先行标记，解析器不知道 (5) 是否是 set（在这种情况下下一个标记将是 ;) 或 paren（仅当下一个标记是操作数时才有效）。这不是一个歧义——解析可以用 LR(2) 解析 table 简单地解决——但是没有很多工具可以生成 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
value 的两个产生式中的 %dprec 声明告诉解析器如果两个产生式都可能，则更喜欢 value: set。 （它们在只能产生一种产品的情况下无效。）
3。修复语言
虽然可能 解析指定的语言，但我们可能不会帮任何人任何忙。甚至可能会有人抱怨说，当他们改变时感到惊讶
a = ( some complicated expression ) * 2
至
a = ( some complicated expression )
突然 a 变成了集合而不是标量。
通常情况下，语法不明显的语言也很难被人类解析。 （例如，参见 C++ 的“最令人烦恼的解析”）。
Python，它使用 ( expression list ) 创建元组文字，采用了一种非常简单的方法：( expression ) 始终是一个表达式，因此元组需要为空或包含在至少一个逗号。为了使后者成为可能，Python 允许用逗号结尾的元组文字；尾随逗号是可选的，除非元组包含单个元素。所以 (5) 是一个表达式，而 ()、(5,)、(5,6) 和 (5,6,) 都是元组（最后两个在语义上相同）。
Python列表写在方括号之间；在这里，再次允许使用尾随逗号，但从不需要，因为 [5] 没有歧义。所以 []、[5]、[5,]、[5,6] 和 [5,6,] 都是列表。
我想写YACC中算术表达式的规则；其中定义了以下操作：
+ - * / ()
但是，我不希望语句包含括号。也就是说，a+(b*c) 应该有一个匹配规则，但 (a+(b*c)) 不应该。
我怎样才能做到这一点？
动机：
在我的语法中，我定义了一个这样的集合：(1,2,3,4) 并且我希望 (5) 被视为一个 1 元素集合。歧义导致 reduce/reduce 冲突。
这是一个非常简单的算术语法。它处理您提到的四个运算符和赋值语句：
stmt: ID '=' expr ';'
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
如果我们假设集合文字只能作为赋值语句中的值出现，而不是算术运算符的操作数，那么我们将为“表达式或集合文字”添加语法：
value: expr | set
并修改赋值语句的语法以使用：
stmt: ID '=' value ';'
但这会导致您提到的 reduce/reduce 冲突，因为 (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 的定义方式，我们仍将以 shift/reduce 冲突告终。遇到赋值语句的开头：
a = ( 5 )
完成 5，因此 ) 是先行标记，解析器不知道 (5) 是否是 set（在这种情况下下一个标记将是 ;) 或 paren（仅当下一个标记是操作数时才有效）。这不是一个歧义——解析可以用 LR(2) 解析 table 简单地解决——但是没有很多工具可以生成 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
value 的两个产生式中的 %dprec 声明告诉解析器如果两个产生式都可能，则更喜欢 value: set。 （它们在只能产生一种产品的情况下无效。）
3。修复语言
虽然可能 解析指定的语言，但我们可能不会帮任何人任何忙。甚至可能会有人抱怨说，当他们改变时感到惊讶
a = ( some complicated expression ) * 2
至
a = ( some complicated expression )
突然 a 变成了集合而不是标量。
通常情况下，语法不明显的语言也很难被人类解析。 （例如，参见 C++ 的“最令人烦恼的解析”）。
Python，它使用 ( expression list ) 创建元组文字，采用了一种非常简单的方法：( expression ) 始终是一个表达式，因此元组需要为空或包含在至少一个逗号。为了使后者成为可能，Python 允许用逗号结尾的元组文字；尾随逗号是可选的，除非元组包含单个元素。所以 (5) 是一个表达式，而 ()、(5,)、(5,6) 和 (5,6,) 都是元组（最后两个在语义上相同）。
Python列表写在方括号之间；在这里，再次允许使用尾随逗号，但从不需要，因为 [5] 没有歧义。所以 []、[5]、[5,]、[5,6] 和 [5,6,] 都是列表。