Лабораторная работа 3 Построение простейшего дерева вывода Цель работы- изучение основных понятий теори

Работа добавлена на сайт samzan.net:

11 -

Лабораторная работа № 3
Построение простейшего дерева вывода

Цель работы: изучение основных понятий теории грамматик простого и операторного предшествования, ознакомление с алгоритмами синтаксического анализа (разбора) для некоторых классов КС-грамматик, получение практических навыков создания простейшего синтаксического анализатора для заданной грамматики операторного предшествования.

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

Рекомендуется программу разбить на три составные части: лексический анализ, построение цепочки вывода и построение дерева вывода. Лексический анализатор должен выделять в тексте лексемы языка и заменять их на терминальный символ грамматики (который в задании обозначен как “a”). Полученная после лексического анализа цепочка должна во второй части программы рассматриваться в соответствии с алгоритмом разбора. При неудачном завершении алгоритма выдается сообщение об ошибке, при удачном – строится цепочка вывода. После построения цепочки вывода на ее основе строится дерево разбора, в котором символы a последовательно заменяются на лексемы из таблицы лексем.

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

Краткие теоретические сведения

По иерархии грамматик Хомского выделяют 4 основные группы языков (и описывающих их грамматик). При этом наибольший интерес представляют регулярные и контексно-свободные (КС) грамматики и языки. Они используются при описании синтаксиса языков программирования. С помощью регулярных грамматик можно описать лексемы языка - идентификаторы, константы, служебные слова и прочие. На основе КС-грамматик строятся более крупные синтаксические конструкции - описания типов и переменных, арифметические и логические выражения, управляющие операторы, и, наконец, полностью вся программа на исходном языке.

Входные цепочки регулярных языков распознаются с помощью конечных автоматов (КА). Они лежат в основе сканеров, выполняющих лексический анализ и выделение слов в тексте программы на входном языке. Результатом работы сканера является преобразование исходной программы в список или таблицу лексем. Дальнейшую ее обработку выполняет другая часть компилятора - синтаксический анализатор. Его работа основана на использовании правил КС-грамматики, описывающих конструкции исходного языка.

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

Распознавание цепочек КС-языков

Класс КС-языков допускает распознавание с помощью недетерминированного конечного автомата со стековой (или магазинной) памятью - МП-автомата. Контекстно-зависимые языки - последний класс языков, которые можно эффективно распознавать с помощью ЭВМ. Они допускаются двусторонними недетерминированными линейно ограниченными автоматами. Для цепочек языка без ограничений, в общем случае, требуется универсальный вычислитель (машина Тьюринга, машина с неограниченным числом регистров и т.п.). Контекстно-зависимые языки и языки без ограничений при создании структур языков программирования не используются.

МП-автомат в отличие от обычного КА имеет стек (магазин), в который можно помещать специальные "магазинные" символы (обычно это терминальные и нетерминальные символы грамматики языка). Переход из одного состояния в другое зависит не только от входного символа, но и от одного или нескольких верхних символов стека. Таким образом, конфигурация автомата определяется тремя параметрами: состоянием автомата, текущим символом входной цепочки (положением указателя в цепочке) и содержимым стека.

При выполнении перехода из стека удаляются верхние символы, соответствующие условию перехода, и добавляется цепочка, соответствующая правилу перехода. Первый символ цепочки становится верхушкой стека. Допускаются переходы, при которых входной символ игнорируется (и, тем самым, он будет входным символом при следующем переходе). Эти переходы называются -переходами. МП-автомат называется недетерминированным, если при одной и той же его конфигурации возможен более чем один переход. Если при окончании цепочки автомат находится в одном из заданных конечных состояний, а стек пуст, цепочка считается принятой (после окончания цепочки могут быть сделаны -переходы). Иначе цепочка символов не принимается.

По КС-грамматике G(VN,VT,P,S), V=VTVN можно построить недетерминированный МП-автомат, который допускает цепочки языка этой грамматики. Он имеет только одно состояние и следующий набор переходов:

(A)() - для каждого правила грамматики A  P, где AVN, V*;

а(а)() - для каждого терминала аVT;

Здесь в круглых скобках показано содержимое верхушки стека. Перед скобками стоит очередной символ входной цепочки или символ  для -перехода, а символ  разделяет состояния автомата до и после выполнения перехода (показывает такт работы автомата). В начале работы автомата в стеке лежит символ SVN, в конце работы автомата стек должен быть пуст.

Можно построить и другой автомат, который также содержит одно состояние и имеет следующие переходы:

а()(а) - для каждого терминала аVT;

()(A) - для каждого правила грамматики A  P, где AVN, V*;

В таком варианте в начале разбора стек автомата пуст. Тогда в конце разбора допустимой цепочки в стеке должен остаться символ SVN.

По недетерминированному МП-автомату всегда можно построить КС-грамматику. Таким образом, класс КС-языков и класс языков, допускаемых МП-автоматами, эквивалентны.

Не каждый КС-язык допускает разбор с помощью детерминированного МП-автомата. Недетерминированные МП-автоматы могут распознавать более широкий класс языков, чем детерминированные - в этом их отличие от обычных КА. Интерес для реализации компиляторов представляют детерминированные КС-языки - собственное подмножество КС-языков, допускающее распознавание с помощью детерминированных МП-автоматов.

Два (недетерминированных) МП-автомата, построенных выше для произвольной КС-грамматики определяют два класса методов разбора КС-языков: сверху вниз и снизу вверх.

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

Во втором случае детерминированный разбор удобно формализовать в терминах "сдвиг" (перенос символа из входной цепочки в магазин) и "свертка" (применение к вершине магазина какого-либо правила грамматики). При просмотре входной цепочки слева направо при этом будут получаться правые выводы. Проблема в этом случае состоит в выборе между сдвигом и сверткой и в выборе правила для свертки.

Грамматики предшествования

Программирование работы недетерминированного МП-автомата - это сложная задача. Разработан алгоритм, позволяющий для произвольной КС-грамматики определить, принадлежит ли ей заданная входная цепочка (алгоритм Кока-Янгера-Касами)[4,5].

Доказано, что время работы этого алгоритма пропорционально n3, где n - длина входной цепочки. Для однозначной КС-грамматики при использовании другого алгоритма (алгоритм Эрли) это время пропорционально n2. Подобная зависимость делает эти алгоритмы требовательными к вычислительным ресурсам, а потому мало пригодными для практических целей. Но на практике и не требуется анализ цепочки произвольного КС-языка - большинство конструкций языков программирования может быть отнесено в один из классов КС-языков, для которых разработаны алгоритмы разбора, линейно зависящие от длины входной цепочки.

КС-языки делятся на классы в соответствии со структурой правил их грамматик. В каждом из классов налагаются дополнительные ограничения на допустимые правила грамматики.

Одним из таких классов является класс грамматик предшествования. Они используются для синтаксического разбора цепочек с помощью алгоритма “сдвиг-свертка”. Выделяют следующие типы грамматик предшествования:

простого предшествования;

расширенного предшествования;

слабого предшествования;

смешанной стратегии предшествования;

операторного предшествования.

Далее будут рассмотрены ограничения на структуру правил и алгоритмы разбора для двух типов - грамматик простого и операторного предшествования.

Грамматикой простого предшествования называют такую КС-грамматику G(VN,VT,P,S), V=VTVN в которой:

Для каждой упорядоченной пары терминальных и нетерминальных символов выполняется не более чем одно из трех отношений предшествования:

Si = Sj ( Si,SjV), если и только если  правило UxSiSjy P, где UVN, x,yV*;

Si < Sj ( Si,SjV), если и только если  правило UxSiDy P и вывод D*Sjz, где U,DVN, x,y,zV*;

Si > Sj ( Si,SjV) , если и только если  правило UxCSjy P и вывод C*zSi или  правило UxCDy P и выводы C*zSi и D*Sjw, где U,C,DVN, x,y,z,wV*.

Различные порождающие правила имеют разные правые части.

Отношения =, < и > называют отношениями предшествования для символов. Отношение предшествования единственно для каждой упорядоченной пары символов. При этом между какими-либо двумя символами может и не быть отношения предшествования - это значит, что они не могут находиться рядом ни в одном элементе разбора синтаксически правильной цепочки. Отношения предшествования зависят от порядка, в котором стоят символы, и в этом смысле их нельзя путать со знаками математических операций - например, если Si > Sj, то не обязательно, что Sj < Si (поэтому знаки предшествования иногда помечают специальной точкой: =, <, >)

Метод предшествования основан на том факте, что отношения предшествования между двумя соседними символами распознаваемой строки соответствуют трем следующим вариантам:

Si < Si+1, если символ Si+1 - крайний левый символ некоторой основы;

Si > Si+1 , если символ Si - крайний правый символ некоторой основы;

Si = Si+1 , если символы Si и Si+1 принадлежат одной основе.

Исходя из этих соотношений выполняется разбор строки для грамматики предшествования.

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

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

L(U) = {T |  U*Tz}, U,TV, zV* - множество крайних левых символов относительно нетерминального символа U (цепочка z может быть и пустой цепочкой);

R(U) = {T |  U*zT}, U,TV, zV* - множество крайних правых символов относительно нетерминального символа U.

Тогда отношения предшествования можно определить так:

Si = Sj ( Si,SjV), если  правило UxSiSjy P, где UVN, x,yV*;

Si < Sj ( Si,SjV), если  правило UxSiDy P и SjL(D), где U,DVN, x,yV*;

Si > Sj ( Si,SjV) , если  правило UxCSjy P и SiR(C) или  правило UxCDy P и SiR(C), SjL(D), где U,C,DVN, x,yV*.

Такое определение отношений удобнее на практике, так как не требует построения выводов, а множества L(U) и R(U) могут быть построены для каждого нетерминального символа UVN по очень простому алгоритму:

Шаг 1. Для каждого нетерминального символа U ищем все правила, содержащие U в левой части. Во множество L(U) включаем самый левый символ из правой части правил, а во множество R(U) - самый крайний символ правой части. Переходи к шагу 2.

Шаг 2. Для каждого нетерминального символа U: если множество L(U) содержит нетерминальные символы грамматики U’,U”,..., то его надо дополнить символами, входящими в соответствующие множества L(U’), L(U”), ... и не входящими в L(U). Ту же операцию надо выполнить для R(U).

Шаг 3. Если на предыдущем шаге хотя бы одно множество L(U) или R(U) для некоторого символа грамматики изменилось, то надо вернуться к шагу 2, иначе построение закончено.

После построения множеств L(U) и R(U) по правилам грамматики создается матрица предшествования. Матрицу предшествования дополняют символами н и к (начало и конец цепочки). Для них определены следующие отношения предшествования:

н < a,  aV, если  S*ax, где SVN, xV* или (с другой стороны) если aL(S);

к > a,  aV, если  S*xa, где SVN, xV* или (с другой стороны) если aR(S).

Грамматикой операторного предшествования называется приведенная КС-грамматика без -правил (e-правил), в которой правые части продукций не содержат смежных нетерминальных символов. Для грамматики операторного предшествования отношения предшествования можно задать на множестве терминальных символов (включая символы н и к).

Отношения предшествования для грамматики операторного предшествования G(VN,VT,P,S) задаются следующим образом:

a = b, если и только если существует правило Uxaby P или правило UxaCby, где a,bVT, U,CVN, x,yV*;

a < b, если и только если существует правило UxaCy P и вывод C*bz или вывод C*Dbz, где a,bVT, U,C,DVN, x,y,zV*;

a > b, если и только если существует правило UxCby P и вывод C*za или вывод C*zaD, где a,bVT, U,C,DVN, x,y,zV*.

В грамматике операторного предшествования различные порождающие правила имеют разные правые части. Для грамматики операторного предшествования тоже строится матрица предшествования, но она содержит только терминальные символы грамматики.

Для построения этой матрицы удобно ввести множества крайних левых и крайних правых терминальных символов относительно нетерминального символа U - Lt(U) или Rt(U):

Lt(U) = {t |  U*tz или  U*Ctz }, где tVT, U,CVN, zV*;

Rt(U) = {t |  U*zt или  U*ztC }, где tVT, U,CVN, zV*.

Тогда определения отношений операторного предшествования будут выглядеть так:

a = b, если  правило Uxaby P или правило UxaCby, где a,bVT, U,CVN, x,yV*;

a < b, если  правило UxaCy P и bLt(C), где a,bVT, U,CVN, x,yV*;

a > b, если  правило UxCby P и aRt(C), где a,bVT, U,CVN, x,yV*.

В данных определениях цепочки символов x,y,z могут быть и пустыми цепочками.

Для нахождения множеств Lt(U) и Rt(U) используется следующий алгоритм:

Шаг 1. Для каждого нетерминального символа грамматики U строятся множества L(U) и R(U).

Шаг 2. Для каждого нетерминального символа грамматики U ищутся правила вида Utz и UCtz, где tVT, CVN, zV*; терминальные символы t включаются во множество Lt(U). Аналогично для множества Rt(U) ищутся правила вида Uzt и UztC.

Шаг 3. Просматривается множество L(U), в которое входят символы U’,U”,... Множество Lt(U) дополняется символами, входящими в Lt(U’), Lt(U”), ... и не входящими в Lt(U). Аналогичная операция выполняется и для множества Rt(U) на основе множества R(U).

Для практического использования матрицу предшествования дополняют символами н и к (начало и конец цепочки). Для них определены следующие отношения предшествования:

н < a,  aVT, если  S*ax или  S*Cax, где S,CVN, xV* или если aLt(S);

к > a,  aVT, если  S*xa или  S*xaC, где S,CVN, xV* или если aRt(S).

Алгоритм “сдвиг-свертка” для грамматик простого и операторного предшествования

Алгоритм “сдвиг-свертка” для грамматики простого предшествования. Данный алгоритм выполняется МП-автоматом с одним состоянием. Отношения предшествования служат для того, чтобы определить в процессе выполнения алгоритма, какое действие - сдвиг или свертка - должно выполняться на данном шаге и однозначно выбрать правило при свертке. В начальном состоянии автомата считывающая головка обозревает первый символ, в конец цепочки помещен символ к.

Разбор считается законченным (алгоритм завершается), если считывающая головка автомата обозревает символ н и при этом больше не может быть выполнена свертка. Решение о принятии цепочки зависит от содержимого стека. Автомат принимает цепочку, если в результате завершения алгоритма он находится в конечном состоянии, когда в стеке находятся начальный символ грамматики S и символ н. Выполнение алгоритма может быть прервано, если на одном из его шагов возникнет ошибка. Тогда входная цепочка не принимается.

Алгоритм состоит из следующих шагов:

Шаг 1. Поместить в верхушку стека символ н.

Шаг 2. Сравнить символ, находящийся на вершине стека, с текущим символом ленты.

Шаг 3. Если имеет место отношение < или =, то произвести перенос и вернуться к шагу 2.

Шаг 4. Если имеет место отношение >, то произвести свертку, то есть найти на вершине стека все символы, связанные отношением = (основу) и заменить их на левую часть соответствующего правила грамматики (если символов, связанных отношением =, на верхушке стека нет, то для правила используется один, верхний символ). Если разбор не закончен, то вернуться к шагу 2.

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

Алгоритм “сдвиг-свертка” для грамматики операторного предшествования в целом похож на алгоритм для грамматик простого предшествования. Он выполняется тем же МП-автоматом и имеет те же условия завершения и обнаружения ошибок. Основное отличие состоит в том, что при работе со стеком в этом алгоритме не принимаются во внимание находящиеся в нем нетерминальные символы, и при сравнении ищется ближайший к верхушке стека терминальный символ. Однако после выполнения сравнения и определения границ основы при поиске правила в грамматике нетерминальные символы следует, безусловно, принимать во внимание.

Шаг 1. Поместить в верхушку стека символ н.

Шаг 2. Сравнить символ, находящийся на вершине стека, игнорируя все нетерминальные символы, с текущим символом ленты.

Шаг 3. Если имеет место отношение < или =, то произвести перенос и вернуться к шагу 2.

Шаг 4. Если имеет место отношение >, то произвести свертку, то есть найти на вершине стека (опять же игнорируя нетерминальные символы) все символы, связанные отношением = (основу) и заменить их на левую часть соответствующего правила грамматики (при выборе правила нетерминальные символы должны учитываться). Если разбор не закончен, то вернуться к шагу 2.

Конечная конфигурация автомата совпадает с конфигурацией при распознавании цепочек грамматик простого предшествования.

Пример построения распознавателя для грамматики операторного предшествования.

Рассмотрим в качестве примера грамматику G({S,B,T,J},{-,&,^,(,),p},P,S) (терминальные символы выделены жирным шрифтом):

P: S  -B (правило 1)
B  T | B&T (правила 2 и 3)
T  J | T^J (правила 4 и 5)
J  (B) | p (правила 6 и 7)

Видно, что эта грамматика является грамматикой операторного предшествования.

Построим множества крайних левых и крайних правых символов L(U), R(U) относительно всех нетерминальных символов грамматики. Результат построения приведен в табл. 2.

На основе полученных множеств построим множества крайних левых и крайних правых терминальных символов Lt(U), Rt(U) относительно всех нетерминальных символов грамматики. Результат (второй и третий шаги построения) приведен в табл. 3.

Таблица 2.

Множества крайних правых и крайних левых символов грамматики (по шагам построения)

Символ	Шаг 1 (начало построения)	Последний шаг (результат)
(U)	L(U)	R(U)	L(U)	R(U)
J	( p	) p	( p	) p
T	J T	J	J T ( p	J ) p
B	T B	T	T B J ( p	T J ) p
S	-	B	-	B T J ) p

Таблица 3.

Множества крайних правых и левых терминальных символов грамматики (по шагам построения)

Символ	Шаг 1 (начало построения)	Последний шаг (результат)
(U)	Lt(U)	Rt(U)	Lt(U)	Rt(U)
J	( p	) p	( p	) p
T	^	^	^ ( p	^ ) p
B	&	&	& ^ ( p	& ^ ) p
S	-	-	-	- & ^ ) p

На основе этих множеств и правил грамматики G построим матрицу предшествования грамматики (табл. 4).

Таблица 4.

Матрица предшествования грамматики

Символы	-	&	^	(	)	p	к
-		<	<	<		<	>
&		>	<	<	>	<	>
^		>	>	<	>	<	>
(		<	<	<	=	<
)		>	>		>		>
p		>	>		>		>
н	<

Посмотрим, как заполняется матрица предшествования в табл. 4 на примере символа &. В правиле грамматики B  B&T (правило 3) этот символ стоит слева от нетерминального символа T. В множество Lt(T) входят символы: ^ ( p. Ставим знак < в клетках матрицы, соответствующих этим символам, в строке для символа &. В то же время в этом же правиле символ & стоит справа от нетерминального символа B. В множество Rt(B) входят символы: & ^ ) p. Ставим знак > в клетках матрицы, соответствующим этим символам, в столбце для символа &. Больше символ & ни в каком правиле не встречается, значит заполнение матрицы для него закончено, берем следующий символ и продолжаем заполнять матрицу таким же методом.

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

P: E  -E (правило 1)
E  E | E&E (правила 2 и 3)
E  E | E^E (правила 4 и 5)
E  (E) | p (правила 6 и 7)

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

Рассмотрим работу алгоритма распознавания на примерах. Последовательность разбора будем записывать в виде последовательности конфигураций МП-автомата из трех составляющих: не просмотренная автоматом часть входной цепочки, содержимое стека и последовательность правил грамматики. Так как автомат имеет только одно состояние, то для определения его конфигурации достаточно двух составляющих - положения считывающей головки во входной цепочке и содержимого стека, - но последовательность номеров правил несет дополнительную полезную информацию, которая должна быть затем использована компилятором на последующих этапах для семантической обработки и для генерации кода объектной программы. (Кроме того, последовательность примененных правил делает пример более наглядным).

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

Последовательности разбора цепочек входных символов будут, таким образом, иметь вид:

Пример 1. Входная цепочка -p&p^(p).

{-p&p^(p)к; н; } п {p&p^(p)к; н-; } п {&p^(p)к; н-p; } с {&p^(p)к; н-E; 7} п {p^(p)к; н-E&; 7} п {^(p)к; н-E&p; 7} с {^(p)к; н-E&E; 7,7} п {(p)к; н-E&E^; 7,7} п {p)к; н-E&E^(; 7,7} п {)к; н-E&E^(p; 7,7} с {)к; н-E&E^(E; 7,7,7} п
{к; н-E&E^(E); 7,7,7} c {к; н-E&E^E; 7,7,7,6} с {к; н-E&E; 7,7,7,6,5} п
{к; н-E; 7,7,7,6,5,3} с {к; нE; 7,7,7,6,5,3,1}

Пример 2. Входная цепочка -p^p(p).

{-p^p(p)к; н; } п {p^p(p)к; н-; } п {^p(p)к; н-p; } с {^p(p)к; н-E; 7} п
{p(p)к; н-E^; 7} п {(p)к; н-E^p; 7} - ошибка ! (нет отношения для пары символов {p,(} )

Пример 3. Входная цепочка -p^p&p.

{-p^p&pк; н; } п {p^p&pк; н-; } п {^p&pк; н-p; } с {^p&pк; н-E; 7} п
{p&pк; н-E^; 7} п {&pк; н-E^p; 7} с {&pк; н-E^E; 7,7} с {&pк; н-E; 7,7,5} п
{pк; н-E&; 7,7,5} п {к; н-E&p; 7,7,5} с {к; н-E&E; 7,7,5,7} с {к; н-E; 7,7,5,7,3} c
{к; нE; 7,7,5,7,3,1}

Пример 4. Входная цепочка -p&p^p.

{-p&p^pк; н; } п {p&p^pк; н-; } п {&p^pк; н-p; } с {&p^pк; н-E; 7} п
{p^pк; н-E&; 7} п {^pк; н-E&p; 7} с {^pк; н-E&E; 7,7} п {pк; н-E&E^; 7,7} п
{к; н-E&E^p; 7,7} с {к; н-E&E^E; 7,7,7} с {к; н-E&E; 7,7,7,5} п {к; н-E; 7,7,7,5,3} c
{к; нE; 7,7,7,5,3,1}

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

Общий алгоритм работы синтаксического анализатора

Синтаксический анализатор работает, опираясь на построенную матрицу предшествования. На его вход поступает обработанный сканером текст исходной программы. Каждый идентификатор или константа представляются для него некоторым терминальным символом (в примере он обозначен как p, в задании - a). Тогда первым шагом общего алгоритма анализа должно являться построение таблицы лексем (что уже выполнялось в предыдущей работе).

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

По последовательности правил легко строится цепочка вывода и дерево синтаксического разбора. Дерево строится сверху вниз путем последовательного применения правил. При построении дерева следует учитывать, что алгоритм разбора порождает правосторонний вывод, поэтому на каждом шаге на основе правила в цепочке следует заменять крайний правый нетерминальный символ (нижний правый в дереве). Это третий шаг общего алгоритма анализа.

Цепочки вывода для двух из рассмотренных выше примеров будут иметь следующий вид:

Пример 3. Входная цепочка -p^p&p.

E  -E  -E&E  -E&p  -E^E&p  -E^p&p  -p^p&p

Пример 4. Входная цепочка -p&p^p.

E  -E  -E&E  -E&E^E  -E&E^p  -E&p^p  -p&p^p

Рис. 4. Деревья вывода для цепочек из примеров 3 и 4 соответственно.

Деревья вывода для этих двух примеров приведены на рис. 4.

После построения дерева остается заменить терминальные символы (p или a) грамматики на соответствующие константы и идентификаторы из таблицы лексем. Для этого достаточно просматривать таблицу от начала к концу и, обходя построенное дерево от корня сверху вниз слева направо, последовательно заменить все листья, помеченные искомым символом, на лексемы из таблицы. Это последний шаг общего алгоритма работы синтаксического анализатора.

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

Порядок выполнения работы

Получить вариант задания у преподавателя.

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

Выполнить разбор простейшего примера вручную по правилам заданной грамматики.

Подготовить и защитить отчет.

Написать и отладить программу на ЭВМ.

Сдать работающую программу преподавателю.

Требования к оформлению отчета

Отчет должен содержать следующие разделы:

Задание по лабораторной работе.

Краткое изложение цели работы.

Запись заданной грамматики входного языка в форме Бэкуса-Наура.

Множества крайних правых и крайних левых символов с указанием шагов построения.

Множества крайних правых и крайних левых терминальных символов.

Заполненную матрицу предшествования для грамматики.

Пример выполнения разбора простейшего предложения (по выбору).

Текст программы (оформляется после выполнения программы на ЭВМ по согласованию с преподавателем).

Основные контрольные вопросы

Какую роль выполняет синтаксический анализ в процессе компиляции?
Какие типы грамматик существуют? Как связаны типы грамматик и языков?
Что такое КС-грамматики? Расскажите об их использовании в компиляторе.
Дайте определение приведенной грамматики. Какие преобразования грамматик существуют?
Поясните правила построения дерева вывода грамматики.
Что такое грамматики простого предшествования?
Как вычисляются отношения предшествования для грамматик простого предшествования ?
Что такое грамматика операторного предшествования ?
Как вычисляются отношения для грамматик операторного предшествования ?
Расскажите о задаче разбора. Что такое распознаватель языка?
Расскажите об общих принципах работы распознавателя языка.
Что такое перенос, свертка. Для чего необходим алгоритм «перенос-свертка»?
Расскажите, как работает алгоритм «перенос-свертка» в общем случае (с возвратами).
Как работает алгоритм «перенос-свертка» без возвратов (объясните на своем примере)?

Варианты исходных грамматик

Ниже приведены варианты грамматик. Во всех вариантах символ S является начальным символом грамматики; S, F, T и E обозначают нетерминальные символы. Терминальные символы выделены жирным шрифтом. Вместо символа a должны подставляться лексемы.

1. S  a := F; 2. S  a := F;

F  F+T | T    F  F or T | F xor T | T
T  T*E | T/E | E    T ® T and E | E
E  (F) | -(F) | a    E ® (F) | not (F) | a

3. S  F; 4. S  F;

F  if E then T else F | if E then F | a := a F  for T do F | a := a

T  if E then T else T | a := a T  (F; E; F) | (; E; F) | (F; E;) | (; E;)

E  a<a | a>a | a=a E  a<a | a>a | a=a

Варианты заданий

№ варианта	№ варианта грамматики	Допустимые лексемы входного языка
1	1	Идентификаторы, десятичные числа с плавающей точкой
2	2	Идентификаторы, константы true и false
3	3	Идентификаторы, десятичные числа с плавающей точкой
4	4	Идентификаторы, десятичные числа с плавающей точкой
5	1	Идентификаторы, римские числа
6	2	Идентификаторы, константы 0 и 1
7	3	Идентификаторы, римские числа
8	4	Идентификаторы, римские числа
9	1	Идентификаторы, шестнадцатеричные числа
10	2	Идентификаторы, шестнадцатеричные числа
11	3	Идентификаторы, шестнадцатеричные числа
12	4	Идентификаторы, шестнадцатеричные числа
13	1	Идентификаторы, символьные константы (в одинарных кавычках)
14	2	Идентификаторы, символьные константы ‘T’ и ‘F’
15	3	Идентификаторы, строковые константы (в двойных кавычках)
16	4	Идентификаторы, строковые константы (в двойных кавычках)

Примечание:

римскими числами считать последовательности больших латинских букв X, V и I;
шестнадцатеричными числами считать последовательность цифр и символов ‘a’, ‘b’, ‘c’,’d’, ’e’ и ‘f’, начинающуюся с цифры (например: 89, 45ac9, 0abc4);
для выполнения работы рекомендуется использовать лексический анализатор, построенный в ходе выполнения лабораторной работы №2.

Будь умным!

Лабораторная работа 3 Построение простейшего дерева вывода Цель работы- изучение основных понятий теори

Лабораторная работа № 3
Построение простейшего дерева вывода

Краткие теоретические сведения

Распознавание цепочек КС-языков

Грамматики предшествования

Алгоритм “сдвиг-свертка” для грамматик простого и операторного предшествования

Общий алгоритм работы синтаксического анализатора

Порядок выполнения работы

Требования к оформлению отчета

Основные контрольные вопросы

Варианты исходных грамматик

Варианты заданий

Рекомендуемая литература

Лабораторная работа 3 Построение простейшего дерева вывода Цель работы- изучение основных понятий теори

Лабораторная работа № 3 Построение простейшего дерева вывода

Краткие теоретические сведения

Распознавание цепочек КС-языков

Грамматики предшествования

Алгоритм “сдвиг-свертка” для грамматик простого и операторного предшествования

Общий алгоритм работы синтаксического анализатора

Порядок выполнения работы

Требования к оформлению отчета

Основные контрольные вопросы

Варианты исходных грамматик

Варианты заданий

Рекомендуемая литература

Лабораторная работа № 3
Построение простейшего дерева вывода