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

Размещено на http://www.allbest.ru/

Содержание

1. Задание

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

где:

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

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

цепочек;

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

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

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

<A> ,;

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

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

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

СУ-схема Т ={V_a, V_твх, V_твых, R, <I>} называется простой, если для каждого правила <A> , из 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> ,

b1` ``bool'` `<Perem>` `<Vyrazh>'='<R6>)

( <boolean>b1</boolean><ass><ID>',`<Vyrazh></ass><R6> ,

b1` ``bool'` `<ID>` `<Vyrazh>'='<R6>)

( <boolean>b1</boolean><ass>b1',`<Vyrazh></ass><R6> ,

b1` ``bool'` `b1` `<Vyrazh>'='<R6>)

( <boolean>b1</boolean><ass>b1',`<Operation></ass><R6> ,

b1` ``bool'` `b1` `<Operation>'='<R6>)

( <boolean>b1</boolean><ass>b1',`<not><Operand></not></ass><R6> ,

b1` ``bool'` `b1` `<Operand>'!''='<R6>)

( <boolean>b1</boolean><ass>b1',`<not><Const></not></ass><R6> ,

b1` ``bool'` `b1` `<Const>'!''='<R6>)

( <boolean>b1</boolean><ass>b1' `<not>'false'</not></ass><R6> ,

b1` ``bool'` `b1` `'false''!''='<R6>)

( <boolean>b1</boolean><ass>b1' `<not>'false'</not></ass> ,

b1` ``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' ! =

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

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

f ( S, b, A)=( S, ', $),

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

( 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>, где BОVa и aО(V_твхUV_твыхUV_a)*, строим функции вида:

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

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

*( 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, "<and>" , <operand> ) = ( 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'"!=

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

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

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

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

I cA

A cA

A dA

A rI

c - буква

d - цифра

r - разделитель (`,' , ' ` , '<')

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

I dB

B dB

B rB

d - цифра

r - разделитель (`,' , ' ` , '<')

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

I <C

C /E

E cD

C cD

D cD

D >I

c - буква

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

I 'F

F cG

G cG

G 'I

c - буква

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

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

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

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

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

TSSl: array[1..16] of StrType = ('char','/char','boolean','/boolean',

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

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

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

TLog: array[1..2] of StrType = ('true','false');

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

TChr: 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');

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

TRzd = ',';

type

TPerem=(TChar,TBool); { - Возможный тип переменной }

TIdent=string[16]; { - Макс. длина идентификатора }

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

{ - Типы лексем:

Idt - идентификатор - a, b[2] Num - целое число (б/зн) - 12, 2341

Rzd - разделитель - "," SSl - служебное слово - <and>, </or>

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

{ Типы, определяющие: }

TAdrTP =^TElTP; { - таблицу переменных - ТП }

TAdrTSP =^TElTSP; { - таблицу симв. представления - ТСП }

TAdrTZ =^TElTZ; { - таблицу значений - ТЗ (ячейки памяти)}

TAdrTN =^TElTN; { - таблицу чисел - ТЧ }

TAdrTL =^TElTL; { - таблицу лексем - ТЛ }

TElTP= record { Тип эл-та ТП: }

TypeP :TPerem; { - тип переменной (TBool, TChar) }

PointTSP:TAdrTSP; { - указатель на эл-т ТСП }

PointTZ :TAdrTZ; { - указатель на эл-т ТЗ }

Dim :Word; { - кол-во эл-тов (+1) в ТЗ

если Dim > 0 , то это - массив }

NextP :TAdrTP; { - указатель на след. эл-т ТП }

end;

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

SimvP :TIdent; { - идентификатор (симв. представление) }

NextS :TAdrTSP; { - указатель на след. эл-т ТСП }

end;

TElTN= record { Тип эл-та ТЧ: }

Numer :Word; { - значение : 0..65535 }

NextN :TAdrTN; { - указатель на след. эл-т ТЧ }

end;

TElTZ= record { Тип эл-та ТЗ: (ячейки памяти) }

TypeZ :TPerem; { - тип хранимого значения }

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

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

end;

TElTL= record { Тип эл-та ТЛ: }

LenL :Byte; { - длина лексемы }

NextL :TAdrTL; { - указатель на след. эл-т ТЛ }

case TypeL:TypeLx of

{ варианты }

Idt: (PointPer :TAdrTP); { - для ид-ра }

Num: (PointNum :TAdrTN); { - для числа }

SSl,Log,Chr : (Index :Byte ); { - для служ. слов,констант}

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

end;

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

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

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

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

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

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

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

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

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

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

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

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

<ass> b7, <not> `true' </not> </ass>

<ass> <earr> ac1, 3 </earr>, `C' </ass>

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

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

1 char9 ass

2/char10/ass

3 boolean11 and

4/boolean12/and

5 arr13 or

6/arr14/or

7 earr15 not

8/earr16/not

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

17`,'

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

18`a'

19`b'

…

43`z'

44`0'

45`1'

…

53`9'

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

54`true'

55`false'

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

56ch

57ac1

58b7

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

595

603

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

№	Тип лексемы	Длина лексемы	Языковая конструкция	Указатель
1	SSl	4	Служ. слово: char	1
2	Idt	2	Идентификатор: ch	56
3	Rzd	1	Разделитель: ,	17
4	SSl	3	Служ. слово: arr	5
5	Idt	3	Идентификатор: ac1	57
6	Rzd	1	Разделитель: ,	17
7	Num	1	Число: 5	59
8	SSl	4	Служ. слово: /arr	6
9	SSl	5	Служ. слово: /char	2
10	SSl	7	Служ. слово: boolean	3
11	Idt	2	Идентификатор: b7	58
12	SSl	8	Служ. слово: /boolean	4
13	SSl	3	Служ. слово: ass	9
14	Idt	2	Идентификатор: b7	58
15	Rzd	1	Разделитель: ,	17
16	SSl	3	Служ. слово: not	15
17	Log	4	Лог. константа: true	54
18	SSl	4	Служ. слово: /not	16
19	SSl	4	Служ. слово: /ass	10
20	SSl	3	Служ. слово: ass	9
21	SSl	4	Служ. слово: earr	7
22	Idt	3	Идентификатор: ac1	57
23	Rzd	1	Разделитель: ,	17
24	Num	1	Число: 3	60
25	SSl	5	Служ. слово: /earr	8
26	Rzd	1	Разделитель: ,	17
27	Chr	1	Симв. константа: z	43
28	SSl	4	Служ. слово: /ass	10

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2. Для числа

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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



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

BeginIdt (Ch)

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

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

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

BeginNum (Ch)

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

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

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

BeginSSl

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

BeginConst

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

FormirRzd

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

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

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

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

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

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

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

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

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

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

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

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

4.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>'

_{a7=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}

_{b8=b10; a9=a8; a10=b9;}

<Vars>_{Ѓ«a11 ЃЄb11} ::='<char>'<NamesChar>_{Ѓ«a12 ЃЄb12} '</char>'<R3>_{Ѓ«a13 ЃЄb13}

_{b11=b13; a12=a11; a13=b12;}

<R3>_{Ѓ«a14 ЃЄb14} ::=<Vars>_{Ѓ«a15 ЃЄb15}