Скачиваний:
9
Добавлен:
01.05.2014
Размер:
170.5 Кб
Скачать

Вариант №5

    1. Составить А-грамматику(автоматную), распознающую цепочки, состоящие из 0 и 1 , в которых кол-во 0 не равно нулю и четно. Каждый нуль находится между единицами.

T = {0,1}

N={S, A, B, C, D, G}

R={ S 1 A, A 0 B, A 1 A, B1 C, C 1 C, C0 D, D 1 G, G1 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 – не корректны

    1. Удаление левой рекурсии. Например: G=<{i, , , , (, )},{S, T, P},S,

{S–>ST, S–>T, T–>TP, 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. Построить преобразователь, преобразующий вещественные числа без знака с фиксированной точкой в последовательность целых чисел.

Уточнение: числа разделены запятыми, последовательность заканчивается #.

Перевод: 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 – значение указателя на свободную позицию в таблице констант

p2p1 p1 – имя константы

q2q1 q1 – значение константы

CNSp2  + CNSNSp1

p2p1 p1 – значение константы

CNSp2   CNSNSp1

p2p1

CNSp2  CNSNSp1

p2p1

CNSNSp2  nump1

p2p1

CNSNSp2  ICp1

p2p1

ICp2  idp1

p2p1 p1 – имя константы

НОВКОН - процедура, которая выдает значение указателя на свободную позицию таблицы констант.

Операционный символ:

{константа}A1,A2,A3

Записывает имя А1 и значение А2 константы в таблицу констант по адресу A3.

P.S. Переведено в триады, LL(1)-анализ

4. Определить является ли грамматика грамматикой слабого предшествования.

КС-грамматика G = < T, N, S, R > называется грамматикой предшествования, если она приведенная, не содержит правил с пустой правой частью и для любой пары символов из V выполняется не более одного отношения простого предшествования.

Пусть G = < T, N, S, R > – приве­денная грамматика без -правил. Назовем G грамматикой сла­бого предшествования, если

  1. отношение •> не пересекается с объединением отношений <• и  ;

2) для AX и В   из R, где XV, не выполняется ни Х <• В, ни Х  В.

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 видов (одновременное сворачивание, раньше/позже или вообще отсутствие отношения).

Для построения матрицы отношений действуем по этим группам:

  • Нахождение всех отношений одновременного сворачивания

XY, если в правой части правила они находятся рядом, т.е.

AXY

Т.о. ищем в нашей грамматике символы, находящиеся рядом и в соответствующие ячейки матрицы заносим обозначение одновременного сворачивания:

В 1-ом правиле: E or, or T

В 3-ем правиле: T and, and  P

В 6-ом правиле: (  E, E  )

В 7-ом правиле: not  P

  • Ищем отношения вида X <• Y (Х сворачивается позже, чем У).

Соседние файлы в папке variaNTS