- •Описание атрибутно-транслирующих грамматик
- •1.Грамматика раздела описания программы
- •2. Грамматика раздела описания меток
- •3. Грамматика раздела описания констант
- •4. Грамматика раздела описания типов
- •5. Грамматика раздела описания переменных
- •8. Грамматика описания операторов
- •9. Грамматика видов операторов
- •10. Грамматика операторов ввода и вывода
- •11. Грамматика оператора присваивания
- •12. Грамматика операторов цикла, условного оператора и оператора безусловного перехода
- •13. Грамматика операторов над списком
- •14. Грамматика логических выражений
- •15. Грамматика арифметических выражений
- •16. Грамматика вызовов функций
- •2. Грамматика раздела описания меток
- •3. Грамматика раздела описания констант
Министерство образования и науки РФ
Санкт-Петербургский государственный электротехнический университет «ЛЭТИ»
кафедра МО ЭВМ
Пояснительная записка
к курсовой работе
по дисциплине
«Теория языков программирования»
Выполнили: студенты гр. 3341 Рыжок М.С
Белов Д.А.
Проверил: доцент кафедры МО ЭВМ Самойленко В.П.
Санкт-Петербург 2006
Задание на курсовую работу
В процессе выполнения курсовой работы необходимо разработать язык программирования, являющийся подмножеством заданного языка, и транслятор с этого языка в промежуточный язык, тип которого определяется вариантом индивидуального задания. Метод синтаксического анализа также определяется заданием.
Язык должен обеспечивать операции над переменными и константами заданных базовых типов, а также над переменными и компонентами производного типа, которые определяются вариантом задания. Перечень операций должен включать как предусмотренные базовым языком, так и операции, перечисленные в варианте задания. В языке должна быть определена операция преобразования типов при именной или структурной эквивалентности типов. В языке должна быть предусмотрена возможность создания пользовательских типов.
Язык должен допускать использование арифметических выражений, в состав которых могут входить константы и простые переменные базовых типов, компоненты структурированных типов, круглые скобки и знаки операций сложения, вычитания, умножения, деления. Приоритет операций – обычный.
Язык должен допускать использование логических выражений, в состав которых могут входить отношения, круглые скобки и знаки логических операций: И, ИЛИ, НЕ и, в случае наличия в языке логического типа, константы и переменные этого типа. Приоритет операций обычный.
Операции над переменными структурированного типа определяются вариантом задания.
Состав операторов языка:
оператор присваивания
оператор ввода
оператор вывода
составной оператор
оператор безусловного перехода
условный оператор, условие в котором задается логическим выражением
оператор цикла, условие в котором задается логическим выражением
Конкретный вид операторов определяется вариантом задания.
Программа на входном языке может содержать комментарии, вид которых предусмотрен базовым языком
Вариант 5 задания на курсовую работу
Базовый язык – Паскаль
Базовые типы – целый, вещественный, булевский, ограниченный, перечислимый
Структурированные типы: запись, список
Операции над списком: определение количества элементов в списке, конкатенация списков, поиск элемента в списке, получение элемента списка с заданным номером.
Оператор цикла – с предусловием.
Перегрузка операций – не разрешается
Эквивалентность типов – именная
Класс грамматик – грамматики слабого предшествования
Промежуточный язык – триады
Описание синтаксиса входного языка с помощью металингвистических формул Бэкуса-Наура
<программа>::=[program<идентификатор>]{<описание объектов программы>;}<раздел операторов>.
<описание объектов программы>::=<раздел меток>|<раздел описания типов>|<раздел описания переменных>|<раздел описания констант>|<раздел описания переменных>
<раздел меток>::= label<метка> {,<метка>}
<метка>::=<идентификатор>|<целое без знака>
<раздел описания типов> ::= type<определение типа> {;<определение типа>}
<определение типа>::=<имя типа>=<тип>
<имя типа>::= <идентификатор>
<тип>::=<простой тип>|<составной тип>|<имя типа>
<простой тип>::=integer|real|boolean|<диапазонный тип>|<перечислимый тип>
<составной тип>::=<запись>|<список>
<диапазонный тип>::=<константа>..<константа>
<перечислимый тип>::=(<перечень имен>)
<запись>::= record<перечень полей>end
<перечень полей>::=[<секция записи>{;<секция записи>}]
<секция записи>::=<перечень имен> : <тип>
<список>::=list of <тип данных элементов списка>
<тип данных элементов списка>::=<имя типа>|<тип>
<раздел описания констант>::= const<определение константы> {;<определение константы>}
<определение константы>::=<имя константы>:=<выражение>
<имя константы>::=<идентификатор>
<константа>::=<целое число>|<вещественное число>
<раздел описания переменных>::=var<описание переменных>{;<описание переменных>}
<описание переменных>::= <перечень имен> :<тип>
<перечень имен>::=<идентификатор> {,<идентификатор>}
<переменная>::=<идентификатор>|<поле записи>
<поле записи>::=<имя записи>.<имя поля>
<имя записи>::=<идентификатор>
<имя поля>::=<переменная>
<раздел операторов>::=<составной оператор>
<составной оператор>::= begin<последовательность операторов>end
<последовательность операторов>::=<оператор>{;<оператор>}
<оператор>::= [метка :] <непомеченный оператор>
<непомеченный оператор>::= <пустой оператор>|<оператор присваивания>|<оператор ввода>|<оператор вывода>|<составной оператор>|<оператор безусловного перехода>|<условный оператор>|<цикл с предусловием>|<оператор преобразования типов>|<операции над списком>
<пустой оператор>::=ε
<оператор присваивания>::=<переменная>:=<выражение>
<оператор ввода>::= read(<переменная>)
<оператор вывода>::= write(<перечень данных>)
<перечень данных>::=<единица данных>{,<единица данных>}
<единица данных>::=<выражение>|<переменная>
<условный оператор>::=if<условие>then<оператор> [else<оператор>]
<оператор безусловного перехода>::= goto<метка>
<цикл с предусловием>::= while<условие>do<оператор>
<условие>::=<выражение сравнения>|<логическое выражение>
<оператор преобразования типов>::=<идентификатор типа>(<переменная>)
<операции над списком>::=<добавление нового элемента> |<конкатенация списков>|<поиск элемента в списке>|<получение элемента списка с заданным номером>|<удаление элемента с заданным номером>|<изменение значения элемента с заданным номером>
<добавление нового элемента>::=add(<имя списка>, <значение элемента>)
<изменение значения элемента>::=set(<имя списка>, <целое без знака>, <значение элемента>)
<определение количества элементов>::=quantity(<имя списка>)
<конкатенация списков>::=concat(<имя списка>{,<имя списка>})
<поиск элемента в списке>::=find(<имя списка>, <значение элемента>, <переменная>)
<получение элемента списка с заданным номером>::=count(<имя списка>, <целое без знака>)
<удаление элемента с заданным номером>::=remove(<имя списка>, <целое без знака>)
<имя списка>::=<идентификатор>
<значение элемента>::=<число><булевское число>|<переменная>|<простое выражение>|<выражение сравнения>
<выражение сравнения>::=<простое выражение><знак сравнения><простое выражение>
<знак сравнения>::=<|>|<=|>=|<>|=
<простое выражение>::= <терм 1><остаток суммы>
<остаток суммы>::=ε|+<терм 1><остаток суммы>|-<терм 1><остаток суммы>| or<терм 1><остаток суммы>
<терм 1>::=<терм 2><остаток произведения>
<остаток произведения>::=ε|*<терм 2><остаток произведения>|/<терм 2><остаток произведения>|and<терм 2><остаток произведения>
<терм 2>::=<переменная>|<значение>|(< арифм. выражение>)|not<терм 2>|<вызов функции>
<значение>::=<целое число>|<вещественное число>
<вызов функции>::=ord(<переменная>)|count(<имя списка>, <целое без знака>)|quantity(<имя списка>)
Описание семантики входного языка.
Представление данных различных типов в оперативной памяти.
Тип |
Размер, байт |
Диапазон значений |
Integer |
2 |
-32768..32768 |
boolean |
1 |
false, true |
real |
48 бит |
2.9*10^-39..1.7*10^38 |
Перечислимый тип определяет упорядоченный набор значений, который задается перечислением идентификаторов, обозначающих эти значения. Порядок значений в таком наборе определен последовательностью, в которой перечисляются идентификаторы. Первый идентификатор в списке имеет порядковый номер 0. Применение функции ord() к значению такого типа дает результат – целое число, которое показывает, какое положение занимает это значение в отношение других значений перечислимого типа. В памяти значение перечислимого типа занимает 1 байт.
Переменная диапазонного типа может принимать значения базового (главного) типа в указанном дипазоне. Базовым типом может быть целый или вещественный тип. Константа, указываемая в качестве верхней границы диапазона, должна быть больше либо равна константе, указываемой в качестве нижней границы, в противном случае на этапе компиляции. Переменная диапазонного типа имеет все свойства переменных главного типа, но ее значение на этапе выполнения должно принадлежать указанному отрезку
Переменная типа запись содержит определенное число полей - переменных различных типов. Объем оперативной памяти определяется суммарным объемом памяти, занимаемой его полями. К каждому полю можно обратиться через его имя, используя оператор доступа к полю.
Связный список представляет собой цепочку записей (узлов), в которой каждая запись содержит значение какого-то типа, номер элемента в списке и ссылку на следующую запись в цепочке. Номера элементов начинаются с 1.Каждый список имеет голову (Head) – ссылку на первый элемент списка. Ссылка последнего элемента указывает на пустой элемент (nil). Если список пуст, тоHead = nil.
Значение поля данных каждого элемента списка представляет собой переменную базового или пользовательского типа. Это может быть целое или вещественное число, логическое значение, перечислимое значение, диапазонная переменная или запись. Изначально при объявлении список пустой. Элементы добавляются в него путем использования оператора add.
Приоритет операций, порядок выполнения операций с одинаковым приоритетом (в порядке убывания приоритета).
Приоритет |
Знак операции |
Название операции |
Порядок выполнения |
Тип операндов |
1 |
( ) |
Скобки |
Слева направо |
Любой |
2 |
not
|
Логическое «НЕ»
|
Справа налево |
Логический
|
ord |
Вычисление порядка переменной переч. типа
|
Перечислимый | ||
count |
Получение значения элемента списка |
Слева направо |
Первый операнд – список, второй – целое без знака | |
3 |
* |
Умножение |
Слева направо |
Целый или вещественный |
/ |
Деление |
Слева направо |
Целый или вещественный | |
and |
Логическое «И» |
Слева направо |
Логический | |
4 |
+ |
Сложение |
Слева направо |
Целый или вещественный |
- |
Вычитание |
Слева направо |
Целый или вещественный | |
or |
Логическое «ИЛИ» |
Слева направо |
Логический | |
5 |
= |
Равно |
Слева направо |
Целый или вещественный |
<> |
Не равно |
Слева направо |
Целый или вещественный | |
< |
Меньше |
Слева направо |
Целый или вещественный | |
<= |
Меньше или равно |
Слева направо |
Целый или вещественный | |
> |
Больше |
Слева направо |
Целый или вещественный | |
>= |
Больше или равно |
Слева направо |
Целый или вещественный |
Для определения старшинства операций есть три правила
Операнд, находящийся между двумя операциями с разными приоритетами, связывется с операцией, имеющей более высокий приоритет.
Операнд, находящийся между двумя операциями с одинаковыми приоритетами, связывается с операцией, находящейся слева от него.
Выражение, заключенное в скобки, перед выполнением вычисляется как отдельный операнд.
Бинарные операции выполняются только с операндами одинакового типа.
Правила выполнения операторов языка.
1) Оператор присваивания.
Порядок выполнения:
вычисляется значение выражения в правой части оператора;
если тип результата вычисления не тот же , что и тип переменной в левой части (имена типов не совпадают), выдается сообщение об ошибке
в противном случае переменной в левой части оператора присваивания присваивается значение правой части.
2) Оператор ввода.
Выполнение оператора read: работа программы приостанавливается, пользователь должен ввести с клавиатуры значение, которое будет присвоено переменной в круглых скобках. Когда значение переменной будет введено, программа продолжит работу
3) Оператор вывода.
Выполнение оператора write: операторwriteвычисляет значение первого выражения (должно быть целым, вещественным или булевским числом) в строке вывода и выводит его на экран. Затем то же самое производится со всеми последующими выражениями (если они указаны в качестве параметров).
4) Оператор преобразования типов.
Переменная, указанная в качестве аргумента меняет свой тип в соответствии со следующими правилами.
Имя нового типа переменной указывается пользователем подобно имени функции
Переменная типа realможет преобразоваться только в переменную типаinteger, а та – только в переменную типаreal. Переменная не должна являться полем записи или элементом списка - иначе – ошибка выполнения оператора
Прочие преобразования переменных не допускаются
5) Оператор безусловного перехода.
Выполнение оператора goto: передает управление оператору, помеченному меткой, следующей за ключевым словомgoto. Если метка, следующая за ключевым словомgoto, не была описана в разделе описаний или в программе нет оператора, помеченного данной меткой, то ошибка выполнения оператора безусловного перехода.
Оператор безусловного перехода может передавать управление в операторы, включенные в условия и циклы. Компилятор не выдает сообщение об ошибке, но такой переход может приводить к непредсказуемым эффектам, и поэтому его лучше избегать.
6) Условный оператор.
Порядок выполнения оператора if.
If(<условие>)then<оператор 1>
else<оператор2>
7) Оператор цикла с предусловием.
Порядок выполнения оператора while:
While (<условие>)do <оператор>
Порядок выполнения операций над списком
-оператор add(<имя списка>, <значение элемента>) добавляет в конец списка новый элемент с заданным значением. Если тип элемента не соответствует типу элементов списка – ошибка выполнения оператора
- функция quantity(<имя списка>) подсчитывает количество элементов в списке с указанным именем и возвращает это значение в программу.
- оператор concat(<имя списка1>,<имя списка 2) осуществляет конкатенацию списков 1 и 2, т. е присоединяет к первому списку 2-й в порядке их перечисления. В первый список в результате конкатенации входят элементы из обоих списков. Второй список не меняется.
- функция find(<имя списка>, <значение элемента>) ищет в списке первый элемент с заданным значением и возвращает номер этого элемента в программу. Если в списке нет такого элемента, то возвращается -1.
- функция count(<имя списка>, <номер>) ищет в списке элемент с заданным номером и возвращает значение в главную функцию. Если элементов в списке меньше, чем указанный номер или номер неположителен – ошибка
-операция remove(<имя списка>, <номер>) удаляет из списка элемент с заданным номером. Если кол-во элементов в списке меньше заданного номера, удаление не производится, но ошибка не выдается (фиктивное удаление). Если номер неположителен, то выдается ошибка выполнения оператора.
Правила реализации конструкций языка.
Все переменные, константы и имена типов (кроме базовых имен типов integer,boolean,real), используемые в программе, должны быть описаны в соответствующих разделах описания переменных, констант и типов и только один раз, в противном случае на этапе компиляции программы возникает ошибка. Имена переменных, констант, меток, типов, ключевых слов не должны совпадать. Константы при описании инициализируются обязательно, а переменные не инициализируются. Но использование неинициализированной переменной в любом месте, кроме левой части оператора присваивания приводит к ошибке на этапе выполнения. Программа на входном языке может содержать комментарии: заключенный в фигурные скобки текст из любых символов кроме символа закрывающей фигурной скобки. Комментарии могут находиться в любом месте программы, если они не разрывают лексемы.
Лексический анализатор
Определение типов лексем
Входной язык определяет следующие лексемы:
Идентификатор – последовательность букв, цифр и знаков подчеркивания, начинающийся с буквы или знака подчеркивания. Идентификатор обозначает имена типов, переменных и констант.
<идентификатор>::=<буква><последовательность> | _<последовательность> <последовательность>::=ε|<буква><последовательность>|_<последовательность>|<цифра><последовательность>
<буква>::=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|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
Целое без знака
<целое без знака>::=<цифра><последовательность цифр>
<последовательностьцифр>::=ε|<цифра><последовательность цифр>
Вещественное число
<число>::=[<знак числа>]<число без знака>
<число без знака>::=<целое без знака>.<целое без знака>
<целое без знака>::=<цифра><последовательность цифр>
<последовательностьцифр>::=ε|<цифра><последовательность цифр>
Булевская константа <булевское число>::=true|false
Ключевое слово
<ключевое слово>::=
program|label|type|var|const|record|list|of|integer|real |boolean|begin|end|read|write|if|then|else|goto|while|do|add|set|quantity|find|count|remove|ord
Знаки операций
<знак операции>::=not|and|or|+|-|*|\|=|<>|<|>|<=|>=|:=
Разделители – символы, предназначенные для отделения друг от друга частей программы, отдельных лексем, операндов, комментариев
<разделитель>::=.|.|:|;|(|)|{|}
Синтаксический анализатор
Построение грамматики по БНФ.
S -> ProgName ObjDes begin OperDesc end .
S -> ProgName ObjDes begin end .
S -> ProgName begin OperDesc end .
S -> ObjDes begin OperDesc end .
S -> ObjDes begin end .
S -> ProgName begin end .
S -> begin OperDesc end .
S -> begin end .
ProgName -> program Id
ObjDesc -> ObjDesc Obj ;
ObjDesc -> Obj ;
Obj -> LabDesc
Obj -> TypeDesc
Obj -> VarDesc
Obj -> ConstDesc
LabDesc -> label ManyL
ManyL -> Lab
ManyL -> ManyL , Lab
Lab -> Id
Lab -> Int
TypeDesc -> type ManyTypeDef
ManyTypeDef -> TypeDef
ManyTypeDef -> ManyTypeDef ; TypeDef
TypeDef -> Id = Type
TypeDef -> Id = Id
Type -> integer
Type -> real
Type -> boolean
Type -> Num .. Num
Type -> Int .. Int
Type -> (Names)
Names -> ManyNames
ManyNames -> Id
ManyNames -> ManyNames , Id
Type -> record FNames end
Type -> list of Id
Type -> list of integer
Type -> list of real
Type -> list of boolean
Fnames -> ManyFNames
ManyFnames -> Field
ManyFNames -> ManyFNames ; Field
Field -> Names : integer
Field -> Names : real
Field -> Names : boolean
Field -> Names : Id
ConstDesc -> const ManyConstDef
ManyConstDef -> ConstDef
ManyConstDef -> ManyConstDef ; ManyConstDef
ConstDef -> Id := EQ
ConstDef -> Id := Condition
VarDesc -> var ManyVarDef
ManyVarDef -> VarDef
ManyVarDef -> ManyVarDef ; VarDef
VarDef -> Names : Type
OperDesc -> ManyOper
ManyOper -> LOper
ManyOper -> ManyOper ; LOper
LOper -> L : Oper
LOper -> Oper
Oper -> begin ManyOper end
Oper -> O
O -> OEq
O -> OIO
O -> OManager
O -> OList
OEq -> V := EQ
OEq -> V := Condition
OEq -> V:= V
V -> F
F -> Id
F -> F . Id
OIO -> OIn
OIO -> OOut
OInput -> read ( V )
OOutput -> write ( ManyD )
ManyD -> D
ManyD -> ManyD , D
D -> EQ
D -> Condition
OManager -> OGo
OManager -> OIf
OManager -> OWh
OGoto -> goto L
OIf -> if Condition then Oper else Oper
OIf -> if Condition then Oper else CO
OIf -> if Condition then CO else Oper
OIf -> if Condition then CO else CO
OIf -> if Condition then Oper
OIf -> if Condition then CO
OWh -> while Condition do Oper
OWh -> while Condition do CO
CO -> begin ManyOper end
CO -> begin end
OList -> add ( Id , Int )
OList -> add (Id , Num)
OList -> add ( Id , B )
OList -> add ( Id , V)
OList -> add ( Id , EQ )
OList -> add ( Id , Condition )
OList -> concat ( Id, Id )
OList -> remove ( Id , Int )
Condition -> Z1 F1
Condition -> Z1
F1 -> or Z1 F1
F1 -> or Z1
Z1 -> Z2 F2
Z1 -> Z2
F2 -> and Z2 F2
F2 -> and Z2
Z2 -> Z3
Z3 -> not Z3
Z3 -> Z4
Z4 -> (Condition)
Z4 ->(Condition Sgn Condition)
Z4 -> (EQ Sgn EQ)
Z4 -> V
Z4 -> B
Sgn -> =
Sgn -> >
Sgn -> <
Sgn -> >=
Sgn -> <=
Sgn -> <>
EQ -> T1 E1
EQ -> T1
E1 -> + T1
E1 -> + T1 E1
E1 -> - T1
E1 -> - T1 E1
T1 -> T2 E2
T1 -> T2
E2 -> * T2
E2 -> * T2 E2
E2 -> \ T2
E2 -> \ T2 E2
T2 -> V
T2 -> Int
T2 -> Num
T2 -> CallFunc
T2 ->( EQ )
CallFunc -> ord ( V )
CallFunc -> count ( Id , Int )
CallFunc -> quantity ( Id )
CallFunc -> integer ( Num )
CallFunc->integer(Int )
CallFunc->real( Int)
CallFunc->real (Num)
CallFunc -> find (Id , Int)
CallFunc -> find (Id , Num)
CallFunc -> find (Id , B)
CallFunc -> find (Id , V)
Разбиение грамматики на подграмматики
По условиям задания полученная грамматика должна принадлежать к классу грамматик слабого предшествования, либо состоит из подграмматик слабого предшествования
Подграмматика раздела описания программы
Терминалы
Нетерминалы
Правила
begin
S
S ->ProgName ObjDesc begin OperDesc end .
End
ProgName
S -> ProgName ObjDesc begin end .
program
ObjDesc
S -> ProgName begin OperDesc end .
.
Obj
S -> ProgName begin end .
OperDesc
S -> ObjDesc begin OperDesc end .
LabDesc
S -> ObjDesc begin end .
TypeDesc
S -> begin OperDesc end .
ConsDesc
S -> begin end .
VarDesc
ProgName -> program Id
Id
ObjDesc -> ObjDesc Obj ;
ObjDesc -> Obj ;
Obj -> LabDesc
Obj -> ConsDesc
Obj -> TypeDesc
Obj -> VarDesc
Подграмматика раздела описания меток
Терминалы
Нетерминалы
Правила
label
LabDesc
LabDesc -> label ManyL
L
ManyL
ManyL -> L
,
ManyL -> ManyL , L
Подграмматика раздела описания констант
Терминалы |
Нетерминалы |
Правила |
const |
ConsDesc |
ConsDesc -> const ManyConsDef |
Id |
ManyConsDef |
ManyConsDef -> ConsDef |
EQ |
ConsDef |
ManyConsDef -> ManyConsDef ; ConsDef |
Con |
|
ConsDef -> Id := EQ |
:= |
|
ConsDef -> Id := Con |
; |
|
|
Подграмматика раздела описания типов
Терминалы |
Нетерминалы |
Правила |
type |
TypeDesc |
TypeDesc -> type ManyTypeDef |
= |
TypeDef |
ManyTypeDef -> ManyTypeDef ; TypeDef |
; |
ManyTypeDef |
ManyTypeDef -> TypeDef |
Id |
Type |
TypeDef -> Id = Type |
Int |
Names |
TypeDef -> Id = Id |
Num |
FNames |
Type -> integer |
record |
Field |
Type -> real |
end |
|
Type -> boolean |
list |
|
Type -> Int .. Int |
of |
|
Type -> Num .. Num |
( |
|
Type -> (Names) |
) |
|
Type -> record FNames end |
: |
|
Type -> list of Id |
, |
|
Type -> list of integer |
.. |
|
Type -> list of real |
integer |
|
Type -> list of boolean |
real |
|
Names -> Id |
boolean |
|
Names -> Names , Id |
|
|
FNames -> Field |
|
|
FNames -> FNames ; Field |
|
|
Field -> Names : Id |
|
|
Field -> Names : integer |
|
|
Field -> Names : real |
|
|
Field -> Names : boolean |
Подграмматика раздела описания переменных
Терминалы
Нетерминалы
Правила
Var
VarDesc
VarDesc -> var ManyVarDef
Id
VarDef
ManyVarDef -> VarDef
:
ManyVarDef
ManyVarDef -> ManyVarDef ; VarDef
,
VarNames
VarDef -> VarNames : Id
;
VarDef -> VarNames : integer
VarDef -> VarNames : real
VarDef -> VarNames : boolean
VarNames -> Id
VarNames -> VarNames , Id
Подграмматика раздела описания операторов
Терминалы
Нетерминалы
Правила
begin
OperDesc
OperDesc -> ManyOperDef
End
ManyOperDef
ManyOperDef -> ManyOperDef ; LabOper
:
LabOper
ManyOperDef -> LabOper
;
Oper
LabOper -> L : Oper
L
LabOper -> Oper
O
Oper -> begin ManyOperDef end
Oper -> O
Подграмматика меток
Терминалы
Нетерминалы
Правила
Id
L
L -> Id
Int
L -> Int
Подграмматика переменных
Терминалы
Нетерминалы
Правила
Id
V
V -> F
.
F
F -> Id
F -> F . Id
Подграмматика видов операторов
Терминалы
Нетерминалы
Правила
OIO
O
O -> OIO
OLs
O -> OEq
OEq
O -> OManager
OManager
O -> OLs
Подграмматика операторов ввода и вывода
Терминалы
Нетерминалы
Правила
write
OIO
OIO -> OIn
read
OIn
OIO -> OOu
(
OOu
OIn -> read ( V )
)
ManyData
OOu -> write ( ManyData )
,
Data
ManyData -> ManyData , Data
EQ
ManyData -> Data
Con
Data -> EQ
V
Data -> Con
Подграмматика оператора присваивания
Терминалы
Нетерминалы
Правила
V
OEq
OEq -> V := EQ
EQ
OEq -> V := Condition
Condition
OEq -> V := V
:=
Подграмматика операторов цикла, условного оператора и оператора безусловного перехода
Терминалы
Нетерминалы
Правила
O
OManager
OManager -> OGo
Condition
OGo
OManager -> OIf
L
OIf
OManager -> OWh
goto
OWh
OGo -> goto L
If
CO
OIf -> if Condition then O else O
then
MnO
OIf -> if Condition then O else CO
else
OIf -> if Condition then CO else CO
while
OIf -> if Condition then CO else O
Do
OIf -> if Condition then O
begin
OIf -> if Condition then CO
End
OWh -> while Condition do O
;
OWh -> while Condition do CO
CO -> begin MnO end
CO -> begin end
MnO -> O
MnO -> MnO ; O
Подграмматика операторов над списком
Терминалы
Нетерминалы
Правила
Add
OLs
OLs -> add ( Id , Int )
concat
OLs -> add ( Id , Num )
remove
OLs -> add ( Id , B )
)
OLs -> add ( Id , V )
(
OLs -> add ( Id , EQ )
,
OLs -> add ( Id , Condition )
Id
OLs -> concat ( Id , Id )
Num
OLs -> remove ( Id , Int )
Int
B
V
Condition
EQ
Подграмматика логических выражений и условий
Терминалы
Нетерминалы
Правила
<
Con
Con -> Z1 F1
>
Z1
Con -> Z1
=
Z2
Z1 -> Z2 F2
<=
Z3
Z1 -> Z2
>=
Z4
Z2 -> Z3
<>
F1
Z3 -> not Z3
(
F2
Z3 -> Z4
)
Sgn
Z4 -> V
Or
Z4 -> B
And
Z4 -> ( EQ Sgn EQ )
Not
Z4 -> ( Con )
V
F1 -> or Z1 F1
EQ
F1 -> or Z1
B
F2 -> and Z2 F2
F2 -> and Z2
Sgn -> <
Sgn -> >
Sgn -> =
Sgn -> <>
Sgn -> <=
Sgn -> >=
Подграмматика арифметических выражений
Терминалы
Нетерминалы
Правила
+
EQ
EQ -> T1 E1
-
E1
EQ -> T1
*
E2
E1 -> + T1 E1
\
T1
E1 -> + T1
(
T2
E1 -> - T1 E1
)
E1 -> - T1
V
E2 -> * T2 E2
Int
E2 -> * T2
Num
E2 -> \ T2 E2
CallFunction
E2 -> \ T2
T1 -> T2 E2
T1 -> T2
T2 -> V
T2 -> Int
T2 -> Num
T2 -> CallFunction
T2 -> ( EQ )
Подграмматика вызовов функций
Терминалы |
Нетерминалы |
Правила |
( |
CallFunction |
CallFunc -> ord ( V ) |
) |
|
CallFunc -> qua ( Id ) |
, |
|
CallFunc -> cou ( Id , Int ) |
Ord |
|
CallFunc -> integer ( V ) |
Qua |
|
CallFunc -> real ( V ) |
Cou |
|
CallFunc -> integer ( Num ) |
Int |
|
CallFunc -> integer ( Int ) |
Id |
|
CallFunc -> real ( Int ) |
V |
|
CallFunc -> real ( Num ) |
integer |
|
CallFunc -> find (Id , Int) |
real |
|
CallFunc -> find (Id , Num) |
Num |
|
CallFunc -> find (Id , B) |
B |
|
CallFunc -> find (Id , V) |
Все приведенные здесь грамматики являются грамматиками слабого предшествования, что подтверждено экспериментально.
Описание промежуточного языка – триад.
Код триады |
Операнд 1 |
Операнд 2 |
Семантика триады |
:= |
a |
b |
Триаде по адресу aприсваивается значение триады по адресуb Ошибка, если типы а и bне совпадают |
+I |
a |
b |
cумма целых значений по адресамaиb |
+R |
a |
b |
cумма вещественных значений по адресамaиb |
-I |
a |
b |
разность целых чисел по адресам aиb |
-R |
a |
b |
разность вещественных чисел по адресам aиb |
*I |
a |
b |
произведение целых значений по адресам aиb |
*R |
a |
b |
произведение вещественных значений по адресам aиb |
/I |
a |
b |
деление целых значений по адресам aиb аномальная ситуация b = 0 |
/R |
a |
b |
деление целых значений по адресам aиb аномальная ситуация b = 0.0 |
=I |
a |
b |
операция «равно» для целых значений по адресам aиb результат булевского типа |
=R |
a |
b |
операция «равно» для вещественных значений по адресам aиb результат булевского типа |
=B |
a |
b |
операция «равно» для булевских значений по адресам aиb результат булевского типа |
<>I |
a |
b |
операция «не равно» для целых значений по адресам aиb, результат булевского типа |
<>R |
a |
b |
операция «не равно» для вещественных значений по адресам aиb, результат булевского типа |
<>B |
a |
b |
операция «не равно» для булевских значений по адресам aиb, результат булевского типа |
>I |
a |
b |
операция «больше» для целых значений по адресам aиb, результат булевского типа |
>R |
a |
b |
операция «больше» для вещественных значений по адресам aиb, результат булевского типа |
>B |
a |
b |
операция «больше» для булевских значений по адресам aиb, результат булевского типа |
<I |
a |
b |
операция «меньше» для целых значений по адресам aиb, результат булевского типа |
<R |
a |
b |
операция «меньше» для вещественных значений по адресам aиb, результат булевского типа |
<B |
a |
b |
операция «меньше» для булевских значений по адресам aиb, результат булевского типа |
>=I |
a |
b |
операция «больше или равно» для целых значений по адресам aиb, результат булевского типа |
>=R |
a |
b |
операция «больше или равно» для вещественных значений по адресам aиb, результат булевского типа |
>=B |
a |
b |
операция «больше или равно» для булевских значений по адресам aиb, результат булевского типа |
<=I |
a |
b |
операция «меньше или равно» для целых значений по адресам aиb, результат булевского типа |
<=R |
a |
b |
операция «меньше или равно» для вещественных значений по адресам aиb, результат булевского типа |
<=B |
a |
b |
операция «меньше или равно» для булевских значений по адресам aиb, результат булевского типа |
AND |
a |
b |
операция логического умножения для булевских значений, результат булевского типа |
OR |
a |
b |
операция логического сложения для булевских значений, результат – булевского типа |
NOT |
a |
|
операция отрицания для булевского значения, результат – булевского типа
|
ITOR |
a |
|
преобразовать целое а в вещественное |
RTOI |
a |
|
привести вещественное а к целому (округлить) |
RF |
a |
b |
поле b записиa |
FND |
ls |
a |
в списке lsищется переменная по адресуa |
RD |
a |
|
записать в таблицу идентификаторов по адресу aзначение, вводимое с клавиатуры. |
WR |
a |
|
вывести на экран значение из таблицы идентификаторов по адресу а |
DEFL |
a |
|
в таблицу меток по адресу aзаносится сгенерированная метка, хранящая адрес следующей за ней триады |
BRL |
l |
|
управление передается метке по адресу l |
BF |
l |
f |
управление передается метке по адресу l, если значение по адресуfравноfalse, аномальная ситуация – значение по адресуf– не булевское |
Неформальное описание перевода
Входная цепочка |
Представление цепочки в выходном языке | |||
№ триады |
Код операции |
Операнд 1 |
Операнд 2 | |
a := b |
1 |
:= |
a |
b |
read(X) |
1 |
RD |
X |
|
write(X, <выражение>)
|
1 |
WR |
X |
|
2 |
<перевод выражения> | |||
3 |
WR |
(2) |
| |
goto L |
1 |
BRL |
L |
|
int(X) |
1 |
CT |
X |
int |
real(X) |
1 |
CT |
X |
real |
add(ls, X) |
1 |
ADD |
Ls |
X |
concat(ls1, ls2) |
1 |
CCT |
ls1 |
ls2 |
find(X, Y) |
1 |
FND |
X |
Y |
remove(ls, X) |
1 |
RMV |
Ls |
X |
if<выражение> then<оператор 1> else<оператор 2> |
1 |
<перевод выражения> | ||
2 |
BF |
L1 |
(1) | |
3 |
<перевод оператора 1> | |||
4 |
BRL |
L2 |
| |
5 |
DEFL |
L1 |
| |
6 |
<перевод оператора 2> | |||
7 |
DEFL |
L2 |
| |
if<выражение> then <оператор> |
1 |
<перевод выражения> | ||
2
|
BF |
L |
(1) | |
3 |
<перевод оператора> | |||
4 |
DEFL |
L |
| |
while <выражение>do <оператор> |
1 |
DEFL |
LBEGIN |
|
2 |
<перевод выражения> | |||
3 |
BF |
LEND |
(2) | |
4 |
<перевод оператора> | |||
5 |
BRL |
LBEGIN |
| |
6 |
DEFL |
LEND |
| |
A.B |
1 |
RF |
A |
B |
Описание атрибутно-транслирующих грамматик
1.Грамматика раздела описания программы
Входные символы:
Имя символа |
Семантика |
Атрибуты |
ProgName |
Имя программы |
|
ObjDesc |
Последовательность разделов описаний (констант, меток, типов, переменных) |
|
OperDesc |
Раздел описания операторов |
|
Obj |
Раздел описаний |
|
LabDesc |
Раздел описания меток |
|
VarDesc |
Раздел описания переменных |
|
TypeDesc |
Раздел описания типов |
|
ConsDesc |
Раздел описания констант |
|
Idname |
Идентификатор. Атрибут соответствует входному символу |
name -синтезированный |
Операционные символы
Имя символа |
Семантика |
Атрибуты |
{ВЫЗОВ OperDesc},{ВЫЗОВ ConsDesc}… |
Вызов соответствующего ДМП-процессора |
|
{ЗАПИСАТЬ ИДЕНТИФИКАТОР} id, adr |
Вписывает в таблицу идентификаторов новый идентификатор с именем idпо адресуadr. Графы «значение» и «тип» не заполняются. Если идентификатор с именемidуже присутствует в таблице идентификаторов, то синтаксическая ошибка |
id – унаследованный,adr- синтезированный |
{ЗАРЕЗЕРВИРОВАТЬ}id |
Идентификатор по имени idв таблице идентификаторов резервируется как имя программы, т.е теперь он не может принимать значение |
id -унаследованный |
Правила:
S -> ProgName ObjDesc begin OperDesc {ВЫЗОВ OperDesc} end .
S -> ProgName ObjDesc begin end .
S -> ProgName begin OperDesc {ВЫЗОВ OperDesc} end .
S -> ProgName begin end .
S -> ObjDesc begin OperDesc {ВЫЗОВ OperDesc} end .
S -> ObjDesc begin end .
S -> begin OperDesc {ВЫЗОВ OperDesc} end .
S -> begin end .
ProgName -> program Idname {ЗАПИСАТЬ ИДЕНТИФИКАТОР} id, adr {ЗАРЕЗЕРВИРОВАТЬ}id1
id , id1<- name
adr <- НовыйИдентификатор
ObjDesc -> ObjDesc Obj ;
ObjDesc -> Obj ;
Obj -> LabDesc {ВЫЗОВ LabDesc}
Obj -> ConsDesc {ВЫЗОВ ConsDesc}
Obj -> TypDesc {ВЫЗОВ TypDesc}
Obj -> VarDesc {ВЫЗОВ VarDesc}
2. Грамматика раздела описания меток
Входные символы
Имя символа |
Семантика |
Атрибуты |
LabDesc |
Раздел описания меток |
|
ManyL |
Последовательность определений меток |
|
Lab |
Определение метки |
|
Idname |
Идентификатор. Атрибут соответствует входному символу |
name -синтезированный |
Intname |
Целое без знака. Атрибут соответствует входному символу |
name -синтезированный |
Операционные символы
Имя символа |
Семантика |
Атрибуты |
{ЗАПИСАТЬ ИДЕНТИФИКАТОР} id, adr |
Вписывает в таблицу идентификаторов новый идентификатор с именем idпо адресуadr. Графы «значение» и «тип» не заполняются. Если идентификатор с именемidуже присутствует в таблице идентификаторов, то синтаксическая ошибка |
id – унаследованный,adr- синтезированный |
{ЗАПИСАТЬ МЕТКУ}id1, adr |
Вписывает в таблицу меток новую метку с именем idпо адресуadr. Значение «содержание метки» не записывается |
id– унаследованный,adr- синтезированный |
{ЗАРЕЗЕРВИРОВАТЬ}id |
Идентификатор по имени idв таблице идентификаторов резервируется как имя метки, т.е теперь он не может принимать значение |
id -унаследованный |
Правила:
LabDesc -> label ManyL
ML -> Lab
ML -> ML , Lab
Lab -> Idname {ЗАПИСАТЬ ИДЕНТИФИКАТОР} id, adr {ЗАПИСАТЬ МЕТКУ}id1, adr1{ПОМЕТИТЬ}adr2
id, id1<-name
adr <- НовыйИдентификатор
adr1<-НоваяМетка
adr2 <- adr
Lab -> Intname {ЗАПИСАТЬ МЕТКУ}id1, adr1
id1<- name
adr1<-НоваяМетка