3. 5. Тестирование лексического анализатора.
|
Тестовая программа |
Выходной поток токенов |
|
program Prog; const c0 = #2,1.5#; var i:integer; v:vector[10]; c:complex; begin i:=1; while i<=10 do begin im(v[i]):=i;
re(v[i]):=1.1*i;
i:=i+1; end; c:=v[5]*c0;
write(c); end. |
program 1 1 id 2 1 ; 5 1 const 1 2 id 2 2 = 5 2 # 5 3 nat 3 1 , 5 4 num 4 1 # 5 3 ; 5 1 var 1 3 id 2 3 : 5 5 integer 1 4 ; 5 1 id 2 4 : 5 5 vector 1 5 [ 5 6 nat 3 2 ] 5 7 ; 5 1 id 2 5 : 5 5 complex 1 6 ; 5 1 begin 1 7 id 2 3 := 5 8 nat 3 3 ; 5 1 while 1 8 id 2 3 rel 5 9 nat 3 2 do 1 9 begin 1 7 im 1 10 ( 5 10 id 2 4 [ 5 6 id 2 3 ] 5 7 ) 5 11 := 5 8 id 2 3 ; 5 1 re 1 11 ( 5 10 id 2 4 [ 5 6 id 2 3 ] 5 7 ) 5 11 := 5 8 num 4 2 * 5 12 id 2 3 ; 5 1 id 2 3 := 5 8 id 2 3 + 5 13 nat 3 3 ; 5 1 end 1 12 ; 5 1 id 2 5 := 5 8 id 2 4 [ 5 6 nat 3 4 ] 5 7 * 5 12 id 2 2 ; 5 1 write 1 13 ( 5 10 id 2 5 ) 5 11 ; 5 1 end 1 12 . 5 14 |
Статические таблицы лексем:
|
1. Таблица ключевых слов |
|
5. Таблица разделителей | ||
|
1 |
program |
|
1 |
; |
|
2 |
const |
|
2 |
= |
|
3 |
var |
|
3 |
# |
|
4 |
integer |
|
4 |
, |
|
5 |
vector |
|
5 |
: |
|
6 |
complex |
|
6 |
[ |
|
7 |
begin |
|
7 |
] |
|
8 |
while |
|
8 |
:= |
|
9 |
do |
|
9 |
<= |
|
10 |
im |
|
10 |
( |
|
11 |
re |
|
11 |
) |
|
12 |
end |
|
12 |
* |
|
13 |
write |
|
13 |
+ |
|
14 |
... |
|
14 |
. |
|
.. |
... |
|
.. |
... |
Сформированные таблицы лексем:
3.
Таблица натуральных констант 1 2 2 10 3 1 4 5
4.
Таблица вещественных
констант 1 1.5 2 1.1
4. Описание этапа синтаксического анализа
4.1. Разбиение кс–грамматики входного языка на подграмматики
1. Головная грамматика программы GR1 (Начальный символ S)
Тип: простого предшествования.
Терминалы :
pro = program ; id = идент ; ; = ; ;
def = *БлокОпис ; opl = *Оператор ; beg = begin ;
end = end ; . = . ;
Нетерминалы :
S = *НачСимвол 2 ; BOp = БлокОпер 1 ;
Ops = ОператорЫ 1 ; Op1 = _-//- 2 ;
Правила :
1) S -> pro id ; def BOp
2) S -> pro id ; BOp
3) BOp -> beg Ops end .
4) Ops -> Op1
5) Op1 -> opl
6) Op1 -> opl ; Op1
2. Грамматика раздела описаний GR2 (Начальный символ Def)
Тип: простого предшествования.
Терминалы :
con = const ; lab = label ; var = var ;
typ = type ; Typ = *Типы ; ; = ; ;
, = , ; : = : ; = = = ;
nat = ЦелоеБезЗн ; id = Идент ; cid = *КонстИден ;
# = ;
Нетерминалы :
Def = *БлокОпис 2 ; Df = _-//- 3 ;
DfL = ОписМеток 1 ; Bl1 = Блок1 3 ;
DfC = ОписКонстант 1 ; Bl2 = Блок2 3 ;
DfT = ОписТипов 1 ; Bl3 = Блок3 1 ;
DfV = ОписПеременных 1 ; LLb = СписокМеток 1 ;
LL1 = _-//- 2 ; LCn = СписокКонстант 2 ;
Cns = Константа 2 ; LTp = СписокТипов 2 ;
Vrs = Переменные 2 ; LVr = СписокПеремен 1 ;
LV1 = _-//- 2 ;
Правила :
1) Def -> Df
2) Def ->
3) Df -> Bl1
4) Df -> DfL Bl1
5) Df -> DfL
6) DfL -> lab LLb
7) Bl1 -> Bl2
8) Bl1 -> DfC Bl2
9) Bl1 -> DfC
10) DfC -> con LCn
11) Bl2 -> Bl3
12) Bl2 -> DfT Bl3
13) Bl2 -> DfT
14) DfT -> typ LTp
15) Bl3 -> DfV
16) DfV -> var Vrs
17) LLb -> LL1
18) LL1 -> nat ;
19) LL1 -> nat , LL1
20) LCn -> id = Cns ;
21) LCn -> id = Cns ; LCn
22) Cns -> cid
23) Cns -> # cid , cid #
24) LTp -> id = Typ ;
25) LTp -> id = Typ ; LTp
26) Vrs -> LVr : Typ ;
27) Vrs -> LVr : Typ ; Vrs
28) LVr -> LV1
29) LV1 -> id
30) LV1 -> id , LV1
3. Грамматика типов GR3 (Начальный символ Typ)
Тип: простого предшествования.
Терминалы :
, = , ; id = Идент ; nat = nat ;
cid = *КонстИден ; int = integer ; rea = real ;
com = complex ; .. = .. ; ( = ( ;
) = ) ; vec = vector ; [ = [ ;
] = ] ;
Нетерминалы :
Typ = *Типы 8 ; Id) = 2 ;
Правила :
1) Typ -> cid .. cid
2) Typ -> id
3) Typ -> int
4) Typ -> rea
5) Typ -> com
6) Typ -> ( id Id)
7) Typ -> vec [ id ]
8) Typ -> vec [ nat ]
9) Id) -> )
10) Id) -> , id Id)
4. Грамматика типов GR4 (Начальный символ Oper)
Тип: LL(1).
Терминалы :
beg = begin ; end = end ; ; = ; ;
, = ; nat = ЦелоеБузЗн ; : = : ;
rd = readln ; wr = writeln ; ( = ( ;
) = ) ; pex = *ПростВыр ; id = Идент ;
:= = := ; vec = *Вектор ; whl = while ;
ex = *Выраж ; do = do ; got = goto ;
oIf = *УсловОпер ; cpx = *Компл ; [ = [ ;
] = ] ; im = im ; re = re ;
Нетерминалы :
OpL = *Оператор 2 ; Op = НепомечОператор 8 ;
BOp = СостОператор 1 ; Ops = ПослОператоров 1 ;
Op1 = _-//- 2 ; Op= = ОпПрисваивания 2 ;
O=1 = 2 ; O=2 = 2 ;
ORd = ОпВвода 1 ; LRd = ПослВвода 1 ;
Rd1 = ХвостВвода 2 ; 1rd = 1цаВывода 2 ;
OWr = ОпВывода 1 ; LWr = ПослВывода 1 ;
Wr1 = ХвостВывода 2 ; OWh = ОпЦикла 1 ;
OGo = ОпБезуслПерех 1 ; ImR = im,re 2 ;
Правила :
1) OpL -> nat : Op
2) OpL -> Op
3) Op ->
4) Op -> BOp
5) Op -> Op=
6) Op -> ORd
7) Op -> OWr
8) Op -> OWh
9) Op -> OGo
10) Op -> oIf
11) BOp -> beg Ops end
12) Ops -> OpL Op1
13) Op1 -> ; Ops
14) Op1 ->
15) Op= -> ImR ( cpx ) := pex
16) Op= -> id O=1
17) O=1 -> [ pex ] := pex
18) O=1 -> := O=2
19) O=2 -> pex
20) O=2 -> vec
21) ORd -> rd ( LRd )
22) LRd -> 1rd Rd1
23) Rd1 -> , LRd
24) Rd1 ->
25) 1rd -> id
26) 1rd -> ImR ( cpx )
27) OWr -> wr ( LWr )
28) LWr -> pex Wr1
29) Wr1 -> , LWr
30) Wr1 ->
31) OWh -> whl ex do OpL
32) OGo -> got nat
33) ImR -> im
34) ImR -> re
5. Грамматика условного оператора GR5 (Начальный символ OIf)
Тип: LL(1).
Терминалы :
if = if ; thn = then ; els = else ;
opl = *Оператор ; ex = *Выраж ;
Нетерминалы :
OIf = *УслОператор 1 ; Els = Ветвь-else 2 ;
Правила :
1) OIf -> if ex thn opl Els
2) Els -> els opl
3) Els ->
6. Грамматика простых выражений GR6 (Начальный символ PEx)
Тип: LL(1).
Терминалы :
+ = +,- ; or = or ; * = *,/ ;
and = and ; not = not ; ( = ( ;
) = ) ; , = ; cid = *КонстИден ;
cpx = *Компл ; vec = *Вектор ; ex = *Выраж ;
id = Идентиф ; int = integer ; rea = real ;
com = complex ; abs = abs ; re = re ;
im = im ; len = length ; mls = multscal ;
Нетерминалы :
PEx = *ПростВыражение 1 ; PE1 = 2 ;
S+ = 2 ; Trm = Терм 1 ;
Tr1 = 2 ; S* = 2 ;
UnS = 2 ; Mul = Множитель 8 ;
OpC = ОперНадКомпл 3 ; T() = 1 ;
Typ = ПростТип 4 ;
Правила :
1) PEx -> Trm PE1
2) PE1 -> S+ Trm PE1
3) PE1 ->
4) S+ -> +
5) S+ -> or
6) Trm -> Mul Tr1
7) Tr1 -> S* Mul Tr1
8) Tr1 ->
9) S* -> *
10) S* -> and
11) UnS -> +
12) UnS -> not
13) Mul -> UnS Mul
14) Mul -> cid
15) Mul -> cpx
16) Mul -> OpC ( cpx )
17) Mul -> len ( vec )
18) Mul -> mls ( vec , vec )
19) Mul -> T()
20) Mul -> ( ex )
21) OpC -> abs
22) OpC -> re
23) OpC -> im
24) T() -> Typ ( PEx )
25) Typ -> int
26) Typ -> rea
27) Typ -> com
28) Typ -> id
7. Грамматика выражений GR7 (Начальный символ Ex)
Тип: LL(1).
Терминалы :
pex = *ПростВыр ; rel = rel ; = = ;
Нетерминалы :
Ex = *Выраж 1 ; Ex) = ХвостВыраж 3 ;
Правила :
1) Ex -> pex Ex)
2) Ex) -> rel pex
3) Ex) -> = pex
4) Ex) ->
8. Грамматика векторов GR8 (Начальный символ Vec)
Тип: LL(1).
Терминалы :
id = Идент ; ( = ( ; ) = ) ;
, = , ; mlC = MultConst ; sum = Sum ;
dif = Dif ; cid = *КонстИден ;
Нетерминалы :
Vec = *Вектор 4 ;
Правила :
1) Vec -> id
2) Vec -> mlC ( Vec , cid )
3) Vec -> sum ( Vec , Vec )
4) Vec -> dif ( Vec , Vec )
9. Грамматика объектов комплексного типа GR9 (Начальный символ Cpx)
Тип: LL(1).
Терминалы :
id = Идент ; # = # ; , = , ;
[ = [ ; ] = ] ; cid = *КонстИден ;
vec = *Вектор3 ; pex = *ПростВыр ;
Нетерминалы :
Cpx = *Компл 3 ;
Правила :
1) Cpx -> id
2) Cpx -> # cid , cid #
3) Cpx -> vec [ pex ]
10. Грамматика константных идентификаторов GR10 (Начальный символ Cid)
Тип: LL(1).
Терминалы :
id = Идент ; + = +.- ; num = num ;
nat = nat ;
Нетерминалы :
Cid = *КонстИдент 3 ; Num = ЧислоБезЗн 2 ;
Правила :
1) Cid -> id
2) Cid -> Num
3) Cid -> + Num
4) Num -> num
5) Num -> nat