Я пытаюсь найти, как синтаксический анализатор LL (1) обрабатывает правильную ассоциативную грамматику. Например, в случае левоассоциативной грамматики, такой как эта, E->+TE' first() и follow() работают плавно, и таблица синтаксического анализа генерируется легко. Но в случае праворекурсивной грамматики, например, в случае мощности типа E->T^E/T таблица синтаксического анализа не генерируется должным образом. Я ищу ресурсы, но нашел каждый пример, избегающий правильной ассоциативности, такой как полномочия.
Как синтаксический анализатор LL(1) обрабатывает правоассоциативную грамматику
Ответы (1)
Алгоритмы LL без проблем обрабатывают правую рекурсию. Фактически упомянутое вами преобразование превращает левоассоциативную грамматику в правоассоциативную, а левоассоциативность необходимо восстанавливать путем преобразования синтаксического дерева в семантическое правило. Таким образом, если продукция действительно правоассоциативна, вы можете использовать ту же грамматику без необходимости постобработки дерева.
Проблема с E->T^E/T не в том, что он правильно рекурсивен. Проблема в том, что две правые части начинаются с одного и того же нетерминала, что делает предсказание невозможным. Решением является левая факторизация, которая даст E->T (^T)*`.
person
rici
schedule
03.12.2017
