Как переписать эту грамматику для разбора LL (1)? - PullRequest
Новая
       36

Как переписать эту грамматику для разбора LL (1)?

1 голос
/ 16 апреля 2020

Я пытаюсь написать нисходящий анализатор рекурсивного спуска для небольшого языка, и у меня возникают некоторые проблемы с операторами присваивания. Вот грамматика из спецификаций языка: 

<assign_stmt> ::= <lvalue> <l_tail> ":=" <expr> ";"

<l_tail> ::= ":=" <lvalue> <l_tail>
           | ""

<expr> ::= ....  
     #multiple layers betwen <expr> and <lvalue>, like <term>, <factor>, etc.
     #in the end, <expr> can be a <lvalue>
         | <lvalue>

, так что назначения могут выглядеть как 

a := b := 3;
c := d := e := f;

Грамматика не кажется неоднозначной, но она вызывает у меня проблемы, потому что <expr> само по себе может быть <lvalue>. При разборе <l_tail> оба правила производства одинаково действительны, и я не знаю, какое из них выбрать. Я пробовал различные левые факторизации (см. Ниже), но до сих пор я не смог найти грамматику LL(1), которая мне подходит. Возможно ли это здесь? 

<assign_stmt> ::= <lvalue> ":=" <rest> 

<rest> ::= <expr> ";"
         | <lvalue> ":=" <l_tail>

Обратите внимание, что я мог бы go обойти эту проблему, проанализировав <l_tail>, а затем ища токен ";". В зависимости от результата я бы знал, был ли последний <lvalue> на самом деле <expr> или нет (без необходимости возврата). Тем не менее, я учусь здесь, и я хотел бы знать, "правильный" способ преодолеть эту проблему.

...