2.5.3Синтаксические анализаторы lr(k)-грамматик. Грамматики предшествования

LR(k)-грамматики – это класс КС-грамматик, гарантирующих существование детерминированных восходящих распознавателей (L – левосторонний просмотр, R – правосторонний разбор, k – количество символов, просматриваемых для однозначного определения следующего правила). В грамматиках этого класса отсутствуют правила с правосторонней рекурсией, и обеспечивается однозначное выделение основы. К этому классу, например, относятся грамматики с операторным предшествованием, простым предшествованием и расширенным предшествованием, обеспечивающие еще более простые алгоритмы распознавания.

При восходящем разборе стек используют для накопления основы. Автомат при этом выполняет две основные операции: свертку и перенос. Свертка выполняется, когда в стеке накоплена вся основа, и заключается в ее замене на левую часть соответствующего правила. Перенос выполняется в процессе накопления основы и заключается в сохранении в стеке очередного распознаваемого символа сентенциальной формы. Основная проблема метода заключается в нахождении способа выделения очередной основы. Проще всего основу выделить для грамматик, получивших название «грамматики предшествования». Рассмотрим эти грамматики.

Если два символа α, β V расположены рядом в сентенциальной форме, то между ними возможны следующие отношения, названные отношениями предшествования:

1. α принадлежит основе, а β – нет, т. е. α – конец основы: α > β;

2. β принадлежит основе, а α – нет, т. е. β – начало основы: α < β ;

3. α и β принадлежит одной основе, т. е. α = β;

4. α и β не могут находиться рядом в сентенциальной форме (ошибка).

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

Различают:

1. грамматики с простым предшествованием, для которых α, β V;

2. грамматики с операторным предшествованием, для которых α, β V_Т; т. е. отношение предшествования определено для терминальных символов и не зависит от нетерминальных символов, расположенных между ними;

3. грамматики со слабым предшествованием, для которых отношение предшествования не однозначно – оно требует выполнения специальных проверок.

Пример. Грамматика описания арифметических выражений, представленная ниже, относится к классу грамматик с операторным предшествованием:

<Выражение> ::= <Терм> | < Терм > + <Выражение> | <Терм> - <Выражение>

<Терм> ::= <Множитель> | <Множитель>* <Терм> | <Множитель> / <Терм>

<Множитель> ::= (<Выражение>) | <Идентификатор>

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

Таблица 10 – Таблица предшествования

	+	*	(	)	◄
►	<	<	<	?	Выход
+	>	<	<	>	>
*	>	>	<	>	>
(	<	<	<	=	?
)	>	>	?	>	>

Обозначения:

? – ошибка;

< - начало основы;

> - конец основы;

= - принадлежат одной основе;

►- начало выражения;

◄ - конец выражения.

В соответствие с этой таблицей при разборе выражения:

►d+c*(a+b) ◄

содержимое стека будет выглядеть следующим образом:

Содержимое стека	Анализируемые символы	Отношение	Операция	Тройка	Результат свертки
►	d+	<	Перенос
►d+	c*	<	Перенос
►d+ c*	(	<	Перенос
►d+ c*(	a+	<	Перенос
►d+ c*( a+	b)	>	Свертка	R1:= a + b	<Выражение>
►d+ c*(	R1)	=	Свертка	R1:= (R1)	<Множитель>
►d+ c*	R1◄	>	Свертка	R2:= c* R1	<Терм>
►d+	R2◄	>	Свертка	R3:= d+ R2	<Выражение>
►	R3◄	Конец