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

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 Описание семантики входного языка

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

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

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

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

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

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

Оператор цикла с постусловием 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 Описание типов лексем

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

·   идентификаторы;

·   целые беззнаковые константы;

·   строковые константы;

·   ключевые слова входного языка;

·   однолитерные и двулитерные разделители.

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

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

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

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

·   класс «буква»: a A … z Z

·   класс «цифра»: 0 1 2 3 4 5 6 7 8 9

·   класс «однолитерные разделители»:;, + - * / = () []

·   класс «литеры однолитерных и двулитерных разделителей»: < > =:.

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

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

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

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

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

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

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

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

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

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