Определение соответствия грамматики требованиям LL (1) - PullRequest
Новая
       6

Определение соответствия грамматики требованиям LL (1)

0 голосов
/ 31 октября 2018

У меня есть BNF для парсера рекурсивного спуска. Одним из шагов к решению этой проблемы является проверка того, что грамматика является LL (1), но я продолжаю проверять, что это не так.

BNF, о котором идет речь, или, точнее, точная область, в которой у меня возникла проблема: 

<S>           ->      start <vars> <block>
<block>       ->      begin <vars> <stats> end
<vars>        ->      e | id = number <vars>
<stats>       ->      <if> | <block> | <loop> | <assign>

Это еще не все, но я считаю, что это единственные произведения, имеющие отношение к этому вопросу.

Мой подход к решению этой проблемы - вычислить ПЕРВЫЕ из правых частей тех производств, у которых есть выбор. Если выбора нет, я пропускаю, так как знаю, что они уже к = 0. 

FIRST(e | id = number <vars>) = {e, id} // Since it produces the empty set, I must also compute follow.

FOLLOW( e | id = number <vars> ) = FOLLOW(<vars>)

Нетерминальные «vars» появляются в 2-х произведениях: и, за которыми следуют два нетерминала: «блок» и «статистика» 

FIRST(<block>) = {begin}
FIRST(<stats>) = { ... begin ... } // contains all terminals

Теперь моя проблема. При вычислении FOLLOW () я нашел два начальных токена, что заставляет меня сказать, что эта грамматика не является LL (1). Однако я не верю, что ответом на это упражнение является невозможность создания анализатора рекурсивного спуска, поэтому я считаю, что где-то допустил ошибку или неправильно выполнил алгоритм.

Кто-нибудь может указать мне правильное направление?

1 Ответ

0 голосов
/ 31 октября 2018

Итак, вы правильно обнаружили, что FOLLOW ( var ) = FIRST ( block ) & cup; ПЕРВЫЙ ( Статистика ). Это все наборы, поэтому, когда вы вычисляете объединение двух первых наборов (каждый из которых содержит begin), вы получите только один begin. Пока ни один из этих наборов не содержит id, все в порядке, и ваша грамматика все еще LL (1).

...