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

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

Содержание

1.        Задание

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

.       
Задание

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

Вариант № 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""BOOL" 5 "RM" B "BOOL"1 "EM" 'TRUE' B! 'FALSE'V&=

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

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

где:

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

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

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

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

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

.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)-грамматикой, т.к. множества ВЫБОР, построенные для правил с одинаковой левой частью не содержат одинаковых элементов.

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

Синтаксически управляемой схемой (СУ-схемой) называется множество, состоящее из пяти объектов:

T ={V_a, V_твх, V_твых, R, <I>},

где:_a- множество нетерминальных символов;_твх- множество терминальных символов, используемых для построения входных

цепочек;_твых- множество терминальных символов, используемых для построения  выходных цепочек;

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

R- множество правил вида

<A> ®a ,b;

где: <A>ÎV_a, aÎ(V_a U V_твх)*, bÎ(V_a U V_твых)* и нетерминалы, входящие в  цепочку b образуют перестановку нетерминалов цепочки a.

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

В данной работе СУ-схема должна быть простой.

СУ-схема Т ={V_a, V_твх, V_твых, R, <I>} называется простой, если для каждого правила <A> ®a ,b из R соответствующих друг другу вхождения нетерминалов встречаются в  и  в одном и том же порядке.

СУ-схема:

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

<I>::=<Vars><Code>== <Vars>' '<Code>

<Bukva>::=a|b|c|d|e == a|b|c|d|e

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

<Const>::="'true'"|"'false'" == "'true'"|"'false'"

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

<ID>::=<Bukva><R1> == <Bukva><R1>

<R1>::=<Bukva><R1> == <Bukva><R1>

<R1>::=<Zifra><R1> == <Zifra><R1>

<R1>::=$ == $

<Chislo>::=<Zifra><R2> == <Zifra><R2>

<R2>::=<Zifra><R2> == <Zifra><R2>

<R2>::=$ == $

<MasBool>::='<arr>'<ID>','<Chislo>'</arr>' == <ID>' ''bool'' '<Chislo>' ''RM'

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

<ElMas>::='<earr>'<ID>','<Chislo>'</earr>' == <ID>' '<Chislo>' ''EM'

<Vars>::='<boolean>'<NamesBool>'</boolean>'<R3>== <NamesBool><R3>

<Vars>::='<char>'<NamesChar>'</char>'<R3> == <NamesChar><R3>

<R3>::=<Vars> == ' '<Vars>

<R3>::=$ == $

<NamesBool>::=<ID><R4> == <ID>' ''bool'<R4>

<NamesBool>::=<MasBool><R4> == <MasBool><R4>

<R4>::=','<NamesBool> == ' '<NamesBool>

<R4>::=$ == $

<NamesChar>::=<ID><R5> == <ID>' ''char'<R5>

<NamesChar>::=<MasChar><R5> == <MasChar><R5>

<R5>::=','<NamesChar> == ' '<NamesChar>

<R5>::=$ == $

<Code>::='<ass>'<Perem>','<Vyrazh>'</ass>'<R6> == <Perem>' '<Vyrazh>'='<R6>

<Perem>::=<ID>|<ElMas> == <ID>|<ElMas>

<Vyrazh>::=<Const>|<Perem>|<Operation>|<Simvol> == <Const>|<Perem>|

<Operation>|<Simvol>

<Operation>::='<and>'<Operand>','<Operand>'</and>'== <Operand>' '<Operand>'&'

<Operation>::='<or>' <Operand>','<Operand>'</or>' == <Operand>' '<Operand>'V'

<Operation>::='<not>'<Operand>'</not>' == <Operand>'!'

<Operand>::=<Operation> == <Operation>

<Operand>::=<Perem> == <Perem>

<Operand>::=<Const> == <Const>

<R6>::=<Code> == ' '<Code>

<R6>::=$ == $

Пример вывода в данной СУ-схеме.

Для примера выведем цепочку: <boolean> b1 </boolean> <ass> b1 <not> ’false’ </not> </ass>

( <I> , <I> ) à (<Vars><Code> , < Vars >’ ‘<Code >) à

( <boolean><NamesBool></boolean><R3><Code> , <NamesBool><R3>’ ‘<Code> ) à

( <boolean><ID><R4></boolean><R_3><Code> , <ID>‘ ‘‘bool’<R4><R3>’ ‘<Code> ) à

( <boolean>b1<R4></boolean><R3><Code> , b1‘ ‘‘bool’<R4><R3>’ ‘<Code> ) à

( <boolean>b1</boolean><R3><Code> , b1’ ’’bool’<R3>’ ‘<Code> ) à

( <boolean>b1</boolean><Code> , b1’ ’’bool’’ ‘<Code> ) à

( <boolean>b1</boolean><ass><Perem>’,‘<Vyrazh></ass><R6> ,‘ ‘‘bool’‘ ‘<Perem>‘ ‘<Vyrazh>’=’<R6>) à

( <boolean>b1</boolean><ass><ID>’,‘<Vyrazh></ass><R6> ,‘ ‘‘bool’‘ ‘<ID>‘ ‘<Vyrazh>’=’<R6>) à

( <boolean>b1</boolean><ass>b1’,‘<Vyrazh></ass><R6> ,‘ ‘‘bool’‘ ‘b1‘ ‘<Vyrazh>’=’<R6>) à

( <boolean>b1</boolean><ass>b1’,‘<Operation></ass><R6> ,‘ ‘‘bool’‘ ‘b1‘ ‘<Operation>’=’<R6>) à

( <boolean>b1</boolean><ass>b1’,‘<not><Operand></not></ass><R6> ,‘ ‘‘bool’‘ ‘b1‘ ‘<Operand>’!’’=’<R6>) à

( <boolean>b1</boolean><ass>b1’,‘<not><Const></not></ass><R6> ,‘ ‘‘bool’‘ ‘b1‘ ‘<Const>’!’’=’<R6>) à

( <boolean>b1</boolean><ass>b1’ ‘<not>’false’</not></ass><R6> ,‘ ‘‘bool’‘ ‘b1‘ ‘’false’’!’’=’<R6>) à

( <boolean>b1</boolean><ass>b1’ ‘<not>’false’</not></ass> ,‘ ‘‘bool’‘ ‘b1‘ ‘’false’’!’’=’) ·

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

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

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

<I>::=<Vars># #<Code>

<Bukva>::=a#a#|b#b#|c#c#|d#d#|e#e#

<Zifra>::=0#0#|1#1#|2#2#|3#3#|4#4#|5#5#|6#6#|7#7#|8#8#|9#9#

<Const>::="'true'"#'true'#|"'false'"#'false'#

<Simvol>::="'a'"#'a'#|"'b'"#'b'#|"'c'"#'c'#|"'d'"#'d'#|"'e'"#'e'#

<ID>::=<Bukva><R1>

<R1>::=<Bukva><R1>

<R1>::=<Zifra><R1>

<R1>::=$

<Chislo>::=<Zifra><R2>

<R2>::=<Zifra><R2>

<R2>::=$

<MasBool>::='<arr>'<ID>','# ##bool## #<Chislo>'</arr>'# ##RM#

<MasChar>::='<arr>'<ID>','# ##char## #<Chislo>'</arr>'# ##RM#

<ElMas>::='<earr>'<ID>','# #<Chislo>'</earr>'# ##EM#

<Vars>::='<boolean>'<NamesBool>'</boolean>'<R3>

<Vars>::='<char>'<NamesChar>'</char>'<R3>

<R3>::=# #<Vars>

<R3>::=$

<NamesBool>::=<ID># ##bool#<R4>

<NamesBool>::=<MasBool><R4>

<R4>::=','# #<NamesBool>

<R4>::=$

<NamesChar>::=<ID># ##char#<R5>

<NamesChar>::=<MasChar><R5>

<R5>::=','# #<NamesChar>

<R5>::=$

<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>::=<Perem>

<Operand>::=<Const>

<R6>::=# #<Code>

<R6>::=$

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

Пример вывода в данной транслирующей грамматике.

Для примера выведем цепочку: <boolean> b1 </boolean> <ass> b1 <not> ’false’ </not> </ass>

<I> à

<Vars># #<Code> à

<boolean><NamesBool></boolean><R3># #<Code> à

<boolean><ID># ##bool#<R4></boolean><R3># #<Code> à

<boolean>b#b#1#1## ##bool#<R4></boolean><R3># #<Code> à

<boolean>b#b#1#1## ##bool#</boolean><R3># #<Code> à

<boolean>b#b#1#1## ##bool#</boolean># #<Code> à

<boolean>b#b#1#1## ##bool#</boolean># #

<ass><Perem>’,’# #<Vyrazh></ass>#=#<R6> à

<boolean>b#b#1#1## ##bool#</boolean># #

<ass><ID>’,’# #<Vyrazh></ass>#=#<R6> à

<boolean>b#b#1#1## ##bool#</boolean># #

<ass>b#b#1#1#’,’# #<Vyrazh></ass>#=#<R6> à

<boolean>b#b#1#1## ##bool#</boolean># #

<ass>b#b#1#1#’,’# #<Operation></ass>#=#<R6> à

<boolean>b#b#1#1## ##bool#</boolean># #

<ass>b#b#1#1#’,’# #<not><Operand></not>#!#</ass>#=#<R6> à

<boolean>b#b#1#1## ##bool#</boolean># #

<ass>b#b#1#1#’,’# #<not><Const></not>#!#</ass>#=#<R6> à

<boolean>b#b#1#1## ##bool#</boolean># #

<ass>b#b#1#1#’,’# #<not>’false’#’false’#</not>#!#</ass>#=#<R6> à

<boolean>b#b#1#1## ##bool#</boolean># #

<ass>b#b#1#1#’,’# #<not>’false’#’false’#</not>#!#</ass>#=# ·

Удалив из выведенной цепочки все выходные символы, получим входную цепочку - <boolean>b1</boolean><ass>b1’,’<not>’false’</not></ass>

Удалив из выведенной цепочки все входные символы, получим выходную цепочку - b1 bool b1 ’false’ ! =

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

1.      Для всех правил вида <A>®ba, где bÎV_твх и aÎ(V_твхUV_твыхUV_a)*, строим функции вида:

f ( S, b, A)=( S, a’, $),

где a’-зеркальное отражение цепочки a.

( S, a, <bukva> ) = ( S, #a#, $ )

( S, b, <bukva> ) = ( S, #b#, $ )

( S, c, <bukva> ) = ( S, #c#, $ )

( S, d, <bukva> ) = ( S, #d#, $ )

( S, e, <bukva> ) = ( S, #e#, $ )

( S, 0, <zifra> ) = ( S, #0#, $ )

( S, 1, <zifra> ) = ( S, #1#, $ )

( S, 2, <zifra> ) = ( S, #2#, $ )

( S, 3, <zifra> ) = ( S, #3#, $ )

( S, 4, <zifra> ) = ( S, #4#, $ )

( S, 5, <zifra> ) = ( S, #5#, $ )

( S, 6, <zifra> ) = ( S, #6#, $ )

( S, 7, <zifra> ) = ( S, #7#, $ )

( S, 8, <zifra> ) = ( S, #8#, $ )

( S, 9, <zifra> ) = ( S, #9#, $ )

( S, "'true'" , <const> ) = ( S, #'true'#, $ )

( S, "'false'" , <const> ) = ( S, #'false'#, $ )

( S, "'a'" , <simvol> ) = ( S, #'a'#, $ )

( S, "'b'" , <simvol> ) = ( S, #'b'#, $ )

( S, "'c'" , <simvol> ) = ( S, #'c'#, $ )

( S, "'d'" , <simvol> ) = ( S, #'d'#, $ )

( S, "'e'" , <simvol> ) = ( S, #'e'#, $ )

( S, "<arr>" , <masbool> ) = ( S, #RM## #"</arr>"<chislo># ##bool## #","<id>, $ )

( S, "<arr>" , <maschar> ) = ( S, #RM## #"</arr>"<chislo># ##char## #","<id>, $ )

( S, "<earr>" , <elmas> ) = ( S, #EM## #"</earr>"<chislo># #","<id>, $ )

( S, "<boolean>" , <vars> ) = ( S, <r3> "</boolean>" <namesbool>, $ )

( S, "<char>" , <vars> ) = ( S, <r3> "</char>" <nameschar>, $ )

( S, "," , <r4> ) = ( S, <namesbool># #, $ )

( S, "," , <r5> ) = ( S, <nameschar># #, $ )

( S, "<ass>", <code> ) = ( S,<r6>#=#"</ass>"<vyrazh># #","<perem> , $ )

( S, "<and>", <operation> ) = ( S, #&# "</and>" <operand> # # "," <operand>, $ )

( S, "<or>" , <operation> ) = ( S, #V# "</or>" <operand> # # "," <operand>, $ )

( S, "<not>", <operation> ) = ( S, #!# "</not>" <operand>, $ )

2.      Для всех правил вида <A>®<B>a, где BÎVa и aÎ(V_твхUV_твыхUV_a)*, строим функции вида:

f *( S, x, <A>)=( S, a<B>, $) для всех xÎВЫБОР(<A>®<B>aвх)

где a_вх - цепочка, полученная из a путем удаления из нее всех выходных символов.

*( S, "<boolean>" , <i> ) = ( S, <code> # # <vars>, $ )

*( S, "<char>" , <i> ) = ( S, <code> # # <vars>, $ )

*( S, a, <id> ) = ( S, <R1> <bukva>, $ )

*( S, b, <id> ) = ( S, <R1> <bukva>, $ )

*( S, c, <id> ) = ( S, <R1> <bukva>, $ )

*( S, d, <id> ) = ( S, <R1> <bukva>, $ )

*( S, e, <id> ) = ( S, <R1> <bukva>, $ )

*( S, a, <R1> ) = ( S, <R1> <bukva>, $ )

*( S, b, <R1> ) = ( S, <R1> <bukva>, $ )

*( S, c, <R1> ) = ( S, <R1> <bukva>, $ )

*( S, d, <R1> ) = ( S, <R1> <bukva>, $ )

*( S, e, <R1> ) = ( S, <R1> <bukva>, $ )

*( S, 0, <R1> ) = ( S, <R1> <zifra>, $ )

*( S, 1, <R1> ) = ( S, <R1> <zifra>, $ )

*( S, 2, <R1> ) = ( S, <R1> <zifra>, $ )

*( S, 3, <R1> ) = ( S, <R1> <zifra>, $ )

*( S, 4, <R1> ) = ( S, <R1> <zifra>, $ )

*( S, 5, <R1> ) = ( S, <R1> <zifra>, $ )

*( S, 6, <R1> ) = ( S, <R1> <zifra>, $ )

*( S, 7, <R1> ) = ( S, <R1> <zifra>, $ )

*( S, 8, <R1> ) = ( S, <R1> <zifra>, $ )

*( S, 9, <R1> ) = ( S, <R1> <zifra>, $ )

*( S, 0, <chislo> ) = ( S, <R2> <zifra>, $ )

*( S, 1, <chislo> ) = ( S, <R2> <zifra>, $ )

*( S, 2, <chislo> ) = ( S, <R2> <zifra>, $ )

*( S, 3, <chislo> ) = ( S, <R2> <zifra>, $ )

*( S, 4, <chislo> ) = ( S, <R2> <zifra>, $ )

*( S, 5, <chislo> ) = ( S, <R2> <zifra>, $ )

*( S, 6, <chislo> ) = ( S, <R2> <zifra>, $ )

*( S, 7, <chislo> ) = ( S, <R2> <zifra>, $ )

*( S, 8, <chislo> ) = ( S, <R2> <zifra>, $ )

*( S, 9, <chislo> ) = ( S, <R2> <zifra>, $ )

*( S, 0, <R2> ) = ( S, <R2> <zifra>, $ )

*( S, 1, <R2> ) = ( S, <R2> <zifra>, $ )

*( S, 2, <R2> ) = ( S, <R2> <zifra>, $ )

*( S, 3, <R2> ) = ( S, <R2> <zifra>, $ )

*( S, 4, <R2> ) = ( S, <R2> <zifra>, $ )

*( S, 5, <R2> ) = ( S, <R2> <zifra>, $ )

*( S, 6, <R2> ) = ( S, <R2> <zifra>, $ )

*( S, 7, <R2> ) = ( S, <R2> <zifra>, $ )

*( S, 8, <R2> ) = ( S, <R2> <zifra>, $ )

*( S, 9, <R2> ) = ( S, <R2> <zifra>, $ )

*( S, "<boolean>" , <R3> ) = ( S, <vars> # #, $ )

*( S, "<char>" , <R3> ) = ( S, <vars> # #, $ )

*( S, a, <namesbool> ) = ( S, <R4> #bool# # # <id>, $ )

*( S, b, <namesbool> ) = ( S, <R4> #bool# # # <id>, $ )

*( S, c, <namesbool> ) = ( S, <R4> #bool# # # <id>, $ )

*( S, d, <namesbool> ) = ( S, <R4> #bool# # # <id>, $ )

*( S, e, <namesbool> ) = ( S, <R4> #bool# # # <id>, $ )

*( S, "<arr>" , <namesbool> ) = ( S, <R4> <masbool>, $ )

*( S, a, <nameschar> ) = ( S, <R5> #char# # # <id>, $ )

*( S, b, <nameschar> ) = ( S, <R5> #char# # # <id>, $ )

*( S, c, <nameschar> ) = ( S, <R5> #char# # # <id>, $ )

*( S, d, <nameschar> ) = ( S, <R5> #char# # # <id>, $ )

*( S, e, <nameschar> ) = ( S, <R5> #char# # # <id>, $ )

*( S, "<arr>" , <nameschar> ) = ( S, <R5> <maschar>, $ )

*( S, a, <perem> ) = ( S, <id>, $ )

*( S, b, <perem> ) = ( S, <id>, $ )

*( S, c, <perem> ) = ( S, <id>, $ )

*( S, d, <perem> ) = ( S, <id>, $ )

*( S, e, <perem> ) = ( S, <id>, $ )

*( S, "<earr>" , <perem> ) = ( S, <elmas>, $ )

*( S, "'true'" , <vyrazh> ) = ( S, <const>, $ )

*( S, "'false'" , <vyrazh> ) = ( S, <const>, $ )

*( S, "'a'" , <vyrazh> ) = ( S, <simvol>, $ )

*( S, "'b'" , <vyrazh> ) = ( S, <simvol>, $ )

*( S, "'c'" , <vyrazh> ) = ( S, <simvol>, $ )

*( S, "'d'" , <vyrazh> ) = ( S, <simvol>, $ )

*( S, "'e'" , <vyrazh> ) = ( S, <simvol>, $ )

*( S, a, <vyrazh> ) = ( S, <perem>, $ )

*( S, b, <vyrazh> ) = ( S, <perem>, $ )

*( S, c, <vyrazh> ) = ( S, <perem>, $ )

*( S, d, <vyrazh> ) = ( S, <perem>, $ )

*( S, e, <vyrazh> ) = ( S, <perem>, $ )

*( S, "<earr>" , <vyrazh> ) = ( S, <perem>, $ )

*( S, "<and>" , <vyrazh> ) = ( S, <operation>, $ )

*( S, "<or>" , <vyrazh> ) = ( S, <operation>, $ )

*( S, "<not>" , <vyrazh> ) = ( S, <operation>, $ )

*( S, "<or>" , <operand> ) = ( S, <operation>, $ )

*( S, "<not>" , <operand> ) = ( S, <operation>, $ )

*( S, a, <operand> ) = ( S, <perem>, $ )

*( S, b, <operand> ) = ( S, <perem>, $ )

*( S, c, <operand> ) = ( S, <perem>, $ )

*( S, d, <operand> ) = ( S, <perem>, $ )

*( S, e, <operand> ) = ( S, <perem>, $ )

*( S, "<earr>" , <operand> ) = ( S, <perem>, $ )

*( S, "'true'" , <operand> ) = ( S, <const>, $ )

*( S, "'false'" , <operand> ) = ( S, <const>, $ )

*( S, "<ass>" , <R6> ) = ( S, <code> # #, $ )

3.      Для всех правил вида <A>®$ строим функции вида:

f *( S, x, <A>) = ( s₀, $, $ ),

для всех xÎВЫБОР(<A>®$), правило <A>®$ принадлежит Г_вх.

*( S, "," , <R1> ) = ( S, $, $)

*( S, "</boolean>" , <R1> ) = ( S, $, $)

*( S, "</char>" , <R1> ) = ( S, $, $ )

*( S, "</ass>" , <R1> ) = ( S, $, $ )

*( S, "</and>" , <R1> ) = ( S, $, $ )

*( S, "</or>" , <R1> ) = ( S, $, $ )

*( S, "</not>" , <R1> ) = ( S, $, $ )

*( S, "</arr>" , <R2> ) = ( S, $, $ )

*( S, "</earr>" , <R2> ) = ( S, $, $ )

*( S, "<ass>" , <R3> ) = ( S, $, $ )

*( S, "</boolean>" , <R4> ) = ( S, $, $ )

*( S, "</char>" , <R5> ) = ( S, $, $ )

*( S, -|, <R6> ) = ( S, $, $ )

4.      Для каждого bÎV_твх, не стоящего на первом месте в правой части правил транслирующей грамматики, строим функции вида:f ( S, b, b) = ( S, $, $).

( S, "," , "," ) = ( S, $, $ )

( S, "</arr>" , "</arr>" ) = ( S, $, $ )

( S, "</earr>" , "</earr>" ) = ( S, $, $ )

( S, "</boolean>" , "</boolean>" ) = ( S, $, $ )

( S, "</char>" , "</char>" ) = ( S, $, $ )

( S, "</ass>" , "</ass>" ) = ( S, $, $ )

( S, "</and>" , "</and>" ) = ( S, $, $ )

( S, "</or>" , "</or>" ) = ( S, $, $ )

( S, "</not>" , "</not>" ) = ( S, $, $ )

5.      Для каждого wÎV_твых, записываемого в магазин, строим функции вида: f *( S, $, w) = ( S, $, w).

*( S, $, #bool#) = (S, $, #bool# )

*( S, $, #char#) = (S, $, #char# )

*( S, $, #a#) = (S, $, #a# )

*( S, $, #b#) = (S, $, #b# )

*( S, $, #c#) = (S, $, #c# )

*( S, $, #d#) = (S, $, #d# )

*( S, $, #e#) = (S, $, #e# )

*( S, $, #0#) = (S, $, #0# )

*( S, $, #1#) = (S, $, #1# )

*( S, $, #2#) = (S, $, #2# )

*( S, $, #3#) = (S, $, #3# )

*( S, $, #4#) = (S, $, #4# )

*( S, $, #5#) = (S, $, #5# )

*( S, $, #6#) = (S, $, #6# )

*( S, $, #7#) = (S, $, #7# )

*( S, $, #8#) = (S, $, #8# )

*( S, $, #9#) = (S, $, #9# )

*( S, $, # #) = (S, $, # # )

*( S, $, #RM#) = (S, $, #RM# )

*( S, $, #EM#) = (S, $, #EM# )

*( S, $, #=#) = (S, $, #=# )

*( S, $, #&#) = (S, $, #&# )

*( S, $, #V#) = (S, $, #V# )

*( S, $, #!#) = (S, $, #!# )

*( S, $, #'true'#) = (S, $, #'true'# )

*( S, $, #'false'#) = (S, $, #'false'# )

*( S, $, #'a'#) = (S, $, #'a'# )

*( S, $, #'b'#) = (S, $, #'b'# )

*( S, $, #'c'#) = (S, $, #'c'# )

*( S, $, #'d'#) = (S, $, #'d'# )

*( S, $, #'e'#) = (S, $, #'e'# )

6.      Строим функцию перехода в заключительное состояние:

( S, -|, [] ) = ( S, $, $ )

Пример работы магазинного преобразователя:

Подадим на вход цепочку:

<boolean>b1</boolean><ass>b1’,’<not>’false’</not></ass>

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

b1 bool b1 ’false’ ! =

ТАКТ 0

состояниеS

входная цепочка"<boolean>" b1 "</boolean>""<ass>" b1, "<not>" "'false'" "</not>" "</ass>"

магазин<I>[]

выходная цепочка

функция перехода*(S,"<BOOLEAN>",<I>)=(S,<CODE># #<VARS>,$)

ТАКТ 1

состояниеS

входная цепочка"<boolean>" b1 "</boolean>""<ass>" b1, "<not>" "'false'" "</not>" "</ass>"

магазин<VARS># #<CODE>[]

выходная цепочка

функция перехода(S,"<BOOLEAN>",<VARS>)=(S,<R3>"</BOOLEAN>"<NAMESBOOL>,$)

ТАКТ 2

состояниеS

входная цепочкаb1 "</boolean>""<ass>" b1, "<not>" "'false'" "</not>" "</ass>"-|

магазин<NAMESBOOL>"</BOOLEAN>"<R3># #<CODE>[]

выходная цепочка

функция перехода*(S,B,<NAMESBOOL>)=(S,<R4>#BOOL## #<ID>,$)

ТАКТ 3

состояние S

входная цепочкаb1 "</boolean>""<ass>" b1, "<not>" "'false'" "</not>" "</ass>"-|

магазин<ID># ##BOOL#<R4>"</BOOLEAN>"<R3># #<CODE>[]

выходная цепочка

функция перехода*(S,B,<ID>)=(S,<R1><BUKVA>,$)

ТАКТ 4

состояние S

входная цепочкаb1 "</boolean>""<ass>" b1, "<not>" "'false'" "</not>" "</ass>"-|

магазин<BUKVA><R1># ##BOOL#<R4>"</BOOLEAN>"<R3># #<CODE>[]

выходная цепочка

функция перехода(S,B,<BUKVA>)=(S,#B#,$)

ТАКТ 5

состояние S

входная цепочка1 "</boolean>""<ass>" b1, "<not>" "'false'" "</not>" "</ass>"-|

магазин#B#<R1># ##BOOL#<R4>"</BOOLEAN>"<R3># #<CODE>[]

выходная цепочка

функция перехода*(S,$,#B#)=(S,$,#B#)

ТАКТ 6

состояние S

входная цепочка1 "</boolean>""<ass>" b1, "<not>" "'false'" "</not>" "</ass>"-|

магазин<R1># ##BOOL#<R4>"</BOOLEAN>"<R3># #<CODE>[]

выходная цепочкаB

функция перехода*(S,1,<R1>)=(S,<R1><ZIFRA>,$)

ТАКТ 7

состояние S

входная цепочка1 "</boolean>""<ass>" b1, "<not>" "'false'" "</not>" "</ass>"-|

магазин<ZIFRA><R1># ##BOOL#<R4>"</BOOLEAN>"<R3># #<CODE>[]

выходная цепочкаB

функция перехода(S,1,<ZIFRA>)=(S,#1#,$)

ТАКТ 8

состояние S

входная цепочка"</boolean>""<ass>" b1, "<not>" "'false'" "</not>" "</ass>"-|

магазин#1#<R1># ##BOOL#<R4>"</BOOLEAN>"<R3># #<CODE>[]

выходная цепочкаB

функция перехода*(S,$,#1#)=(S,$,#1#)

ТАКТ 9

состояние S

входная цепочка"</boolean>""<ass>" b1, "<not>" "'false'" "</not>" "</ass>"-|

магазин<R1># ##BOOL#<R4>"</BOOLEAN>"<R3># #<CODE>[]

выходная цепочкаB1

функция перехода*(S,"</BOOLEAN>",<R1>)=(S,$,$)

ТАКТ 10

состояние S

входная цепочка"</boolean>""<ass>" b1, "<not>" "'false'" "</not>" "</ass>"-|

магазин# ##BOOL#<R4>"</BOOLEAN>"<R3># #<CODE>[]

выходная цепочкаB1

функция перехода*(S,$,# #)=(S,$,# #)

ТАКТ 11

состояние S

входная цепочка"</boolean>""<ass>" b1, "<not>" "'false'" "</not>" "</ass>"-|

магазин#BOOL#<R4>"</BOOLEAN>"<R3># #<CODE>[]

выходная цепочкаB1"" ""

функция перехода*(S,$,#BOOL#)=(S,$,#BOOL#)

ТАКТ 12

состояние S

входная цепочка"</boolean>""<ass>" b1, "<not>" "'false'" "</not>" "</ass>"-|

магазин<R4>"</BOOLEAN>"<R3># #<CODE>[]

выходная цепочкаB1"" """BOOL"

функция перехода*(S,"</BOOLEAN>",<R4>)=(S,$,$)

ТАКТ 13

состояние S

входная цепочка"</boolean>""<ass>" b1, "<not>" "'false'" "</not>" "</ass>"-|

магазин"</BOOLEAN>"<R3># #<CODE>[]

выходная цепочкаB1"" """BOOL"

функция перехода(S,"</BOOLEAN>","</BOOLEAN>")=(S,$,$)

ТАКТ 14

состояние S

входная цепочка"<ass>" b1, "<not>" "'false'" "</not>" "</ass>"-|

магазин<R3># #<CODE>[]

выходная цепочкаB1"" """BOOL"

функция перехода*(S,"<ASS>",<R3>)=(S,$,$)

ТАКТ 15

состояние S

входная цепочка"<ass>" b1, "<not>" "'false'" "</not>" "</ass>"-|

магазин# #<CODE>[]

выходная цепочкаB1"" """BOOL"

функция перехода*(S,$,# #)=(S,$,# #)

ТАКТ 16

состояние S

входная цепочка"<ass>" b1, "<not>" "'false'" "</not>" "</ass>"-|

магазин<CODE>[]

выходная цепочкаB1"" """BOOL""" ""

функция перехода(S,"<ASS>",<CODE>)=(S,<R6>#=#"</ASS>"<VYRAZH># #","<PEREM>,$)

ТАКТ 17

состояние S

входная цепочкаb1, "<not>" "'false'" "</not>" "</ass>"-|

магазин<PEREM>","# #<VYRAZH>"</ASS>"#=#<R6>[]

выходная цепочкаB1"" """BOOL""" ""

функция перехода*(S,B,<PEREM>)=(S,<ID>,$)

ТАКТ 18

состояние S

входная цепочкаb1, "<not>" "'false'" "</not>" "</ass>"-|

магазин<ID>","# #<VYRAZH>"</ASS>"#=#<R6>[]

выходная цепочкаB1"" """BOOL""" ""

функция перехода*(S,B,<ID>)=(S,<R1><BUKVA>,$)

ТАКТ 19

состояние S

входная цепочкаb1, "<not>" "'false'" "</not>" "</ass>"-|

магазин<BUKVA><R1>","# #<VYRAZH>"</ASS>"#=#<R6>[]

выходная цепочкаB1"" """BOOL""" ""

функция перехода(S,B,<BUKVA>)=(S,#B#,$)

ТАКТ 20

состояние S

входная цепочка1, "<not>" "'false'" "</not>" "</ass>"-|

магазин#B#<R1>","# #<VYRAZH>"</ASS>"#=#<R6>[]

выходная цепочкаB1"" """BOOL""" ""

функция перехода*(S,$,#B#)=(S,$,#B#)

ТАКТ 21

состояние S

входная цепочка1, "<not>" "'false'" "</not>" "</ass>"-|

магазин<R1>","# #<VYRAZH>"</ASS>"#=#<R6>[]

выходная цепочкаB1"" """BOOL""" ""B

функция перехода*(S,1,<R1>)=(S,<R1><ZIFRA>,$)

ТАКТ 22

состояние S

входная цепочка1, "<not>" "'false'" "</not>" "</ass>"-|

магазин<ZIFRA><R1>","# #<VYRAZH>"</ASS>"#=#<R6>[]

выходная цепочкаB1"" """BOOL""" ""B

функция перехода(S,1,<ZIFRA>)=(S,#1#,$)

ТАКТ 23

состояние S

входная цепочка, "<not>" "'false'" "</not>" "</ass>"-|

магазин#1#<R1>","# #<VYRAZH>"</ASS>"#=#<R6>[]

выходная цепочкаB1"" """BOOL""" ""B

функция перехода*(S,$,#1#)=(S,$,#1#)

ТАКТ 24

состояние S

входная цепочка, "<not>" "'false'" "</not>" "</ass>"-|

магазин<R1>","# #<VYRAZH>"</ASS>"#=#<R6>[]

выходная цепочкаB1"" """BOOL""" ""B1

функция перехода*(S,",",<R1>)=(S,$,$)

ТАКТ 25

состояние S

входная цепочка, "<not>" "'false'" "</not>" "</ass>"-|

магазин","# #<VYRAZH>"</ASS>"#=#<R6>[]

выходная цепочкаB1"" """BOOL""" ""B1

функция перехода(S,",",",")=(S,$,$)

ТАКТ 26

состояние S

входная цепочка"<not>" "'false'" "</not>" "</ass>"-|

магазин# #<VYRAZH>"</ASS>"#=#<R6>[]

выходная цепочкаB1"" """BOOL""" ""B1

функция перехода*(S,$,# #)=(S,$,# #)

ТАКТ 27

состояние S

входная цепочка"<not>" "'false'" "</not>" "</ass>"-|

магазин<VYRAZH>"</ASS>"#=#<R6>[]

выходная цепочкаB1"" """BOOL""" ""B1"" ""

функция перехода*(S,"<NOT>",<VYRAZH>)=(S,<OPERATION>,$)

ТАКТ 28

состояние S

входная цепочка"<not>" "'false'" "</not>" "</ass>"-|

магазин<OPERATION>"</ASS>"#=#<R6>[]

выходная цепочкаB1"" """BOOL""" ""B1"" ""

функция перехода(S,"<NOT>",<OPERATION>)=(S,#!#"</NOT>"<OPERAND>,$)

ТАКТ 29

состояние S

входная цепочка"'false'" "</not>" "</ass>"-|

магазин<OPERAND>"</NOT>"#!#"</ASS>"#=#<R6>[]

выходная цепочкаB1"" """BOOL""" ""B1"" ""

функция перехода*(S,"'FALSE'",<OPERAND>)=(S,<CONST>,$)

ТАКТ 30

состояние S

входная цепочка"'false'" "</not>" "</ass>"-|

магазин<CONST>"</NOT>"#!#"</ASS>"#=#<R6>[]

выходная цепочкаB1"" """BOOL""" ""B1"" ""

функция перехода(S,"'FALSE'",<CONST>)=(S,#'FALSE'#,$)

ТАКТ 31

состояние S

входная цепочка"</not>" "</ass>"-|

магазин#'FALSE'#"</NOT>"#!#"</ASS>"#=#<R6>[]

выходная цепочкаB1"" """BOOL""" ""B1"" ""

функция перехода*(S,$,#'FALSE'#)=(S,$,#'FALSE'#)

ТАКТ 32

состояние S

входная цепочка"</not>" "</ass>"-|

магазин"</NOT>"#!#"</ASS>"#=#<R6>[]

выходная цепочкаB1"" """BOOL""" ""B1"" """'FALSE'"

функция перехода(S,"</NOT>","</NOT>")=(S,$,$)

ТАКТ 33

состояние S

входная цепочка"</ass>"-|

магазин#!#"</ASS>"#=#<R6>[]

выходная цепочкаB1"" """BOOL""" ""B1"" """'FALSE'"

функция перехода*(S,$,#!#)=(S,$,#!#)

ТАКТ 34

состояние S

входная цепочка"</ass>"-|

магазин"</ASS>"#=#<R6>[]

выходная цепочкаB1"" """BOOL""" ""B1"" """'FALSE'"!

функция перехода(S,"</ASS>","</ASS>")=(S,$,$)

ТАКТ 35

состояние S

входная цепочка-|

магазин#=#<R6>[]

выходная цепочкаB1"" """BOOL""" ""B1"" """'FALSE'"!

функция перехода*(S,$,#=#)=(S,$,#=#)

ТАКТ 36

состояние S

входная цепочка-|

магазин<R6>[]

выходная цепочкаB1"" """BOOL""" ""B1"" """'FALSE'"!=

функция перехода*(S,-|,<R6>)=(S,$,$)

ТАКТ 37

состояние S

входная цепочка-|

магазин[]

выходная цепочкаB1"" """BOOL""" ""B1"" """'FALSE'"!=

функция перехода(S,-|,[])=(S,$,$)

ТАКТ 38

состояние S

входная цепочка-|

магазин[]

выходная цепочкаB1"" """BOOL""" ""B1"" """'FALSE'"!=

Магазинный автомат успешно завершил работу

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

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

. Грамматика идентификатора

I ® cA

A ® cA

A ® dA® rI

- буква - цифра

r - разделитель (‘,’ , ’ ‘ , ’<’)

. Грамматика числа

I ® dB

B ® dB

B ® rB

d - цифра

r - разделитель (‘,’ , ’ ‘ , ’<’)

. Грамматика служебного слова

I ® <C

C ® /E

E ® cD® cD® cD® >I

 - буква

. Грамматика констант

I ® ’F

F ® cG® cG® ’I

- буква

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

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

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

Структуры данных:

{ Таблица служебных слов }: array[1..16] of StrType = ('char','/char','boolean','/boolean',

'arr','/arr','earr','/earr','ass','/ass',

'and','/and','or','/or','not','/not');

{ Таблица логических констант }: array[1..2] of StrType = ('true','false');

{ Таблица символьных констант }: array[1..36] of Char =('a','b','c','d','e','f','g','h','i','j','k','l',

'm','n','o','p','q','r','s','t','u','v','w','x',

'y','z','0','1','2','3','4','5','6','7','8','9');

{ Таблица разделителей }= ',';=(TChar,TBool); { - Возможный тип переменной }=string[16]; { - Макс. длина идентификатора }

TypeLx=(Idt,Num,SSl,Log,Chr,Rzd);

{ - Типы лексем:- идентификатор - a, b[2] Num - целое число (б/зн) - 12, 2341- разделитель - "," SSl - служебное слово - <and>, </or>

Log - логическая константа - true, false Chr - символьная константа - 'a', 'c' }

{ Типы, определяющие: }=^TElTP; { - таблицу переменных - ТП }=^TElTSP; { - таблицу симв. представления - ТСП }=^TElTZ; { - таблицу значений - ТЗ (ячейки памяти)}=^TElTN; { - таблицу чисел - ТЧ }=^TElTL; { - таблицу лексем - ТЛ  }= record { Тип эл-та ТП: }:TPerem; { - тип переменной (TBool, TChar) }:TAdrTSP; { - указатель на эл-т ТСП }:TAdrTZ; { - указатель на эл-т ТЗ }:Word; { - кол-во эл-тов (+1) в ТЗ

end;= record { Тип эл-та ТСП: }

SimvP :TIdent; { - идентификатор (симв. представление) }:TAdrTSP; { - указатель на след. эл-т ТСП }

end;= record { Тип эл-та ТЧ: }:Word; { - значение : 0..65535 }:TAdrTN; { - указатель на след. эл-т ТЧ };= record { Тип эл-та ТЗ: (ячейки памяти) } :TPerem; { - тип хранимого значения }

Value :Byte; { - значение - 1 байт (char,bool) }

NextZ :TAdrTZ; { - указатель на след. эл-т ТЗ }

end;= record { Тип эл-та ТЛ: }:Byte; { - длина лексемы }:TAdrTL; { - указатель на след. эл-т ТЛ }TypeL:TypeLx of

{ варианты }: (PointPer :TAdrTP); { - для ид-ра }: (PointNum :TAdrTN); { - для числа },Log,Chr : (Index :Byte ); { - для служ. слов,констант}

Rzd: (); { - для разделителя "," };

Количество таблиц определено количеством типов лексем. В нашем случае их шесть - четыре заранее известных и две формируемых в процессе работы лексического анализатора.

Заранее известные таблицы:

. Таблица служебных слов

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

. Таблица констант типа Boolean

. Таблица констант типа Char

Формируемые таблицы:

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

. Таблица чисел

Пример работы лексического анализатора:

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

<char> ch, <arr> ac1, 5 </arr></char> <boolean> b7 </boolean>

<ass> b7, <not> ‘true’ </not> </ass>

<ass> <earr> ac1, 3 </earr>, ‘C’ </ass>

В результате работы лексического анализатора получим таблицы:

Таблица служебных слов:

char9 ass

2/char10/ass

3 boolean11 and

/boolean12/and

arr13 or

/arr14/or

earr15 not

/earr16/not

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

‘,’

Таблица символьных констант:

‘a’

‘b’

…

‘z’

‘0’

‘1’

…

‘9’

Таблица логических констант:

‘true’

‘false’

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

ch

ac1

b7

Таблица чисел:

Таблица лексем:

Символы действия (семантика анализа):

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

1.      Для идентификатора

Идентификатор должен начинаться с буквы и не должен иметь длину более 16 символов.

{НИ} - Начало идентификатора

подготовка буфера для записи (очистка)

установка длины = 1

{ФИ} - Формирование идентификатора

запись очередного входного символа в буфер

увеличение длины на 1

проверка счетчика длины на допустимое значение (≤ 16)

{КИ} - Конец идентификатора

поиск идентификатора в таблице идентификаторов (если его нет, то добавляем )

добавляем лексему типа Idt с длиной идентификатора

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

.        Для числа

Число должно принадлежать диапазону от 0 до 65535 (word).

Следовательно, его длина не может быть больше, чем 5.

{НЧ} - Начало числа

подготовка буфера для записи (очистка)

установка длины = 1

{ФЧ} - Формирование числа

запись очередного входного символа в буфер

увеличение длины на 1

проверка счетчика длины на допустимое значение (≤ 16)

{КЧ} - Конец числа

поиск числа в таблице чисел (если его нет, то добавляем )

добавляем лексему типа Num с длиной числа

указатель лексемы ставим на соответствующую ячейку таблицы чисел

.        Для служебного слова

Служебное слово должно быть точно описано в соответствии с языком.

{НС} - Начало служебного слова

подготовка буфера для записи (очистка)

установка длины = 1

{ФС} - Формирование служебного слова

запись очередного входного символа в буфер

увеличение длины на 1

{КС} - Конец служебного слова

поиск служебного слова в таблице служебных слов (если его нет, то ошибка )

добавляем лексему типа SSl с длиной служебного слова

указатель лексемы ставим на соответствующую ячейку таблицы служебных слов

.        Для константы (char, boolean)

Константы должны быть точно описаны в соответствии с языком.

{НК} - Начало константы

подготовка буфера для записи (очистка)

установка длины = 1

{ФК} - Формирование константы

запись очередного входного символа в буфер

увеличение длины на 1

{КК} - Конец константы

поиск константы в таблицах констант (char, boolean) (если ее нет, то ошибка)

добавляем лексему типа Log или Chr с длиной константы

указатель лексемы ставим на соответствующую ячейку соответствующей таблицы

.        Для разделителя

Разделители должны быть точно описаны в соответствии с языком.

{ФР} - Формирование разделителя

поиск разделителя в таблице разделителей (если его нет, то ошибка)

добавляем лексему типа Rzd с длиной = 1

указатель лексемы ставим на соответствующую ячейку таблицы разделителей

.        Дополнительные символы действия

{ФО} - Формирование ошибки

вывод информации об ошибке

{ЧС} - Чтение символа

чтение очередного входного символа из файла

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

Спецификация процедур:

BeginIdt (Ch)

Процедура формирования идентификатора и лексемы типа Idt

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

Выход:символ, следующий во входном файле непосредственно за идентификатором

BeginNum (Ch)

Процедура формирования числа и лексемы типа Num

Вход:  первый символ числа (цифра)

Выход:символ, следующий во входном файле непосредственно за числом

BeginSSl

Процедура распознавания служебного слова и формирование лексемы типа SSl

BeginConst

Процедура распознавания константы (симв. или лог.) и формирование лексемы типа Chr или Log

FormirRzd

Процедура формирования лексемы типа Rzd (разделитель)

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

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

Для задания семантики применяются различные приемы: W-грамматики, венский метаязык, аксиоматический и денотационный методы, а также атрибутные транслирующие грамматики (АТ - грамматики).

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

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

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

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

Когда на вход подается цепочка лексем, мы находим идентификатор переменной из описания, который имеет атрибут, указывающий на таблицу идентификаторов (ТИ), смотрим была ли описана эта переменная ранее. Если была, то выход с кодом ошибки. Если нет, то создаем элемент таблицы переменных и записываем в структуру переменной ее тип; выделяем память, соответствующую ее типу, в таблице значений и записываем ссылку в структуру переменной. Также необходимо занести информацию о том, что это - переменная (установить количество элементов = 1).

Если мы описываем массив, то мы в структуру переменной в ТП заносим информацию о массиве (количество элементов). После этого выделяем память в ТЗ, состоящей из N элементов (N - количество элементов в массиве). И далее записываем указатель в ТП на начало этого поля памяти (первый элемент массива).

Операции могут выполняться с двумя типами данных Boolean и Char. Операции не могут выполняться, если в них используются операнды различного типа. Чтобы это учесть, введем в структуру ячейки памяти поле TypeZ (TChar, TBool), которое и будет указывать нам тип переменной, значение которой хранится в данной ячейке. Также в выполнении операции не могут участвовать переменные и элементы массива, которые не имеют значения (не инициализированы).

При работе с массивами необходимо проверять индексы элементов массивов при обращении к ним на допустимые значения.

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

<I>_{↓a1 ↑b1} ::=<Vars> _{↓a2 ↑b2} <Code> _{↓a3 ↑b3}

_{a2=a1; a3=b2; b1=b3;}

<MasBool>_{↓a4 ↑b4 ↑x1} ::=’<arr>’ <Id>_↑x2 ’,’ <Chislo>_↑y1 {WrRM}_{↓x3 ↓y2} {FMB}_{↓a5 ↑b5 ↓x4} ’</arr>’

_{a5=a4; b4=b5; (x1, x3, x4)=x2; y2=y1;}

< MasChar>_{↓a6 ↑b6 ↑x5} ::=’<arr>’ <Id>_↑x6 ’,’ <Chislo>_↑y3 {WrRM}_{↓x7 ↓y4} {FMC}_{↓a7 ↑b7 ↓x8} ’</arr>’_{=a6; b6=b7; (x5, x7, x8)=x6; y4=y3;}

<ElMas>_↑t1 ::=’<earr>’<Id>_↑x9 ’,’ <Chislo>_↑y5 {FUkTZEM}_{↓x10 ↓y6 ↑t2} ’</earr>’

_{t1=t2; x10=x9; y6=y5;}

<Vars>_{↓a8 ↑b8} ::=’<boolean>’<NamesBool>_{↓a9 ↑b9} ’</boolean>’<R3>_{↓a10 ↑b10=b10; a9=a8; a10=b9;}

<Vars>_{↓a11 ↑b11} ::=’<char>’<NamesChar>_{↓a12 ↑b12} ’</char>’<R3>_{↓a13 ↑b13=b13; a12=a11; a13=b12;}

<R3>_{↓a14 ↑b14} ::=<Vars>_{↓a15 ↑b15=a14; b14=b15;}

<R3>_{↓a16 ↑b16} ::=$

_{b16= a16;}

<NamesBool>_{↓a17 ↑b17} ::=<Id>_↑x11 {NewB}_{↓a18 ↑b18 ↓x12} <R4>_{↓a19 ↑b19=b19; a18=a17; a19=b18; x12=x11;}

<NamesBool>_{↓a20 ↑b20} ::=<MasBool>_{↓a21 ↑b21 ↑x13} <R4>_{↓a22 ↑b22=b22; a21=a20; a22=b21;}

<R4>_{↓a23 ↑b23} ::=’,’<NamesBool>_{↓a24 ↑b24=a23; b23=b24;}

<R4>_{↓a25 ↑b25} ::=$

_{b25= a25;}

<NamesChar>_{↓a26 ↑b26} ::=<Id>_↑x14 {NewC}_{↓a27 ↑b27 ↓x15} <R5>_{↓a28 ↑b28=b28; a27=a26; a28=b27; x15=x14;}

<NamesChar>_{↓a29 ↑b29} ::=<MasChar>_{↓a30 ↑b30 ↑x16} <R5>_{↓a31 ↑b31=b31; a30=a29; a31=b30;}

<R5>_{↓a32 ↑b32} ::=’,’<NamesChar>_{↓a33 ↑b33=a32; b32=b33;}

<R5>_{↓a34 ↑b34} ::=$

_{b34= a34;}

<Code>_{↓a35 ↑b35} ::=’<ass>’<Perem>_↑t3 ’,’<Vyrazh>_{↓a36 ↑b36 ↑t4} {FAt=}_{↓t5 ↓t6 ↓t7} ’</ass>’<R6>_{↓a37 ↑b37=a35; a37=b36; b35=b37; (t5, t7)=t3; t6=t4;}

<Perem>_↑t8 ::= <Id>_↑x17 {FUkTZId}_{↓x18 ↑t9=x17; t8=t9;}

<Perem>_↑t10 ::= <ElMas>_↑t11=t11;

<Vyrazh>_{↓a38 ↑b38 ↑t12} ::= <Const>_{↑z1=a38; t12=z1;}

<Vyrazh>_{↓a39 ↑b39 ↑t13} ::= <Simvol>_{↑c1=a39; t13=c1;}

<Vyrazh>_{↓a40 ↑b40 ↑t14} ::= <Perem>_{↑t15=a40; t14=t15;}

<Vyrazh>_{↓a41 ↑b41 ↑t16} ::= <Operation>_{↓a42 ↑b42 ↑t17=a41; b41=b42; t16=t17;}

<Operation>_{↓a43 ↑b43 ↑t18} ::= ‘<and>’<Operand>_{↓a44 ↑b44 ↑t19} ’,’<Operand>_{↓a45 ↑b45 ↑t20}

{FAt&}_{↓t21 ↓t22 ↓t23} {NextZ}_{↓a46 ↑b46} ‘</and>’

_{a44=a43; a45=b44; b43=b46; (t18, t23, a46)=b45; t21=t19; t22=t20;}

<Operation>_{↓a47 ↑b47 ↑t24} ::= ‘<or>’<Operand>_{↓a48 ↑b48 ↑t25} ’,’<Operand>_{↓a49 ↑b49 ↑t26}

{FAtV}_{↓t27 ↓t28 ↓t29} {NextZ}_{↓a50 ↑b50} ‘</or>’

_{a48=a47; a49=b48; b47=b50; (t24, t29, a50)=b49; t27=t25; t28=t26;}

<Operation>_{↓a51 ↑b51 ↑t30} ::=‘<not>’<Operand>_{↓a52 ↑b52 ↑t31}{FAt!}_{↓t32 ↓t33 ↓t34}{NextZ}_{↓a53 ↑b53} ‘</not>’

_{a52=a51; b51=b53; (t30, t34, a53)=b52; t32=t31; t33=NULL;}

<Operand>_{↓a54 ↑b54 ↑t35} ::= <Operation>_{↓a55 ↑b55 ↑t36=a54; b54=b55; t35=t36;}

<Operand>_{↓a56 ↑b56 ↑t37} ::= <Perem>_{↑t38=a56; t37=t38;}

<Operand>_{↓a57 ↑b57 ↑t39} ::= <Const>_{↑z2=a57; t39=z2;}

<R6>_{↓a58 ↑b58} ::= <Code>_{↓a59 ↑b5959=a58; b58=b59;}

<R6>_{↓a60 ↑b60} ::= $

_b60=a60;

Для работы нам понадобятся следующие типы атрибутов:

. Для идентификатора:

X - ссылка на идентификатор в таблице идентификаторов

. Для числа:

↑Y - ссылка на число в таблице чисел

. Для логической константы:

↑Z - номер ячейки в таблице логических констант

. Для символьной константы:

↑С - номер ячейки в таблице символьных констант

4.      Для ячеек таблицы значений

↓A - указатель на первую свободную ячейку до начала трансляции выражения

↑B - указатель на первую свободную ячейку после завершения трансляции выражения

T - указатель на ячейку, в которой хранится (в которую необходимо записать) значение  выражения (константы, переменной, элемента массива, результата операции)

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

{WrRM}_{↓x ↓y}Запись размера массива в структуру идентификатора.

x- ссылка на идентификатор в ТИ (куда нужно записать)

{FMB}_{↓a ↑b ↓x}Формирование массива Boolean

{FMC}_{↓a ↑b ↓x}Формирование массива Char

a - указатель на первую свободную ячейку ТЗ, откуда можно начинать  формирование b - новый указатель на первую свободную ячейку ТЗ

x - ссылка на идентификатор в ТИ (в структуре которого находится   информация о массиве)

Проверяет количество элементов на допустимое значение, если значение допустимо, то формирует в ТЗ массив.

{FUkTZEM}_{↓x ↓y ↑t}Формирование указателя на ячейку ТЗ, в которой хранится значение элемента массива

x - ссылка на идентификатор массива в ТИ

y - ссылка на число в ТЧ (номер элемента в массиве)

t - сформированный указатель на ячейку ТЗ

{NewB}_{↓a ↑b ↓x}Выделение памяти под переменную типа Boolean

{NewC}_{↓a ↑b ↓x}Выделение памяти под переменную типа Char

a - указатель на первую свободную ячейку ТЗ (выделяемая ячейка)

b - новый указатель на первую свободную ячейку ТЗ

x - ссылка на идентификатор переменной в ТИ, для которой  необходимо выделить память

Устанавливает указатель на ТЗ в структуре идентификатора.

{FUkTZId}_{↓x ↑t}Формирование указателя на ячейку ТЗ, в которой хранится значение переменной

x - ссылка на идентификатор переменной в ТИ

t - сформированный указатель на ячейку ТЗ

{FAt=}_{↓t1 ↓t2 ↓t3}Формирование атома (=, Операнд1, Операнд2, Результат)

t1 - указатель на ячейку памяти, в которой хранится значение Операнд1

t2 - указатель на ячейку памяти, в которой хранится значение Операнд2

t3 - указатель на ячейку памяти, в которую нужно записать Результат

Проверяет по значению поля TypeZ структуры ячейка памяти типы

Операнд1 и Операнд2. Если они совпадают, то формирует атом(=, Операнд1, Операнд2, Операнд1).

{FAt&}_{↓t1 ↓t2 ↓t3}Формирование атома (&, Операнд1, Операнд2, Результат)

t1 - указатель на ячейку памяти, в которой хранится значение Операнд1

t2 - указатель на ячейку памяти, в которой хранится значение Операнд2

t3 - указатель на ячейку памяти, в которую нужно записать Результат

Проверяет по значению поля TypeZ структуры ячейка памяти типы

Операнд1 и Операнд2. Если они совпадают и имеют значение TBool, то формирует атом(=, Операнд1, Операнд2, Результат).

{FAtV}_{↓t1 ↓t2 ↓t3}Формирование атома (&, Операнд1, Операнд2, Результат)

t1 - указатель на ячейку памяти, в которой хранится значение Операнд1

t2 - указатель на ячейку памяти, в которой хранится значение Операнд2

t3 - указатель на ячейку памяти, в которую нужно записать Результат

Проверяет по значению поля TypeZ структуры ячейка памяти типы

Операнд1 и Операнд2. Если они совпадают и имеют значение TBool, то формирует атом(V, Операнд1, Операнд2, Результат).

{FAt!}_{↓t1 ↓t2 ↓t3}Формирование атома (!, Операнд, NULL, Результат)

t1 - указатель на ячейку памяти, в которой хранится значение Операнд

t2 - NULL (унарная операция)

t3 - указатель на ячейку памяти, в которую нужно записать Результат

Проверяет по значению поля TypeZ структуры ячейка памяти тип

Операнд. Если он имеет значение TBool, то формирует атом(!, Операнд, NULL, Операнд).

{NextZ}_{↓a ↑b}Получение указателя на очередную свободную ячейку ТЗ

а - указатель на ячейку ТЗ

b - сформированный указатель на очередную свободную ячейку ТЗ

грамматика лексический атрибутный преобразователь

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

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

Порядок построения АТ - преобразователя по заданной LАТ-грамматике в форме простого присваивания выглядит следующим образом:

1)   Удалим из правил заданной LАТ-грамматики все атрибуты и правила их вычисления. В результате получим транслирующую грамматику.

2)   Для полученной транслирующей грамматики построим преобразователь. Учитывая, что такой преобразователь в дальнейшем должен быть использован для работы с атрибутами, внесем следующие изменения в правила его построения:

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

(s₀ , <заданная цепочка>, h₀ ),

б) откажемся от совмещения команд для правил вида <А> à b , где b является терминалом, имеющим атрибут, и  - некоторая цепочка из терминальных и нетерминальных символов, используя вместо команды

f(s₀, b,<A>) = (s₀, a^R)

две команды

*(s₀, b, <A>) = (s₀, a^Rb)

(s₀, b, b) = (s₀, $),

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

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

*( S, <char>, [] ) = ( S, []<I>, $ )

*( S, <boolean>, [] ) = ( S, []<I>, $ )

( S, "<arr>" , <masbool> ) = ( S, "</arr>" "{FMB}" "{WrRM}" "<chislo>" "," "<id>" , $ )

( S, "<arr>" , <maschar> ) = ( S, "</arr>" "{FMC}" "{WrRM}" "<chislo>" "," "<id>" , $ )

( S, "<earr>" , <elmas> ) = ( S, "</earr>" "{FUkTZEM}" "<chislo>" "," "<id>" , $ )

( S, "<boolean>" , <vars> ) = ( S, <r3> "</boolean>" <namesbool> , $ )

( S, "<char>" , <vars> ) = ( S, <r3> "</char>" <nameschar> , $ )

*( S, "<id>" , <namesbool> ) = ( S, <r4> "{NewB}" "<id>", $ )

( S, "," , <r4> ) = ( S, <namesbool> , $ )

*( S, "<id>" , <nameschar> ) = ( S, <r5> "{NewC}" "<id>", $ )

( S, "," , <r5> ) = ( S, <nameschar> , $ )

( S, "<ass>" , <code> ) = ( S, <r6> "</ass>" "{FAt=}" <vyrazh> "," <perem> , $ )

*( S, "<id>" , <perem> ) = ( S, "{FUkTZId}" "<id>", $ )

*( S, "<const>" , <vyrazh> ) = ( S, "<const>" , $ )

*( S, "<simvol>" , <vyrazh> ) = ( S, "<simvol>" , $ )

( S, "<and>" , <operation> ) = ( S, "</and>" "{NextZ}" "{FAt&}" <operand> "," <operand> , $ )

( S, "<or>" , <operation> ) = ( S, "</or>" "{NextZ}" "{FAtV}" <operand> "," <operand> , $ )

( S, "<not>" , <operation> ) = ( S, "</not>" "{NextZ}" "{FAt!} " <operand> , $ )

*( S, "<const>" , <operand> ) = ( S, "<const>" , $ )

*( S, "<boolean>" , <i> ) = ( S, <code> <vars> , $ )

*( S, "<char>" , <i> ) = ( S, <code> <vars> , $ )

*( S, "<boolean>" , <r3> ) = ( S, <vars> , $ )

*( S, "<char>" , <r3> ) = ( S, <vars> , $ )

*( S, "<arr>" , <namesbool> ) = ( S, <r4> <masbool> , $ )

*( S, "<arr>" , <nameschar> ) = ( S, <r5> <maschar> , $ )

*( S, "<earr>" , <perem> ) = ( S, <elmas> , $ )

*( S, "<id>" , <vyrazh> ) = ( S, <perem> , $ )

*( S, "<earr>" , <vyrazh> ) = ( S, <perem> , $ )

*( S, "<and>" , <vyrazh> ) = ( S, <operation> , $ )

*( S, "<or>" , <vyrazh> ) = ( S, <operation> , $ )

*( S, "<not>" , <vyrazh> ) = ( S, <operation> , $ )

*( S, "<and>" , <operand> ) = ( S, <operation> , $ )

*( S, "<or>" , <operand> ) = ( S, <operation> , $ )

*( S, "<not>" , <operand> ) = ( S, <operation> , $ )

*( S, "<id>" , <operand> ) = ( S, <perem> , $ )

*( S, "<earr>" , <operand> ) = ( S, <perem> , $ )

*( S, "<ass>" , <r6> ) = ( S, <code> , $ )

*( S, "<ass>" , <r3> ) = ( S, $ , $ )

*( S, "</boolean>" , <r4> ) = ( S, $ , $ )

*( S, "</char>" , <r5> ) = ( S, $ , $ )

*( S, -|, <r6> ) = ( S, $ , $ )

( S, "," , "," ) = ( S , $ , $ )

( S, "<id>" , "<id>" ) = ( S , $ , $ )

( S, "<chislo>" , "<chislo>" ) = ( S , $ , $ )

( S, "</ass>" , "</ass>" ) = ( S , $ , $ )

( S, "</arr>" , "</arr>" ) = ( S , $ , $ )

( S, "</earr>", "</earr>" ) = ( S , $ , $ )

( S, "</boolean>" , "</boolean>" ) = ( S , $ , $ )

( S, "</char>" , "</char>" ) = ( S , $ , $ )

( S, "</and>" , "</and>" ) = ( S , $ , $ )

( S, "</or>" , "</or>" ) = ( S , $ , $ )

( S, "</not>" , "</not>" ) = ( S , $ , $ )

*( S, "{WrRM}", "{WrRM}") = (S, $, $ )

*( S, "{FMB}", "{FMB}") = (S, $, $ )

*( S, "{FMC}", "{FMC}") = (S, $, $ )

*( S, "{NewB}", "{NewB}") = (S, $, $ )

*( S, "{NewC}", "{NewC}") = (S, $, )

*( S, "{FUkTZEM}", "{FUkTZEM}") = (S, $, $ )

*( S, "{FUkTZId}", "{FUkTZId}") = (S, $, $ )

*( S, "{FAt=}", "{FAt=}") = (S, $, $ )

*( S, "{FAt&}", "{FAt&}") = (S, $, $ )

*( S, "{FAtV}", "{FAtV}") = (S, $, $ )

*( S, "{FAt!}", "{FAt!} ") = (S, $, $ )

*( S, "{NextZ}", "{NextZ}") = (S, $, $ )

( S, -|, [] ) = ( S1, $, $ )

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

Для каждого правила заданной атрибутной грамматики необходимо построить инструкции, выполняемые при записи правила в магазин. Затем нужно все инструкции пронумеровать, обозначив их # N.

Инструкции атрибутного преобразователя :

Инструкция #1

{

Записать в магазин цепочку

b1 a1 <I>

stack [sp-1]:=a// a - начальное значение атрибута а1 (указатель на первую своб. ячеку ТЗ)

}

Инструкция #2

{

Удалить символ из магазина

Записать в магазин цепочку

b3 a3 <Code> b2 a2 <Vars>[sp-1]:=-5[sp-2]:=-2[sp-5]:=-2

}

Инструкция #3

{

Удалить символ из магазина

Записать в магазин цепочку

‘</arr>’ x4 b5 a5 {FMB} y2 x3 {WrRM} y1 <Chislo> ‘,’ x2 <Id>[sp-1]:=-5[sp-4]:=-3[sp-6]:=-5[sp-9]:=-3[sp-10]:=-3[sp-11]:=-3

}

Инструкция #4

{

Удалить символ из магазина

Записать в магазин цепочку

‘</arr>’ x8 b7 a7 {FMC} y4 x7 {WrRM} y3 <Chislo> ‘,’ x6 <Id>[sp-1]:=-5[sp-4]:=-3[sp-6]:=-5[sp-9]:=-3[sp-10]:=-3[sp-11]:=-3

}

Инструкция #5

{

Удалить символ из магазина

Записать в магазин цепочку

‘</earr>’ t2 y6 x10 {FUkTZEM} y5 <Chislo> ‘,’ x9 <Id>[sp-1]:=-4[sp-3]:=-3[sp-7]:=-7}

Инструкция #6

{

Удалить символ из магазина

Записать в магазин цепочку

b10 a10 <R3> ‘</boolean>’ b9 a9 <NamesBool>[sp-1]:=-6[sp-2]:=-3[sp-6]:=-2

}

Инструкция #7

{

Удалить символ из магазина

Записать в магазин цепочку

b13 a13 <R3> ‘</char>’ b12 a12 <NamesChar>[sp-1]:=-6[sp-2]:=-3[sp-6]:=-2

}

Инструкция #8

{

Удалить символ из магазина

Записать в магазин цепочку

b19 a19 <R4> x12 b18 a18 {NewB} x11 <Id>[sp-1]:=-4[sp-3]:=-6[sp-4]:=-3 [sp-8]:=-2

}

Инструкция #9

{

Удалить символ из магазина

Записать в магазин цепочку

b24 a24 <NamesBool>

stack [sp-1]:=-2[sp-2]:=-2

}

Инструкция #10

{

Удалить символ из магазина

Записать в магазин цепочку

b28 a28 <R5> x15 b27 a27 {NewC} x14 <Id>[sp-1]:=-4[sp-3]:=-6[sp-4]:=-3 [sp-8]:=-2

}

Инструкция #11

{

Удалить символ из магазина

Записать в магазин цепочку

b33 a33 <NamesChar>

stack [sp-1]:=-2[sp-2]:=-2

}

Инструкция #12

{

Удалить символ из магазина

Записать в магазин цепочку

b37 a37 <R6> ‘</ass>’ t7 t6 t5 {FAt=} t4 b36 a36 <Vyrazh> ‘,’ t3 <Perem>[sp-1]:=-7[sp-4]:=-11[sp-5]:=-8[sp-6]:=-3[sp-8]:=-2[sp-14]:=-2

}

Инструкция #13

{

Удалить символ из магазина

Записать в магазин цепочку

t9 x18 {FUkTZId} x17 <Id>[sp-1]:=-2[sp-4]:=-1

}

Инструкция #14

{

Удалить символ из магазина

Записать в магазин цепочку

z1 <Const>[sp-1]:=-3[sp-2]:=-1

}

Инструкция #15

{

Удалить символ из магазина

Записать в магазин цепочку

c1 <Simvol>[sp-1]:=-3[sp-2]:=-1

}

Инструкция #16

{

Удалить символ из магазина

Записать в магазин цепочку

‘</and>’ b46 a46 {NextZ} t23 t22 t21 {FAt&} t20 b45 a45 <Operand> ‘,’ t19 b44 a44 <Operand>[sp-1]:=-16[sp-2]:=-4[sp-3]:=-7[sp-7]:=-5[sp-8]:=-3[sp-12]:=-2[sp-14]:=-5[sp-15]:=-3

}

Инструкция #17

{

Удалить символ из магазина

Записать в магазин цепочку

‘</or>’ b50 a50 {NextZ} t29 t28 t27 {FAtV} t26 b49 a49 <Operand> ‘,’ t25 b48 a48 <Operand>[sp-1]:=-16[sp-2]:=-4[sp-3]:=-7[sp-7]:=-5[sp-8]:=-3[sp-12]:=-2[sp-14]:=-5[sp-15]:=-3

}

Инструкция #18

{

Удалить символ из магазина

Записать в магазин цепочку

‘</not>’ b53 a53 {NextZ} t34 t33 t32 {FAt!} t31 b52 a52 <Operand>[sp-1]:=-11[sp-2]:=-5[sp-3]:=-2[sp-6]:=Null[sp-7]:=-2[sp-9]:=-5[sp-10]:=-2

}

Инструкция #19

{

Удалить символ из магазина

Записать в магазин цепочку

z2 <Const>[sp-1]:=-3[sp-2]:=-1

}

Инструкция #20

{

Удалить символ из магазина

Записать в магазин цепочку

b15 a15 <Vars>[sp-1]:=-2 [sp-2]:=-2

}

Инструкция #21

{

Удалить символ из магазина

Записать в магазин цепочку

b22 a22 <R4> x13 b21 a21 <MasBool>

stack [sp-1]:=-6[sp-2]:=-3[sp-6]:=-2

}

Инструкция #22

{

Удалить символ из магазина

Записать в магазин цепочку

b31 a31 <R5> x16 b30 a30 <MasChar>[sp-1]:=-6[sp-2]:=-3[sp-6]:=-2

}

Инструкция #23

{

Удалить символ из магазина

Записать в магазин цепочку

t11 <ElMas>[sp-1]:=-1

}

Инструкция #24

{

Удалить символ из магазина

Записать в магазин цепочку

t15 <Perem>[sp-1]:=-3[sp-2]:=-1}

Инструкция #25

{

Удалить символ из магазина

Записать в магазин цепочку

t17 b42 a42 <Operation>[sp-1]:=-3[sp-2]:=-3[sp-3]:=-3}

Инструкция #26

{

Удалить символ из магазина

Записать в магазин цепочку

t36 b55 a55 <Operation>[sp-1]:=-3[sp-2]:=-3[sp-3]:=-3

}

Инструкция #27

{

Удалить символ из магазина

Записать в магазин цепочку

t38 <Perem>[sp-1]:=-3[sp-2]:=-1

}

Инструкция #28

{

Удалить символ из магазина

Записать в магазин цепочку

b59 a59 <Code>[sp-1]:=-2 [sp-2]:=-2

}

Инструкция #29

{

Удалить символ из магазина

stack [sp]:=-1

}

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

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

(S, <входной символ>, <вершина магазина>) = (S, <номер выполняемой инструкции>)

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

*( S, <char>, [] ) = ( S, #1 )

*( S, <boolean>, [] ) = ( S, #1 )

( S, "<arr>" , <masbool> ) = ( S, #3 )

( S, "<arr>" , <maschar> ) = ( S,#4 )

( S, "<earr>" , <elmas> ) = ( S, #5 )

( S, "<boolean>" , <vars> ) = ( S, #6 )

( S, "<char>" , <vars> ) = ( S, #7 )

*( S, "<id>" , <namesbool> ) = ( S, #8 )

( S, "," , <r4> ) = ( S, #9 )

*( S, "<id>" , <nameschar> ) = ( S, #10 )

( S, "," , <r5> ) = ( S, #11 )

( S, "<ass>" , <code> ) = ( S, #12 )

*( S, "<id>" , <perem> ) = ( S, #13 )

*( S, "<const>" , <vyrazh> ) = ( S, #14 )

*( S, "<simvol>" , <vyrazh> ) = ( S, #15 )

( S, "<and>" , <operation> ) = ( S, #16 )

( S, "<or>" , <operation> ) = ( S, #17 )

( S, "<not>" , <operation> ) = ( S, #18 )

*( S, "<const>" , <operand> ) = ( S, #19 )

*( S, "<boolean>" , <i> ) = ( S, #2 )

*( S, "<char>" , <i> ) = ( S, #2 )

*( S, "<boolean>" , <r3> ) = (S, #20 )

*( S, "<char>" , <r3> ) = (S, #20 )

*( S, "<arr>" , <namesbool> ) = ( S, #21 )

*( S, "<arr>" , <nameschar> ) = ( S, #22 )

*( S, "<earr>" , <perem> ) = ( S, #23 )

*( S, "<id>" , <vyrazh> ) = ( S, #24 )

*( S, "<earr>" , <vyrazh> ) = ( S, #24 )

*( S, "<and>" , <vyrazh> ) = ( S, #25 )

*( S, "<or>" , <vyrazh> ) = ( S, #25 )

*( S, "<not>" , <vyrazh> ) = ( S, #25 )

*( S, "<and>" , <operand> ) = ( S, #26 )

*( S, "<or>" , <operand> ) = ( S, #26 )

*( S, "<not>" , <operand> ) = ( S, #26 )

*( S, "<id>" , <operand> ) = ( S, #27 )

*( S, "<earr>" , <operand> ) = ( S, #27 )

*( S, "<ass>" , <r6> ) = ( S, <code> , #28 )

*( S, "<ass>" , <r3> ) = ( S, #29 )

*( S, "</boolean>" , <r4> ) = ( S, #29 )

*( S, "</char>" , <r5> ) = ( S, #29 )

*( S, -|, <r6> ) = ( S, #29 )

( S, "," , "," ) = ( S , $ , $ )

( S, "<id>" , "<id>" ) = ( S , $ , $ )

( S, "<chislo>" , "<chislo>" ) = ( S , $ , $ )

( S, "</ass>" , "</ass>" ) = ( S , $ , $ )

( S, "</earr>", "</earr>" ) = ( S , $ , $ )

( S, "</boolean>" , "</boolean>" ) = ( S , $ , $ )

( S, "</char>" , "</char>" ) = ( S , $ , $ )

( S, "</and>" , "</and>" ) = ( S , $ , $ )

( S, "</or>" , "</or>" ) = ( S , $ , $ )

( S, "</not>" , "</not>" ) = ( S , $ , $ )

*( S, "{WrRM}", "{WrRM}") = (S, $, $ )

*( S, "{FMB}", "{FMB}") = (S, $, $ )

*( S, "{FMC}", "{FMC}") = (S, $, $ )

*( S, "{NewB}", "{NewB}") = (S, $, $ )

*( S, "{NewC}", "{NewC}") = (S, $, )

*( S, "{FUkTZEM}", "{FUkTZEM}") = (S, $, $ )

*( S, "{FUkTZId}", "{FUkTZId}") = (S, $, $ )

*( S, "{FAt=}", "{FAt=}") = (S, $, $ )

*( S, "{FAt&}", "{FAt&}") = (S, $, $ )

*( S, "{FAtV}", "{FAtV}") = (S, $, $ )

*( S, "{FAt!}", "{FAt!} ") = (S, $, $ )

*( S, "{NextZ}", "{NextZ}") = (S, $, $ )

( S, -|, [] ) = ( S1, $, $ )

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

Список используемой литературы

1. Гордеев А.В., Молчанов А.Ю. Системное программное обеспечение / Учебник для вузов. - СПб.: Питер, 2001.

2.      Ахо А., Сети Р., Ульман Д. Компиляторы: принципы, технологии и инструменты. - М., Изд. дом «Вильямс», 2001.

.        Пратт Т., Зелковиц М. Языки программирования: реализация и разработка. - СПб.: Питер, 2001.

.        Рейуорд-Смит В.Дж. Теория формальных языков. Вводный курс. - М.: Радио и связь, 1988.

.        Хантер Р. Проектирование и конструирование компиляторов. - М.: Финансы и статистика, 1984.

.        Льюис Ф., Розенкранц Д., Стирнз Р. Теоретические основы проектирования компиляторов. - М., Мир, 1979.

.        Грис Д. Конструирование компиляторов для цифровых вычислительных машин. - М., Мир, 1985.