3

我正在使用 Treetop 为 Verilog 语言创建语法，并且遇到了一些情况，其中语言规范涉及不转换为 Treetop 的左递归构造。

我已经对此进行了一些阅读，这个答案很好地总结了消除左递归的通用方法：左递归消除

但是，我无法理解这实际上是如何工作的，如果有更多知识的人可以确认我的方法是否正确，我将不胜感激......

对于这个包含左递归的原始规则（注释是它在语言规范中的编写方式）：

  # constant_expression ::=
  #   constant_primary
  #   | unary_operator { attribute_instance } constant_primary
  #   | constant_expression binary_operator { attribute_instance } constant_expression
  #   | constant_expression ? { attribute_instance } constant_expression : constant_expression
  rule constant_expression
    constant_primary /
    (unary_operator (s attribute_instance)* s constant_primary) /
    (constant_expression s binary_operator (s attribute_instance)* s constant_expression) /
    (constant_expression s "?" (s attribute_instance)* s constant_expression s ":" s constant_expression)
  end

以下内容是否真的等同于删除了左递归？

  rule constant_expression
    (constant_primary constant_expression_tail?) /
    (unary_operator (s attribute_instance)* s constant_primary constant_expression_tail?)
  end

  rule constant_expression_tail
    (s binary_operator (s attribute_instance)* s constant_expression constant_expression_tail?) /
    (s "?" (s attribute_instance)* s constant_expression s ":" s constant_expression constant_expression_tail?)
  end
4

1 回答 1

1

这似乎是有道理的，并且做同样的事情。可能有助于理解的一件事是像下面的代码一样重写。关于 PEG 语法要记住的一件事是，如果规则无法匹配，它将尝试匹配下一个交替。

rule constant_expression
   (constant_primary / (unary_operator (s attribute_instance)* s constant_primary)) constant_expression_tail?
end

rule constant_expression_tail
   ((s binary_operator (s attribute_instance)* s) /
    (s "?" (s attribute_instance)* s constant_expression s ":" s)) constant_expression constant_expression_tail?
end
于 2018-02-08T19:51:00.503 回答