Лабораторная работа № 4
Построение синтаксического анализатора

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

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

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

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

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

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

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

Анализаторы для различных типов языков

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

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

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

Распознаватели на основе МП-автоматов

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

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

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

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

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

· l(A)¸(a) - для каждого правила грамматики A®a Î P, где AÎVN, aÎV^*;

· а(а)¸() - для каждого терминала аÎVT;

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

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

· а()¸(а) - для каждого терминала аÎVT;

· l(a)¸(A) - для каждого правила грамматики A®a Î P, где AÎVN, aÎV^*;

Такой МП-автомат называют расширенным МП-автоматом, поскольку при выполнении перехода между состояниями он анализирует не один символ на верхушке стека, а цепочку символов. Для расширенного МП-автомата в начале разбора стек автомата пуст, а в конце разбора допустимой цепочки в стеке должен остаться целевой символ грамматики SÎVN.

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

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

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

Сложность синтаксического разбора. Разбор сверху вниз и снизу вверх

Программирование работы недетерминированного МП-автомата – это сложная задача. Разработан алгоритм, позволяющий для произвольной КС-грамматики определить, принадлежит ли ей заданная входная цепочка (алгоритм Кока-Янгера-Касами) [1, 2, 7, 13]. Доказано, что время работы этого алгоритма пропорционально n³, где n - длина входной цепочки. Для однозначной КС-грамматики при использовании другого алгоритма (алгоритм Эрли [1, 2, 7, 13]) это время пропорционально n². Подобная зависимость делает эти алгоритмы требовательными к вычислительным ресурсам, а потому малопригодными для практических целей.

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

В первом случае, при синтаксическом разборе сверху вниз выполняется просмотр входной цепочки слева направо, а в результате получаются левосторонние выводы [1, 2, 7, 9]. МП-автомат, лежащий в основе такого разбора, называется МП-автоматом с подбором альтернатив. Он является недетерминированным, так как нет однозначного выбора, какое правило применить для раскрытия самого левого нетерминального символа (подборе альтернативы). ДМП-автоматы, построенные на его основе, используют различные модификации, позволяющие сделать однозначный выбор правила при подборе альтернативы. Примерами таких автоматов являются разбор по методу рекурсивного спуска и распознаватель на основе LL-грамматик.

Во втором случае при синтаксическом разборе снизу вверх выполняется просмотр входной цепочки слева направо, а в результате получаются правосторонние выводы [1, 2, 7, 9]. МП-автомат, лежащий в основе такого разбора, называется МП-автоматом типа сдвиг-свертка. Это название определено тем, сто такой разбор удобно формализовать в терминах "сдвиг" (перенос символа из входной цепочки в магазин) и "свертка" (применение к вершине магазина какого-либо правила грамматики). Для построения ДМП-автоматов на основе МП-автомата типа сдвиг-свертка необходимо на каждом шаге работы автомата однозначно определить, какое действие – сдвиг или свертка – должно выполняться, а если выполняется свертка, то для нее должно однозначно выбираться правило. Примерами таких автоматов являются распознаватели на основе LR-грамматик и грамматик предшествования.

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

Синтаксический разбор на основе грамматик предшествования

Как было сказано выше, на практике не требуется анализ цепочки произвольного КС-языка – большинство конструкций языков программирования может быть отнесено в один из классов ДКС-языков, для которых разработаны алгоритмы разбора, линейно зависящие от длины входной цепочки.

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

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

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

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

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

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

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

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

Существует несколько видов грамматик предшествования. Они различаются по тому, какие отношения предшествования в них определены и между какими типами символов (терминальными или нетерминальными) могут быть установлены эти отношения. Кроме того, возможны незначительные модификации функционирования алгоритма «сдвиг-свертка» в распознавателях для таких грамматик (в основном на этапе выбора правила для выполнения свертки, когда возможны неоднозначности) [1, 2, 5].

Выделяют следующие типы грамматик предшествования:

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

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

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

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

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

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

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

Грамматикой операторного предшествования называется приведенная КС-грамматика без l-правил (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^*.

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

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

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

· построить два дополнительных множества – крайних левых и крайних правых символов относительно нетерминальных символов грамматики;

· на основе множеств крайних левых и крайних правых символов относительно нетерминальных символов грамматики построить множества крайних левых и крайних правых терминальных символов;

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

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

· L(U) = {T | $ UÞ*Tz}, U,TÎV, zÎV^* – множество крайних левых символов относительно нетерминального символа U;

· R(U) = {T | $ UÞ*zT}, U,TÎV, zÎV^* – множество крайних правых символов относительно нетерминального символа U.

В приведённых выше определениях цепочка z может быть любой произвольной цепочкой символов, в том числе и пустой цепочкой.

Множества 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, иначе построение закончено.

Далее необходимо построить множества крайних левых и крайних правых терминальных символов относительно нетерминального символа U - L^t(U) или R^t(U). Эти множества могут быть определены следующим образом:

· L^t(U) = {t | $ UÞ*tz или $ UÞ*Ctz }, где tÎVT, U,CÎVN, zÎV^*;

· R^t(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ÎL^t(C), где a,bÎVT, U,CÎVN, x,yÎV^*;

· a ×> b, если $ правило U®xCby ÎP и aÎR^t(C), где a,bÎVT, U,CÎVN, x,yÎV^*.

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

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

Шаг 1. Для каждого нетерминального символа грамматики U строятся множества L(U) и R(U). Таким образом, множества L(U) и R(U) являются исходными данными для заполнения множеств L^t(U) и R^t(U).

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

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

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

^_н <× a, " aÎVT, если $ SÞ*ax или $ SÞ*Cax, где S,CÎVN, xÎV^* или если aÎL^t(S);

^_к ×> a, " aÎVT, если $ SÞ*xa или $ SÞ*xaC, где S,CÎVN, xÎV^* или если aÎR^t(S).

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

1. Построить множества крайних левых и крайних правых символов грамматики – L(U) и R(U).

2. На основе построенных множеств L(U) и R(U) построить множества крайних левых и крайних правых терминальных символов грамматики – L^t(U) и R^t(U).

3. Используя построенные множества L^t(U) и R^t(U) на основе правил исходной грамматики заполнить матрицу операторного предшествования.

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

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

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

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

Шаг 1. Поместить в верхушку стека символ начала цепочки – ^_н.

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

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

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

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

Шаг 6. Проверить условие завершения разбора (на верхушке стека находится целевой символ грамматики S и символ ^_н, текущий входной символ – символ конца цепочки ^_к). Если разбор не закончен, то вернуться к шагу 2, иначе выполнение алгоритма завершено.

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

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

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

Рассмотрим в качестве примера грамматику 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) относительно всех нетерминальных символов грамматики. Результат построения приведен в таблице 3.

Таблица 3.

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

Символ	Шаг 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

На основе полученных множеств L(U) и R(U) построим множества крайних левых и крайних правых терминальных символов L^t(U) и R^t(U) относительно всех нетерминальных символов грамматики. Результат (второй и третий шаги построения) приведен в таблице 4.

Таблица 4.

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

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

На основе множеств L^t(U) и R^t(U) и правил грамматики G построим матрицу предшествования исходной грамматики (таблица 5).

Таблица 5.

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

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

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

Выполнив аналогичные действия для всех терминальных символов исходной грамматики, заполним всю матрицу предшествования отношениями <× и ×>. Остается добавить в неё отношения =× («составляет основу»). Для этого надо найти в исходной грамматике все правила, где два терминальных символа стоят рядом или между ними есть один нетерминальный символ. В исходной грамматике такое правило только одно: J ® (B) (правило 6). В нём терминальные символы ( и ) стоят рядом и между ними только один нетерминальный символ (символ B). При этом символ ( стоит слева, а символ ) – справа (порядок символов принципиально важен!). Тогда на пересечении строки для символа ( и столбца для символа ) ставим знак отношения =×.

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

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

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} – разбор закончен, цепочка принята.

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

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

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

2. Выполнить предварительные преобразования, необходимые для построения матрицы предшествования.

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

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

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

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

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

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

· Задание по лабораторной работе с описанием своего варианта.

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

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

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

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

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

· Выводы по проделанной работе.

Допускается оформлять единый (совместный) отчёт для лабораторных работ №4 и №5.

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

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

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

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

1. Какую роль выполняет синтаксический анализ в процессе компиляции?

2. Расскажите о классификации грамматик. Какие типы грамматик существуют?

3. Расскажите о классификации языков. Как связаны типы грамматик и языков?

4. Что такое КС-грамматики? Расскажите об их использовании в компиляторе.

5. Расскажите о грамматиках предшествования. Какие общие черты присущи всем грамматикам предшествования?

6. Расскажите о грамматиках операторного предшествования. Какие черты характеризуют грамматики операторного предшествования?

7. Дайте определения отношений предшествования для грамматик операторного предшествования.

8. Как вычисляются отношения предшествования для грамматик операторного предшествования?

9. Расскажите алгоритм построения множеств крайних левых и крайних правых символов.

10. Расскажите алгоритм построения множеств крайних левых и крайних правых терминальных символов.

11. Расскажите о задаче разбора. Что такое распознаватель языка?

12. Расскажите об общих принципах работы распознавателя языка.

13. Какие типы распознавателей существуют? Какие из них используются в компиляторе и на каких этапах?

14. Что такое МП-автомат? Расскажите о МП-автоматах.

15. Расскажите, как работает алгоритм «сдвиг-свертка» в общем случае (с возвратами).

16. Как работает алгоритм «сдвиг-свертка» для грамматик операторного предшествования? Поясните разбор предложения входного языка на своем примере.

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

Ниже приведены варианты грамматик. Во всех вариантах символ 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

5. S ® F; 6. S ® F;

F ® case E of T end | a := E F ® while T do a := E | a := E

T ® a: a := E | T; a: a := E T ® E < E | E > E | E = E

E ® E + a | E - a | a E ® E + a | E - a | a

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

Варианты заданий приведены далее в таблице 6.

Таблица 6.

Варианты заданий для лабораторной работы №4.

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

Примечание: требования к представлению римских чисел и шестнадцатеричных чисел соответствуют требованиям, изложенным в задании на лабораторную работу №2.

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

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

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

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

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

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

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

Третий шаг этого алгоритма – построение дерева вывода на основе полученной последовательности правил. Входными данными для этого шага алгоритма являются исходная грамматика и последовательность правил вывода, полученная при выполнении предыдущего шага алгоритма.

Первые два шага общего алгоритма работы синтаксического анализатора были рассмотрены выше при выполнении лабораторных работ №3 и №4. В данной лабораторной работе будет уделено внимание последнему (третьему) шагу этого алгоритма.

Вывод. Цепочки вывода

Определение вывода

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

Цепочка b = d₁gd₂ называется непосредственно выводимой из цепочки a = d₁wd₂ в грамматике G(VT,VN,P,S), V = VTÈVN, d₁,g,d₂ Î V^*, w Î V⁺, если в грамматике G существует правило: w ® g Î P. Непосредственная выводимость цепочки b из цепочки a обозначается так: a Þ b. Согласно определению при непосредственном выводе a Þ b выполняется подстановка подцепочки g вместо подцепочки w. Иными словами, цепочка b выводима из цепочки a в том случае, если можно взять несколько символов в цепочке a, поменять их на другие символы согласно некоторому правилу грамматики и получить цепочку b.

В формальном определении непосредственной выводимости любая из цепочек d₁ или d₂ (а равно и обе эти цепочки) может быть пустой. В предельном случае вся цепочка a может быть заменена цепочкой b, тогда в грамматике G должно существовать правило: a ® bÎP.

Цепочка b называется выводимой из цепочки a (обозначается a Þ* b) в том случае, если выполняется одно из условий:

· эти две цепочки совпадают (a = b);

· b непосредственно выводима из a (a Þ b);

· $ цепочка g, такая, что: g выводима из a и b непосредственно выводима из g (a Þ* g и g Þ b).

Это рекурсивное определение выводимости цепочки. Суть его заключается в том, что цепочка b выводима из цепочки a, если a Þ b или же если можно построить последовательность непосредственно выводимых цепочек от a к b следующего вида: a Þ g₁ Þ…Þ g_i Þ…Þ g_n Þ b, n ³ 1. В этой последовательности каждая последующая цепочка g_i непосредственно выводима из предыдущей цепочки g_i-1.

Такая последовательность непосредственно выводимых цепочек называется выводом или цепочкой вывода. Каждый переход от одной непосредственно выводимой цепочки к следующей в цепочке вывода называется шагом вывода. Очевидно, что шагов вывода в цепочке вывода всегда на один больше, чем промежуточных цепочек. Если цепочка b непосредственно выводима из цепочки a: a Þ b, то имеется всего один шаг вывода, если же две цепочки совпадают, то считается, что имеется ноль шагов вывода.

Если цепочка вывода из a к b содержит одну или более промежуточных цепочек (два или более шагов вывода), то она имеет специальное обозначение a Þ+ b (говорят, что цепочка b нетривиально выводима из цепочки a). Если количество шагов вывода известно, то его можно указать непосредственно у знака выводимости цепочек. Например, запись a Þ⁴ b означает, что цепочка b выводится из цепочки a за 4 шага вывода.

Левосторонний и правосторонний выводы

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

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

Для грамматик типов 2 и 3 (КС-грамматик и регулярных грамматик) для любой сентенциальной формы всегда можно построить левосторонний или правосторонний выводы. Для грамматик других типов это не всегда возможно, так как по структуре их правил не всегда можно выполнить замену крайнего левого или крайнего правого нетерминального символа в цепочке.

Сентенциальная форма грамматики. Язык, заданный грамматикой

Вывод называется законченным (или конечным), если на основе цепочки b, полученной в результате этого вывода, нельзя больше сделать ни одного шага вывода. Иначе говоря, вывод называется законченным, если цепочка b, полученная в результате этого вывода, пустая или содержит только терминальные символы грамматики G(VT,VN,P,S): bÎVT^*. Цепочка b, полученная в результате законченного вывода, называется конечной цепочкой вывода.

Цепочка символов aÎV^* называется сентенциальной формой грамматики G(VT,VN,P,S), V = VTÈVN, если она выводима из целевого символа грамматики S: S Þ* a. Если цепочка aÎVT^* получена в результате законченного вывода, то она называется конечной сентенциальной формой.

Язык L, заданный грамматикой G(VT,VN,P,S),– это множество всех конечных сентенциальных форм данной грамматики. Язык L, заданный грамматикой G, обозначается как L(G). Очевидно, что алфавитом такого языка L(G) будет множество терминальных символов грамматики VT, поскольку все конечные сентенциальные формы грамматики – это цепочки над алфавитом VT.

Следует помнить, что две грамматики G(VT,VN,P,S) и G'(VT',VN',P',S') называются эквивалентными, если эквивалентны заданные ими языки: L(G) = L(G'). Очевидно, что эквивалентные грамматики должны иметь, по крайней мере, пересекающиеся множества терминальных символов VTÇVT' ¹ Æ (как правило, эти множества даже совпадают VT=VT'), а вот множества нетерминальных символов, правила грамматики и целевой символ у них могут кардинально отличаться.

Дерево вывода. Методы построения дерева вывода

Деревом вывода грамматики G(VT,VN,P,S) называется дерево (граф), которое соответствует некоторой цепочке вывода и удовлетворяет следующим условиям:

l каждая вершина дерева обозначается символом грамматики AÎ(VTÈVNÈ{l});

l корнем дерева является вершина, обозначенная целевым символом грамматики — S;

l листьями дерева (концевыми вершинами) являются вершины, обозначенные терминальными символами грамматики или символом пустой цепочки l;

l если некоторый узел дерева обозначен нетерминальным символом AÎVN, а связанные с ним узлы — символами b₁,b₂,…,b_n; n > 0, "n³i>0: b_iÎ(VTÈVNÈ{l}), то в грамматике G(VT,VN,P,S) существует правило A®b₁,b₂,…,b_n Î P.

Из определения видно, что по структуре правил дерево вывода в указанном виде всегда можно построить только для грамматик типов 2 и 3 (контекстно-свободных и регулярных). Для грамматик других типов дерево вывода в таком виде можно построить не всегда (либо же оно будет иметь несколько иной вид).

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

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

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

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

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

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

Пример 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

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

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

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

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

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

2. Построить матрицу предшествования для заданной грамматики (по результатам лабораторной работы №4).

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

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

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

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

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

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

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

· Задание по лабораторной работе с описанием своего варианта.

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

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

· Пример построения дерева вывода.

· Текст программы (оформляется только при необходимости по согласованию с преподавателем).

· Выводы по проделанной работе.

Требования к оформлению отчета полностью соответствуют требованиям, изложенным в задании на лабораторную работу №4.

Допускается оформлять единый (совместный) отчёт для лабораторных работ №4 и №5.

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

1. Дайте определение алфавита, языка.

2. Какие способы определения языков существуют.

3. Что такое грамматика? Дайте определение грамматики.

4. Какую роль выполняет синтаксический анализ в процессе компиляции?

5. Дайте определение непосредственной выводимости цепочки символов.

6. Что такое вывод? Дайте определение цепочке вывода.

7. Дайте определение левостороннего и правостороннего вывода.

8. Что такое дерево вывода?

9. Какие методы построения дерева вывода существуют?

10. Что такое КС-грамматики? Расскажите об их использовании в компиляторе.

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

12. Что такое грамматика операторного предшествования?

13. Как вычисляются отношения для грамматик операторного предшествования?

14. Расскажите о задаче разбора. Что такое распознаватель языка?

15. Расскажите об общих принципах работы распознавателя языка.

16. Поясните построение дерева вывода на своем примере

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

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

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

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

Варианты заданий полностью соответствуют вариантам, указанным в задании на лабораторную работу №4.