Понятие грамматического разбора

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

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

Для обозначения подстановки используют символ «Þ».

Пример. Вывод строки «-45»:

<целое> Þ₁

Þ₁<знак><целое без знака> Þ₂

Þ₂ <знак><цифра><целое без знака>Þ₃

Þ₃ <знак><цифра><цифра> Þ₄

Þ₄ - <цифра><цифра> Þ₅

Þ₅ - 4<цифра> Þ₆

Þ₆- 45

Вывод можно представить графически, в виде синтаксического дерева, корнем которого является аксиома, а листья – образуют предложение языка (см. рисунок 1).

Неоднозначные грамматики. Существуют грамматики, в которых для одной строки можно построить несколько деревьев. Такие грамматики называются неоднозначными. Разбор неоднозначных грамматик затруднен, поэтому их, если возможно, преобразуют в однозначные или ограничивают правилами.

Пример 1. Строка х+х+х, порождаемая грамматикой с правилами S ® S + S и S ® x, имеет два дерева разбора (см. рисунок 2, а–б). Описывающая тот же язык однозначная грамматика использует правила: S ® S + x и S ® x (см. рисунок 2, в).

Рисунок 2 – Деревья разбора неоднозначной грамматики (а, б) и единственное дерево однозначной (в)

Пример 2. Конструкция if <лог. выр.> then <оператор> [ else <оператор>] при вложении неполного варианта получается неоднозначной. Поскольку ее преобразование невозможно, разбор ограничен правилом вложенности.

Грамматический разбор – процедура построения синтаксического дерева для конкретного предложения языка. Грамматический разбор может осуществляться в разной последовательности, причем дерево можно строить как «сверху» – от аксиомы, так и «снизу» – от предложения. Соответственно существуют нисходящий и восходящий методы разбора. При этом предложения языка можно рассматривать слева направо и наоборот. Соответственно различают левосторонний и правосторонний разбор. Левосторонний разбор используют чаще, т. к. мы читаем слева направо.

Левосторонний восходящий грамматический разбор («слева-направо»). Данный метод разбора применим, если грамматика не содержит правил с правосторонней рекурсией.

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

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

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

Пример. Разобрать строку «-45»

Правила грамматики:

<целое>::= <знак><целое без знака>|<целое без знака>,

<целое без знака>::= <целое без знака><цифра>|<цифра>,

<цифра >::= 0|1|2|3|4|5|6|7|8|9,

<знак>::= +| -.

Последовательность получения сентенциальных форм данным методом:

<знак> 45

<знак> <цифра>5

<знак> <цбз>5

<целое> 5 – Тупик! Возвращаемся и ищем другой вариант подстановки!

<знак><целое>5 – Тупик! Возвращаемся и ищем другой вариант подстановки!

<знак> <цбз><цифра>

<целое> <цифра> – Тупик! Возвращаемся и ищем другой вариант подстановки!

<знак> <целое> <цифра> – Тупик! Возвращаемся и ищем другой вариант!

<знак> <цбз>

<целое>

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

Левосторонний нисходящий грамматический разбор («сверху-вниз»). Данный метод разбора применим, если грамматика не содержит правил с левосторонней рекурсией.

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

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

При наличии правил с левосторонней рекурсией процедура разбора становится бесконечной.

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

Пример. Разобрать строку «-45»

Правила грамматики:

а) <целое>::= <знак><целое без знака>|<целое без знака>

б) <целое без знака>::= <цифра><целое без знака>|<цифра>,

в) <цифра >::= 0|1|2|3|4|5|6|7|8|9,

г) <знак>::= +| -.

Последовательность разбора:

	Распознано	Текущий символ	Цель или подцель	Правило	Истина?
		-	Целое	а1	да
		-	Знак	г1	нет
				г2	да
	-		Цбз	б1	да
			Цифра	в1-в4	нет
				в5	да
	- 4		Цбз	б1	нет
			Цифра	в1-в5	нет
				в6	да
	-45	­_	Цбз	б1	нет
		_	Цифра	в1-в10	нет
		­_	Цбз	б2	нет
		_	Цифра	в1-в10	нет
	- 4		Цбз	б2	да
			Цифра	в1-в5	нет
				в6	да

Также как в предыдущем случае в программе разбора следует хранить всю информацию о каждом шаге разбора.

Выбор метода разбора для грамматики определяется видом правил продукции языка.

Поиск по сайту: