Левый факторинг и удаление левой рекурсии JavaCC

Question

У меня есть грамматика, которую я должен использовать JJTree и JavaCC для создания таблицы символов и AST. Хотя я полностью понимаю разделы моего задания для создания таблицы и дерева, грамматика, которую я дал, неоднозначна, содержит левую рекурсию и косвенную левую рекурсию. Его также нужно учитывать. Я проехал по всему Интернету, чтобы попробовать найти методы, которые будут работать для меня.

Например:

A :: = Аа | β

может быть изменен на:

A :: = 'βA
A' :: = αA» | ε

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

void statement() #STM : {} 
{ 
    identifier() <ASSIGNMENT> expression() 
    | identifier() <ASSIGNMENT> <STRING> 
    | <EXCLAMATION> expression() 
    | <QUESTION> identifier() 
    | identifier() <LBR> arg_list() <RBR> 
    | <BEGIN> (statement() <SEMIC>)+ <END> 
    | matched() 
    | unmatched() 
    | <WHILE> <LBR> condition() <RBR> <DO> statement() 
    | {} 
} 

void matched() #void : {} 
{ 
    <IF> condition() <THEN> matched() <ELSE> matched() 
} 

void unmatched() #void : {} 
{ 
    <IF> condition() <THEN> statement() 
    | <IF> condition() <THEN> matched() <ELSE> unmatched() 
} 

void expression() #EXPR : {} 
{ 
    fragment() ((<PLUS>|<MINUS>|<MULT>|<DIV>) fragment())* 
} 

void fragment() #FRAG : {} 
{ 
    (identifier() | <NUM> | (<PLUS>|<MINUS>) fragment() | expression()) 
} 

Answer 1

У вас здесь есть ряд проблем. Большинство из них рассматриваются в вопросе 4.6 часто задаваемых вопросов JavaCC. http://www.engr.mun.ca/~theo/JavaCC-FAQ/

Во-первых, есть много левого факторинга. Левый факторинг пытается переместить выбор позже в синтаксическом анализе. Например. если у вас есть

void statement() #STM : {} 
{ 
    identifier() <ASSIGNMENT> expression() 
| identifier() <ASSIGNMENT> <STRING> 
| identifier() <LBR> arg_list() <RBR> 
} 

и анализатор ожидает заявление и следующий элемент ввода является идентификатором, то синтаксический анализатор не может сделать выбор. Фактор из общих частей на левые, чтобы получить

void statement() #STM : {} 
{ 
    identifier() 
     ( <ASSIGNMENT> expression() 
     | <ASSIGNMENT> <STRING> 
     | <LBR> arg_list() <RBR> 
    ) 
} 

и затем

void statement() #STM : {} 
{ 
    identifier() 
     ( <ASSIGNMENT> (expression() | <STRING>) 
     | <LBR> arg_list() <RBR> 
    ) 
} 

Во-вторых, нетерминал «соответствует» бесполезно, так как нет нерекурсивного случая. Я подозреваю, что вы пытаетесь справиться с этой проблемой. Это не лучший способ справиться с этой проблемой. См. FAQ по JavaCC для разумного способа борьбы с ним.

В-третьих, существует взаимная левая рекурсия между нетерминалами «фрагмент» и «выражение». Я не уверен, что вы пытаетесь сделать здесь. Существует несколько способов обработки выражений, которые не используют левую рекурсию. См. http://www.engr.mun.ca/~theo/Misc/exp_parsing.htm для получения дополнительной информации. Мое руководство по использованию JavaCC также может помочь. http://www.engr.mun.ca/~theo/JavaCC-Tutorial/

И наконец слово совета. Начните с грамматики для небольшого подмножества вашего языка, а затем добавьте конструкции по одному или два за раз. Таким образом, вам не придется иметь дело с множеством проблем сразу.