Перед тем как читать изложение, ознакомьтесь с двумя прошлыми статьями и определением, что такое разбор, в этом порядке: раз, два, три. Прочли? Замечательно! В противном случае вы ничего не поймёте. Приступим.
Левая и правая рекурсия правил вывода.
Пусть у нас есть некоторая цепочка α - состоящая из конечных и неконечных символов, тогда если при выводе некоторого неконечного А, через один и более вывод мы приходим к виду А => … => Aα, где А находится слева от цепочки α, говорят что такая грамматика содержит левую рекурсию, и соответственно при А => … => αА, где А справа от α, правую рекурсию.
О правой рекурсии уже упоминалось, в теме «Рисунок порядка КС-языка», она позволяет легко свести рекурсию к циклу. При построении рекурсивного спуска требуются праворекурсивные грамматики, в противном случае возможна бесконечная рекурсию, затем переполнения стэка (стога) вызовов, как мы любим.
Леворекурсивная грамматика всегда может быть преобразована в эквивалентную праворекурсивную.
Направляющие символы, маяки.
Маяки это решающие в определении пути разбора, на одну ветвь может приходится множество направляющих символов. Это множество состоит из конечных символов и очень важно чтобы множество маяков одной ветви, не пересекалось со множеством другой ветви.
Перед - множество конечных направляющих символов.
LL-грамматика
LL(k)-грамматикой называется КС-грамматика, в которой выбор правила в ходе левостороннего разбора однозначно определяется не более чем k очередным символом входной цепочки, считываемой слева на право.
Своё название она получила из двух слова left left. что имеется ввиду левосторонее чтение, левостороний разбор.
Самой удобной для распознавания является грамматика которая позваляет опередлить правило по первому прочтённому символу, то есть LL(1)-грамматика.
Под рекурсивным спуском обычно подразумевают, предопределённый способ нисходящего разбора КС-языков, порождаемых ЛЛ(1)-грамматиками.
ЛЛ-грамматика праворекурсивна и множества направляющих символов в её правилах не пересекаются, что соответствует вышеуказанным требованиям.
Заключение
Эти правила касаются только лишь для метода рекурсивного спуска и ЛЛ-разбора по табелю (табличный анализатор), который рассмотрим в следующих статьях.