Министерство образования РФ

Санкт-Петербургский государственный

электротехнический университет

Кафедра ВТ

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

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

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

Выполнил: Королев К.А.

гр.9307

Проверил: Фомичев В.С.

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

2001 год

Содержание

1. Задание

2. Символьный преобразователь

1. Входная грамматика

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

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

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

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

2. Диаграмма состояний

3. Структуры данных и таблицы

4. Семантика анализа и символы действия

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

6. Структура программы

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

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

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

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

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

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

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

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

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

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

6. Заключение

1. Задание

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

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

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

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

{<bool>ca45,b0,<ass>d1gt ‘true’</ass></bool>;

<char><ass><arr>dee068 2 2</arr><iarr>’a’ ‘b’ ‘c’ ‘d’</iarr></ass></char>;

<ass><marr>dee068 1 1</marr> <not>’e’</not></ass>;

<ass>ca45 <or>dlgt <not>’false’</not></or></ass>;}

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

ca45 “bool” b0 “bool” dlgt “bool” ‘true’=

des068 “char” 2 “РМ” 2 “РМ” ‘a’ ‘b’ ‘c’ ‘d’=

dee068 1 “РМ” 1 “РМ” ‘e’!=

ca45 dlgt ‘false’!v=

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

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

где:

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

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

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

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

2. Символьный преобразователь

1. Входная грамматика

<I> ::= '{'<Опис.><Опер.>'}' --вывод описаний и операций

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

<Ч.> ::= <Ц.><R1> --вывод целого числа

<R1> ::= <Ц.><R1>

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

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

<Ид.> ::= <Б.><R2> --вывод буквы в идентификаторе

<R2> ::= <Б.><R2>

<R2> ::= <Ц.><R2> --вывод цифры в идентификаторе

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

-- Массив --

<Массив b> ::= '<arr>'<Ид.>' '<Ч.><R3>'</arr>' --вывод массива bool

<Массив c> ::= '<arr>'<Ид.>' '<Ч.><R3>'</arr>' --вывод массива char

<R3> ::= ' '<Ч.><R3> --вывод размерности массива

<R3> ::= $ --конец вывода размерности массива

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

<Эл.мас.> ::= '<marr>'<Ид.>' '<Ч.><R4>'</marr>' --вывод элемента массива

<R4> ::= ' '<Ч.><R4> --вывод адреса элемента в массиве

<R4> ::= $ --конец вывода адреса элемента в массиве

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

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

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

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

<К.> ::= 'True'|'False' --константы

-- Описания --

<Опис.> ::= '<bool>'<Тип bool>'</bool>'';'<R5> --описание переменных типа

--bool

<Опис.> ::= '<char>'<Тип char>'</char>'';'<R5> --описание переменных типа

--char

<R5> ::= <Опис.> --продолжение описаний

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

<Тип bool> ::= <Ид.><R6> --ввыводится идентификатор переменной bool

<Тип bool> ::= <Массив b><R6> --ввыводится массив типа bool

<Тип bool> ::= '<ass>'<Класс bool>'</ass>'<R6> --описание переменной или

--массива bool с инициализацией

<Класс bool> ::= <Ид.>' '<К.>|<Массив b><Иниц.мас.bool> --инициализация перемен-

--ной или массива bool

<Иниц.мас.bool> ::= '<iarr>'<Константы>'</iarr>' --инициализация массива bool

<Константы> ::= <К.><R7> --выводится список из констант 'true','false'

<R7> ::= ' '<К.><R7>

<R7> ::= $ --конец списка констант

<R6> ::= ','<Тип bool> --продолжение вывода описаний bool

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

<Тип char> ::= <Ид.><R8> --ввыводится идентификатор переменной char

<Тип char> ::= <Массив c><R8> --ввыводится массив типа char

<Тип char> ::= '<ass>'<Класс char>'</ass>'<R8> --описание переменной или

--массива char с инициализацией

<Класс char> ::= <Ид.>' '<С.>|<Массив c><Иниц.мас.char> --инициализация перемен-

--ной или массива char

<Иниц.мас.char> ::= '<iarr>'<Символы>'</iarr>' --инициализация массива char

<Символы> ::= <С.><R9> --выводится список из символов 'a',..,'e'

<R9> ::= ' '<С.><R9>

<R9> ::= $ --конец списка символов

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

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

-- Операции --

<Опер.> ::= '<ass>'<Оп.1>' '<Л.опер.>'</ass>'';'<R10> --вывод

--операций

<Оп.1> ::= <Ид.>|<Эл.мас.> --вывод первого операнда

<Л.опер.> ::= '<and>'<Оп.2>' '<Оп.2>'</and>' --вывод лог.операции &

<Л.опер.> ::= '<or>'<Оп.2>' '<Оп.2>'</or>' --вывод лог.операции v

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

<Оп.2> ::= <С.>|<К.> --вывод второго операнда

<Оп.2> ::= <Л.опер.>

<Оп.2> ::= <Ид.>|<Эл.мас.>

<R10> ::= <Опер.> --продолжение вывода операций

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

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

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

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

Схемой синтаксически управляемого перевода (СУ-схемой) называется совокупность пяти объектов:  T ={V_a,V_твх,V_твых,Q,<I>}, где:

V_a - множество  нетерминальных символов;

V_твх - множество терминальных символов,  используемых для построения входных

цепочек;

V_твых - множество терминальных символов,  используемых для построения  выходных

цепочек;

<I> - начальный символ; <I>Va;

Q - множество правил вида <A>  ,; где:

<A>V_a, (V_a U V_твх)*, (V_a U V_твых)* и нетерминалы,  входящие в цепочку

 образуют перестановку нетерминалов цепочки .

Приведенное определение СУ-схемы не накладывает никаких ограничений на прави-ла, кроме необходимости совпадения нетерминалов во входной и выходной частях правила. Для построения детерминированных устройств, осуществляющих перевод цепочек, исполь-зуются СУ-схемы с дополнительными ограничениями на вид правил. В данной работе СУ-схема должна быть простой. СУ-схема Т ={V_a,V_твх,V_твых,Q,<I>} называется простой, если для  каждого правила  <A>  , из Q соответствующих друг другу вхождения нетермина-лов встречаются в  и  в одном и том же порядке.

СУ-схема:

Входные цепочки Выходные цепочки

<I> ::= '{'<Опис.><Опер.>'}' <Опис.>' '<Опер.>

<Ч.> ::= <Ц.><R1> <Ц.><R1>

<R1> ::= <Ц.><R1> <Ц.><R1>

<R1> ::= $ $

<Ид.> ::= <Б.><R2> <Б.><R2>

<R2> ::= <Б.><R2> <Б.><R2>

<R2> ::= <Ц.><R2> <Ц.><R2>

<R2> ::= $ $

<Массив b> ::= '<arr>'<Ид.>' '<Ч.><R3>'</arr>' <Ид.>' ''bool'' '<Ч.>' ''РМ'<R3>

<Массив c> ::= '<arr>'<Ид.>' '<Ч.><R3>'</arr>' <Ид.>' ''char'' '<Ч.>' ''РМ'<R3>

<R3> ::= ' '<Ч.><R3> ' '<Ч.>' ''РМ'<R3>

<R3> ::= $ $

<Эл.мас.> ::= '<marr>'<Ид.>' '<Ч.><R4>'</marr>' <Ид.>' '<Ч.>' ''ЭМ'<R4>

<R4> ::= ' '<Ч.><R4> ' '<Ч.>' ''ЭМ'<R4>

<R4> ::= $ $

<Б.> ::= a|b|c|d|e a|b|c|d|e

<Ц.> ::= 1|2|3|4|5|6|7|8|9|0 1|2|3|4|5|6|7|8|9|0

<С.> ::= "'a'"|"'b'"|"'c'"|"'d'"|"'e'" "'a'"|"'b'"|"'c'"|"'d'"|"'e'"

<К.> ::= 'True'|'False' 'True'|'False'

-- Описания --

<Опис.> ::= '<bool>'<Тип bool>'</bool>'';'<R5> <Тип bool>

<Опис.> ::= '<char>'<Тип char>'</char>'';'<R5> <Тип char>

<R5> ::= <Опис.> ' '<Опис.>

<R5> ::= $ $

<Тип bool> ::= <Ид.><R6> <Ид.>' ''bool'<R6>

<Тип bool> ::= <Массив b><R6> <Массив b><R6>

<Тип bool> ::= '<ass>'<Класс bool>'</ass>'<R6> <Класс bool>'='<R6>

<Класс bool> ::= <Ид.>' '<К.> <Ид.>' ''bool'' '<К.>

<Класс bool> ::= <Массив b><Иниц.мас.bool> <Массив b><Иниц.мас.bool>

<Иниц.мас.bool> ::= '<iarr>'<Константы>'</iarr>' <Константы>

<Константы> ::= <К.><R7> ' '<К.><R7>

<R7> ::= ' '<К.><R7> ' '<К.><R7>

<R7> ::= $ $

<R6> ::= ','<Тип bool> ' '<тип bool>

<R6> ::= $ $

<Тип char> ::= <Ид.><R8> <Ид.>' 'char'<R8>

<Тип char> ::= <Массив c><R8> <Массив c><R8>

<Тип char> ::= '<ass>'<Класс char>'</ass>'<R8> <Класс bool>'='<R8>

<Класс char> ::= <Ид.>' '<С.> <Ид.>' ''char'' '<С.>

<Класс char> ::= <Массив c><Иниц.мас.char> <Массив c><Иниц.мас.char>

<Иниц.мас.Char> ::= '<iarr>'<Символы>'</iarr>' <Символы>

<Символы> ::= <С.><R9> ' '<С.><R9>

<R9> ::= ' '<С.><R9> ' '<C.><R9>

<R9> ::= $ $

<R8> ::= ','<Тип Char> ' '<тип char>

<R8> ::= $ $

<Опер.> ::= '<ass>'<Оп.1>' '<Л.опер.>'</ass>'';'<R10> <Оп.1>' '<Л.опeр.>'='<R10>

<Оп.1> ::= <Ид.>|<Эл.мас.> <Ид.>|<Эл.мас.>

<Л.опер.> ::= '<and>'<Оп.2>' '<Оп.2>'</and>' <Оп.2>' '<Оп.2>'&'

<Л.опер.> ::= '<or>'<Оп.2>' '<Оп.2>'</or>' <Оп.2>' '<Оп.2>'v'

<Л.опер.> ::= '<not>'<Оп.2>'</not>' <Оп.2>'!'

<Оп.2> ::= <С.>|<К.> <С.>|<К.>

<Оп.2> ::= <Л.опер.> <Л.опер.>

<Оп.2> ::= <Ид.>|<Эл.мас.> <Ид.>|<Эл.мас.>

<R10> ::= <Опер.> ' '<Опер.>

<R10> ::= $ $

Пример вывода в данной СУ-схеме. Для примера выведем цепочку:

{<bool>a7</bool>;<ass>a7 <not>’false’</not></ass>;}

( <I>,<I> )  ( {<Опис.><Опер.>},<Опис.>’ ‘<Опер.> ) 

( {<bool> <Тип bool> </bool>;<R5> <Опер.>},<Тип bool><R5>’ ‘<Опер.> )

( {<bool><Ид.><R6> </bool>;<R5><Опер.>},<Ид.> ‘ ‘‘bool’<R6><R5>’ ‘<Опер.>)

( {<bool>a7<R6></bool>;<R5><Опер.>},a7‘ ‘‘bool’<R6><R5>’ ‘<Опер.>)

({<bool>a7</bool>;<R5><Опер.>}, a7’ ’’bool’<R5>’ ‘<Опер.> ) 

({<bool>a7</bool>;<Опер.>}, a7’ ’’bool’’ ‘<Опер.> ) 

({<bool>a7</bool>;<ass><Оп.1>’ ‘<Л.опер.></ass>;<R10>},

a7‘ ‘‘bool’‘ ‘<Оп.1>‘ ‘<Л.опер.>’=’<R10>)

({<bool>a7</bool>;<ass><Ид.>’ ‘<Л.опер.></ass>;<R10>},

a7‘ ‘‘bool’‘ ‘<Ид.>‘ ‘<Л.опер.>’=’<R10>)

({<bool>a7</bool>;<ass>a7’ ‘<Л.опер.></ass>;<R10>},

a7‘ ‘‘bool’‘ ‘a7‘ ‘<Л.опер.>’=’<R10>)

({<bool>a7</bool>;<ass>a7’ ‘<not><Оп.2></not></ass>;<R10>},

a7‘ ‘‘bool’‘ ‘a7‘ ‘<Оп.2>’!’’=’<R10>)

({<bool>a7</bool>;<ass>a7’ ‘<not><К.></not></ass>;<R10>},

a7‘ ‘‘bool’‘ ‘a7‘ ‘<К.>’!’’=’<R10>)

({<bool>a7</bool>;<ass>a7’ ‘<not>’false’</not></ass>;<R10>},

a7‘ ‘‘bool’‘ ‘a7‘ ‘’false’’!’’=’<R10>)

({<bool>a7</bool>;<ass>a7’ ‘<not>’false’</not></ass>;},

a7‘ ‘‘bool’‘ ‘a7‘ ‘’false’’!’’=’)

Транслирующая грамматика.

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

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

Транслирующая грамматика:

<I> ::= '{'<Опис.>{ }<Опер.>'}'

<Ч.> ::= <Ц.><R1>

<R1> ::= <Ц.><R1>

<R1> ::= $

<Ид.> ::= <Б.><R2>

<R2> ::= <Б.><R2>

<R2> ::= <Ц.><R2>

<R2> ::= $

<Массив b> ::= '<arr>'<Ид.>{ }{bool}' '<Ч.>{ }{РМ}<R3>'</arr>'

<Массив c> ::= '<arr>'<Ид.>{ }{char}' '<Ч.>{ }{РМ}<R3>'</arr>'

<R3> ::= ' '{ }<Ч.>{ }{РМ}<R3>

<R3> ::= $

<Эл.мас.> ::= '<marr>'<Ид.>{ }' '<Ч.>{ }{ЭМ}<R4>'</marr>'

<R4> ::= ' '{ }<Ч.>{ }{ЭМ}<R4>

<R4> ::= $

<Б.> ::= a{a}|b{b}|c{c}|d{d}|e{e}

<Ц.> ::= 1{1}|2{2}|3{3}|4{4}|5{5}|6{6}|7{7}|8{8}|9{9}|0{0}

<С.> ::= "'a'"{"'a'"}|"'b'"{"'b'"}|"'c'"{"'c'"}|"'d'"{"'d'"}|"'e'"{"'e'"}

<К.> ::= 'True'{'True'}|'False'{'False'}

<Опис.> ::= '<bool>'<Тип bool>'</bool>'';'<R5>

<Опис.> ::= '<char>'<Тип char>'</char>'';'<R5>

<R5> ::= { }<Опис.>

<R5> ::= $

<Тип bool> ::= <Ид.>{ }{bool}<R6>

<Тип bool> ::= <Массив b><R6>

<Тип bool> ::= '<ass>'<Класс bool>{=}'</ass>'<R6>

<Класс bool> ::= <Ид.>{ }{bool}{ }' '<К.>|<Массив b><Иниц.мас.bool>

<Иниц.мас.bool> ::= '<iarr>'<Константы>'</iarr>'

<Константы> ::= { }<К.><R7>

<R7> ::= { }' '<К.><R7>

<R7> ::= $

<R6> ::= { }','<Тип bool>

<R6> ::= $

<Тип char> ::= <Ид.>{ }{char}<R8>

<Тип char> ::= <Массив c><R8>

<Тип char> ::= '<ass>'<Класс char>{=}'</ass>'<R8>

<Класс char> ::= <Ид.>{ }{char}{ }' '<С.>|<Массив c><Иниц.мас.char>

<Иниц.мас.char> ::= '<iarr>'<Символы>'</iarr>'

<Символы> ::= { }<С.><R9>

<R9> ::= { }' '<С.><R9>

<R9> ::= $

<R8> ::= { }','<Тип char>

<R8> ::= $

<Опер.> ::= '<ass>'<Оп.1>{ }' '<Л.опер.>{=}'</ass>'';'<R10>

<Оп.1> ::= <Ид.>|<Эл.мас.>

<Л.опер.> ::= '<and>'<Оп.2>' '<Оп.2>{&}'</and>'

<Л.опер.> ::= '<or>'<Оп.2>' '<Оп.2>{v}'</or>'

<Л.опер.> ::= '<not>'<Оп.2>{!}'</not>'

<Оп.2> ::= <С.>|<К.>

<Оп.2> ::= <Л.опер.>

<Оп.2> ::= <Ид.>|<Эл.мас.>

<R10> ::= { }<Опер.>

<R10> ::= $

В данной транслирующей грамматике выходные символы заключены в {}.

Пример вывода в данной транслирующей грамматике. Для примера выведем цепочку:

{<bool>a7</bool>;<ass>a7 <not>’false’</not></ass>;}

<I>

{<Опис.>{ }<Опер.>}

{<bool><Тип bool></bool>;<R5>{ }<Опер.>}

{<bool><Ид.>{ }{bool}<R6> </bool>;<R5>{ }<Опер.>}

{<bool>a{a}7{7}{ }{bool}<R6></bool>;<R5>{ }<Опер.>}

{<bool>a{a}7{7}{ }{bool}</bool>;<R5>{ }<Опер.>}

{<bool>a{a}7{7}{ }{bool}</bool>;{ }<Опер.>}

{<bool>a{a}7{7}{ }{bool}</bool>;{ }<ass><Оп.1>{ }’ ‘<Л.опер.>{=}</ass>;<R10>}

{<bool>a{a}7{7}{ }{bool}</bool>;{ }<ass><Ид.>{ }’ ‘<Л.опер.>{=}</ass>;<R10>}

{<bool>a{a}7{7}{ }{bool}</bool>;{ }<ass>a{a}7{7}{ }’ ‘<Л.опер.>{=}</ass>;<R10>}

{<bool>a{a}7{7}{ }{bool}</bool>;{ }<ass>a{a}7{7}{ }’ ‘<not><Оп.2>{!}</not>{=}</ass>;<R10>}

{<bool>a{a}7{7}{ }{bool}</bool>;{ }<ass>a{a}7{7}{ }’ ‘<not><К.>{!}</not>{=}</ass>;<R10>}

{<bool>a{a}7{7}{ }{bool}</bool>;{ }<ass>a{a}7{7}{ }’ ‘<not>’false’{‘false’}{!}</not>{=}</ass>;<R10>}

{<bool>a{a}7{7}{ }{bool}</bool>;{ }<ass>a{a}7{7}{ }’ ‘<not>’false’{‘false’}{!}</not>{=}</ass>;}