- •Транслирующая грамматика
- •C) Функии переходов преобразователя и пример его работы
- •Пример работы преобразователя
- •Лексический анализатор
- •A) Грамматика лексических единиц и структура лексем
- •B) Матрица переходов лексического анализатора
- •D) Структура программы лексического анализатора и пример его работы
- •C) Описание символов действия
- •D) Атрибутная грамматика в окончательном виде
- •E) Вывод в атрибутной грамматике
- •B) Построение инструкций а-преобразвателя
- •C) Фрагмент работы а-преобразователя
- •Заключение
E) Вывод в атрибутной грамматике
Входная цепочка:
main()
{
float x, y;
}
first=0 last=?<PROGRAM>
|- 0 ? “main()” ‘{’ first1 last1 <MAIN_BLOCK> ‘}’
|- 0 ? “main()” ‘{’ 0 ? first1 last1 <DEF_VAR> ‘}’
|- 0 ? “main()” ‘{’ 0 ? 0 ? first1 last1 <VAR> first2 last2 <CONTINUE>‘}’
|- 0 ? “main()” ‘{’ 0 ? 0 ? 0 ? first1 last1 <DEFINE_CONSTANT> first2 last2 <CONT_VAR >
? ? <CONTINUE>‘}’
|- 0 ? “main()” ‘{’ 0 ? 0 ? 0 ? 0 ? “float” first1 last1 <LIST_IDENT_F> ‘;’ ? ? <CONT_VAR >
? ? <CONTINUE>‘}’
|- 0 ? “main()” ‘{’ 0 ? 0 ? 0 ? 0 ? “float” 0 ? #Name=#1 <IDENTIFICATOR> first1 last1=0+1=1 name
{new_float} first2 last2 <C_L_I_F> ‘;’ ? ? <CONT_VAR > ? ? <CONTINUE>‘}’
|- 0 ? “main()” ‘{’ 0 ? 0 ? 0 ? 0 ? “float” 0 ? #1 “x” 0 1 #1 {new_float} 1 ? ‘,’ first1 last1
<LIST_IDENT_F> ‘;’ ? ? <CONT_VAR > ? ? <CONTINUE>‘}’
|- 0 ? “main()” ‘{’ 0 ? 0 ? 0 ? 0 ? “float” 0 ? #1 “x” 0 1 #1 {new_float} 1 ? ‘,’ 1 ? #Name=#2
<IDENTIFICATION> first1 last1=1+1=2 name {new_float} first2 last2 <C_L_I_F>‘;’ ? ?
<CONT_VAR > ? ? <CONTINUE>‘}’
|- 0 ? “main()” ‘{’ 0 ? 0 ? 0 ? 0 ? “float” 0 ? #1 “x” 0 1 #1 {new_float} 1 ? ‘,’ 1 ? #2 “y” 1 2 #2
{new_float} 2 ? $ ‘;’ ? ? <CONT_VAR > ? ? <CONTINUE>‘}
|- 0 ? “main()” ‘{’ 0 ? 0 ? 0 ? 0 2 “float” 0 2 #1 “x” 0 1 #1 {new_float} 1 2 ‘,’ 1 2 #2 “y” 1 2 #2
{new_float} 2 2 ‘;’ 2 ? $ ? ? <CONTINUE>‘}’
|- 0 ? “main()” ‘{’ 0 ? 0 ? 0 2 0 2 “float” 0 2 #1 “x” 0 1 #1 {new_float} 1 2 ‘,’ 1 2 #2 “y” 1 2 #2
{new_float} 2 2 ‘;’ 2 2 2 ? $ ‘}’
|- 0 2 “main()” ‘{’ 0 2 0 2 0 2 0 2 “float” 0 2 #1 “x” 0 1 #1 {new_float} 1 2 ‘,’ 1 2 #2 “y” 1 2 #2
{new_float} 2 2 ‘;’ 2 2 2 2 ‘}’
Атрибутный преобразователь
a) Построение функций переходов А-преобразователя
-- оптимизация для правил, правая часть которых начинается с терминала
-- сдвиг, вытолкнуть, заменить
#1 ( S, "main()" , <program> ) = ( S, }<mainblock> { , $ )
#2 ( S, "int" , <define_constant> ) = ( S, ;<list_ident_i> ,$ )
#3 ( S, "float" , <define_constant> ) = ( S, ;<list_ident_f> , $ )
#4 ( S, "," , <c_l_i_i> ) = ( S, <list_ident_i> , $ )
#5 ( S, "," , <c_l_i_f> ) = ( S, <list_ident_f> , $ )
#6 ( S, {, <block> ) = ( S, }<body> , $ )
#7 ( S, +, <cont_r_equation> ) = ( S, {#(+)#}{new_cell}<r_equation>,$ )
#7 ( S, , <cont_r_equation> ) = ( S, {#(*)#}{new_cell}<r_equation>,$ )
#8 ( S, "for(" , <head> ) = ( S, <cont_head> <equation>,$ )
#9 ( S, ;, <cont_head> ) = ( S, <ccont_head>{#(jmp_down_false)#}{make_lbl} <condition2>{#(label)#}, $ )
#10 ( S, ;, <ccont_head> ) = ( S, ")"<condition3> , $ )
#11 ( S, ">" , <cont_cond2> ) = ( S, {#(>)#}{new_cell}<constant> , $ )
#11 ( S, "<" , <cont_cond2> ) = ( S, {#(<)#}{new_cell}<constant> , $ )
-- правила общего вида
-- нет сдвига, заменить
#12 *( S, "int" , <mainblock> ) = ( S, <def_var> , $)
#12 *( S, "float" , <mainblock> ) = ( S, <def_var> , $ )
#13 *( S, "int" , <def_var> ) = ( S, <continue> <var> , $ )
#13 *( S, "float" , <def_var> ) = ( S, <continue> <var> , $ )
#14 *( S, "int" , <var> ) = ( S, <cont_var> <define_constant> , $ )
#14 *( S, "float" , <var> ) = ( S, <cont_var> <define_constant> , $ )
#15 *( S, _ID_, <list_ident_i> ) = ( S, <c_l_i_i>{new_int}<identificator> , $ )
#16 *( S, _ID_, <list_ident_f> ) = ( S, <c_l_i_f>{new_float}<identificator> , $ )
#17 *( S, {, <continue> ) = ( S, <block> , $ )
#18 *( S, _ID_, <body> ) = ( S, <cont_body> <start> , $ )
#18 *( S, "for(" , <body> ) = ( S, <cont_body> <start> , $ )
#19 *( S, _ID_, <start> ) = ( S, ;<equation> , $ )
#20 *( S, "for(" , <start> ) = ( S, <for> , $ )
#21 *( S, _ID_, <equation> ) = ( S, {#(=)#}<r_equation> =<identificator> , $ )
#22 *( S, _ID_, <r_equation> ) = ( S, <cont_r_equation> <identificator> ,$ )
#23 *( S, _CONST_, <r_equation> ) = ( S, <cont_r_equation> <constant> , $ )
#24 *( S, "for(" , <for> ) = ( S, ;{#(label)#}{#(jmp_up)#}<block> <head>{make_lbl} , $ )
#25 *( S, _ID_, <condition2> ) = ( S, <cont_cond2> <identificator> , $ )
#26 *( S, _ID_, <condition3> ) = ( S, ;<equation> , $ )
#27 *( S, _ID_, <cont_body> ) = ( S, <body> , $ )
#27 *( S, "for(" , <cont_body> ) = ( S, <body> , $ )
#28 *( S, "int" , <cont_var> ) = ( S, <var> , $ )
#28 *( S, "float" , <cont_var> ) = ( S, <var> , $ )
-- Е-правила
-- нет сдвига, вытолкнуть
#29 *( S, }, <mainblock> ) = ( S, $,$ )
#30 *( S, ;, <c_l_i_i> ) = ( S, $ ,$)
#31 *( S, ;, <c_l_i_f> ) = ( S, $ ,$)
#32 *( S, {, <cont_var> ) = ( S, $,$ )
#32 *( S, }, <cont_var> ) = ( S, $ ,$)
#33 *( S, }, <continue> ) = ( S, $ ,$)
#34 *( S, }, <cont_body> ) = ( S, $ ,$)
#35 *( S, ;, <cont_r_equation> ) = ( S, $ ,$)
-- выталкивание терминалов
-- сдвиг, вытолкнуть
-- выталкивание терминалов
-- сдвиг, вытолкнуть
#36 ( S, {, {) = ( S, $, $ )
#36 ( S, ;, ;) = ( S, $, $ )
#36 ( S, }, }) = ( S, $, $ )
#36 ( S, "," , "," ) = ( S, $, $ )
#36 ( S, "<" , "<" ) = ( S, $, $ )
#36 ( S, ">" , ">" ) = ( S, $, $ )
#36 ( S, ")" , ")" ) = ( S, $, $ )
#36 ( S, "for(" , "for(" ) = ( S, $, $ )
#36 ( S, "int" , "int" ) = ( S, $, $ )
#36 ( S, "float" , "float" ) = ( S, $, $ )
#36 ( S, "main()" , "main()" ) = ( S, $, $ )
#36 ( S, *, *) = ( S, $, $ )
#36 ( S, +, +) = ( S, $, $ )
#36 ( S, =, =) = ( S, $, $ )
#36 ( S, a, a) = ( S, $, $ )
#36 ( S, b, b) = ( S, $, $ )
#36 ( S, c, c) = ( S, $, $ )
#36 ( S, 0, 0) = ( S, $, $ )
#36 ( S, 1, 1) = ( S, $, $ )
#36 ( S, 2, 2) = ( S, $, $ )
#36 ( S, ., .) = ( S, $, $ )
-- переход в заключительное состояние
#37 ( S, -|, [] ) = ( S1, $, $ )