Математическая теория формальных языков
Синтаксический разбор
В этой лекции даются формальные определения, связанные с прямыми (то есть читающими входную строку слева направо) синтаксическими анализаторами. В первом разделе доказывается, что для языков из класса LL(1) можно построить основанный на детерминированном автомате с магазинной памятью анализатор, который создает дерево разбора, двигаясь снизу вверх, то есть от листьев к корню (в теории контекстно-свободных грамматик принято изображать деревья с корнем наверху). Во втором разделе формулируется аналогичный результат об анализе сверху вниз для грамматик из класса . При этом понятие анализа снизу вверх формализовано в терминах последовательности правил, примененных в левостороннем выводе, а понятие анализа сверху вниз - в терминах обращенной последовательности правил, примененных в правостороннем выводе.
