Лекция 14: LR-разбор

Содержание лекции

Пусть задана некоторая контекстно-свободная грамматика. Рассмотрим произвольную терминальную цепочку. Требуется определить, принадлежит ли она языку, заданному данной грамматикой, и если принадлежит, то восстановить вывод ее вывод. Процесс решения этой задачи называется "разбором", программа, выполняющая разбор, называется "парсером" (от английского "to parse") или синтаксическим анализатором.

Наиболее популярны два метода разбора: рекурсивный разбор и разбор, использующий стек и конечный автомат (часто употребляется термин "автомат с магазинной памятью"). Мы не будем рассматривать рекурсивный разбор, потому что класс грамматик, допускающий его, значительно уже, чем в случае LR-разбора, и зачастую леворекурсивная грамматика конкретного языка выглядит неестественно, даже если язык допускает рекурсивный разбор. Перейдем к определению LR-разбора -- разбора, использующего стек и конечный автомат. Буква L означает, что исходная цепочка просматривается слева направо, R -- что при этом строится правый вывод.

Определим понятие LR-процесса. Состояние LR-процесса в любой момент времени описывается стеком LR-процесса и непрочитанной частью входной цепочки. Стек LR-процесса хранит обычные символы и метасимволы. Удобно представлять стек LR-процесса "повернутым невстречу входной цепочке".

При выполнении LR-процесса в любой момент времени возможны следующие два действия.

1. Сдвиг. Мы берем первый непрочитанный символ входной цепочки и переносим его в стек. Пример: +--------- до сдвига | aMBbaC abcdef +--------- +--------- после сдвига | aMBbaCa bcdef +--------- (символ "a" передвинут из начала входной цепочки в стек).
2. Свертка по некоторому правилу. Пусть конец слова, содержащегося в стеке, совпадает с правой частью некоторого правила грамматики. Тогда сверткой по этому правилу называется замена этого конца на левую часть правила, т.е. на один нетерминал. Рассмотрим следующий пример. Пусть в грамматике имеется правило A -> baCa Состояние LR-процесса до свертки: +--------- | aMBbaCa bcdef +--------- Состояние LR-процесса после свертки по этому правилу: +--------- | aMBA bcdef +--------- (конец "baCa" слова в стеке заменен на "A").

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

Конечное состояние успешного LR-процесса:

Пример: рассмотрим грамматику

1. Начальное состояние +-- | a+a*a +-- действие -- сдвиг.
    
2. Состояние LR-процесса +-- |a +a*a +-- действие -- свертка по правилу F -> a
    
3. +-- |F +a*a +-- действие -- сдвиг.
    
4. +--- |F+ a*a +--- действие -- сдвиг.
    
5. +--- |F+a *a +--- действие -- свертка по правилу F -> a
    
6. +--- |F+F *a +--- действие -- сдвиг.
    
7. +---- |F+F* a +---- действие -- сдвиг.
    
8. +----- |F+F*a +----- действие -- свертка по правилу F -> a
    
9. +----- |F+F*F +----- действие -- свертка по правилу F -> F*F
    
10. +---- |F+F +---- действие -- свертка по правилу F -> F+F
     
11. +-- |F +-- действие -- свертка по правилу S -> F
     
12. +-- |S +-- конечное состояние успешного LR-процесса.

Предложение. Имеется взаимно-однозначное соответствие между успешными LR-процессами и правыми выводами терминальных цепочек.

Приведенному выше успешному LR-процессу соответствует правый вывод

Следующее предложение очевидным образом вытекает из предыдущего.

Предложение. Для всякой выводимой терминальной цепочки существует успешный LR-процесс.

Проблема состоит в том, что априори не всегда можно решить, какое действие в данный конкретный момент следует выполнить: сдвиг или свертку, если свертку, то по какому правилу -- ведь могут быть ситуации, когда возможны свертки по разным правилам. Ошибочное решение может привести к тому, что LR-процесс невозможно будет довести до успешного завершения. Например, если в приведенном выше примере LR-процесса на шаге 1)

Перейдем к построению конечного автомата. Рассмотрим сначала более простой случай -- LR(0)-разбор. На практике используется LR(1)-разбор, определения для LR(1)-разбора будут даны позже.

Определение. LR(0)-ситуацией грамматики называется некоторое правило этой грамматики с отмеченной позицией в правой части. Позиция может быть перед началом правой части, где-нибудь в середине правой части или за концом правой части.

Давайте с данного момента времени вместо символа "->" (стрелка) в записи правила использовать двоеточие, как это принято в YACC'е. Правилу A: bCd (раньше мы бы написали A -> bCdE) соответствуют четыре LR(0)-ситуации:

Определение. LR(0)-состоянием разбора называется конечное подмножество множества всех возможных LR(0)-ситуаций.

Так как имеется лишь конечное число LR(0)-ситуаций, то число LR(0)-состояний также конечно.

Построение множества возможных LR(0)-состояний и переходов

В автомате, который мы будем строить, не все состояния будут использоваться. Проиллюстрируем процесс построения множества возможных LR(0)-состояний на примере. Рассмотрим грамматику

Постороение LR(0)-состояний

1. Начинаем с ситуации S: _F, где S -- начальный метасимвол грамматики, отмеченная позиция перед началом правой части правила. Если было бы несколько правил с левой частью S, то надо было бы добавить их все. Далее, ОЧЕНЬ ВАЖНО!!! если символ подчеркивания в правой части некоторой ситуации, уже включенной в множество, стоит перед нетерминалом, то надо добавить все ситуации для правил, левая часть которых совпадает с этим нетерминалом, с позицией перед началами правых частей этих правил. В нашем случае символ подчеркивания стоит перед нетерминалом "F", поэтому надо добавить ситуации F: _T, F: _F+T. Теперь получили метасимволы "T" и "F" после подчеркивания. Значит, еще раз надо добавить ситуации для правил с левой частью "T" и с левой частью "F". Во втором случае мы уже не добавим ничего нового (замечание на будущее: для LR(1)-разбора и здесь будут добавляться новые ситуации). Итак, добавляются ситуации T: _a, T: _(F). Окончательно множество ситуаций, составляющих начальное состояние LR(0)-разбора, равно { S: _F, F: _T, F: _F+T, T: _a, T: _(F) }.
2. Делая сдвиг метасимвола "F" в ситуациях S: _F и F: _F+T начального состояния, получаем состояние { S: F_, F: F_+T }, которое состоит из двух ситуаций.
    
3. Делая сдвиг "T" в ситуации F: _T начального состояния, получаем состояние { F: T_ }. Это состояние состоит всего из одной ситуации.
    
4. Делая сдвиг "a" в ситуации T: _a начального состояния, получаем состояние { T: a_ }.
5. Наконец, делая сдвиг круглой скобки "(" в ситуации T: _(F) начального состояния, получаем ситуацию T: (_F) Здесь опять приходится, как и в случае состояния 1, добавлять все ситуации с левой частью "F" и позицией перед началом правой части, F: _T, F: _F+T, затем все ситуации с левой частью "T" (т.к. подчеркивание стоит перед "T") и ситуации с левой частью "F" (что в случае LR(0)-разбора, к счастью, ничего не добавляет, но, увы, в случае LR(1)-разбора придется добавить еще ситуации...). T: _a, T: _(F). Окончательно получаем, что шестое состояние состоит из следующих ситуаций: { T: (_F), F: _T, F: _F+T, T: _a, T: _(F) }.
6. Делая сдвиг символа "+" в ситуации F: F_+T состояния 2, получим состояние F: F+_T. Так как подчеркивание стоит перед нетерминалом "T", надо добавить все ситуации с левой частью "T": T: _a, T: _(F). Окончательно получаем состояние { F: F+_T, T: _a, T: _(F) }.
7. Делая сдвиг метасимвола "F" в ситуациях T: (_F) и F: _F+T состояния 5, получим состояние { T: (F_), F: F_+T }. Отметим, что делая сдвиги символов "T", "a", "(" в состоянии 5, мы уже не получим новых состояний -- все они уже были построены раньше.
    
8. Делая сдвиг метасимвола "T" в ситуации F: F+_T состояния 6, получаем состояние { F: F+T_ }.
9. Делая сдвиг закрывающей скобки в T: (T_) состояния 7, получим состояние { F: (F)_ }.

Итак, мы построили все возможные состояния LR(0)-разбора. Их получилось девять. Выпишем их еще раз:

Будем говорить, что в состоянии возможна свертка по правилу, если это состояние содержит ситуацию, соответствующую этому правилу, с позицией за концом правой части правила. Например, в состоянии 2 возможна свертка по правилу S: F, в состоянии 3 -- свертка по правилу F: T. Будем говорить, что в состоянии возможен сдвиг, если есть ситуация, в которой после в правой части за отмеченной позицией следует терминальный символ. В нашем случае сдвиги возможны в состояниях 1, 2, 5, 6, 7. Естественным образом определяются переходы при сдвигах: например, из состояния 7

Мы будем говорить, что в данном состоянии имеется конфликт типа сдвиг-свертка, если оно допускает и сдвиг, и свертку. Будем говорить, что имеется конфликт типа свертка-свертка, если допустима свертка по двум разным правилам. В нашем случае имеется конфликт типа сдвиг-свертка в состоянии 2:

Будем говорить, что грамматика допускает LR(0)-разбор или является LR(0)-грамматикой, если построенной множество LR(0)-состояний не имеет конфликтов. Рассмотренная нами грамматика не является LR(0) грамматикой, поскольку имеет один конфликт типа сдвиг-свертка во втором состоянии.

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

Упражнение. Постройте систему LR(0)-состояний для грамматики

Язык, заданваемый приведенной выше грамматикой, состоит из цепочек вида