Санкт-Петербургский Государственный Электротехнический Университет

Кафедра ВТ

Курсовой проект по дисциплине

«Формальные языки, грамматики и автоматы»

Построение атрибутного преобразователя.

Выполнил: Соколов Д. О.

Группа: 0361

Проверил: Головкин Д. Б.

Санкт-Петербург 2002 год

Содержание:

1. Задание

2. Построение символьного преобразователя

1. Входная грамматика в структурированной форме

2. СУ-схема и транслирующая грамматика

3. Функции переходов преобразователя

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

1. Грамматика лексических единиц и структура лексем

2. Диаграмма состояний лексического анализатора

3. Структуры данных и символы действия

4. Структура программы лексического анализатора

4. Семантика перевода

1. Неформальное описание семантики

2. Атрибутная грамматика

3. Описание символов действия

4. Пример вывода в атрибутной грамматике

5. Атрибутный преобразователь

1. Построение функций переходов атрибутного преобразователя

2. Построение инструкций атрибутного преобразователя

3. Фрагмент работы атрибутного преобразователя

6. Программная реализация атрибутного преобразователя

1. Описание структур данных

2. Структура программы на уровне функций

3. Спецификация функций

1. Задание

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

Вариант № 48

Конструкции языка программирования состоят из последовательностей описаний переменных (char,boolean), описаний массивов и операторов присваивания с логическими выражениями (операции: &(and),v(or), /(not) ).

Форма языка – тэговая.

Примеры, поясняющие смысл задания:

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

<char> c0, <arr> ca2, 2 </arr> </char>

<boolean> <arr> ba5, 5 </arr> , b </boolean>

<ass> <earr> ba5, 1 </earr>, <and> ‘true’, <or> <not> b</not>, ‘false’ </or> </and> </ass>

После символьного преобразования цепочка примет вид:

C0 "CHAR" CA2 "CHAR" 2 "RM"

Ba5 "BOOL" 5 "RM" B "BOOL"

Ba5 1 "EM" 'TRUE' B! 'FALSE'V&=

На выходе атрибутный преобразователь должен построить последовательность атомов вида:

(знак операции, А1, А2, А3)

где:

знак операции – символ операции;

А1 – первый операнд

А2 – второй операнд

А3 – ячейка таблицы значений для сохранения результата вычисления.

2. Построение символьного преобразователя

2.1. Входная грамматика в структурированной форме

<I>::=<Vars><Code> -- вывод раздела описаний и операций

-- Терминальные символы --

<Bukva> ::= a|b|c|d|e -- буквы

<Zifra>::=0|1|2|3|4|5|6|7|8|9 -- цифры

<Const>::="'true'"|"'false'" -- константы

<Simvol>::="'a'"|"'b'"|"'c'"|"'d'"|"'e'" -- символы

-- Идентификатор --

<ID>::=<Bukva><R1> -- вывод первой буквы идентификатора

<R1>::=<Bukva><R1> -- вывод последующей буквы ид-ра

<R1>::=<Zifra><R1> -- вывод последующей цифры ид-ра

<R1>::=$ -- конец вывода ид-ра

-- Целое число --

<Chislo>::=<Zifra><R2> -- вывод первой цифры числа

<R2>::=<Zifra><R2> -- вывод последующей цифры числа

<R2>::=$ -- конец вывода числа

-- Массив --

<MasBool>::='<arr>'<ID>','<Chislo>'</arr>' -- вывод массивов

<MasChar>::='<arr>'<ID>','<Chislo>'</arr>'

-- Элемент массива --

<ElMas>::='<earr>'<ID>','<Chislo>'</earr>' -- вывод элемента массива

-- Раздел описаний --

-- описание переменных

<Vars>::='<boolean>'<NamesBool>'</boolean>'<R3> -- типа boolean

<Vars>::='<char>'<NamesChar>'</char>'<R3> -- типа char

<R3>::=<Vars> -- продолжение описаний

<R3>::=$ -- конец описаний

<NamesBool>::=<ID><R4> -- вывод ид-ра переменной типа boolean

<NamesBool>::=<MasBool><R4> -- вывод массива типа boolean

<R4>::=','<NamesBool> -- продолжение вывода описаний boolean

<R4>::=$ -- конец вывода описаний boolean

<NamesChar>::=<ID><R5> -- вывод ид-ра переменной типа char

<NamesChar>::=<MasChar><R5> -- вывод массива типа char

<R5>::=','<NamesChar> -- продолжение вывода описаний char

<R5>::=$ -- конец вывода описаний char

-- Раздел операций --

<Code>::='<ass>' <Perem> ',' <Vyrazh> '</ass>' <R6> -- вывод операции

-- присваивания

<Perem>::=<ID>|<ElMas> -- вывод переменной, которой

-- будет присвоено новое значение

<Vyrazh>::=<Const>|<Perem>|<Operation>|<Simvol> -- вывод выражения, значение которого

-- будет присвоено переменной

<Operation>::='<and>' <Operand> ',' <Operand> '</and>' -- вывод лог. операции &

<Operation>::='<or>' <Operand> ',' <Operand> '</or>' -- вывод лог. операции v

<Operation>::='<not>' <Operand> '</not>' -- вывод лог. операции !

<Operand>::=<Operation> -- вывод операнда лог. операций

<Operand>::=<ID>|<ElMas>

<Operand>::=<Const>

<R6>::=<Code> -- продолжение вывода операций

<R6>::=$ -- конец вывода операций

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

КС-грамматика называется LL(1) грамматикой тогда и только тогда, когда множества ВЫБОР, построенные для правил с одинаковой левой частью, не содержат одинаковых элементов. Входная грамматика проверялась на принадлежность к классу LL(1)-грамматик в системе OSA. Данная грамматика является LL(1)-грамматикой, т.к. множества ВЫБОР, построенные для правил с одинаковой левой частью не содержат одинаковых элементов.