Предварительные сведения

В этом разделе мы приводим некоторые сведения из теории синтаксического анализа. Более подробное изложение приведенных фактов можно найти в известной книге А. Ахо, Р. Сети и Д. Ульмана (см. [5]).

Грамматика формального языка задается четверкой G = (T,N,P,S), где

T – множество терминальных символов или токенов;
N – множество нетерминальных символов;
P – список правил грамматики;
S – стартовый символ грамматики.

Множество предложений формального языка, задаваемого грамматикой G, будем обозначать

Дадим несколько определений.

Расширением грамматики G (или просто расширенной грамматикой) называется грамматика G' = (T,N',P',S'), где S' – новый нетерминальный символ, а к множеству правил добавлено правило S' > S.

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

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

Пример. Рассмотрим следующую грамматику:

S > AB

A > cd

B > eCf

C > Ae

В ней сентенциальная форма cdB не имеет правого вывода, т.е. не может быть получена с помощью последовательного раскрытия самых правых нетерминалов. Примером правосентенциальной формы может служить форма AeCf. >

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

Пример. Пусть грамматика та же, что и в предыдущем примере. Форма AeCf, как мы уже заметили, является правосентенциальной. В ней есть две подпоследовательности символов Ae и eCf, которые могут быть свернуты в нетерминалы C и B соответственно. Однако основой является только последовательность eCf, так как сентенциальная форма CCf невыводима из стартового символа.
> Активным префиксом правосентенциальной формы называется префикс, не выходящий за границы самой правой основы этой формы. Пунктом грамматики G называется правило вывода с точкой в некоторой позиции правой части. Множество всех пунктов грамматики G будем обозначать через

. Пример. Правило вывода A > XYZ дает 4 пункта: A > •XYZ, A > X•YZ, A > XY•Z и A > XYZ•. > Базисным называется пункт с точкой не у левого края правой части правила, а также пункт S' > •S в расширенной грамматике. Замыканием множества пунктов I (обозначается closure(I)) называется наименьшее множество пунктов, содержащее I в качестве подмножества такое, что для всякого пункта A > ?•B?? I и любого правила B > ? пункт B > •? лежит в closure(I). Для пары (I,X), где I некоторое множество пунктов грамматики G, а X – символ грамматики (терминал или нетерминал), определим функцию goto(I,X) – замыкание множества всех пунктов A > ?X•? таких, что A > ?•X? ? I. Рассмотрим расширенную грамматику G' = (T,N',P',S'), где N' = N?{S'}, P = P?{S' > S}. Пусть I0 = closure({S' > •S}). Начиная с I0, строится система множеств пунктов I0,...,IN так, что для всякой пары (Ik,X), где k = 0,...,N и X – символ грамматики, существует индекс j = 0,...,N такой, что goto(Ik,X) = Ij. Эта система пунктов называется канонической системой множеств пунктов. Используя каноническую систему I0,...,IN, можно построить конечный автомат V, распознающий активные префиксы, если в качестве состояний sj взять канонические множества Ij, а переходы задать с помощью функции goto. Широко известны два класса алгоритмов синтаксического анализа: LL-анализ и LR-анализ (см. [5]). LL-анализатор с помощью диаграммы переходов или таблицы разбора строит левый вывод предложения целевого языка. Нерекурсивная реализация LL-анализатора использует стек и таблицу разбора. Изначально в стеке находится символ конца строки $ и стартовый символ грамматики.

На каждом шаге рассматривается символ на вершине стека X и текущий входной символ a. Действия анализатора определяются этими двумя символами:

если X = a = $, то анализатор прекращает работу и сообщает об успешном завершении разбора;
если X = a ? $, анализатор удаляет из стека символ X и переходит к следующему символу входного потока;
если X является нетерминалом, анализатор ищет такую альтернативу раскрытия символа X, для которой символ a является допустимым первым символом. После того, как требуемая альтернатива найдена, символ X в стеке заменяется обратной последовательностью символов альтернативы. Например, если искомая альтернатива X > ABC, то анализатор заменит X на вершине стека на последовательность CBA, т.е. на вершине стека окажется символ A. Конфликты, возникающие в процессе поиска альтернатив, могут разрешаться, например, с помощью “заглядывания вперед”, т.е. просмотра нескольких входных символов вместо одного.

Анализатор завершает работу, когда на вершине стека оказывается символ конца строки $. Рассмотрим теперь LR-анализатор, построенный на основе стека. У такого LR-анализатора имеются две основные операции:

перенос символа из входного потока в стек;
свертка нескольких последовательных символов на вершине стека в некоторый нетерминал.

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

Содержание раздела