- •1. Постановка задачи
- •Исходные данные:
- •Описание синтаксиса входного языка:
- •Описание семантики входного языка:
- •Объявления и области действия
- •Операции.
- •Лексический анализ
- •Определение синтаксиса лексем
- •49 Таблица констант
- •Тестирование лексического анализатора
- •Описание кс-грамматики входного языка
- •Разбиение на подграмматики
- •Описание языка триад
- •Построение атрибутной транслирующей грамматики
- •Построение атрибутного дмп – процессора
- •Организация взаимодействия дмп-процессоров
Описание языка триад
1 |
BFL |
label |
|
Безусловный переход на метку label |
2 |
BF |
Label |
R |
Переход на метку Label, если R=false |
3 |
DEFL |
Label |
|
Определение метки Label |
4 |
MORE |
X |
Y |
сравнение X > Y |
5 |
ADD |
R |
(5) | |
6 |
LESS |
X |
Y |
сравнение X < Y |
7 |
ADD |
R |
(7) | |
8 |
+ |
X |
Y |
операция сложения X и Y |
9 |
- |
X |
Y |
операция вычитания X и Y |
10 |
* |
X |
Y |
операция умножения X и Y |
11 |
/ |
X |
Y |
операция деления X и Y |
12 |
move |
X |
Y |
операция присваивания X к Y |
13 |
++ |
X |
|
инкремент X |
14 |
-- |
X |
|
декремент X |
15 |
&& |
X |
Y |
операция логического "И" X и Y |
16 |
ADD |
R |
(15) | |
17 |
|| |
X |
Y |
операция логического "ИЛИ" X и Y |
18 |
ADD |
R |
(17) | |
19 |
! |
X |
|
операция логического отрицания X |
20 |
== |
X |
Y |
операция логического равенства X и Y |
21 |
ADD |
R |
(20) | |
22 |
concat |
S1 |
S2 |
операция конкатенации строк S1 и S2 |
23 |
find |
S0 |
S1 |
операция поиска подстроки S1 в строке S0 |
24 |
replace |
S0 |
S1 |
операция замены подстроки S1 в строке S0 на строку S2 |
25 |
add |
(24) |
S2 | |
26 |
length |
S |
|
вычисление длины строки S |
27 |
ADD |
R |
(26) | |
28 |
substring |
S0 |
A |
доступ к подстроке в строке S0, с символа номер A по B |
29 |
ADD |
(28) |
B | |
30 |
LE |
X |
Y |
сравнение X <= Y |
31 |
ADD |
(30) |
| |
32 |
GE |
X |
Y |
сравнение X >= Y |
33 |
ADD |
(32) |
| |
|
|
|
|
|
Построение атрибутной транслирующей грамматики
В тех операционных символах, где присутствует атрибут «r» - он определяет ссылку на соответствующую триаду (номер триады).
При несовпадении типов операндов – производится проверка на приводимось типов. Например, вызывается триада I2D. Если типы неприводимы, то ОШИБКА.
В таблице идентификаторов хранятся метки, создаваемые транслятором для организации ветвлений и циклов. Для генерации таких специальных меток служит функция NewLаbel. При вызовеNewLabelтранслятор генерирует новое уникальное имя метки, заносит его в незанятую строку таблицы и возвращает номер этой строки.
Используемые операционные символы:
Код операции |
Атрибуты |
Семантика | |||||||||||||
{MOV} |
p1 – 1-й операнд p2 – 2-й операнд |
Вызов триады = ab | |||||||||||||
{UOP} |
a- операнд b– код операции |
по bопределяет какую триаду вызвать: если bсоответствует «++», то ++ если bсоответствует «--», то -- | |||||||||||||
{MAOP} |
a- 1-й операнд b- 2-й операнд par – код операции r |
parопределяет какую триаду вызвать: если parсоответствует «*», то * если parсоответствует «/», то / | |||||||||||||
{AAOP} |
a- 1-й операнд b- 2-й операнд par – код операции r |
по parопределяет какую триаду вызвать: если parсоответствует «+», то + если parсоответствует «-», то - | |||||||||||||
{OR} |
a |
b |
a || b | ||||||||||||
{AND} |
a |
b |
a && b | ||||||||||||
{NOT} |
a |
|
!a | ||||||||||||
{REL} |
p1 – 1-й операнд p2 – 2-й операнд c– ссылка на тип отношения (номер строки в таблице отношений) |
По атрибуту «с»
определяется какую триаду вызвать.
Таблица соответствия:
LESS a<b LE a<
=b MORE a>b GE a>
=b == a=
=b ! a!
=b | |||||||||||||
{L} |
a |
b |
Вызов триады LESS (a < b) | ||||||||||||
{LE} |
a |
b |
Вызов триады LE(a< =b) | ||||||||||||
{G} |
a |
b |
Вызов триады MORE (a > b) | ||||||||||||
{GE} |
a |
b |
Вызов триады GE(a> =b) | ||||||||||||
{EQL} |
a |
b |
Вызов триады (a= =b) | ||||||||||||
{NEQL} |
a |
b |
Вызов триады (a! =b) | ||||||||||||
{TP} |
t– ссылка на соответствующий тип в таблице типов a- операнд |
<тип>t<идентификатор>a В таблицу идентификаторов добавляется новая строка и ячейки этой строки заполняются в соответствии с атрибутами | |||||||||||||
{LEN} |
a– операнд - строка r |
Вызов триады LEN (length(a)) | |||||||||||||
{CONC} |
a– операнд1 b– операнд2 r |
Вызов триады CONC (concat(a,b)) | |||||||||||||
{FND} |
s1 |
s2 |
Вызов триады FND (find(s1,s2)) | ||||||||||||
{RPLSTR} |
s1 |
s2 |
Вызов триады RPLSTR (replace(s1,s2,s3)) | ||||||||||||
|
s3 |
| |||||||||||||
{SBSTR} |
a– исходная строка b– номер начального элемента результирующей строки с – номер конечного элемента результирующей строки r |
Если с!=0, то вызывается триада SBSTR3 (substring(a,b,c)), иначеSBSTR2 (substring(a,b)) | |||||||||||||
| |||||||||||||||
{NEW} |
t |
|
new t() |
ГРАММАТИКА ГЛАВНЫЙ_КЛАСС
MCls– базовый нетерминальный символ
MCls → DecPak {ConCls} DecCls {Met } MMet {DecVar}
MCls → DecPak {ConCls} DecCls {Met} MMet {Met}
MCls → DecPak {ConCls} DecCls {DecVar} MMet {DecVar}
MCls → DecPak {ConCls} DecCls {DecVar} MMet {Met}
ГРАММАТИКА КЛАСС
Cls → DecPak {ConCls } DecCls { Met }
Cls → DecPak {Concls} DecCls {DecVar}
ГРАММАТИКА ПРОГРАММА
Prog→ MCls {Cls}
ГРАММАТИКА ОБЪЯВЛЕНИЕ КЛАССА
DecCls → class ID v {AddID} v1
v1 ← v
ГРАММАТИКА ПУТЬ
Adr → СAdr v {AddID} v1 . СAdr
v1 ← v
СAdr → VCHAR{VCHAR}v {AddID} v1
v1 ← v
СAdr → VCHAR{NUM} v {AddID} v1
v1 ← v
ГРАММАТИКА ПОДКЛЮЧЕНИЕ КЛАССА
ConCls → import Adr . ID v {AddID} v1
v1 ← v
ГРАММАТИКА ОБЪЯВЛЕНИЕ ПАКЕТА
DecPak → package Adr v {AddID} v1
v1 ← v
ГРАММАТИКА СПИСОК ПАРАМЕТРОВ
listValues→TypetIDp{TP} a,blistValues
a ← t
b ← p
listValues → exp
ГРАММАТИКА “NEW”
N → new Type t (listValues args) {NEW} p1,p2,r
p1 ← t
p2 ← args
a ← r
ГРАММАТИКА ПРОСТАЯ ПЕРЕМЕННАЯ
SVar → ID v {AddID} v1
v1 ← v
ГРАММАТИКА КОНСТАНТА БЕЗ ЗНАКА
FCon r → num {num} v
r ← v
FCon r → VCHAR{char}v
r ← v
FCon r → Str {str} v
r ← v
ГРАММАТИКА КОНСТАНТА
Con → num v {num} v1
v1 ← v
Con → DOUBLE v {doub} v1
v1 ← v
Con → Str Str v {str} v1
v1 ← v
Con → VCHAR v {char} v1
v1 ← v
ГРАММАТИКА ОПЕРАЦИЯ СКОБКИ
BrOp br1→ (Val r)
ГРАММАТИКА ОПЕРАЦИЯ ПРИСВАИВАНИЯ
EqOp r → SVar = Val v {UpdID} v1
r, v1 ← v
EqOp r → N v {UpdID} v1
r, v1 ← v
ГРАММАТИКА ОБЪЯВЛЕНИЕ ПЕРЕМЕННОЙ
DecVar → Type p {TP} SVar v {UpdID} a,b
a ← v
b← p
DecVar → Type p {TP} EqOp a
a ← v
ГРАММАТИКА ЗНАЧЕНИЕ
Val id→ Con v
id <- v
Val id → Op v
id <- v
Val id → StrOp v
id <- v
ГРАММАТИКА ЛЕВАЯ ЧАСТЬ УНАРНОЙ ОПЕРАЦИИ
LUOp id → SVar v
id <- v
LUOp id → FCon v
id <- v
LUOp id → StrOp v
id <- v
LUOp id → UOp v
id <- v
LUOp id → BrOp v
id <- v
ГРАММАТИКА УНАРНАЯ ОПЕРАЦИЯ
UOp v→ LUOp id ++ a {UOP}p1,p2
p1 <- id
p2 <- a
v <-p1
UOp v → LUOp id -- a {UOP}p1,p2
p1 <- id
p2 <- a
v <-p1
ГРАММАТИКА ЛЕВАЯ ЧАСТЬ МУЛЬТИПЛЕКАТИВНОЙ ОПЕРАЦИИ
LMOp id → LUOp v
id <- v
LMOp id → Mop v
id <- v
ГРАММАТИКА МУЛЬТИПЛЕКАТИВНАЯ ОПЕРАЦИЯ
MOp v → LMOp id * a LUOp par {MAOP}p1,p2,p3,p4
p1 <- id
p2 <- a
p3 <- par
v <- p4
MOp v → LMOp id / a LUOp par {MAOP}p1,p2,p3,p4
p1 <- id
p2 <- a
p3 <- par
v <- p4
ГРАММАТИКА ЛЕВАЯ ЧАСТЬ АДДИТИВНОЙ ОПЕРАЦИИ
LAdOp id → LMOp v
id <- v
LAdOp id → AdOp v
id <- v
ГРАММАТИКА АДДИТИВНАЯ ОПЕРАЦИЯ
AdOp v→ LAdOp id + a LMOp par {MAOP}p1,p2,p3,p4
p1 <- id
p2 <- a
p3 <- par
v <- p4
AdOp v→ LAdOp id – a LMOp par {MAOP}p1,p2,p3,p4
p1 <- id
p2 <- a
p3 <- par
v <- p4
ГРАММАТИКА УСЛОВНОЕ ПРИСВАИВАНИЕ
IEqOp p → LogExp lv ? Val {BF} m,v : Val
m ← NewLabel
p ← m
v ← lv
ГРАММАТИКА ОПЕРАЦИЯ ДЛИНА СТРОКИ
StrL v → StrVal p2 length() {LEN}p4,r
p4 <- p2
v <- r
ГРАММАТИКА ОПЕРАЦИЯ КОНКАТЕНАЦИЯ СТРОК
ConStr v → str p2_concat(str) p3 SRRP {CONC}b,c,r
b <- p2
с <- p3
v <- r
ГРАММАТИКА ОПЕРАЦИЯ ДОСТУП К СТРОКЕ
AcToStr v → str p2 substring(num p3,num p4) {SBSTR}b,c,d,r
b <- p2
с <- p3
d <- p4
v <- r
AcToStr v → str p2 substring(num p3) {SBSTR} b,c,d,r
a <- p2
b <- p3
с <- 0
v <- r
ГРАММАТИКА ОПЕРАЦИЯ ЗАМЕНА ПОДСТРОКИ В СТРОКЕ
ChStr v → str p2 replace(str p3, str p4) {RPLSTR}a,b,c,r
a <- p2
b <- p3
с <- p4
v <- r
ГРАММАТИКА ОПЕРАЦИЯ ПОИСК ПОДСТРОКИ В СТРОКЕ
FnStr v → str p2 find(str p3) {FND}a,b,r
a <- p2
b <- p3
v <- r
ГРАММАТИКА СТРОКОВАЯ ОПЕРАЦИЯ
StrOp id → StrL v
id <- v
StrOp id → ConStr v
id <- v
StrOp id → AcToStr v
id <- v
StrOp id → ChStr v
id <- v
StrOp id → FnStr v
id <- v
ГРАММАТИКА ОПЕРАЦИЯ
Op id → BrOp v
id <- v
Op id → UOp v
id <- v
Op id → MOp v
id <- v
Op id → AdOp v
id <- v
Op id → IEqOp v
id <- v
ГРАММАТИКА БЛОК_КОДА
Blc → { Blc Bel }
Blc → { Bel }
Bel → UOp
Bel → DecVar
Bel → EqOp
Bel → StrOp
Bel → Cyc
Bel → CMet
ГРАММАТИКА ВЫЗОВ МЕТОДА
CMet args1→ ID v (ListVal args)
args1 ← args + v
ListVal args1 → val v ListVal args
args1 ← args + v
ListVal args1 → val v
args1 ← v
ГРАММАТИКА МЕТОД
Met → Type t ID p {TP} a,b (listValues v) Blc {MOV} p1,,p2
a ← t //1-е слагаемое
b ← p //2-е слагаемое
p1 ← p//номер в таблице идентификаторов
p2 ← v//зачение идентификатора
ГРАММАТИКА МЕТОД MAIN
MMet → void main(listValues v) Blc {MOV} p1,,p2
p1 ← 0
p2 ← v
ГРАММАТИКА ОТНОШЕНИЕ
Att r→ LAtt v > c NVal v1 {REL}p1,p2,p3,res
p1 <- с
p2 <- v
p3 <- v1
r <- res
Att r→ LAtt v < c NVal v1 {REL}p1,p2,p3,res
p1 <- с
p2 <- v
p3 <- v1
r <- res
Att r→ LAtt v >= c NVal v1 {REL}p1,p2,p3,res
p1 <- с
p2 <- v
p3 <- v1
r <- res
Att r→ LAtt v <= c NVal v1 {REL}p1,p2,p3,res
p1 <- с
p2 <- v
p3 <- v1
r <- res
LAtt r→ NVal v
r <- v
LAtt r → Att v
r <- v
NVal r → MNUM v
r <- v
NVal r → DOUBLE v
r <- v
ГРАММАТИКА ЭКВИВАЛЕНТНОСТЬ
Ecv r→ LLogExp v == c LAtt vl {EQL}p1,p2,res
p1 <- v
p2 <- vl
r <- res
Ecv r→ LLogExp v != c LAtt vl {EQL}p1,p2,res
p1 <- v
p2 <- vl
r <- res
ГРАММАТИКА ЛЕВАЯ ЧАСТЬ ЛОГИЧЕСКОГО ВЫРАЖЕНИЯ
LLogExp r → LogExp v
r <- v
LLogExp r → Val v
r <- v
ГРАММАТИКА ЛОГИЧЕСКОЕ ВЫРАЖЕНИЕ
LogExp r→ LogExp v1 || v2 LLogExp {OR} a,b,res
a<- v1
b<- v2
r<- res
LogExp r→ LogExp v1 && LLogExp v2 {AND} a,b,res
a<- v1
b<- v2
r<- res
LogExp r→ LLogExp v
r <- v
LogExp r→ ! LLogExp v {NOT} a,res
a<- v
r<- res
LogExp r→ Ecv v
r <- v
LogExp r→ Att v
r <- v
ГРАММАТИКА ЦИКЛ С ПРЕДУСЛОВИЕМ
Cyc p → while(LogExp lv) {BF} m,v EqOp
m ← NewLabel
p ← m
v ← lv
Cyc p → while(LogExp lv) {BF} m,v Blc
m ← NewLabel
p ← m
v ← lv
Cyc p → while(LogExp lv) {BF} m,v
m ← NewLabel
p ← m
v ← lv
ГРАММАТИКА УСЛОВНЫЙ ОПЕРАТОР
Opifp →if(LogExplv){BF} m,v Blc
m ← NewLabel
p ← m
v ← lv
Opif p → if (LogExp lv) {BF} m,v Blc else Blc
m ← NewLabel
p ← m
v ← lv