Название: Информатика (формальные языки и грамматики) - Методическая разработка(С.Е. Рояк)

Жанр: Информатика

Просмотров: 1363


Занятие 8.  деревья грамматического разбора. проблема неоднозначности кс-грамматик и кс-языков

 

Цель занятия: уметь строить синтаксические деревья разбора. Знать и понимать проблему неоднозначности формальных языков и грамматик и решение этой проблемы в практических приложениях (в частности, в языках программирования).

 

Методические указания

 

Что необходимо знать:

канонический вывод и синтаксические деревья;

какие грамматики называются неоднозначными?

какие языки называются неоднозначным?

что значит существенно- неоднозначный язык?

признаки неоднозначности грамматики.

 

Основные определения

 

1. Вывод называется каноническим (левосторонним), если на каждом шаге вывода правило вывода применяется к самому левому вхождению нетерминального символа.

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

3. Неоднозначность часто является свойством не языка, а грамматики, так как для одного и того же языка можно построить эквивалентные грамматики, одна из которых будет однозначной, а другая нет.

4. Язык называется существенно-неоднозначным, если не существует однозначной грамматики, его порождающей.

5. Проблема неоднозначности неразрешима уже для КС-языков. Автоматные языки однозначны. Существуют некоторые признаки, по которым можно определить неоднозначную грамматику. Такими признаками являются: 

а) двойная рекурсия по одному и тому же нетерминальному символу. Например, A ® AaA, где A Î N, a Î (TÈN)*;

б) наличие в грамматике леволинейных и праволинейных правил вывода, имеющим рекурсию по одному и тому же нетерминальному символу одновременно. Например, A ® aA | Ab,

где a,bÎ(TÈN)+, AÎN;

в) наличие в грамматике леволинейных (праволинейных) правил вывода совместно с правилами, имеющими центральную рекурсию по одному и тому же нетерминальному символу.

Например, A ®aA | aAb или A ® Ab |aAb,

где  a,bÎ(T È N)+, A Î N.

 

Задачи и упражнения

 

1. Пусть грамматика G=<T,N,S,P> имеет вид: N={S, A, B}, T={a, b} P={S®AB,  A®Aa½bB, B®a½Sb}. Построить деревья выводов цепочек:

а) baabaab,       b) bBABb,         c) baSb.

2. Построить левый и правый выводы цепочки baabaab в грамматике из упражнения 8.

3. Построить левый вывод цепочки if bÙb then if bÚb then s else s else s в грамматике

G=<{S, B}, {b,s,Ù,Ú, if, then, else}, { S®if B then S else S½s, B®BÙB½BÚB½b}, S>.

Добавье правило S ® if B then S и постройте левый вывод цепочки if b then if b then s else s. Сколько таких выводов можно построить?

4. Докажите, что если грамматика G=<T,N,S,P> содержит правила P' (т.е. P'ÌP), то она неоднозначна.

P'={A®AA½a}

P'={A®AaA| a}

P'={A®aA½Ab| a}

P'={A®aA½aAb |a}

e)P'={A®Ab½aAb|}.

5. Определите, какие из следующих языков являются неоднозначными:

L1={anbmcmdn½n,m³1}U{ambmcndn½ n,m ³ 1},

L2={anbmckdmpn½n,m,k³1}I{ambmckdnpn ½n,m,k ³ 1},

L3={anbm½n,m³1, m ³ n}.

6. Построить КС-грамматику, порождающую заданный язык и привести пример дерева разбора в построенной грамматике:

a) (abc+   U ancccb2n+1  U (aba)+)* , n³ 0

b) ((acb)*ad+(a+ba)n+1cb3n+1  U (a*bc+)*)*  U a*b+ , n³ 0

c) (bc*  U (ad)ncb2n+1  U (ba*)+)* , n³ 0

d) (cca2n+2ab+(bc)n)* U (a*b+   U  (bc)kdda2k)+,n,k ³ 0