Разработка транслятора с языка PROST на язык С++. Часть 2., страница 2

Рис. 3. Матрица переходов КА для разделителей

Константа

Рис. 4. Матрица переходов КА для констант

2.1.3.4  КС-грамматика, порождающая язык PROST:

После непосредственного перевода описания языка из БНФ в грамматику весьма вероятно появление леворекурсивных правил, недостижимых или бесполезных символов, цепных правил. Существующие методы синтаксического анализа разработаны только для грамматик в нормальной форме Грейбах. Поэтому, прежде чем перейти к созданию синтаксического анализатора (СА), необходимо устранить левую рекурсию, недостижимые и бесполезные символы, цепные правила, то есть привести грамматику к нормальной форме.

Запишем порождающую грамматику для языка, описанного в Бэкусово-науровой форме. Список терминальных и нетерминальных символов грамматики не приводится, нетерминалы будут обозначаться словами из заглавных букв (например, EXPRESSION). Все остальные символы будем считать терминалами, в том числе

<identifer>, <const>.

TYPE → integer | float | label

VARDEF→ <identifer> as TYPE;

VARDEFS→ VARDEF VARDEFS | end

DEFS → vars VARDEFS

UNOP → BINOP→ + | - | * | /

CONDITION → < | > | = | <> | <= | >=

EXPRESSION  → <const> | EX | <identifer> | (EXPRESSION)

EX → UNOP EXPRESSION

EX → EXPRESSION BINOP EXPRESSION

OP_ASSIGNMENT → <identifer> : = EXPRESSION;

OP_INPUT → input <identifer>;

OP_OUTPUTN → outputn EXPRESSION;

OP_OUTPUTS → outputs STRC;

OP_WHLE → while (EXPRESSION CONDITION EXPRESSION) do OPERATORS

OP_IF → if (EXPRESSION CONDITION EXPRESSION) then OPERATORS

OP_IF → if (EXPRESSION CONDITION EXPRESSION) then OPERATORS else OPERATORS

OP_FOR → for (OPERATOR ; EXPRESSION CONDITION EXPRESSION ; OPERATOR) OPERATORS

OP_SWITCH → switch (EXPRESSION) SWITCH_BODY

SWITCH_BODY → SWITCH_STATEMENT | SWITCH_STATEMENT SWITCH_BODY | end

SWITCH_STATEMENT → case (EXPRESSION) OPERATORS

OP_LABEL → label <identifer>;

OP_GOTO → goto <identifer>;

OP_BREAK → break;

OP_CONTINUE → continue;

OP_CALL → call <identifer>;

OP_RETURN → return;

OPERATOR → OP_ASSIGNMENT | OP_WHLE | OP_IF | OP_INPUT | OP_OUTPUTN | OP_OUTPUTS | OP_BREAK | OP_CONTINUE | OP_SWITCH

OPERATOR → OPERATOR OPERATORS | end

CODE → code OPERATORS

PROGRAM → DEFS CODE;

2.1.3.5 Устранение недостижимых символов.

При анализе на достижимые символы считаем, что EXPRESSION и CONDITION являются терминалами.

V₀ = CODE = code OPERATORS

V₁ = V₀ U {operator | OPERATORS → operator OPERATORS є P;  OPERATORS є V₀} = {code OPERATORS, operator}

V₂ = V₁ U { end | OPERATORS → end є P; OPERATORS є V₁} = { code OPERATORS, operator, end }

V₃ = V₂ U { op_assignment | operator → op_assignment є P; OPERATOR є V₂} = { code OPERATORS, operator, end, op_assignment }

V₄ = V₃ U { op_while | operator → op_while є P; OPERATOR є V₃} = { code OPERATORS, operator, end, op_assignment, op_while }

V₅ = V₄ U { op_input | operator → op_input є P; OPERATOR є V₄} = { code OPERATORS, operator, end, op_assignment, op_while, op_input }

V₆ = V₅ U { op_outputn  | operator → op_outputn є P; OPERATOR є V₅} = { code OPERATORS, operator, end, op_assignment, op_while, op_input, op_outputn  }