img193

D3. Podstawowe pojęcia teorii języków formalnych i automatów 193

t) -i-> 7 oznacza wyprowadzenie w gramatyce 0, tzn. istnieje taki ciąg

170, m.....Vk, że % = y, r)_t - 7 oraz r)i —* »7<+i 6 P dla i = 0,1,..., k-1.

Oczywiście ——► jest zwrotnym przechodnim domknięciem —► .

Językiem generowanym przez gramatykę 0 nazywamy zbiór L(0) = {7 | 7 e Ey taki,że 5—*7}.

Zdefiniujmy teraz dogodną do analizy syntaktycznej podklasę gramatyk bezkontekstowych.

Dla A 6 Ew: first(A) = {a € E | A 7, 7 € £⁺ oraz 7 = ar)}. Tak więc, zbiór first dla nieterminala A zawiera wszystkie symbole, jakie mogą pojawić się na jego pozycji. Przykładowo, jeśli w gramatyce występują produkcje: A —* aB, A —► Cb, C —* eEa, to a, £7, e 6 firsi(A).

Niech 77 —> 7 będzie bezpośrednim krokiem wyprowadzającym w gramatyce bezkontekstowej takim, że

77 = 771.4772, 7 = »?i T-772 i A—>reP.

Jeśli 777 6 Ef, to krok wyprowadzający nazywamy lewostronną kanoniczną generacją i oznaczamy 77 —* 7. Zwrotne i przechodnie domknięcie —£* nazywamy lewostronnym wyprowadzeniem i oznaczamy —j~*. Innymi słowy, lewostronnym wyprowadzeniem nazywamy takie wyprowadzenie, gdzie w każdym kroku produkcję stosujemy dla najbardziej lewego nieterminala.

Bezkontekstową gramatykę 0 nazywamy gramatyką klasy LL( 1) [22], [23], jeśli spełnione są dwa następujące warunki:

1) gramatyka nie zawiera produkcji o postaci A —* Af, A G Ejv<,

7€S*.

2) jeśli istnieją dwa wyprowadzenia:

S -j-71^72 -^71 <^72 -77*71 f)i.

5 -77*71 ^72 -j* 7i ^r72 -77* 7i <?2 oraz zachodzi first(r)i) = first(r)?), to a = r.