Стандартные методы легко доступны для преобразования контекстно-свободной грамматики, которая не является LL (1), в эквивалентную грамматику, которая есть. Существуют ли какие-либо инструменты, позволяющие автоматизировать этот процесс?
В приведенных ниже примерах я использую заглавные буквы для нетерминалов и строчные буквы для терминалов.
Следующие леворекурсивные нетерминальные:
A -> A a | b
можно преобразовать в праворекурсивную форму:
A -> b A'
A' -> NIL | a A'
Однако обратите внимание, что леворекурсивные правила производства гарантируют, что выражения ассоциируются слева, и аналогично для правых рекурсивных производств; Таким образом, модификация грамматики также изменит ассоциативность выражения.
Другой проблемой является косвенная левая рекурсия, например следующая:
A -> B a
B -> A b
Левый факторинг также используется для того, чтобы синтаксическому анализатору требовался только один упреждающий токен. Следующее производство должно смотреть вперед на два жетона:
A -> a b | a c
Это также можно отредактировать; к:
A -> a (b | c)
Существуют ли какие-либо программные инструменты, которые могут автоматизировать эти преобразования грамматики; и так создать эквивалентную грамматику, подходящую для парсера LL (1)?
