Лабораторная работа 2. Синтаксический анализ. Нисходящий разбор без возвратов

Цель работы

Изучение принципов работы синтаксического анализатора на ос

нове метода нисходящего разбора с возвратами.

Теоретические положения

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

Грамматика

G [< id> ]

< id>:: =< l> |< id1>

< id1>:: =< l> |< d> |< l> < id1> |< d> < id1>

d:: =0|1|2|3|4|5|6|7|8|9

l:: = a|b|c...

Рис. 4. 1. Построение вывода для предложения 'c1'

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

Реализация программы нисходящего разбора.

Задание грамматики в ЭВМ.

Одним из способов задания грамматики может служит хранение в виде последовательности правил в одномерном массиве GRAMMAR таким образом, что каждое множество правил

U:: =x|y|... |z

представлено как

Ux|y|... |z|$.

То есть каждый символ занимает один элемент массива, за каждой правой частью U следует символ конца альтернативы - вертикальная черта " |", а за последней правой частью U следует пара символов " |$" (конец аль-тернативы и конец правила). Таким образом, грамматика

G1[Z]

Z:: =E#

E:: =T+E|T

T:: =F*T|F

F:: =(E)|i

будет выглядеть как

ZE#|$ET+E|T|$TF*T|F|$F(E)|i|$.

Синтаксический стек.

Для порождения и уничтожения выводов впрограмме используется стек типа LIFO (Last-In-First-Out). Как пра-вило для реализации стека используются массив S и счетчик v. Приv=0 стек пуст. При v=n, где n> 0, в стеке находятся элементы S(1), S(2),..., S(n), где S(n)-верхний элемент стека.

Каждый элемент стека соответствует одному порожденному непос

редственному выводу и состоит из пяти компонент

(GOAL, i, FAT, SON, BRO)

которые означают следующее:

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

- i - индекс в массиве GRAMMAR, указывающий на тот символ в правой части правила для GOAL, с которым производится работа в данный момент;

- FAT - имя родителя (номер элемента стека, соответствующего родителю);

- SON - имя самого последнего из непосредственных выводов для текущей альтернативы;

- BRO - имя предыдущего непосредственного вывода в текущей альтернативе.

Нуль в любом из полей означает, что данная величина отсутствует.

В качестве иллюстрации на рис. 4. 2. a) приведено синтаксическоедерево для предложения i+i*i грамматики G1[Z].

Состояние стека после окончания алгоритма разбора для предложения i+i*i (грамматика G1[Z]) показано в табл. 4. 1.

Таблица 4. 1. Состояние синтаксического стека

СТЕК	GOAL	i	FAT	SON	BRO
	Z
	E
	T
	F
	i
	+
	E
	T
	F
	i
	*
	T
	F
	i
	#

Массив GRAMMAR имеет 29 элементов:

(

)

При порождении элемента стека с номером 2 определяется его цель Е; а далее, в соответствии с грамматикой, использует правило E:: = T+E. Таким образом, для того, чтобы найти чему соответствуют символы T, + и Е, потребуется породить три вывода. Значения поля S(2). SON равно 7, так что последним потомком является элемент стека с номером 7, цель которого E. Номер предыдущего потомка для элемента 7 - число 6, определяется значением поля S(7). BRO; цель этого этого потомка - символ +. Имя старшего потомка находится в поле BRO элемента стека 6 и равно 3.

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

Стек в его окончательном виде не что иное, как внутренняя форма синтаксического дерева.

Следует отметить, что в конце каждого предложения в соответствие с грамматикой G1[Z] используется разделитель. По нему можно судить о том, что окончен разбор всего предложения, а не только какой-то из его подцепочек.

Требования к грамматикам для нисходящего разбора.

В алгоритме, описанном выше, есть недостаток, который проявляется, когда цель определена с использованием левосторонней рекурсии. Если X- цель, а первое же правило для X имеет вид X:: =X..., то происходит бесконечное порождение непосредственных выводов X => X..... Поэтому грамматика G1[Z] написана с применением правосторонней рекурсии вместо привычной левосторонней. Лучший способ избавится от прямой левосторонней рекурсии - записывать правила, используя итеративные и факультативные цепочки. При этом правила будут преобразованы к следующему виду:

- вместо E:: =E+T | T будет E: =T{+T}

- вместо T:: =T*F|T/F|F будет T:: =F{*F|/F}.

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

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

Если существуют правила вида

U:: =xy|xw|... | xz,

то их надо заменить на

U:: =x(y|w|... |z),

где скобки ( и ) являются

метасимволами.

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

y=fv, w=fm,

то

U:: =x(f(v|m)|....

Следует отметить, что исходные правила

U:: =x|xy

преобразуются

к виду

U:: =x(y|l⁰),

где l⁰-пустая цепочка.

Когда бы не использовалось подобное преобразование, l⁰ всегда помещается как альтернатива, так как принимается условие, что если цель - l⁰, то эта цель всегда сопоставляется части входной цепочки.

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

Итерация.

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

Пусть

U:: =x|y|... |z|Uv

- правила, у которых осталась леворекурсивная правая часть. Эти правила означают, что членом синтаксического класса U является x, y или z, за которыми ничего не следует, либо следует сколько-то v. Тогда правила преобразуются к виду

U:: =(x|y|... |z) {v}.

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

Устранение прямой левосторонней рекурсии не позволяет устра

нить общую левостороннюю рекурсию. При этом правила

U:: =Vx

V:: =Uy|v

дают вывод

U=> +Uyx.

Избавится от этого сложно, но обнаружить такую ситуацию возможно, если использовать отношение FIRST+/4/.

Задание на работу

Заданием является проектирование синтаксического анализатора

по методу нисходящего разбора с возвратами для вариантов, приведен

ных ниже.

Номер варианта состоит из 8 цифр:

(8)оператор WRITE

(7)оператор READ

(6)оператор цикла FOR -1, WHILE -2

(5)условный оператор IF

(4)индексированная переменная

(3)оператор присваивания

(2)выражение с целыми

(1)язык: C – 1, PASCAL - 2

Варианты.

1 - 11101000; 2 - 21101000; 3 - 11110000; 4 - 21110000;

5 - 11100100; 6 - 21100100; 7 - 11100200; 8 - 21100200.

Оформление отчета

В отчете должны быть приведены:

- исходная грамматика;

- преобразованная грамматика для устранения левосторонней рекурсии;

- схема алгоритма программы анализатора;

- схема данных;

- схемы процедур;

- спецификации процедур, к которым относятся входные и выход

ные параметры, а также выполняемые функции;

- исходные тексты процедур;

- результаты работы анализатора в виде синтаксических деревьев

и их представлений с помощью стека для конкретных примеров входных цепочек.

2.5 Контрольные вопросы

1) Каким способом в методе нисходящего разбора с возвратами осуществляется определение места продолжения разбора при неудаче?

2) Для чего в элементе стека используется поле BRO?

3) Как устранить леворекурсивность правила E:: =E+T|E-T|T, не используя итерацию?

4) В чем заключается сущность метода определения леворекурсивности грамматики?

5) Каким образом по синтаксическому дереву вывода можно построить окончательный вид стека, его промежуточный вид?

6) Каким образом можно сократить число возвратов в нисходящем методе? (Поясните на примере грамматики G1[Z]).

12 3 Следующая ⇒