Как устранить левую рекурсию в примере грамматики Verilog

Question

Я использую 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 

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