n15 = n14 u {op_if | op_if → if (<const> < <const>) then end else end Є p, if (<const> < <const>) then end else end Є (n14 u t)}
= {unop, binop, condition, expression, op_input, op_outputs, op_label, op_goto, operators, EX, op_assignment, op_outputn, op_while, ELSE, op_if}
n16 = n15 U {operator → label <identifer> ; Є p, label <identifer> ; Є (n15 U T)}
= {unop, binop, condition, expression, op_input, op_outputs, op_label, op_goto, operators, EX, op_assignment, op_outputn, op_while, ELSE, op_if, operator}
n17 = n16 U {code | code → code end Є p, code end Є (n16 u t)}
= {unop, binop, condition, expression, op_input, op_outputs, op_label, op_goto, operators, EX, op_assignment, op_outputn, op_while, ELSE, op_if, operator, code}
Безполезными являются символы: op_DIM
N0 = operator
n1 = {op_assignment | operator → op_assignment Є p, operator Є n0} U n0
= {operator, op_assignment}
n2 = {op_while | operator → op_while Є p, operator Є n1} U n1
= {operator, op_assignment, op_while}
n3 ={op_input | operator → op_input Є p, operator Є n2} U n2
= {operator, op_assignment, op_while, op_input}
n4 = {op_outputn | operator → op_outputn Є p, operator Є n3} U n3
= {operator, op_assignment, op_while, op_input, op_outputn}
n5 = {op_outputs | operator → op_outputs Є p, operator Є n4} U n4
= {operator, op_assignment, op_while, op_input, op_outputn, op_outputs}
n6 = {op_GOTO | operator → op_GOTO Є p, operator Є n5} U n5
= {operator, op_assignment, op_while, op_input, op_outputn, op_outputs, op_GOTO}
n7 = {OP_LABEL | operator → OP_LABEL Є p, operator Є n6} U n6
= {operator, op_assignment, op_while, op_input, op_outputn, op_outputs, op_GOTO, OP_LABEL}
n8 = {OP_IF | operator → OP_IF Є p, operator Є n7} U n7
= {operator, op_assignment, op_while, op_input, op_outputn, op_outputs, op_GOTO, OP_LABEL, OP_IF}
noperator = {operator, op_assignment, op_while, op_input, op_outputn, op_outputs, op_GOTO, OP_LABEL, OP_IF}
N0 = expression
N1 = {ex | expression → ex Є p, expression Є n0} U n0
= {expression, ex}
Nexpression = {expression, ex}
P’ = { operator → <identifer> := expression; |
while ( expression condition expression ) do operators |
input <identifer> ;|
outputn expression ; |
outputs <strc> ; |
goto <identifer> ; |
label <identifer> ; |
if ( expression condition expression ) then operators ELSE
expression → <const>|
- expression |
expression binop expression |
<identifer>|
(expression) }
P = { expression → <const> |
- expression |
expression binop expression |
<identifer> |
(expression) }
P’ = { EXPRESSION → <const> EXPRESSION’|
- expression EXPRESSION’ |
<identifer> EXPRESSION’ |
(expression) EXPRESSION’
EXPRESSION’ → binop expression EXPRESSION’ | λ }
Преобразовав грамматику, таким образом, мы получаем грамматику без левой рекурсии, без цепных правил, без бесполезных и недостижимых символов:
TYPE → integer | float | label
vardef → <identifer> as type ;
vardefs → vardef vardefs | end
defs → vars vardefs
binop → + | - | * | /
condition → < | > | = | <> | <= | >=
EXPRESSION → <const> EXPRESSION’|
- expression EXPRESSION’ |
<identifer> EXPRESSION’ |
(expression) EXPRESSION’
EXPRESSION’ → binop expression EXPRESSION’ | λ
ELSE → else operators | λ
operator → <identifer> := expression; |
while ( expression condition expression ) do operators |
input <identifer> ; | outputn expression ; |
outputs <strc> ; |
goto <identifer> ; |
label <identifer> ; |
if ( expression condition expression ) then operators ELSE
operators → operator operators | end
code → code operators
program → defs code ;
Уважаемый посетитель!
Чтобы распечатать файл, скачайте его (в формате Word).
Ссылка на скачивание - внизу страницы.