- •Вариант №5
- •Управляющая таблица детерминированного конечного автомата по автоматной
- •Языку принадлежат цепочки, содержащие четное число нулей (не равное нулю), а также каждый ноль находится между единицами:
- •Для этого должны существовать правила исходной грамматики вида
- •Для этого должны существовать правила исходной грамматики вида
Вариант №5
-
Составить А-грамматику(автоматную), распознающую цепочки, состоящие из 0 и 1 , в которых кол-во 0 не равно нулю и четно. Каждый нуль находится между единицами.
T = {0,1}
N={S, A, B, C, D, G}
R={ S 1 A, A 0 B, A 1 A, B1 C, C 1 C, C0 D, D 1 G, G1 G,
G 0 B, G }
Управляющая таблица детерминированного конечного автомата по автоматной
грамматике G = <T, N, S,R >
-
0
1
Eps
S (q0 )
A
A (q1 )
B
A
B (q2 )
C
C(q3 )
D
C
D(q4 )
G
G(q5 )
B
G
Функции перехода:
(q0 , 1) q1
(q1 , 0) q2
(q1 , 1) q1
(q2 , 1) q3
(q3 , 0) q4
(q3 , 1) q3
(q4 , 1) q5
(q5 , 0) q2
(q5 , 1) q5
Языку принадлежат цепочки, содержащие четное число нулей (не равное нулю), а также каждый ноль находится между единицами:
10101 , 11101101111101011 – корректные; 101, , 111, 1001 – не корректны
-
Удаление левой рекурсии. Например: G=<{i, , , , (, )},{S, T, P},S,
{S–>ST, S–>T, T–>TP, T–>P, P–>P, P–>(S), P–>i}>
Нетерминал A называется леворекурсивным , если, применяя к нему одно или более правил, можно вывести цепочку, начинающуюся этим нетерминалом. КС-грамматика, имеющая хотя бы один леворекурсивный нетерминал, называется грамматикой с левой рекурсией . При удалении левой рекурсии входная грамматика должна быть НКС-грамматикой без циклов. (Грамматикой без циклов называется грамматика, не содержащая правила вывод A=>+A). После удаления левой рекурсии в грамматике могут появиться e -правила и цепные правила.
Алгоритм удаления левой рекурсии :
-
N’=N, R’=0
-
R’={P–>P, P–>(S), P–>i} (T, S – леворекурсивные, в R’ включаем правила, слева в которых – P )
-
R’’={ S–>TS’, S’–>TS’, S’–>e, T–>PT’, T’–>PT’, T’–>e, P–>P, P–>(S), P–>i }
-
N’=N{S’, T’}
-
Построить преобразователь, преобразующий вещественные числа без знака с фиксированной точкой в последовательность целых чисел.
Уточнение: числа разделены запятыми, последовательность заканчивается #.
Перевод: 1.23 1 , 234. 45577 234 и т.д. Т.е. в результате получаем последовательность целых чисел, разделенных запятой и заканчивающейся на #.
Управляющая таблица:
|
ch |
. |
, |
# |
Eps |
S (q0 ) |
A |
|
|
|
|
A (q1 ) |
A |
B |
|
|
|
B (q2 ) |
D |
|
|
|
|
D (q3 ) |
D |
|
A |
D |
|
(q0, ch) {(q1, ch)}
(q1, ch) {(q1, ch)}
(q1, . ) {(q2, ) }
(q2, ch) {(q3, )}
(q3, , ) {(q1, , )}
(q3, # ) {(q3, #)}
3. АТ-грамматика для раздела описаний констант в Pascal
<раздел_описания_констант>::= const <опр_константы>;{<опр_константы>;}
<опр_константы>::= <имя_константы> = <константа>
<константа>::= [<знак>] <константа_без_знака>
<константа_без_знака>::= число_без_знака | <имя константы>
<имя константы>::= идентификатор
RC |
раздел констант |
|
OC |
определение константы |
|
OC` |
остаток определения константы |
|
ICp |
имя константы |
p – синтезированный |
CNSp |
константа |
p – синтезированный |
CNSNSp |
константа без знака |
p – синтезированный |
RC con OC ; OC`
RC
OC` OC ; OC`
OC`
OC ICp1 = CNSq1 {константа}p2,q2,r
rНОВКОН r – значение указателя на свободную позицию в таблице констант
p2p1 p1 – имя константы
q2q1 q1 – значение константы
CNSp2 + CNSNSp1
p2p1 p1 – значение константы
CNSp2 CNSNSp1
p2p1
CNSp2 CNSNSp1
p2p1
CNSNSp2 nump1
p2p1
CNSNSp2 ICp1
p2p1
ICp2 idp1
p2p1 p1 – имя константы
НОВКОН - процедура, которая выдает значение указателя на свободную позицию таблицы констант.
Операционный символ:
{константа}A1,A2,A3 |
Записывает имя А1 и значение А2 константы в таблицу констант по адресу A3. |
P.S. Переведено в триады, LL(1)-анализ
4. Определить является ли грамматика грамматикой слабого предшествования.
КС-грамматика G = < T, N, S, R > называется грамматикой предшествования, если она приведенная, не содержит правил с пустой правой частью и для любой пары символов из V выполняется не более одного отношения простого предшествования.
Пусть G = < T, N, S, R > – приведенная грамматика без -правил. Назовем G грамматикой слабого предшествования, если
-
отношение •> не пересекается с объединением отношений <• и ;
2) для AX и В из R, где XV, не выполняется ни Х <• В, ни Х В.
E E or T (1)
E T (2)
T T and P (3)
T P (4)
P i (5)
P ( E ) (6)
P not P (7)
Алгоритм построения матрицы предшествования:
Существуют отношения 4 видов (одновременное сворачивание, раньше/позже или вообще отсутствие отношения).
Для построения матрицы отношений действуем по этим группам:
-
Нахождение всех отношений одновременного сворачивания
XY, если в правой части правила они находятся рядом, т.е.
AXY
Т.о. ищем в нашей грамматике символы, находящиеся рядом и в соответствующие ячейки матрицы заносим обозначение одновременного сворачивания:
В 1-ом правиле: E or, or T
В 3-ем правиле: T and, and P
В 6-ом правиле: ( E, E )
В 7-ом правиле: not P
-
Ищем отношения вида X <• Y (Х сворачивается позже, чем У).