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

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

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


java parsing ebnf context-free-grammar
person muttley91    schedule 15.03.2011    source источник

Ответы (1)


arrow_upward
4
arrow_downward

Грамматики 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 здесь, однако, ваш генератор парсера обозначает пустую строку.

person Jeremiah Willcock    schedule 15.03.2011
comment
Вам нужно добавить: X:=( A | B ) становится тремя правилами: X:= A и X:= B - person Ira Baxter; 15.03.2011
comment
@Ira: Спасибо за предложение - я его вставил. - person Jeremiah Willcock; 15.03.2011
comment
@Jeremiah: я не думаю, что ты сделал это правильно. Моя трансформация избавляет от оператора РБНФ | сведя его к двум отдельным грамматическим правилам. Ваша переделка определяет | с точки зрения |; как это помогает? - person Ira Baxter; 15.03.2011
comment
@Ира: я забыл об этом; Остальные тоже разделю. - person Jeremiah Willcock; 15.03.2011
comment
@Ira: Посмотрим, стало ли лучше. - person Jeremiah Willcock; 15.03.2011
comment
@ Джеремайя: Лучше. Вам не нужно было разделять другие; просто согласитесь применять их все до тех пор, пока ни один из них больше не будет применяться. Но это не больно. - person Ira Baxter; 15.03.2011
comment
Кроме того, {n,m}, вероятно, можно преобразовать следующим образом: B{3,5} становится B_x3to5, определяемым как B_x3to5 ::= B_x3 | B_x4 | B_x5, B_x5 ::= B B_x4, B_x4 ::= B B_x3, ..., B_x1 ::= B B_x0, B_x0 ::= epsilon. Кроме того, если вы добавите остальную часть слева или справа от этих переводов, будет определяться, являются ли вещи левоассоциативными или правоассоциативными. - person ninjagecko; 02.05.2012