#compiler-construction #context-free-grammar #ll
#построение компилятора #контекстно-свободная грамматика #ll
Вопрос:
Исходный cfg
S -> S S | SS | (S) | S* | a
После рефакторинга и устранения левой рекурсии я прихожу к следующему сокращению:
S -> TB
B -> AB | e
A -> S | TB | *
T -> (S) | a
При вычислении follow(B) онлайн-источники, которые я могу найти, говорят, что это должно быть {$} . Однако, основываясь на правилах в книге dragon, похоже follow(B) = follow(S) follow(A) , что из-за правила 3 (производство A -> aB приводит к тому, что все follow(A) находится внутри follow(B) .
Я неправильно понимаю правило?
Комментарии:
1. Цитата для (неправильного) утверждения, что FOLLOW (B) является
{$}?2. cs.sjtu.edu.cn /~цзянли/обучение/CS308/CS308-slides03.pdf
3. С другой стороны, я пытаюсь научить себя компиляторам, и мне было интересно, есть ли у вас какие-либо советы. В настоящее время я самостоятельно изучаю свой путь через книгу дракона.
4. Да, я согласен. Эти примечания к классу ошибочны
5. Комментарий SO слишком краток для совета, который я действительно хотел бы дать, поэтому я оставлю вас с некоторыми сокращенными советами: не тратьте слишком много времени на изучение того, как работают генераторы синтаксических анализаторов. Не тратьте время на генераторы синтаксического анализа LL. Не тратьте время на плохо документированные генераторы синтаксических анализаторов. Узнайте, как использовать какой-нибудь зрелый, хорошо документированный генератор, способный обрабатывать большинство полезных грамматик; по крайней мере, генератор LALR (1) и генератор GLR или GLL, если вы можете найти его для своего языка реализации. Не пишите калькулятор. Выясните, как создать AST. Затем начните компиляцию.
Ответ №1:
Нет, ваш интернет-источник неверен. Ваше понимание алгоритма FOLLOW в порядке (а также отображается в примечаниях к классу, которые вы цитируете).
На самом деле это странный пример для упражнения в синтаксическом анализе, поскольку грамматика неоднозначна. Рефакторинг и устранение левой рекурсии не устраняют двусмысленность; конечный результат по-прежнему неоднозначен, а неоднозначные грамматики всегда будут иметь конфликты синтаксического анализа.