Лабораторные работы 1-7(старые) / Отчет по ТЯП2

Санкт-Петербургский государственный электротехнический университет

КАФЕДРА МО ЭВМ

ОТЧЕТ ПО ЛАБОРАТОРНОЙ РАБОТЕ N2

по дисциплине "Теория языков программирования"

Преподаватель: Самойленко В.П.

студенты гр. 0341 Юбрин А.Н.

Шин Е.Д.

Санкт-Петербург

2002

Задание: Описать синтаксис описания процедуры в языке Паскаль при условии, что операторы, составляющие тело процедуры, описывать не нужно.

1. Преобразовать КС-грамматику G = < Т, N, S, R > в эквивалентную грамматику, не содержащую бесполезных символов.

G = < Т, N, S, R >

Терминалы : а ; b ;

Нетерминалы : S; B; C; D; A;

Правила :

1) S  a B

2) B  a C

3) B  b A

4) C  b C

5) D  b

6) A  a A

7) A  a

Построим множество производящих нетерминалов:

{}, {S}, {S, B}, {S,B, D}, {S, B, D, A}

нетерминал С является непрозводящим, т.к. из него нельзя вывести цепочку не содержащую нетерминалов.

Удалим правила 2), 4)

Np={S, A, B, D}

G = < Т, N, S, R >

Терминалы : а ; b ;

Нетерминалы : S; B; D; A;

Правила :

1) S  a B

3) B  b A

5) D  b

6) A  a A

7) A  a

Построим множество достижимых символов

{S} {S, a ,B } {S, a ,B , b, A}

нетерминал D является недостижимым т.к. ни одно правило содержащее нетерминал D не удовлетворяет условию занесения в множество достижимых символов.

Удалим правило 5)

Nr={ S, a ,B , b, A }

Запишем результат:

G = < Т, N, S, R >

Терминалы : а ; b ;

Нетерминалы : S; B; A;

Правила :

1) S  a B

2) B  b A

3) A  a A

4) A  a

2. Преобразовать исходную КС-грамматику G = < Т, N, S, R > в эквивалентную НКС-грамматику.

G = < Т, N, S, R >

Терминалы : 0 ; 1 ;

Нетерминалы : S ; A ;

Правила :

1) S  S S

2) S  1 A 0

3) A  1 A 0

4) A 

Требуется получить НКС-грамматику G`={T,N`, S`, R`}

Построим множество укорачивающих терминалов.

{A}

Ne={A}

Построим множество R` правил НКС-грамматики

{}, {S  S S}, {S  S S; S  1 A 0; }, {S  S S; S  1 A 0; A 1 A 0}

{S  S S; S  1 A 0; A 1 A 0; S  1 0; } {S  S S; S  1 A 0; A 1 A 0; S  1 0; A 1 0; }

Т.к. S не принадлежит Ne, то

N`=N

S`=S

Запишем результат:

G`={T,N`, S`, R`}

Терминалы : 0 ; 1 ;

Нетерминалы : S` ; A ;

Правила :

1) S`  S` S`

2) S`  1 A 0

3) S`  1 0

4) A  1 A 0

5) A  1 0

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

G = < T, N, S, R >

Терминалы : a; b; c;

Нетерминалы : S; A; B;

Правила :

1) S  a A b

2) S  c

3) A  b S

4) A  B b

5) B  a A

6) B  c

Требуется получить КС-грамматику без правил с одинаковой правой частью G`={T,N`, S, R`}

Построим множество R`

Разобъем множество R на подмножества правил с одинаковой правой частью. И построим множества нетерминалов N_i={A | Aa_i  R_i AN}

R₁ ={ S  a A b} N₁ ={S}

R₂ ={ S  c; B  c } N₂ ={S, B}

R₃ ={ A  b S } N₃ ={A}

R₄ ={ A  B b } N₄ ={A}

R₅ ={ B  a A } N₅ ={B}

Включим в R` множества R_i такие, что количество правил в R_i =1.

R`={S  a A b ; A  b S ; A  B b ; B  a A }

Включим в R` первое правило множества R₂

R`={S  a A b ; A  b S ; A  B b ; B  a A ; S  c }

Добавим правило полученное из A  B b , A  c b

R`={S  a A b ; A  b S ; A  B b ; B  a A ; S  c ; A  c b }

Полученная грамматика не содержит бесполезных символов.

Запишем результат:

G`={T,N`, S, R`}

Терминалы : a; b; c;

Нетерминалы : S; A; B;

Правила :

1) S  a A b

2) S  c

3) A  b S

4) A  B b

5) A  c b

6) B  a A

4. Преобразовать НКС-грамматику G = < Т, N, S, R > в эквивалентную КС-грамматику, не содержащую цепных правил.

G = < Т, N, S, R >

Терминалы : a; j;

Нетерминалы : S; A; B; C; D;

Правила :

1) S  A C

2) A  B

3) A  A a B

4) B  j

5) C  D

6) C  D a C

7) D  j

Требуется получить КС-грамматику без цепных правил G`={T,N, S, R`}

Построим множество нетерминалов N_A

NS={S} R`={S  A C}

NA={A} R`={ S  A C ; A  A a B }

NB={B} R`={ S  A C ; A  A a B ; B  j ; A  j}

NC={C} R`={ S  A C ; A  A a B ; B  j ; A  j; C  D a C }

ND={D} R`={ S  A C ; A  A a B ; B  j ; A  j; C  D a C ;

D  j ; C  j }

Запишем результат:

G`={T,N, S, R`}

Терминалы : a; j;

Нетерминалы : S; A; B; C; D;

Правила :

1) S  A C

2) A  j

3) A  A a B

4) B  j

5) C  j

6) C  D a C

7) D  j

5. Исключить левую рекурсию из КС-грамматики G = < Т, N, S, R >.

G = < Т, N, S, R >

Терминалы : a; b; c

Нетерминалы : S; A;

Правила :

1) S  S a A

2) S  A A

3) S  b

4) A  A S a

5) A  A b

6) A  c

Требуется получить КС-грамматику без левой рекурсии G`={T,N`, S, R`}

Построим множество R`

{}

Добавим правила для самолеворекурсивного нетерминала S

{S1  a A S1; S1  ; S  b S1; S  A A S1}

Добавим правила для самолеворекурсивного нетерминала A

{S1  a A S1; S1  ; S  b S1; S  A A S1;

A1  S a A1 ; A1  b A1 ; A  c A1; A1  }

Построим множество N`=N+{S1, A1} = {S, S1, A, A1}

Запишем результат:

G`={T,N`, S, R`}

Терминалы : a; b; c

Нетерминалы : S; A; S1; A1

Правила :

1) S  A A S1

2) S  b S1

3) A  c S1

4) S1  a A S1

5) S1 

6) A1  S a A1

7) A1  b A1

8) A1 