Решенные задачи на экзамен Опалевой / variaNTS / VAR_4
.DOCВариант №4
-
Составить А-грамматику, КС-грамматику, распознающую язык {a2n b, где n>0}
Автоматная грамматика
T = {a,b}
N= {S, A, B, C}
R={ S a A, A aB, BaA, BbC, B , C }
Управляющая таблица детерминированного конечного автомата по автоматной
грамматике G = <T, N, S,R >
-
a
b
Eps
S (q0)
A
A (q1)
B
B (q2)
A
C
C (q3)
Функции перехода : q2 , q3 – заключительные состояния
(q0 , a) q1
(q1 , a) q2
(q2 , a) q1
(q2 , b) q3
Контекстно-свободная грамматика
T = {a,b}
N= {S, A, B, C}
R={ S A b , A A a a , A a a }
-
Исключение произвольного правила.
Нужно получить G’ = <T, N, S, R’>
Необходимо исключить правило AB R’
Пусть существует множество правил B1, …Bm
Тогда R’ = (R\{ AB}) (A1, A2,… Am)
-
Построить расширенный МПА {S->bAb, A->(L, A->a, L->Aa) }
Алгоритм: a) (q, a, ) = {(q, a)}, a{T}
б) AR, (q, ,) = {(q, A)}
в) (q, , S) = {(r, )}
Применим:
-
(q, a, ) = {(q, a)}, a{ a, b, ), ( }
б) (q, ,bAb ) = {(q, S)}
(q, ,(L ) = {(q, A)}
(q, ,a ) = {(q, A)}
(q, , Aa) ) = {(q, L)}
в)(q, ,S ) = {(r, )}
Пример разбора цепочки:
(q, bab, ) (q, ab, b) (q, b, ba) (q, b, bA) (q, , bAb) (q, , S) (r, ,)
-
Написать AT-грамматику для описания простых переменных в С++
P.S. Перевод в польскую инверсную запись, опер. предш., «перенос-свертка»
arc- арифметическая константа
loc- логическая константа
num- число
ind - идентификатор
typ- тип
<описание переменной> |
OPP |
<присвоенное значение> |
PZN |
<значение> |
ZNA |
OPP<<q1>> -> typ<<k1>> ind<<k2>> PZN<<k3>>
{{ИНИТ_ПРЕМ1}}<<q2,q3,q4>>
q1,q2 <- k1
q3 <- k2
q4 <- k3
OPP<<q1>> -> ind<<k1>> ind<<k2>> PZN<<k3>>
{{ИНИТ_ПРЕМ2}}<<q2,q3,q4>>
q1,q2 <- k1
q3 <- k2
q4 <- k3
OPP<<q1>> -> OPP<<k1>> ,ind<<k2>> PZN<<k3>>
{{ИНИТ_ПРЕМ1}<<q2,q3,q4>>
q1,q2 <- k1
q3 <- k2
q4 <- k3
OPP<<q1>> -> ind<<k1>> ind<<k2>>
{{ИНИТ_ПРЕМ4}}<<q2,q3>>
q1,q2 <- k1 q3 <- k2
OPP<<q1>> -> typ<<k1>> ind<<k2>>
{{ИНИТ_ПРЕМ3}}<<q3,q3>>
q1,q2 <- k1
q3 <- k2
OPP<<q1>> -> OPP<<k1>> ,ind<<k2>>
{{ИНИТ_ПРЕМ3}}<<q2,q3>>
q1,q2 <- k1
q3 <- k2
PZN<<q1>> -> = ZNA<<k1>>
q1 <- k1
ZNA<<q1>> -> loc<<k1>>
q1 <- k1
ZNA<<q1>> -> arc<<k1>>
q1 <- k1, где к1 соответствующие значения.
{{ИНИТ_ПРЕМ1}}Выполняет следующие:
Проверяет соответствие типа с номером q2 в таблице идентификаторов и значение атрибута q4 и если ошибка не обнаружена, то записывает данные о типе q2 и значении q4 в таблицу переменных, создавая ссылку на нее в таблице идентификаторов для идентификатора с номером q3.
{{ИНИТ_ПРЕМ2}}Выполняет следующие:
Находит в таблице идентификаторов в позиции q2 тип и проверяет соответствие типа и значение атрибута q4 и если ошибка не обнаружена, то записывает данные о типе q2 и значении q4 в таблицу переменных, создавая ссылку на нее в таблице идентификаторов для идентификатора с номером q3.
{ИНИТ_ПРЕМ3}}Выполняет следующие:
Записывает данные о типе q2 в таблицу переменных, создавая ссылку на нее в таблице идентификаторов для идентификатора с номером q3.
{{ИНИТ_ПРЕМ4}}Выполняет следующие:
Находит в таблице идентификаторов в позиции q2 тип. Записывает данные о типе в таблицу переменных, создавая ссылку на нее в таблице идентификаторов для идентификатора с номером q3.
4. Построить нисходящий ДМП
R={E->TE’, E’->+T{+}E’, E’-> , T->PT’, T’->*P{*}T’, T’-> , P->.{.}/{/}C.{.}, C->/{/}, C-> }
Определение нисходящего ДМП, который должен описывать перевод, задаваемый транслирующей грамматикой, входной грамматикой которой является LL(1) грамматика.
ETE’ (1) E’+T{+}E’(2) E’ (3) T PT’ (4) T’*P{*}T’ (5) T’ (6)
P .{.}/{/}C.{.} (7) C /{/}(8) C (9)
Вход: (Vi (вход.) Va (опер.) N {}) x (Vi {})
С опер. символами: {x}: выдача, выброс, допуск, ошибка.
// Н. построить упр. таблицу LL(1) без опер. символов.
1) ПЕРВ (Е) = {.}
2) ПЕРВ (Е’) = {+}
3)СЛЕД (E’) = {}
4) ПЕРВ (T) = {.}
5) ПЕРВ (T’) = {*}
6) СЛЕД (T’) = {, +}
7) ПЕРВ (P) = {.}
8) ПЕРВ (C) = {/}
9) СЛЕД (C) = {.}
|
/ |
+ |
* |
. |
|
E |
|
|
|
T E’ , |
|
E’ |
|
+ T{+}E’, |
|
|
, |
T |
|
|
|
P T’ , |
|
T’ |
|
, |
* P {*}T’, |
|
, |
P |
|
|
|
.{.}/{/}C.{.}, |
|
C |
/ {/}, |
|
|
, |
|
/ |
ВЫБРОС |
|
|
|
|
+ |
|
ВЫБРОС |
|
|
|
* |
|
|
ВЫБРОС |
|
|
. |
|
|
|
ВЫБРОС |
|
|
|
|
|
|
ДОПУСК |
{/} |
В Ы Д А Ч А { / } |
||||
{*} |
В Ы Д А Ч А { * } |
||||
{+} |
В Ы Д А Ч А { + } |
||||
{.} |
В Ы Д А Ч А { . } |
В результате работы построенного ДМП на выходе автоматически получаем польскую инверсную запись.