img143

143

10.3. Języki opisu obrazów (PDL) Shawa

Bez kontekstową gramatykę ©j, podklasy LL{ 1) generującą podane wzorce, konstruujemy w następujący sposób:

©» = (£*, Sr, 35. S).

gdzie:

produkcje generujące I:

(1)    S—*a+a (w przypadku gramatyki LL(1) w produkcjach nie uwzględniamy znacznika końca $),

produkcje generujące P:

(2)    S —» Si + S₂,

(3)    Sr - (S₈ * a),

(4)    S₂ - a,

(5) Sj-(6 + c),

produkcje generujące R: (2), (3), (5) oraz

(6)    S₂ —► (a x d), produkcje generujące D:

(7)    5 —► S₄ * S$,

(8)    S₄ — 6,

(9)    5_S - (S₆ + S?),

(10)    S₆ -(a + a),

(11)    S7 -* (~ c+ ~ a),

E* = {S,Si}, i= 1,2,...,7,

Er = {a,6,c,d,(,),+, x,*,~}.

Teraz, możemy zdefiniować automat 21, klasy LL{ 1) według następujących reguł:

21, =(Ei.,E',«,Z₀),

gdzie:

(1)    E^ :=Er,

(2)    E ;= Er U Es U {Zo},