ruby - 如何消除 Verilog 语法示例中的左递归

Question

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

我已经阅读了一些这方面的资料，这个答案很好地总结了消除左递归的通用方法:Left recursion elimination

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

对于这个包含左递归的原始规则(注释是它在语言规范中的写法):

  # 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 

Answer 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