IMAGE2

1/ IS

Automaty i Gramatyki Egzamin poprawkowy 3009/2010

Y - 7 M:    f\

_L /V- /r,£    M ^u

pT 1 Czy następująca gramatyka jest jednoznaczna? 5 —* aSb I 566 I e

i t}p't | !*■ vl*ł lty;f prsttA paciane wzorce od (Im ii:i |i< ti-ltM. i >j> 11 (w śmiele zawierania

Itńł tfrrW

a) *

(»)    rt‘6* | 6*ti*

f) « i b d) (r I (I I 6)⁴

*») («&j)t    I p

li /O t’c i ^:"ił i HB »)0[

nnhiitmly »hnl)< tniw do wzorców oplsują-t yfh jsfa a(flrfrtohlim przez nie jeżyki.

o56 | 566 |

( 1 »I7\71 Czy w następującej gramatyce można wyprowadzić słowo aabd? S —> aaS | 566 | 6

m E3 ^c*y w następującej gramatyce można wyprowadzić puste słowo? 5 —+ 55 | o56 | 6

\ * 1T 1 Czy język generowany przez następującą gramatykę jest skończony? 5 —* bSa | 565 | a

C /) ^[yV| Czy następująca gramatyka generuje pusty język? 5 —* a56 | 6

‘W*

TT

P_

2E

-C; // 4. j Automaty stosowe rozpoznają języki bezkontekstowe.

|    | *7" | Dopełnienie języka regularnego jest języ

kiem regularnym.

/l \A/\ Każdy język    kontekstowy jest

b ezkontekstowy.

	-M	ra
o^4 I 6^+		B2)
(aa I 66)*
b*ab*ab*	M ^5*	m

zykiem bezkontekstowym. Każdy język bezkontekst lamy.

(aa)* a

(a j b(aa)*ab)*

-/

X⁴*

u*

wszystkim dopasować jak najdłuższy lleksem.

Jeśli gramatyka bezkontekstowa jest jednoznaczna, to nie występuje w niej lewostronna rekurąja.

i l^t | Determinizacja automatu skończonego może spowodować wykładniczą eksplozję liczby stanów.

-f o +\/[/\ Automat stosowy w każdym kroku wczytuje dokładnie jeden znak.

Żeton reprezentuje parę: leksem, atrybut.

F I

3

	M	K	Ig
4, P	t#	Af	m
	/y t * Cy Ol,U	11	1
		1|	SI

A 1 6.    | ~f~ | W parserach LL(1) drzewo wyprowadze

nia jest odtwarzane od korzenia do liści. -£ f 1/1/1 Parsery LR(1) obchodzą drzewo wyprowadzenia w porządku prefiksowym.

|~P J Analizator składniowy generowany przez Yacc’a/Bison’a to rodzaj deterministycznego automatu stosowego.

| j Konstrukcja parsera LR(1) nie może się udać dla gramatyki niejednoznacznej. Yacc i Bison implementują mechanizm atrybutów dziedziczonych.

-f IV

?nin/n9/i7 i/i./n