Преобразование грамматики EBNF в контекстно-свободную грамматику

Question

Мне нужно написать спецификацию JavaCUP, и мне дали грамматику EBNF.Тем не менее, я не знаю, как конвертировать между ними.Я слышал основные идеи, но я не совсем понимаю, что мне нужно изменить, какие будут «терминалы» и т. Д.

Может кто-нибудь объяснить, как конвертировать из одного в другой, или еслигде-нибудь, где я могу прочитать об этом?

Answer 1

грамматики EBNF похожи на обычные BNF, но с некоторыми дополнительными функциями (похожими на операторы регулярных выражений) в качестве синтаксического сахара.Поскольку вы не показывали свою грамматику, я могу только догадываться, в каких частях вам нужно десугарировать для преобразования в обычный BNF, но вот наиболее распространенные (для генератора LALR, такого как JavaCUP):

B*    becomes Bstar, defined as Bstar ::= epsilon; Bstar ::= Bstar B
B+    becomes Bplus, defined as Bplus ::= B; Bplus ::= Bplus B
B?    becomes Bquestion, defined as Bquestion ::= epsilon; Bquestion ::= B
B | C becomes BorC, defined as BorC ::= B; BorC ::= C

epsilon идентификатор здесь, однако ваш генератор синтаксического анализа обозначает пустую строку.