解析器更喜欢转换而不是乘法

Question

我一直在开发一种爱好语言，在过去的几天里，我一直在努力理解我遇到的一个问题。我的语言的精简版的某些方面是：

指针类型
结构类型（类似于类型，但它们被解析为标识符）
键入转换表达式
简单的数学表达式（+、-、*、/、()）
变量的评估

为了重现此问题，语法已被精简，因此有些事情没有意义（例如，无法分配给变量）。这是语法：

program =
   expression.e             {: return new Program(e); :};

literal =
    INTEGER_LITERAL.l       {: return new IntegerLiteral(l, false); :};

type =
    normal_type
  | reference_type;

normal_type =
    INT                     {: return new TypeAccess("int"); :};

reference_type =
    type.t MULT             {: return new RefTypeAccess("ref", t); :}
  | id_use.id MULT          {: return new RefTypeAccess("ref", new StructTypeAccess(id.getID())); :};

id_use =
    IDENTIFIER.id           {: return new IdUse(id); :};

primary =
    literal
  | LPAREN.n expression.e RPAREN {: return new ParExpr(e); :};

postfix_expression =
    primary
  | id_use;

unary_expression =
    postfix_expression
  | MULT cast_expression.e                    {: return new DereferenceExpr(e); :};

cast_expression =
    unary_expression
  | LPAREN.n type.t RPAREN cast_expression.e  {: return new CastExpr(t, e); :};

multiplicative_expression =
    cast_expression
  | multiplicative_expression.e1 MULT cast_expression.e2  {: return new MulExpr(e1, e2); :}
  | multiplicative_expression.e1 DIV cast_expression.e2   {: return new DivExpr(e1, e2); :};

additive_expression =
    multiplicative_expression
  | additive_expression.e1 PLUS multiplicative_expression.e2   {: return new AddExpr(e1, e2); :}
  | additive_expression.e1 MINUS multiplicative_expression.e2  {: return new SubExpr(e1, e2); :};

expression =  additive_expression;

语法是为 Beaver 解析器生成器编写的，但它与 BNF 非常相似。问题是当我想（分别）解析以下内容时：

a * 5   //OK
5 * a   //OK
(a + 1) //OK
(a + 1) //OK
(a * 5) //Syntax error: Unexpected token 5

我已经设法将范围缩小到强制转换表达式。显然，当我打算在 a 和 5 之间写一个乘法表达式时，解析器认为我正在写一个类型转换表达式 a* （指向名为 [=12= 的结构的指针） ]).但是在这一点上我被卡住了。为什么？查看 C's grammar 规范（与我的非常相似），没有明显不同，但该表达式在 C 中解析得很好。

我仍然是个语法菜鸟，但这不应该引起 multiplicative_expression 和 cast_expression 之间的某种语法冲突吗？

Answer 1

该语法存在移位归约冲突。我不确定为什么您的解析器生成器不显示它。

我将语法转换为 bison（在顶层进行了小的修改以使其更易于在测试中使用）。作为参考，这是从我的输入文件（没有优先声明）中提取的野牛：

Grammar
    1 program: %empty
    2        | program expression '\n'
    3        | program error '\n'

    4 literal: INTEGER_LITERAL

    5 type: normal_type
    6     | reference_type

    7 normal_type: "int"

    8 reference_type: type '*'
    9               | id_use '*'

   10 id_use: IDENTIFIER

   11 primary: literal
   12        | '(' expression ')'

   13 postfix_expression: primary
   14                   | id_use

   15 unary_expression: postfix_expression
   16                 | '*' cast_expression

   17 cast_expression: unary_expression
   18                | '(' type ')' cast_expression

   19 multiplicative_expression: cast_expression
   20                          | multiplicative_expression '*' cast_expression
   21                          | multiplicative_expression '/' cast_expression

   22 additive_expression: multiplicative_expression
   23                    | additive_expression '+' multiplicative_expression
   24                    | additive_expression '-' multiplicative_expression

   25 expression: additive_expression

（见注1）

这产生了状态 23 中存在 shift/reduce 冲突的警告：

State 23

    9 reference_type: id_use . '*'
   14 postfix_expression: id_use .

    '*'  shift, and go to state 32

    '*'       [reduce using rule 14 (postfix_expression)]
    $default  reduce using rule 14 (postfix_expression)

解析器通过状态 7 到达状态 23：（注意：为了清晰起见，我删除了大部分转到操作 space。）

State 7

   12 primary: '(' . expression ')'
   18 cast_expression: '(' . type ')' cast_expression

    INTEGER_LITERAL  shift, and go to state 4
    IDENTIFIER       shift, and go to state 5
    "int"            shift, and go to state 19
    '*'              shift, and go to state 6
    '('              shift, and go to state 7

    id_use                     go to state 23
    ...

实际上，发生的事情是解析器遇到括号，并且语法允许它作为带括号的子表达式或强制转换表达式的开头。这很酷;解析器可以接受这两种可能性，这就是状态 7 中显示的内容。因此它移动了左括号。此时，除了标识符之外，几乎所有输入都可以解决括号的含义问题。标识符可能是一个类型名，或者它可能命名一个变量。因此解析器继续探索这两种可能性，将其引导至状态 23。

但是如果标识符后面的符号是 *，就会出现问题，因为如果括号围绕子表达式，那将是一个乘法运算符，如果括号围绕着一个类型表达式。由于解析器直到右括号移动后很久才知道括号采用什么句法形式（事实上，我们稍后会看到，甚至可能不知道），因此它需要继续保持两种选择。但它不能，因为语法现在坚持在一种情况下将标识符缩减为 postfix_expression，或者将其保留为标识符以便在另一种情况下将其集成到 reference_type 中。由于必须立即或永远不进行归约，因此解析器无法处理这种不确定性。因此冲突。

海狸和野牛一样，会不自觉地选择解决这个有利于转变的冲突。这将解析器提交给解析器，其中括号是强制转换表达式的开头，* 是后缀指针类型构造函数。在 (i*5) 的情况下，情况并非如此，并且会导致语法错误。（多一个前瞻标记就足以解决这个冲突，至少在这个简化的语法中是这样。但在完整的语法中可能并非如此。）

如您所说，处理类似语法的 C 解析器在这里没有问题。但那是因为 C 解析器已经不得不处理语法中的实际歧义。在 C 语言中，表达式 (foo)*(bar) 可以是两个变量的乘积，也可以转换为取消引用指针变量 bar 的类型 foo。语法没有提供任何机制来解决这种歧义，但如果知道 foo 是否是类型名，则可以轻松解决。因为 C 坚持声明先于使用，所以这个事实必须是可知的，尽管它需要一个稍微丑陋的 hack 来确保词法扫描器可以访问由解析器维护的符号 table。（由于类型别名也受范围规则的约束，词法分析器需要能够进行全名解析才能做出此决定。这增加了丑陋性。但它仍然相当简单。）

您的语法似乎没有出现上述歧义，因为您不允许转换为类型，只允许转换为指向类型的指针。但这并不能保护您免受与 multiplication/pointer-construction 运算符 * 的 shift-reduce 冲突。所以你仍然需要解决这个问题，你可以用与 C 编译器相同的方式来解决这个问题。

当然，另一种解决方案是使用不同的语法进行转换。您可能会发现 C++ 语法笨拙 (reinterpret_cast<int*>(x))，但对于阅读代码的人来说它是明确的并且可以说更清晰。它还有助于阻止强制转换的使用，您可能会或可能不会觉得这是一件好事。一个不那么冗长的替代方法是 as 运算符：x as int*，它在多种脚本语言中使用。（抱歉，我记不起引用了。）

备注

其实不需要两个独立的非终结符，cast_expression和unary_expression；您可以轻松地将两者结合起来而不影响语法：

unary_expression: postfix_expression
                | '(' type ')' unary_expression
                | '*' unary_expression

multiplicative_expression: unary_expression
                         | multiplicative_expression '*' unary_expression
                         | multiplicative_expression '/' unary_expression

这并没有解决或加剧冲突问题，但确实使语法稍微简单了一些。

解析器更喜欢转换而不是乘法

Parser prefers casting over multiplication

parsing

context-free-grammar

备注