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

ФГОУ  ВПО 
«Санкт-Петербургский университет Водных Коммуникаций» 
Кафедра Вычислительных Систем и Информатики 
 
 

Курсовая  работа по курсу:

«Языки  программирования и Методы Трансляции» 
На тему :

 «Построение лексического и синтаксического анализатора» 
Вариант №15 
 
 
 
 
 
 
 
 

Выполнила студентка  факультета ИТ 
группы ИП-31 
Полугина Юлия 
Проверила: Крупенина Наталья Викторовна 
 
 
 

СПБ 2011 г.

 

Задания на Курсовую работу

1. Построить  таблицы идентификаторов метод рехеширования умножением и методом цепочек.
2. Реализовать лексический анализатор.
3. Реализовать синтаксический анализатор.

Цель  работы.

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

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

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

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

Теоретические сведения.

Для организации таблиц идентификаторов использовались следующие способы:

1)Хеш-адресация с рехешированием (рехеширование умножением).

В рехешировании умножением (в расстановке), если для элемента А адрес n₀=h(A), вычисленный с помощью хэш-функции h , указывает на уже занятую ячейку, то необходимо вычислить значение функции n₁=h₁(A) и проверить занятость ячейки по адресу n₁ и так далее, пока не будет найдена свободная ячейка, либо очередное значение h_i(A) не совпадет с h(A).

В моем случае хэш-функция  h(A)- это численное представление первой буквы идентификатора в кодировке ASCII. Рехеш-функция вычисляется как h_i=h(A)*i, где i-это шаг рехеширования.

2)Хеш-адресация с использованием метода цепочек.

1)Во все ячейки  хеш-таблицы помещаем пустое значение, таблица идентификаторов пуста, переменная FreePtr (указатель первой свободной ячейки) указывает на начало таблицы идентификаторов.

2)Вычисляем значение  хэш-функции n для нового элемента A. В моем случае хэш-функция h(A) –это численное представление первой буквы идентификатора в кодировке ASCII. Если ячейка хэш-таблицы по адресу n пустая, то поместить в нее значение переменной FreePtr и перейти к шагу 5, иначе перейти к шагу 3.

3)Выбрать из  хэш-таблицы адрес ячейки таблицы  идентификаторов m и перейти к шагу 4.

4)Для ячейки  таблицы идентификаторов по адресу  m проверить значение поля ссылки. Если оно пустое, то записать в него адрес из переменной FreePtr и перейти к шагу 5, иначе выбрать из поля ссылки новый адрес m  и повторить шаг 4.

5)Добавить в  таблицу идентификаторов новую  ячейку, записав  в нее информацию  для элемента А, (поле  ссылки должно быть пустым), в переменную FreePtr поместить адрес за концом добавленной ячейки. Если больше нет идентификаторов, которые надо поместить в таблицу, то выполнение алгоритма закончено, иначе перейти шагу 2.

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

Лексема - структурная единица языка, которая состоит из элементарных символов языка и не содержит в своем составе других структурных единиц языка.

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

      Входной язык содержит операторы условия типа if…then…else и if…then, разделенные ; (точка с запятой). Операторы условия содержат идентификаторы, знаки сравнения <,>,=, строковые константы (последовательность символов в двойных кавычках), знак присваивания (:=).

Грамматика:

 <cb>-><A-z>|<0-9>|<cb> 
<id>-><A-z>|<A-z><0-9>|<A-z><cb>

<s>-><A-z>|<0-9>|<:,=,<,>, >|<s>

<str>->”<s>”

<idcount>-><id>|<str>

<operator>-><>>|<<>|<=>

<op>-><idcount><operator><idcount>|<op><operator><op>|<op><operator><idcount>| <idcount><operator> <op>

<prisv>-><id>:=<id>|<id>:=<str>|<id>:=<op>

<allop>-><op>|<prisv>

<ifthen>->if<allop>then<allop>|if<allop>then<allop>else<allop>| if<ifthen>then<ifthen>|if<ifthen>then<ifthen>else<ifthen>|<ifthen

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

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

Исходная  грамматика для конструкции if then else

 S->F;

F->if E then T else F| if E then F| a: =E

T->if E then T else T| a: =E

E->E<D|E>D|E=D|D

D->a| c

 

Грамматика  входного языка

E-> E;

E ->if E then E else E |if E then E |a:=E

E ->if E then E else E |a:=E

E->E< E |E> E |E= E | E

E ->a| c

Упрощенная грамматик

E ->if E then E else E |if E then E |a:=E

E->E< E |E> E |E= E | E

E ->E

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

 

Генерация объектного кода – это перевод компилятором внутреннего представления исходной программы в цепочку символов входного языка.

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

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

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