Преобразование EBNF в BNF для парсера LALR

Question

Я знаю, что есть несколько постов с похожим названием.Большинство ссылок на мертвый сайт - и у меня есть более конкретный вопрос в любом случае.

Я пытаюсь преобразовать EBNF в спецификации XPath в прямой BNF, чтобы я мог легко создать файл грамматики, совместимый с Bison.

Прошло много времени с тех пор, как я это сделал, и я не помню, к какой стороне производства относится рекурсия.Я думал, что это был левый - но мой "прямой" перевод дает мне синтаксические ошибки с выражениями XPath, написанными простым языком, когда они запускаются через сгенерированный Bison синтаксический анализатор.Взвесьте - так что я не гонюсь за призраком:

В приведенном ниже правиле Expr:

Expr::=     
    ExprSingle ("," ExprSingle)*

Это правильный перевод?(помещая рекурсию слева):

Expr::= 
    Expr "," ExprSingle
    | ExprSingle

Answer 1

Это нормально ....

Вы можете поместить рекурсию справа, и она должна работать, но вы заставите парсер "делать больше работы", так как он должен отслеживать позвоночник рекурсиии для этого нужно использовать больше стеков.