Синтаксический анализатор

 

1. Задание на курсовую работу

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

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

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

Язык должен допускать использование логических выражений, в состав которых могут входить отношения, круглые скобки и знаки логических операций: И, ИЛИ, НЕ и, в случае наличия в языке логического типа, константы и переменные этого типа. Приоритет операций обычный.

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

Состав операторов языка:

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

·оператор ввода;

·оператор вывода;

·составной оператор;

·оператор безусловного перехода;

·условный оператор, условие в котором задается логическим выражением;

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

Конкретный вид операторов определяется вариантом задания.

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

Исходная постановка задачи

Базовый язык - Паскаль.

Базовые типы: целый, символьный, ограниченный.

Структурированный тип: символьная строка.

Операции над строками: определение длины строки, конкатенация строк, замена подстроки в строке, поиск подстроки в строке, доступ к элементу строки по индексу, доступ к подстроке.

Оператор цикла - с постусловием.

Перегрузка операций - не разрешается.

Эквивалентность типов - именная.

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

Промежуточный язык - тетрады.

2. Описание входного языка

.1 Описание синтаксиса входного языка

синтаксис лексема анализатор язык

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

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

Для описания синтаксиса языков программирования наибольшее распространение получила форма Бэкуса-Наура и ее различные модификации

Форма Бэкуса-Наура

Форма Бэкуса-Наура (БНФ) представляет собой очень естественный способ описания синтаксиса. В БНФ каждое определяемое понятие - это металингвистическая переменная. Значением металингвистической переменной может быть любая конструкция из некоторого фиксированного для этого понятия набора конструкций. Каждая металингвистическая форма определяет одну металингвистическую переменную и состоит из двух частей: левой и правой. В левой части записывается определяемая металингвистическая переменная, которая заключается в угловые скобки '<' и '>' (предполагается, что эти скобки являются метасимволами и не принадлежат алфавиту определяемого языка), например: <двоичное число>, <метка>, <арифметическое выраже-ние>. В правой части формы записываются все варианты определения конструкции, задаваемой этой формой. Каждый вариант представляет собой цепочку основных символов определяемого языка и металингвистических переменных. Варианты разделяются металингвистической связкой '|', имеющей смысл «или». Левая и правая части формы разделяются метасимволом ':=', означающим «по определению есть».

На практике для описания синтаксиса языков программирования часто используют расширения БНФ, позволяющие более естественно представлять альтернативные, необязательные и повторяющиеся части металингвистических формул. Так, одно из расширений БНФ (РБНФ) разрешает использовать следующие упрощения:

1.необязательные элементы синтаксической конструкции заключаются в квадратные скобки ' [' и ']';

2.альтернативные варианты могут в случае необходимости заключаться в квадратные скобки для образования многовариантного выбора;

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

Форма Бэкуса-Наура для задания

<программа>:=[program <идентификатор>] {<описание объектов программы>;}<раздел операторов>.

<описание объектов программы>:=<раздел меток>|<раздел описания типов>|<раздел описания переменных>|<раздел описания констант>

<раздел меток>:= label <метка> {,<метка>}

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

<раздел описания типов>:= type <определение типа> {;<определение типа>}

<определение типа>:=<имя типа>=<тип>

<имя типа>:= <идентификатор>

<тип>:=<простой тип>|<составной тип>|<имя типа>

<простой тип>:=integer|char|<диапазонный тип>

<составной тип>:=<строка>

<строка>:=string

<диапазонный тип>:=<константа>..<константа>

<раздел описания констант>:= const <определение константы> {;<определение константы>}

<определение константы>:=<имя константы>=<простое выражение>

<имя константы>:=<идентификатор>

<константа>:=<целое число>|<имя константы>

<раздел описания переменных>:= var <описание переменных>{;<описание переменных>}

<описание переменных>:= <перечень имен>: <тип>

<перечень имен>:=<идентификатор> {,<идентификатор>}

<раздел операторов>:=<составной оператор>

<составной оператор>:= begin <последовательность операторов> end

<последовательность операторов>:=<оператор>{;<оператор>}

<оператор>:= [метка:] <непомеченный оператор>

<непомеченный оператор>:= <оператор присваивания>|<оператор ввода>|<оператор вывода>|<составной оператор>|<оператор безусловного перехода>|<условный оператор>|<цикл с постусловием>|<операции над строками>

<оператор присваивания>:=<переменная>:=<простое выражение>

<оператор ввода>:= read (<перечень имен>)

<оператор вывода>:= write (<перечень выражений>)

<перечень выражений >:=<простое выражение>{,<простое выражение>}

<оператор безусловного перехода>:= goto <метка>

<условный оператор>:=if <условие> then <оператор> [else <оператор>]

<цикл с постусловием>:= repeat <последовательность операторов> until <условие>

<условие>:=<логическое выражение>

<операции над строками>:=<определение длины строки> |<конкатенация строк>|<замена подстроки в строке>|<поиск подстроки в строке>|<доступ к элементу строки по индексу>|<доступ к подстроке>|<равенство строк>

<определение длины строки>:=length (<строка>)

<конкатенация строк>:=concat (<строка>,<строка>)

<замена подстроки в строке>:=replace (<строка>,<подстрока>,<новая строка>)

<поиск подстроки в строке>:=pos (<строка>,<подстрока>)

<доступ к элементу строки по индексу>:=StrChar (<строка>,<целое без знака>)

<доступ к подстроке>:= copy (<строка>,<целое без знака>,<целое без знака>)

<равенство строк>:= Same (<строка>,<строка>)

<подстрока>:=<строка>

<новая строка>:=<строка>

<простое выражение>:= <терм 1><остаток суммы>

<остаток суммы>:=?|+<терм 1><остаток суммы>|-<терм 1><остаток суммы>

<терм 1>:=<терм 2><остаток произведения>

<остаток произведения>:=?|*<терм 2><остаток произведения>|/<терм 2><остаток произведения>

<терм 2>:=<переменная>|<константа>|(< простое выражение>)|<оператор преобразования типов>

<оператор преобразования типов>:=<тип>(<простое выражение>)

<Логическое выражение>:= <Лог_терм 1><остаток Лог_суммы>

<остаток Лог_суммы>:=?| or <Лог_терм 1><остаток суммы>

<Лог_терм 1>:=<Лог_терм 2><остаток Лог_произведения>

<остаток Лог_произведения>:=?|and <Лог_терм 2><остаток Лог_произведения>

<Лог_терм 2>:=<выражение сравнения>|(<Логическое выражение>)|<вызов функции>|not <Лог_терм 2>

<выражение сравнения>:=<простое выражение><знак сравнения><простое выражение>

<знак сравнения>:=<|>|<=|>=|<>|=

.2 Описание семантики входного языка

Представление данных различных типов в оперативной памяти

ТипРазмер, байтДиапазон значенийInteger2-32768..32767Char1-128…127

Входной язык также поддерживает ограниченный тип.

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

Операции входного языка и их приоритет

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

Знак операцииПорядок выполнения и особенности использованияСемантический смысл-Слева направо, УнарныйУнарный минус, определен для числовых переменных, возвращает переменную такого же типа, что и получает. Меняет знак числа на противоположный.*Слева направо, БинарныйУмножение, определено для числовых переменных. Результат вычисляется в наибольшем типе среди указанных операндов/Слева направо, БинарныйДеление с отбрасыванием дробной части, определено для числовых переменных. Результат вычисляется в наибольшем типе среди указанных операндов+Слева направо, БинарныйСложение, определено для числовых переменных. Результат вычисляется в наибольшем типе среди указанных операндов-Слева направо, БинарныйВычитание, определено для числовых переменных. Результат вычисляется в наибольшем типе среди указанных операндов=, <>, <, >, <=, >=Слева направо, БинарныйОперации сравнения, определены для числовых переменных. Необходимы только для формирования условияnotСлева направо, УнарныйЛогическое НЕ, определено для операций сравнения. Необходимо только для формирования условияandСлева направо, БинарныйЛогическое И, определено для операций сравнения. Необходимо только для формирования условияorСлева направо, БинарныйЛогическое ИЛИ, определено для операций сравнения. Необходимо только для формирования условия

Конструкции входного языка

Оператор цикла с постусловием repeat-until.

<цикл с постусловием>:= repeat <последовательность операторов> until <условие>

1.Выполняется оператор (Тело цикла).

2.Вычисляется условие.

.Выполняется переход на пункт 1 в случае, если условие не выполнилось.

Оператор присваивания:=

<оператор присваивания>:=<переменная>:= <простое выражение>

1.Вычисляется выражение, стоящее справа от знака присваивания

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

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

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

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

Оператор безусловного перехода goto.

<оператор безусловного перехода>:=goto <метка>

Выполняется переход на метку

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

Условный оператор if-then-else:

<условный оператор>:=if <условие> then <оператор1> [else <оператор2>]

Вычисляется значение логического выражения и выполняется в переход на оператор2, если условие не выполнилось. Иначе выполняется оператор1 и происходит безусловный переход на конец оператора if-then-else.

Оператор ввода read.

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

Оператор вывода write.

Оператор write вычисляет значение первого выражения в строке вывода и выводит его на экран. Затем то же самое производится со всеми последующими выражениями.

3. Лексический анализатор

.1 Описание типов лексем

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

• идентификаторы;
• целые беззнаковые константы;
• строковые константы;
• ключевые слова входного языка;
• однолитерные и двулитерные разделители.
• Соотношение между токенами и лексемами для различных языковых конструкций иллюстрируется следующей таблицей:

ТокенЛексемыЯзыковая конструкцияidcount, indexИдентификаторsconHello, WorldСтрокаnat0, 1, 3, 943Целое число без знакаprogram, begin, end, label, const, var, type, integer, char, string, read, readln, write, writeln, goto, if, then, else, repeat, until, length, concat, replace, pos, StrChar, copy, Same, and, or, notprogram, begin, end, label, const, var, type, integer, char, string, read, readln, write, writeln, goto, if, then, else, repeat, until, length, concat, replace, pos, StrChar, copy, Same, and, or, notКлючевые слова program, begin, end, label, const, var, type, integer, char, string, read, readln, write, writeln, goto, if, then, else, repeat, until, length, concat, replace, pos, StrChar, copy, Same, and, or, not:=:=Оператор присваивания==Операция «равно»<<Операция «меньше»>>Операция «больше»<=<=Операция «меньше равно»>=>=Операция «больше равно»<><>Операция «неравно»++, -Операция типа «сложение»**, /Операция типа «умножение»((Открывающая круглая скобка))Закрывающая круглая скобка[[Открывающая квадратная скобка]]Закрывающая квадратная скобка;;Символ «;»,,Символ «,»::Символ «:»..Символ конца программы

• 3.2 Определение синтаксиса лексем

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

Классы литер, с помощью которых записываются программы на входном языке:

• класс «буква»: a A … z Z
• класс «цифра»: 0 1 2 3 4 5 6 7 8 9
• класс «однолитерные разделители»:;, + - * / = () []
• класс «литеры однолитерных и двулитерных разделителей»: < > =:.

Составление автоматных грамматик, описывающих синтаксис лексем

Терминальными символами грамматики являются классы литер, а начальным символом грамматики - символ S.

1)Автоматная грамматика, описывающая синтаксис лексем «идентификатор» и «ключевое слово». Здесь «Буква» - класс «буква», «Цифра» - класс «цифра», «e1» - класс, включающий все литеры, за исключением букв, цифр и знака подчеркивания.

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

SàБуква IdSà_ IdIdàБуква IdIdàЦифра IdIdà_ IdIdàe1

2)Автоматная грамматика, описывающая синтаксис лексемы «целая константа без знака». Здесь «Цифра» - класс «цифра», «e3» - класс, включающий все литеры, за исключением цифр.

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

SàЦифра CCàЦифра CCàe3

3)Автоматная грамматика, описывающая синтаксис лексемы «строковая константа». Здесь «НE » - любой символ, кроме.

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

Sà TTàНЕ TTà

4)Автоматные грамматики, описывающие синтаксис лексем «однолитерный разделитель» и «двулитерный разделитель». Здесь «Знак» - классы «однолитерные разделители» и «литеры однолитерных и двулитерных разделителей», «e4» - класс, включающий все литеры.

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

однолитерные разделители:SàЗнак LLàe4

лексема «:=»Sà: NextNextà= EEàe4

лексема «<=»Sà< NextNextà= EEàe4

лексема «>=»Sà> NextNextà= EEàe4

лексема «<>»Sà< NextNextà> EEàe4

лексема «.»SàNextNextàEEàe4

.3 Построение диаграммы лексического анализатора

Построение графов конечных автоматов для распознавания лексем

Здесь S - начальное состояние конечного автомата, F - конечное состояние, соответствующее концу разбора лексемы.

1.Граф конечного автомата для распознавания лексем «идентификатор» и «ключевое слово».

2.Граф конечного автомата для распознавания лексемы «целая константа без знака».

3.Граф конечного автомата для распознавания лексемы «строковая константа».

4.Графы конечных автоматов для распознавания лексем «однолитерный разделитель» и «двулитерный разделитель». Здесь «Знак1» - включает литеры класса «однолитерные разделители».

Диаграмма лексического анализатора

Здесь «Пробел» - класс, включающий пробелы, символы табуляции и перевода строки, «Не}» - класс, включающий все литеры кроме литеры «}».

Спецификации функций лексического анализатора

1)Процедура ReadLexem(Text) - считывает лексему из входного потока и распознает ее тип.

Вход: входной поток литер текста программы.

)Процедура GetLexem (Type, Lexem) - в зависимости от типа переданной лексемы вызывает одну из процедур:

• GetId(Lexem) - для лексем «идентификатор» и «ключевое слово»;
• GetNum(Lexem) - для лексем «целая константа без знака»;
• GetSCon(Lexem) - для лексем «строковая константа»;
• GetLet(Lexem) - для лексем «однолитерный разделитель» и «двулитерный разделитель»;

Вход: лексема и ее тип.

3)Процедура GetId(Lexem) - если переданная лексема является ключевым словом, определяет ее адрес(pos) в таблице ключевых слов и вызывает процедуру WriteToken (Key, pos); в противном случае ищет запись(pos) об этой лексеме в таблице идентификаторов, если находит, то вызывает процедуру WriteToken (Id, pos), иначе вызывает процедуру AddLexem (Id, Lexem);

Вход: лексема типа «идентификатор» или «ключевое слово».

4)Процедура GetNum(Lexem) - ищет запись(pos) о переданной лексеме в таблице констант, если находит, то вызывает процедуру WriteToken (Num, pos), иначе вызывает процедуру AddLexem (Num, Lexem);

Вход: лексема типа «целая константа без знака».

5)Процедура GetLet(Lexem) - определяет адрес(pos) лексемы в таблице разделителей и вызывает процедуру WriteToken (Let, pos);

Вход: лексема типа «однолитерный разделитель» или «двулитерный разделитель»;.

6)Процедура AddLexem (Type, Lexem) - добавляет запись(pos) о лексеме в таблицу лексем заданного класса и вызывает процедуру WriteToken (Type, pos);

Вход: лексема и ее тип.

7)Процедура WriteToken (Type, Position) - формирует токен и записывает его в выходной поток токенов.

Вход: номер лексемы в соответствующей таблице лексем.

.4 Таблицы лексем

1. Таблица ключевых слов

Таблица ключевых словимя ключевого слова

Таблица идентификаторов

Таблица идентификаторовимяТипзначение

Таблица целых констант

Таблица целых константзначение

Таблица разделителей

Таблица разделителейРазделитель

Таблица строковых констант

Таблица строковых константзначение

Таблица пользовательских типов. (Заполняется на этапе синтаксического анализа)

Таблица пользовательских типовИмяНачалоКонец

Таблица меток (Заполняется на этапе синтаксического анализа)

Таблица метокИмяНомер тетрады

Таблица строковых переменных. (Заполняется на этапе синтаксического анализа)

Таблица строковых переменныхИмяДлинаЗначение

Таблица промежуточных значений. (Заполняется на этапе синтаксического анализа)

Таблица промежуточных значенийТипЗначение

.5 Тестирование лексического анализатора

Тестовая программаВыходной поток токеновprogram Test; const C=10; type TCounter=0..C; var i:TCounter; CurEl:integer; summa:integer; begin writeln (Hello World!!!); i:=0; summa:=0; repeat read(CurEl); summa:=summa+CurEl; i:=i+1; until i=C; write(summa); end.program 1 1 id 2 1; 4 1 const 1 2 id 2 2 = 4 2 nat 3 1; 4 1 type 1 15 id 2 3 = 4 2 nat 3 2. 4 19 id 2 2; 4 1 var 1 3 id 2 4: 4 4 id 2 3; 4 1 id 2 5: 4 4 integer 1 4; 4 1 id 2 6: 4 4 integer 1 4; 4 1 begin 1 7 writeln 1 17 (4 9 scon 5 1) 4 10; 4 1 id 2 4:= 4 7 nat 3 2; 4 1 id 2 6:= 4 7 nat 3 2; 4 1 repeat 1 8 read 1 10 (4 9 id 2 5) 4 10; 4 1 id 2 6:= 4 7 id 2 6 + 4 12 id 2 5; 4 1 id 2 4:= 4 7 id 2 4 + 4 12 nat 3 3; 4 1 until 1 9 id 2 4 = 4 2 id 2 2; 4 1 write 1 11 (4 9 id 2 6) 4 10; 4 1 end 1 12. 4 13Таблицы ключевых слов и разделителей - статические, таблицы идентификаторов и констант заполняются в процессе лексического и синтаксического анализа.

Статические таблицы лексем

1. Таблица ключевых слов4. Таблица разделителей1program1;2const2=3var3,4integer4:5char5[6string6]7begin7:=8repeat8<=9until9(10read10)11write11*12end12+13and13.14label14<15type15>16readln16>=17writeln17<>18goto18/19if19.20then21else22length23concat24replace25pos26StrChar27copy28Same29or30not

4. Синтаксический анализатор

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

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

.1 Построение КС-грамматики входного языка

Для построения КС-грамматики входного языка необходимо:

1.Заменить металингвистические переменные БНФ обозначениями нетерминальных символов, используя короткие имена;

2.В качестве терминальных символов использовать токены;

.Металингвистический символ «:=» заменить символом «à»;

.Заменить одну металингвистическую формулу с n альтернативами на n правил грамматики с одинаковым символом в левой части правила вывода;

.Исключить металингвистические символы [] и {}, включив в правила грамматики e-правила и рекурсивные правила.

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

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

Синтаксический анализ, основанный на простом предшествовании, использует для выделения основы правовыводимой цепочки ??w три отношения предшествования (<), (=) и (>) следующим образом:

·если ? - основа, то между всеми смежными символами цепочки ? выполняется либо отношение (<), либо (=);

·между последним символом цепочки ? и первым символом цепочки ? выполняется отношение (<);

·между смежными символами основы выполняется отношение (=);

·между последним символом цепочки ? и первым символом цепочки w выполняется отношение (>).

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

Отношения предшествования для КС-грамматики G = (N, ?, Р, S) определяются на множестве (N U ? U {?}) × (N U ? U {?}) следующим образом:

·X < У, если в множестве правил грамматики Р есть правило А -> ?XB? и существует вывод В =>+ Y?;

·X = Y, если в Р содержится правило вида А -> ?XY?;

·X > а, если в Р есть правило вида А -> ?BY? и существуют выводы В =>+ ?X и Y => а? (если У=>° а?, то Y= а);

·? < X для всех X, для которых S =>+ Х?;

·Y > ? для всех Y, для которых S =>* ?Y.

КС-грамматика G = (N, ?, P, S) называется грамматикой предшествования, если она приведенная, не содержит ? - правил и для любой пары символов из множества N U ? выполняется не более одного отношения предшествования.

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

Построение грамматики по БНФ

S -> pro id; Def BOp.-> pro id; BOp.-> Def BOp.-> BOp.

-> DfL Def-> DfL-> DfC Def-> DfC-> DfT Def-> DfT-> DfV Def-> DfV

-> lab LLb-> M;-> M, LLb

-> con LCn-> Cn1; LCn-> Cn1;-> id = Pex

-> typ LTp-> Tp1; LTp-> Tp1;-> id = Typ-> id = id-> Cid. Cid-> int-> chr-> str

-> var LVr-> DV1;-> DV1; LVr-> id-> Vr1, id-> Vr1-> Vrs: id-> Vrs: int-> Vrs: chr-> Vrs: str

-> id-> nat

-> M: Op-> Op-> BOp-> O:=-> OIO-> OMn

-> beg OPs end-> Op1-> Opl-> Opl; Op1

:= -> id:= Pex

-> OIn-> OOu-> rd (Vrs)-> wr (LWr)-> Pex-> Pex, W1-> W1

-> ORu-> OGo-> OIf-> rpt Ops unt Lex-> got M-> if Lex thn Opl-> if Lex thn Opl els Opl

-> Z1 F1-> Z1-> Z2 F2-> Z2-> Z3-> not Z3-> Z4-> sme (str, str)-> Pex Sgn Pex-> (Lex)-> or Z1 F1-> or Z1-> and Z2 F2-> and Z2-> <-> >-> =-> <=-> >=-> <>

-> T1 E1-> T1-> + T1 E1-> + T1-> - T1 E1-> - T1-> * T2 E2-> * T2-> / T2 E2-> / T2-> T2 E2-> T2-> id-> Cid-> Scn-> Fun-> (Pex)

Fun -> int (Pex)-> str (Pex)-> lng (Pex)-> cnc (Pex, Pex)-> pos (Pex, Pex)-> sym (Pex, Pex)

-> - nat-> nat

-> ' Sms '-> ' '-> Sym-> Any -> Any Sym

.2 Разбиение грамматики на подграмматики

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

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

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

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

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

2.Основной символ подграмматики становится (специальным) терминальным символом исходной грамматики.

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

1. Базовая грамматика программы GR1 (Начальный символ S)

Терминалы:= program; id = идент; =;

Def = *БлокОпис; BOp = *БлокОпер; =.;

Нетерминалы:

S = НачСимвол 4;

Правила:

) S -> pro id; Def BOp.

) S -> pro id; BOp.

) S -> Def BOp.

4) S -> BOp.

. Грамматика раздела описаний GR2 (Начальный символ Def)

Терминалы:

DfL = ОписМеток; DfC = ОписКонст; DfT = ОписТипов;

DfV = ОписПерем;

Нетерминалы:

Def = *БлокОпис 8;

Правила:

) Def -> DfL Def

) Def -> DfL

) Def -> DfC Def

) Def -> DfC

) Def -> DfT Def

) Def -> DfT

) Def -> DfV Def

) Def -> DfV

3. Грамматика описания меток GR3 (Начальный символ DfL)

Терминалы:

lab = label; =;, =;

id = идент; nat = ЦелБезЗнак;

Нетерминалы:

DfL = *ОписМеток 1; M = Метка 2;

LLb = СписокМеток 2;

Правила:

) DfL -> lab LLb

2) LLb -> M;

) LLb -> M, LLb

) M -> id

5) M -> nat

. Грамматика описания констант GR4 (Начальный символ DfC)

Терминалы:

con = const; =; = = =;

id = идент; Pex = *выражение;

Нетерминалы:

DfC = *ОписКонстант 1; LCn = СписокКонстант 2;

Cn1 = ОписКонстанты 1;

Правила:

) DfC -> con LCn

) LCn -> Cn1; LCn

) LCn -> Cn1;

) Cn1 -> id = Pex

. Грамматика описания типов GR5 (Начальный символ DfT)

Терминалы:

typ = type; =; = = =;

id = идент; Сid = *КонстИден; int = integer;

chr = char; =.; str = string;

Нетерминалы:

DfT = *ОписТипов 1; LTp = СписокТипов 2;= ОписТипа 2; Typ = Тип 4;

Правила:

) DfT -> typ LTp

) LTp -> Tp1; LTp

) LTp -> Tp1;

) Tp1 -> id = Typ

) Tp1 -> id = id

) Typ -> Cid. Cid

) Typ -> int

) Typ -> chr

9) Typ -> str

6. Грамматика описания переменных GR6 (Начальный символ DfV)

Терминалы:= var; =;, =;

: =:; id = идент; int = integer;= char; str = string;

Нетерминалы:

DfV = *ОписПеременных 1; LVr = СписокОписПерем 2;

Vr1 = Перемен 2; Vrs = СписокПеременных 1;

DV1 = 1ОписПеремен 4;

Правила:

) DfV -> var LVr

2) LVr -> DV1;

) LVr -> DV1; LVr

) Vr1 -> id

) Vr1 -> Vr1, id

) Vrs -> Vr1

) DV1 -> Vrs: id

) DV1 -> Vrs: int

) DV1 -> Vrs: chr

10) DV1 -> Vrs: str

. Грамматика меток GR7 (Начальный символ M)

Терминалы:= идент; nat = ЦелБезЗнак;

Нетерминалы:

M = *Метка 2;

Правила:

) M -> id

) M -> nat

. Грамматика описания операторов GR8 (Начальный символ opl)

Терминалы:

M = *метка;: =:; O:= = *ОпПрисв;

OIO = *ОпВв / Выв; OMn = *ОперУправ; BOp = *БлокОпер;

Нетерминалы:

Opl = *Оператор 2; Op = НепомечОпер 4;

Правила:

) Opl -> M: Op

) Opl -> Op

) Op -> BOp

) Op -> O:=

) Op -> OIO

) Op -> OMn

9. Грамматика блока операторов GR9 (Начальный символ BOp)

Терминалы:= begin; end = end; =;

Opl = *Оператор;

Нетерминалы:

BOp = *БлокОпер 1; OPs = Набор операторов 1;

Op1 = Оператор 2;

Правила:

) BOp -> beg OPs end

2) OPs -> Op1

) Op1 -> Opl

) Op1 -> Opl; Op1

10. Грамматика оператора присваивания GR10 (Начальный символ O:=)

Терминалы:= идент;:= =:=; Pex = *выражение;

Нетерминалы:

O:= = *ОпПрисв 1;

Правила:

) O:= -> id:= Pex

. Грамматика операторов ввода / вывода GR11 (Начальный символ OIO)

Терминалы:= readln; wr = writeln; (= (;

) =); Pex = *выражение;, =;

id = идент;

Нетерминалы:

OIO = *ОпВв / Выв 2; OIn = ОперВвода 1;= ОперВывода 1; W1 = Аргумент вывода 2;

LWr = СписВыраж 1; Vrs = СписПерем 1;

Vr1 = Перемен 2;

Правила:

) OIO -> OIn

) OIO -> OOu

) OIn -> rd (Vrs)

) OOu -> wr (LWr)

) W1 -> Pex

) W1 -> Pex, W1

) LWr -> W1

) Vrs -> Vr1

) Vr1 -> id

10) Vr1 -> id, Vr1

. Грамматика операторов управления GR12 (Начальный символ OMn)

Терминалы:= repeat; unt = until; Opl = *Оператор;

Lex = *ЛогВыраж; got = goto; if = if;= then; els = else; M = *Метка;

; =;

Нетерминалы:

OMn = *ОперУправ 3; ORu = ОперЦикла 1;

OGo = ОперПерехода 1; OIf = ОперУсловия 2;

Ops = Операторы 1; Op1 = Оператор 2;

Правила:

) OMn -> ORu

) OMn -> OGo

) OMn -> OIf

4) ORu -> rpt Ops unt Lex

) OGo -> got M

) OIf -> if Lex thn Opl

) OIf -> if Lex thn Opl els Opl

) Ops -> Op1

) Op1 -> Opl;

) Op1 -> Opl; Op1

13. Грамматика логических выражений GR13 (Начальный символ Lex)

Терминалы:

> = >; < = <; = = =;

>= = >=; <= = <=; <> = <>;

(= (;) =); or = or;= and; not = not; Pex = *выражение;= строка; sme = Same;, =;

Нетерминалы:

Lex = *ЛогВыраж 2; Z1 = 2;= 1; Z3 = 2;4 = 3; F1 = 2;

F2 = 2; Sgn = знак сравнения 6;

Правила:

) Lex -> Z1 F1

) Lex -> Z1

3) Z1 -> Z2 F2

) Z1 -> Z2

) Z2 -> Z3

) Z3 -> not Z3

) Z3 -> Z4

) Z4 -> sme (str, str)

) Z4 -> Pex Sgn Pex

) Z4 -> (Lex)

) F1 -> or Z1 F1

) F1 -> or Z1

) F2 -> and Z2 F2

) F2 -> and Z2

) Sgn -> <

) Sgn -> >

17) Sgn -> =

) Sgn -> <=

) Sgn -> >=

) Sgn -> <>

. Грамматика простых выражений GR14 (Начальный символ Pex)

Терминалы:

+ = +; - = -; * = *,/;

(= (; / = /;) =);

id = идент; Cid = *КонстИден; Scn = *СтрокКонст;

Fun = *функция;

Нетерминалы:

Pex = *выражение 2; E1 = 2;= 2; T1 = 2;= 5;

Правила:

) Pex -> T1 E1

2) Pex -> T1

) E1 -> + T1 E1

) E1 -> + T1

) E1 -> - T1 E1

) E1 -> - T1

) E2 -> * T2 E2

) E2 -> * T2

) E2 -> / T2 E2

) E2 -> / T2

) T1 -> T2 E2

) T1 -> T2

) T2 -> id

) T2 -> Cid

) T2 -> Scn

) T2 -> Fun

) T2 -> (Pex)

15. Грамматика вызова фукций GR15 (Начальный символ Fun)

Терминалы:= integer; str = string; lng = length;= concat; pos = pos; sym = StrChar;

(= (;) =);, =;

Pex = *выражение;

Нетерминалы:

Fun = *функция 6;

Правила:

) Fun -> int (Pex)

) Fun -> str (Pex)

) Fun -> lng (Pex)

) Fun -> cnc (Pex, Pex)

) Fun -> pos (Pex, Pex)

) Fun -> sym (Pex, Pex)

16. Грамматика целых констант GR16 (Начальный символ Cid)

Терминалы:= ЦелБезЗнак; - = -;

Нетерминалы:

Cid = *КонстИден 2;

Правила:

) Cid -> - nat

) Cid -> nat

. Грамматика строковых констант GR17 (Начальный символ Scn)

Терминалы:= Любой символ; ' = ';

Нетерминалы:

Scn = *СтрокКонст 2; Sms = список символов 1;= символ 2;

Правила:

) Scn -> ' Sms '

2) Scn -> ' '

) Sms -> Sym

) Sym -> Any

5) Sym -> Any Sym

.3 Описание промежуточного языка

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

Формат тетрад:

<код операции>, <операнд_1>, <операнд_2>, <результат>,

где <операнд_1> и <операнд_2> специфицируют аргументы, а <результат> - временное имя для хранения результата выполнения операции (переменная из рабочей области).

В качестве операндов тетрад наряду с переменными и константами, определенными в исходной программе, могут выступать результаты ранее выполненных тетрад. Например, выражение a* b + с* d представляется в виде последовательности следующих тетрад:

*, a, b, t1

*, c, d, t2

+, t1, t2, t3

Последовательность тетрад представляет собой программу, инструкции которой обрабатываются последовательно. Операнды одной тетрады должны быть одинакового типа. Для преобразования типа операнда можно использовать тетрады преобразования типа с кодами операций ITOS (целый - в строкоый) и STOI (строковый - в целый). Поскольку операция преобразования типа одноместная, она записывается с пустым вторым операндом, например, STOI, а, t.

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

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

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

синтаксис лексема анализатор язык

Описание тетрадСинтаксисСемантикаКопОп1Оп2РезBRLLБезусловный переход на метку LBFLRПереход на метку L, если R = «Ложь»DEFLLОпределение метки LWRTAВывод значения А на экранREDAЗапрос на ввод с клавиатуры значения переменной ACRLFВозврат каретки и перевод строкиSETARНазначает тип A для переменной RCHTPABRПреобразует тип выражения A к типу B=IABRоперация «равно» для целых значений A и B=CABRоперация «равно» для символьных значений A и B<IABRоперация «меньше» для целых значений A и B>IABRоперация «больше» для целых значений A и B<=IABRоперация «меньше равно» для целых значений A и B>=IABRоперация «больше равно» для целых значений A и B<>IABRоперация «неравно» для целых значений A и B<>CABRоперация «неравно» для символьных значений A и B:=BAA:= B+IABRR:= A + B-IABRR:= A - B*IABRR:= A * B/IABRR:= A / BORABRR:= A or BANDABRR:= A and B-IARR:= - ANOTARR:= not ALENARОпределение длины строкиCNCABRКонкатенация строкPOSABRПоиск подстроки в строкеSTCHABRВозврат из строки A символа с номером BSTOIARПреобразует строку A в целое числоITOSARПреобразует целое число A в строкуSMEABRСравнение двух строк

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

Больше работ по теме: