Синтаксический анализ (стр. 3 )

4. Генерация программы вычисления выражения для стековой машины

(Данная задача равносильна задаче перевода выражения в постфиксную (обратную польскую) запись.)

Вписать в каждую процедуру разбора вывод в выходной поток (файл) некоторой последовательности команд виртуальной стековой машины. Для литералов и идентификаторов (в процедуре Match) выводится одноадресная команда записи значения в стек push(x). Для операции выводится безадресная команда (add, sub, div, mul), снимающая нужное число аргументов со стека и помещающая реезультат в стек. Генерация команд производится в постфиксном порядке.

Развитие задачи: реализовать эту схему "стековых вычислений" командами реальной двухадресной регистровой машины (типа i86). Для каждой арифметической команды вида op(r1,r2), вычисляющей r := r1 op r2, необходимо явно снимать аргументы со стека и принимать их в некоторые регистры: pop(r1), pop(r2), а также явно записывать результат операции в стек из регистра-результата: push(r1). (Здесь в первом приближении возникает задача распределения регистров, а полученный выходной код может быть поучительной иллюстрацией к задаче оптимизации вычислений.)

LL(k)-грамматики

Название этого класса грамматик обозначает тип синтаксического разбора, для которого они предназначены: L – левосторонний ввод входной строки, L – левосторонний вывод разверткой, k – c распознаванием продукций по k-предиктору.

Определение направляющих множеств

Пусть a Î (TÈN)*.

Firstk (a) – множество k-префиксов всех терминальных цепочек, выводимых из a :
Firstk (a) = {x Î T* | (a Þ* xb, |x|=k) Ú (a Þ* x , |x| < k) }

Followk (a) – множество k-префиксов всех терминальных цепочек, выводимых после a :
Followk (a) = {x Î T* | S Þ* wab, x Î Firstk (b ) }

Firstk (A®a) – множество k-префиксов всех терминальных цепочек, выводимых из нетерминала A продукцией A® a :
Firstk (A®a) = Firstk (a Followk (A))

Определение и свойства LL(k)-грамматик

Грамматика G – (нестрогая) LL(k)-грамматика: G Î LL(k),
если из условий: следует: где:
1. S Þl* wAb Þl wab Þl* wy w, y, z Î T*
2. S Þl* wAb Þl wdb Þl * wz a = d A Î N
3. Firstk (y) = Firstk (z) a, b, d Î (NÈT)*

Грамматика G – строгая LL(k)-грамматика: G Î SLL(k),
если выполнено усиленное условие 2:
2+. S Þl* vAg Þl vdg Þl* vz v Î T*; g, d Î (NÈT)*

Следствия определений, удобные для проверки LL(k)-свойства:

G Î LL(k) Û
Firstk (aib) Ç Firstk (ajb) = Æ "A®ai, A®aj ΠP, ai ¹aj; "b : S Þ* wAb

G Î SLL(k) Û
Firstk (A®ai) Ç Firstk (A®aj) = Æ "A®ai, A®aj Î P, ai ¹aj

Cмысл LL(k)-свойства: если A®ai и A®aj – две различные продукции, то множества k-префиксов терминальных цепочек, выводимых с их помощью (и на последующих шагах), не пересекаются. Значит, если k-префикс непрочитанной части входа известен, выводящая продукция для A определяется однозначно.

В нестрогой LL(k)-грамматике основанием для выбора продукции являются уже прочитанная часть входной строки w и множество k-префиксов непрочитанной части, а в строгой – только последнее.

LL(0)-грамматики существуют, но не применяются: при k = 0 First0 (a) = {e }, и поэтому для каждого нетерминала в грамматике разрешена только одна продукция. Такие грамматики описывают языки, состоящие из единственной цепочки.

Свойства LL(k)-грамматик:

1. LL(k)-грамматика однозначна.

2. Леворекурсивная грамматика не является LL(k) ни для какого k.

Соотношения классов LL(k)-грамматик:

1. "k³1: LL(k) Í LL(k+1) , SLL(k) Í SLL(k+1) .

2. "k>1: LL(k) É SLL(k) .

3. LL(1) = SLL(1) .

Последнее свойство делает особенно привлекательным класс LL(1): множества Firstk (A®ai) для SLL(k) вычисляются легче, чем для LL(k), а при k=1 они совпадают. Реализация нисходящего LL(1)-анализатора упрощается также тем, что 1-предиктор – это одиночная лексема, а не цепочка.

При невозможности построения LL(1)-грамматики для языка, можно пытаться найти решение в классах LL(2) и выше, т. е. различать продукции по двум очередным лексемам и т. д.

Построение направляющих множеств для LL(1)-грамматики

Алгоритм вычисления First1 (A):

1. Инициализация:
"X Î T: First1(X) = {X }.
"X Î N: First1(X) = Æ.

2. "X Î N применять следующие правила, пока First1(X ) изменяется:

а) Если X ® e Î P Þ {e }ÜFirst1(X )

б) Если X ® Y1Y2…Yk Î P:
– если "j < i e Î First1(Yj) и a Î First1(Yi) Þ {a}ÜFirst1(X)
– если "j £.k e Î First1(Yj) Þ {e }ÜFirst1(X)

Алгоритм вычисления Follow1 (A):

1. Инициализация:
"X Î N: Follow1(X ) = Æ.
Follow1(S) = {Ä} (Ä – символ конца ввода)

2. "X Î N применять следующие правила, пока какое-либо Follow1(Y ) изменяется:

а) Если A ® a Bb Î P Þ First1(b) \ {e } Ü Follow1(B)

б) Если A ® a B Î P
или A ® a Bb и e ΠFirst1(b) Þ Follow1(A) Ü Follow1(B)

Пример. Для грамматики:

E ® TE' First1(E) = First1(T) = First1(F) = {(,id}
E'® +TE'|e First1(E') = {+,e}
T ® FT' First1(T') = {*,e}
T'® *FT'|e Follow1(E) = Follow1(E') = {),Ä}
F ® (E) |id Follow1(T) = Follow1(T') = {+,),Ä}
Follow1(F) = {*,+,),Ä}
First1(E®+TE') = {+}
First1(E®e) = First1(e Follow1(E)) = {),Ä} First1(T®*FT') = {*}
First1(T®e) = First1(e Follow1(F)) = {*,+,),Ä}
First1(F®(E)) = {(} First1(F®id) = {id}

Направляющие множества для каждого из нетерминалов E, T, F не пересекаются, значит это LL(1)-грамматика.

Приемы приведения грамматики к классу LL(k)

Устранение левой рекурсии

Пусть A ® Aa1 | ... | Aan | b1 | ... | bk – все продукции для A и ни одно bi не начинается с A. Тогда замена этих продукций следующими:

A ® b1B | ... | bkB

B ® e | a1B | ... | anB

где B – новый нетерминал, устраняет левую рекурсию нетерминала A и не изменяет множества порождаемых цепочек: (b1 | ... | bk)(a1| ... |an)*.

Однако это преобразование меняет топологию дерева вывода цепочки с леворекурсивной на праворекурсивную. Семантическое различие видно, например, для дерева разбора арифметического выражения a–b–c+d: порядок ассоциации операций меняется с правильного ((a–b)–c)+d на неправильный a–(b–(c+d).

Факторизация

Пока в грамматике существуют две или более продукций, имеющих общий префикс правых частей, выполнять следующее преобразование факторизации:

A ® ab1 | ab2 Þ A ® aB
B ® b1 | b2

Факторизация позволяет отложить распознавание ветвления на более позднее время, когда, возможно, удастся различить направляющие множества по предиктору меньшей длины.

Грамматики для арифметического выражения

При рассмотрении способов разбора арифметического выражения ограничимся для краткости выражениями, состоящими из идентификаторов, бинарных операций двух уровней приоритета (высший – умножение и деление, низший – сложение и вычитание) и выражений в скобках. Добавление других видов аргументов, операций и уровней приоритета в дальнейшем возможно по аналогии.

"Наивная" грамматика G1:

E ® E+E | E-E | E*E | E/E | (E) | id

Свойства: леворекурсивная, неоднозначная (допускает различный порядок ассоциации операций, в том числе с нарушением приоритетов), т. е. не LL(k) по обоим признакам.

"Однозначная" грамматика G2:

E ® E+T | E-T | T
T ® T*F | T/F | F
F ® (E) | id

Свойства: однозначная, с разделением операций по группам приоритетов, левоассоциативная в каждой группе, но леворекурсивная, т. е. не LL(k).

LL(1)-грамматика G3:

E ® TE'
E'® +TE' | - TE' | e
T ® FT'

T'® *FT' | /FT' | e
F ® (E) | id

Свойства: однозначная, с разделением операций по группам приоритетов, нелеворекурсивная, LL(1), но правоассоциативная в каждой группе.

Эта грамматика допускает разбор методом рекурсивного спуска, но при построении дерева вычислений необходима перегруппировка левоассоциативных операций. В строго рекурсивной схеме, изложенной выше, это может быть с некоторыми усилиями достигнуто только семантическими действиями, изменяющими информационные связи в дереве, индуцированные рекурсией. Однако возможно расширение рекурсивной схемы разбора, решающее эту проблему.

Усовершенствованный метод рекурсивного спуска

Появление нетерминалов E’ и T’ и праворекурсивных продукций в грамматике G3 в результате избавления от левой рекурсии – явление несколько искусственное: эти нетерминалы не имеют значимого смысла в семантике выражений, а служат лишь для реализации некоторой техники разбора в рамках строго рекурсивной нотации грамматических правил. Но мы можем расширить эту нотацию в интересах дела!

Рассмотрим стандартную схему замены хвостовой рекурсии циклом, используя расширенную нотацию регулярных выражений, допускающую повторители в определениях:

A’ ® e | a1A’ | a2A’ | … | anA’ где e Ï Firstk (ai) Þ

A ® {a1 | a2 | … | an}*

С её помощью избавимся от искусственных нетерминалов E’ и T’ и хвостовой рекурсии в G3:

"Псевдорегулярная" грамматика G4:

E ® T {+T | - T}*
T ® F {*F | /F}*

F ® (E) | id

В дереве разбора выражения по этой грамматике последовательности операций одного приоритета находятся на одном уровне рекурсии и никак не ассоциированы, в отличие от лево - и правоассоциативных каскадов, который они образовывали в G2 и G3.

Для реализации этого подхода расширим схему генерации процедур разбора в методе рекурсивного спуска, добавив в неё циклы:

procedure ParseA; -- A ® a0 {a1|a2|…|an}*

begin

действия по разбору a0

do while LookAhead(1) in ÈFirstk(A®ai)\{e}

select LookAhead(k) of
Firstk(A®a1): действия по разбору a1

Firstk(A®a2): действия по разбору a2

...

Firstk(A®an): действия по разбору an

end select;

end do;

end;

Пример. Процедура разбора нетерминала E с семантической нагрузкой (выделена) для вычисления выражения. Левая ассоциативность реализуется семантическими средствами.

procedure ParseE(): int; -- E ® T {{+|-} T}*

var res: int;

begin

res := ParseT();

do while LookAhead(1) in {'+','-'} -- First1(E')\{e}

select LookAhead(1) of
'+': res := res + ParseT(); -- First1(E'®+TE')

'-': res := res – ParseT(); -- First1(E'®-TE')

end select;

end do;

return res;

end;

Восходящий синтаксический разбор без возвратов

Методы автоматной реализации

К восходящему синтаксическому разбору неприменимы рекурсивные методы, нисходящие по своей сути. Обычно его реализуют с помощью автомата типа «перенос-свертка», за основу которого берется рассмотренный выше недетерминированный восходящий анализатор MR, который детерминизируется некоторым механизмом решения RR - и SR-конфликтов, настраиваемым по заданной грамматике.

Устранение недетерминированности, как и в случае нисходящего разбора, накладывает ограничения на свойства грамматики. Мы рассмотрим два наиболее изученных класса грамматик, пригодных для восходящего разбора:

1.  Грамматики предшествования: на множестве символов грамматики вводятся специальные отношения предшествования, которые позволяют детерминированно находить в стеке границы сворачиваемой основы. Однако класс грамматик предшествования сравнительно невелик.

2.  LR(k)-грамматики: конфликты решаются просмотром непрочитанной части входной цепочки и анализом k-предикторов. Этот подход аналогичен LL(k)-подходу для нисходящего разбора. Но LL(k)-анализатор выбирает следующий шаг разбора, зная только прочитанную часть цепочки и k-префикс самой основы, а LR(k)-анализатор – зная прочитанную часть цепочки, всю основу и еще k символов после неё. Поэтому возможности LR(k)-анализа шире, а класс LR(k)-грамматик описательно мощнее класса LL(k)-грамматик. В действительности, он с избытком покрывает потребности анализа современных языков программирования.

Грамматики предшествования

В курсе для ФИТ не изучаются.

LR(k)-грамматики

(Материал в работе)

LR(k)-метод

LR(k)-метод восходящего разбора (L – левосторонний ввод, R – правосторонний вывод сверткой, k – c k-предиктором) основан на том же принципе, что и LL(k)-метод нисходящего разбора: знание k-предиктора должно однозначно определять следующий шаг анализатора.

Теоретические основы метода:

–  LR(k)-грамматики: класс грамматик, свойства которых исключают неоднозначность вывода на любом шаге LR(k)-разбора; в LR(k) выделяются также более простые подклассы SLR(k) и LALR(k).

–  система активных префиксов грамматики: описывает состояния стека LR(k)-анализатора в процессе разбора и структуру переходов между ними;

–  система допустимых LR(k)-ситуаций: описывает состояния вывода входной цепочки по грамматике и соотносит их с состояниями стека LR(k)-анализатора;

–  критерии проверки LR(k)-свойства грамматики, эквивалентные её определению: позволяют проверить внутреннюю непротиворечивость каждого из множеств LR(k)-ситуаций, определить по ним подкласс, которому принадлежит грамматика, и построить для нее подходящий анализатор.

Для реализации метода строятся:

–  множество состояний LR(k)-разбора и функция перехода между ними – по сути, конечный автомат: его структура индуцируется структурой системы допустимых LR(k)-ситуаций;

–  функция действия: для каждого состояния разбора по множеству допустимых в нем LR(k)-ситуаций однозначно определяет, какое действие: свертку, перенос, допуск или ошибку, – должен выполнить LR(k)-анализатор.

–  LR(k)-анализатор: детерминированный магазинный автомат-преобразователь, переключением состояний которого управляет функция переходов КА, а выводом цепочки – функция действия.

Далее все эти аспекты построения универсального LR(k)-анализатора описываются подробнее.

Схема универсального LR(k)-анализатора

LR(k)-анализатор – это магазинный автомат типа «перенос-свертка», управляемый вспомогательными функциями перехода и действия.

Пусть G = < T, N, S, P > – LR(k)-грамматика:

Множество состояний LR(k)-разбора:
V={V0 , …,Vn}

Функция переходов:
goto: V ´ (NÈT) ® V

Функция действия:
do: V ´ Tk ® {перенос, допуск, ошибка} È {cвертка p | p Î P}

(Функции goto и do также называются управляющими таблицами LR(k)-анализатора. Они, а также множество V, строятся по грамматике G согласно её подклассу.)
Множество V с функцией перехода goto можно рассматривать как вспомогательный конечный автомат, управляющий переключением состояний LR(k)-разбора:
K = < SK = NÈT, QK = V, qK0=V0, dK = goto >

LR(k)-анализатор для G – следующий (расширенный) МА:
MLR(V, goto, do) = < SM = T, QM = {q0, qF, qe}, ГM = (NÈTÈ{$})´V, s0 = [$,V0], FM = {qF}, dM >,
где функция переходов dM задана на конфигурациях:
1. Начальная конфигурация: (q0, [$,V0], w) ;
2. Правила переноса:
если do(V, u) = перенос, u = av:
(q0, …[c,V], av…) ð (q0, …[c, V][a, goto(V, a)], v…) ;
3. Правила cвертки:
если do(Vn, u) = свертка A ®X1…Xn:
(q0, …[c,V][X1,V1] …[Xn,Vn], u…) ð (q0, …[c,V][A, goto(V, A)], u…);
4. Правило допуска:
если do(V, e ) = допуск:
(q0, …[c,V], …) ð (qF, e, e ) – допуск;
5. Правила ошибки:
если do(V, u) = ошибка:
(q0, …[c,V], u…) ð (qe, …, u…) – ошибка.

Сравним это определение с определением недетерминированного анализатора MR.

Элементы стека расширены до пар, где вторыми элементами являются состояния из V: таким образом, в стеке сохраняется история состояний разбора (обратите внимание, что это внутренние состояния автомата K, а не автомата MLR!). Последнее (в стеке) из этих состояний управляет функциями действия и перехода.

Функция перехода goto по последнему состоянию V и новому символу в стеке определяет новое состояние разбора, которое также сохраняется в стеке.

Функция действия do по последнему состоянию V и k-предиктору u однозначно определяет следующий шаг анализатора. Именно в её определении заложено решение конфликтов. Поэтому автомат MLR –детерминированный.

Описываемый им алгоритм является универсальным для всего класса LR(k) c точностью до V, goto и do, которые зависят от конкретной грамматики. Переходим к их построению.

Задача описания состояний LR(k)-разбора

Для реализации анализатора надо подходящим образом определить конечное множество возможных состояний разбора и функцию перехода между ними. Каждое состояние в соответствующий ему момент времени должно так или иначе отражать сумму знаний о текущей ситуации разбора, достаточную для выбора следующего шага анализатора (перехода в следующее состояние). Построение модели состояний для LR(k)-анализатора требует привлечения вспомогательного понятийного аппарата.

Система активных префиксов грамматики

Вспомним, что восходящий анализатор MR выполняет (в недетерминированном порядке) шаги переноса очередного входного символа в стек и свертки в нетерминал суффикса стековой цепочки, образующей основу некоторой продукции.

Состояние анализатора MR (пока еще не LR(k)!) на каждом шаге полностью определяется текущим содержимым стека и непрочитанной частью входной цепочки (другой информации у него нет):

(g || v) – cостояние восходящего анализатора, где:
g – активный префикс: считанная и частично свернутая часть входной цепочки, находящаяся в стеке;
v – остаток ввода: еще не считанная часть входной цепочки.

Цепочка gv является правильной сентенциальной формой: S Þ* gv.

Активный префикс g – это «история» правостороннего разбора. Строгое определение:

Пусть S Þr* a Aw Þr ab w.
Активный префикс грамматики G – это любой префикс g цепочки ab.

Это определение исключает из содержания понятия стековые цепочки, которые не ведут к свертке (они могут появляться в стеке, например, при разборе недопустимой входной цепочки).

На множестве активных префиксов введем частичный порядок по отношению включения:

< Y, P > – система активных префиксов G, где:
Y – множество активных префиксов G;
P – отношение «g2 является расширением g1 посредством X»:
P(g1, X, g2)  Û  g2 = g1X, X Î TÈN

Cистему < Y, P > можно изобразить в виде орграфа, узлы которого помечены префиксами из Y, и если P(g1, X, g2), то из узла g1 в узел g2 ведет дуга, помеченная символом X. Этот граф является корневым деревом c корнем e и ветвями неограниченной длины (т. к. длины входной цепочки и активных префиксов неограниченны).

Будучи потенциально бесконечной, система активных префиксов сама не может быть принята за систему состояний LR(k)-анализатора, но она может быть преобразована в нее путем факторизации по отношению неразличимости активных префиксов при разборе.

Допустимые LR(k)-ситуации

Следующее понятие формализует представление о допустимых состояниях вывода по грамматике:

LR(k)-ситуация для грамматики G и k ³ 0:
[ A ® b1 · b2 | u ], где A ® b1b2 Î P, u Î Tk.

LR(k)-ситуация указывает, какая часть продукции (до разделителя ·) уже распознана анализатором, а какую еще ожидается распознать. Допустимость LR(k)-ситуации в некоторый момент разбора означает, что:

–  анализатор находится в состоянии (…b1 || wu…), т. е. начало основы b1 уже сформировано в стеке;

–  ожидается, что последующими шагами переносов и сверток входная подцепочка w будет преобразована в окончание основы b2 в стеке, что соответствует переходу анализатора в состояние (…b1b2 || u…); при этом k-префиксом остатка ввода будет u;

–  после этого станет возможна свертка основы в стеке в A – т. е. переход в состояние (…A || u…).

Все LR(0)-ситуации имеют вид [A ® b1 · b2 | e ], т. е. информацией о символах, следующих за основой, LR(0)-анализатор не располагает.

Множество всех LR(k)-ситуаций можно получить комбинируя конечное множество возможных расстановок разделителя · по всем основам продукций из P с конечным числом всех терминальных k-префиксов u. Это множество конечно.

Однако, не все LR(k)-ситуации встречаются при разборе. Выделим только те, которые допустимы в возможных состояниях анализатора:

Допустимая LR(k)-ситуация для активного префикса:
[ A ® b1 ·b2 | u ] допустима для g = ab1 Û S Þr* a Aw Þr a b1b2 w,
u Î Firstk (w)

Теперь каждому активному префиксу из Y можно сопоставить множество допустимых для него ситуаций:

Каноническая система множеств допустимых LR(k)-ситуаций для G:
Jk = {Vk (g) | Vk (g) – мн-во допустимых LR(k)-ситуаций для акт. префикса g}

Каждое из множеств Vk (g) содержит ситуации, возможные при разборе, когда в стеке анализатора лежит активный префикс g.

Хотя множество активных префиксов Y может быть бесконечным, множество Jk конечно, поскольку оно состоит из подмножеств конечного множества. Это позволяет эффективно строить каждое Vk (g) и Jk в целом.

Построение канонической системы множеств LR(k)-ситуаций

Метод построения:

Процедура closure (Vk (g)):

–  повторять, пока образуются новые ситуации:
если B ® b Î P и [A ® a ·Bd | u ] Î Vk (g), то:
"x Î Firstk (d u): [B ® ·b | x ] Ü Vk (g).

Эта процедура вычисляет «замыкание» множества ситуаций: для всех ситуаций, в которых ожидается вывод нетерминала (·B), инициируются все продукции для этого нетерминала (B®·b). Повторения нужны, т. к. новые ситуации могут содержать новые ожидания.

1. Построение Vk (e ):

–  [S’ ® ·S | e ] Ü Vk (e ) ;

–  построить closure (Vk (e )).

Vk (e ) отвечает за начало разбора: в стеке пустой префикс e – корень системы < Y, P >. Инициируется единственная продукция для стартового нетерминала пополненной грамматики и строится замыкание.

2. Повторять, пока образуются новые непустые множества:
"X: Vk (g) ® Vk (gX) = goto (Vk (g), X ):

–  если [A ® a ·Xb | u ] Î Vk (g), то: [A ® a X·b | u] ÜVk (gX ) ;

–  построить closure (Vk (gX )).

Обход системы < Y, P > в порядке расширения префиксов: для всех g, для которых Vk (g) уже построены ранее, отрабатываются все возможные переходы g ® gX. Из Vk (g) в Vk (gX ) переносятся только ситуации, ожидающие X (·X ); при этом разделитель переносится через X ( X·). Cтроится замыкание нового множества.

Способ реализации:

1.  closure (Vk (g)): цикл итераций до окончания изменений; на каждой итерации просматриваются все ситуации в множестве;

2.  Построение системы Jk как графа с вершинами Vk и дугами goto: алгоритм «бегущей волны» с пометкой обработанных множеств и рабочим списком для необработанных; обработка множества Vk (g) заключается в построении Vk (gX) = goto (Vk (g), X) для всех X; каждое новое множество добавляется в рабочий список, если оно не cовпадает ни с одним из уже построенных.

Анализ сходимости:

Алгоритм заканчивает работу за конечное время, поскольку:

1.  Вызов closure (Vk (g)) добавляет не более |Vk (g)|×|P| новых ситуаций. На каждой итерации цикла добавляется не менее одной ситуации;

2.  Каждое из множеств Vk (g) появляется в рабочем списке не более одного раза; число этих множеств конечно.

Управляющий КА: LR(k)-состояния и функция перехода

Именно система множества принимаются за состояния управляющего конечного автомата LR(k)-анализатора.

Функция переходов этого КА – это функция goto(Vk(g), X) из алгоритма построения Jk.

Классы активных префиксов, неразличимых по выводу

Неразличимость по выводу для активных префиксов:
g1 » g2 Û Vk (g1) = Vk (g2)

Свойства:

1.  Одинаковые расширения неразличимых префиксов – неразличимы:
"a : g1 » g2 ® g1a » g2a (по построению Jk)

2.  Неразличимость является отношением эквивалентности на Y.

3.  < Jk, goto >  @  < Y/», P/» >

Для всех неразличимых между собой активных префиксов информация о допустимых состояниях вывода, которую несет общее для них множество Vk, одинакова. Исходя из нее, при любом из этих префиксов в стеке, анализатор выполнит один и тот же следующий шаг, снова получит одно и то же множество допустимых ситуаций в следующем состоянии (по свойству 3) и т. д. Иными словами, дальнейшее поведение анализатора из состояний, в которых активные префиксы были неразличимы, одинаково.

Состояния анализатора, неразличимые по множествам допустимых ситуаций, могут быть приняты за одно.

Одинаковое знание влечет один и тот же шаг продолжения, а значит, и все последующие состояния и действия будут одинаковы. В этом смысле множество классов эквивалентности неразличимых активных префиксов Y/» является подходящей моделью искомых состояний для LR(k)-анализатора. Свойство 3 означает, что это множество классов изоморфно системе канонических множеств Jk, которую мы уже умеем строить.

Таким образом, система Jk может быть принята в качестве искомого множества состояний LR(k)-анализатора, потому что она удовлетворяет исходным требованиям к состояниям.

Построение множества ситуаций для всех активных префиксов вовсе не требует перебора всех префиксов. Данный алгоритм выполняет обход корневого дерева < Y, P >, делая при этом два вида отсечений ветвей:

1.  Отсечение по активному префиксу g, для которого Vk (g) пусто: ни сам этот префикс, ни все его расширения ga никогда не встречаются при разборе, т. к. им не соответствует ни одна допустимая LR(k)-ситуация.

2.  Отсечение по активному префиксу g, для которого Vk (g) совпадает с некоторым другим Vk (g1): для всех его расширений ga будет истинно Vk (ga) = Vk (g1a) – т. е. эти ветви порождают одни и те же последовательности Vk.

Благодаря этим отсечениям, обход бесконечного дерева активных префиксов заканчивается за конечное число шагов с образованием конечной системы Jk.

….

LR(k)-грамматики

Все рассмотренные выше понятия и построения, хотя и содержат в названиях “LR(k)”, но применимы к произвольной КСГ и пока не исключают конфликтов.

Собственно LR(k)-подход предусматривает выделение класса грамматик, свойства которых изначально исключают конфликты, так что нет необходимости решать их во время анализа.

Формальное определение класса LR(k)-грамматик, для которого реализуется этот подход:

Пополненная грамматика G – LR(k)-грамматика: G Î LR(k), k ³ 0,
если из условий: следует: где:
1. S Þr* a A w Þr ab w w, v, x Î T*
2. S Þr* d B x Þr ab v a =d , A = B, x = v A, B Î N
3. Firstk (w) = Firstk (v) a, b, d Î (NÈT)*

Условие 1 означает возможность свертки по A®b в состоянии (ab || w). Условие 2 допускает:

–  возможность свертки по B ® b1 b в состоянии (d b1 b || v) (если x = v, a = d b1);

–  перенос в стек терминала a в состоянии (d b1 b || azx), имея в виду дальнейшее применение продукции B ® b1b аz (если v = azx, a = d b1).

Совместность условий 1 и 2 означала бы возможность SR - или RR-конфликта (при w = v), но условие 3 запрещает им осуществляться одновременно при совпадении k-префиксов w и v.

Грамматики класса LR(0) – это грамматики с исключенным условием 3, т. е. решающие конфликты без предпросмотра. В отличие от класса LL(0), класс LR(0)-грамматик описывает нетривиальные языки.

Доказано, что любой LR(k)-язык при k > 0 описывается LR(1)-грамматикой, однако такая грамматика может быть очень велика. Даже для LR(1)-грамматик могут получаться очень громоздкие и практически неудобные анализаторы. Поэтому в классе LR(k) выделены и изучаются более узкие, но более практичные подклассы; два из них: Simple LR(k) – SLR(k), и Lookahead LR(k) – LALR(k), – будут рассмотрены ниже.

Системы множеств допустимых LR(k)-ситуаций

Следующие cистемы множеств используются для построения подклассов LR(k):

SLR(k)-система множеств для грамматики G:
J0

LALR(k)-система множеств для грамматики G:
J’k = { V’ | "VÎJk: V’=ÈWÎJk: core(W) = core(V) },
где core(V) = {[A ® a | e ] | [A ® a | u ]ÎV}

(Каждый элемент J’k получается слиянием всех множеств из Jk, ядра которых совпадают. Ядро множества получается стиранием информации о предикторах u из всех ситуаций.)

Управляющий конечный автомат LR(k)-анализатора

Конечная система множеств Jk может быть представлена как конечный автомат с заданной функцией переходов goto:

K = <SK = NÈT, QK = Jk, q0 = Vk(e ), F = {Vk(g) | [A ® a · | u] ÎVk(g)}, dK = goto >.

Любая цепочка g из терминалов и нетерминалов, переводящая автомат из состояния q0 = Vk(e) в состояние Vk(g), является одним из возможных префиксов. «Допускающими» состояниями этого КА являются множества состояний, в которых возможна свертка по одной из продукций.

Этот автомат теперь будет управлять работой LR(k)-анализатора.

Свойства LR(k)-грамматик:

1. LR(k)-грамматика однозначна.

Соотношения классов LR(k)-грамматик:

1. "k: LR(k) Í LR(k+1) .

2. "k>0: SLR(k) Í LALR(k) Í LR(k) .