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

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

ruby treetop
person Ginty    schedule 07.11.2017    source источник

Ответы (1)


arrow_upward
1
arrow_downward

Кажется, это имеет смысл и делает то же самое. Одна вещь, которая может помочь в понимании, - это переписать код, как показано ниже. Одна вещь, которую следует помнить о грамматиках 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
person Josh Voigts    schedule 08.02.2018