Анализ переносимости смены-сдвига

Question

Я использую инструмент JavaCUP, чтобы создать парсер для моего языка. Я пытаюсь написать грамматику, которая соответствует вложенным и нескольким операторам if_else.

входного файл

// matches 
if() 
    if() 

    else 

    if() 

    else 
else 

// no match -> modifying grammar leads to shift/reduce conflict 
if() 

else 

Грамматик

expr ::= if_then_else_statement; 

if_then_else_statement ::= IF LPAREN RPAREN if_then_else_statement ELSE if_then_else_statement 
         | ; 

Эта грамматика соответствует вложенному if_else заявления. Однако он распознает только первый вложенный оператор if_else моего входного файла.

Я изменил мою грамматику, чтобы соответствовать несколько инструкций, как это:

expr ::= expr if_then_else_statement; 
     | ; 

if_then_else_statement ::= IF LPAREN RPAREN if_then_else_statement ELSE if_then_else_statement 
         | ; 

В результате произошел сдвиг/свертка конфликт, вызванный пустого правила (я думаю). Как я могу изменить его для поддержки как вложенных, так и множественных операторов if_else без использования приоритета?

Answer 1

Обычное решение было бы что-то вроде этого:

expr_list ::= | expr_list expr ; 
expr ::= if_then_else_statement ; 
if_then_else_statement ::= IF LPAREN RPAREN expr ELSE expr ; 

Это не позволяет пустой else положения (или пустые then положения), потому что пустой другой пункт неоднозначна: нет никакого способа узнать, является ли s2 в if() s1 else s2 - это предложение else или оператор, который следует за инструкцией complete if с предложением else else.

Чтобы устранить эту неоднозначность, необходимо выписки терминатор (например, точка с запятой) или if выписки терминатор (fi и end общие выборы) или что-то еще.