Как делают LL (*) работа синтаксических анализаторов?
Я не могу найти полное описание о LL (*) синтаксический анализатор, такой как ANTLR, в Интернете.
Я задаюсь вопросом, что является различием между LL (k) синтаксический анализатор и LL (*) один и почему они не могут поддерживать лево-recusrive грамматики несмотря на свою гибкость.
2 ответа
Вот статья (Теренса Парра, автора antlr) о LL(*) грамматическом анализе: статья с хорошим примером того, что является LL(*), но не LL(k), для любого k.
Еще одна хорошая ссылка (и гораздо более полная) - "Definitive ANTLR Reference", опять же Теренса Парра, и оригинальная журнальная статья, описывающая, как работает antlr [pdf].
Когда вы когда-либо видите это, это обычно количество токенов, которые смотрят вперед, чтобы проанализировать язык.
То же самое и для парсера LR.
Таким образом, k - это максимальное количество токенов, которое парер получит перед принятием решения. Имейте в виду, что чем больше k, тем сложнее будет анализатор, если вы не используете генератор (ANTLR, yacc, bison, ...).
LL-синтаксический анализатор использует подход сверху вниз, что означает, что он будет искать самое глубокое дерево. Из-за этой левой рекурсии будет получено бесконечно глубокое дерево и сломается синтаксический анализатор.
AFAIK Большая часть языка использует парсер LR.