Програмски преводиоци 1/К1 2012

Prvi kolokvijum 2012. godine održan je 26. oktobra i trajao je 1.5 sat. Postavka roka dostupna je sa stranice predmeta.

1. zadatak

Postavka

Robot se kreće po pravougaonoj rešetki. Može da ide napred (f), skrene levo (l), ili skrene desno (r).

1. Konstruisati konačni automat koji opisuje one i samo one sekvence pokreta koje robota dovode u isti pravac i smer kretanja kao i na početku.
2. Konstruisati bezkontekstnu gramatiku koja opisuje isti skup sekvenci kao i pod a).

Rešenje

Deterministički konačni automat u stavci pod a

	f	l	r	Prihvata
N	N	W	E	1
W	W	S	N	0
E	E	N	S	0
S	S	E	W	0

Bezkontekstna gramatika je:

• <N> → ε
• <N> → f <N>
• <N> → l <W>
• <N> → r <E>
• <W> → f <W>
• <W> → l <S>
• <W> → r <N>
• <E> → f <E>
• <E> → l <N>
• <E> → r <S>
• <S> → f <S>
• <S> → l <E>
• <S> → r <W>

2. zadatak

Postavka

Napisati regularni izraz kojim se opisuju sve sekvence koje:

• počinju jednim ili više malih slova engleske abecede, nakon kojih se pojavljuje
  • ili nula ili više znakova iz skupa cifara od 5 do 9 i velikih slova engleske abecede (poređanih u proizvoljnom redosledu, tj. mešaju se slova i cifre).
  • ili se pojavljuje jedan ili više brojeva iz opsega od 0 do 4.

Rešenje

[a-z]+([5-9A-Z]*|[0-4]+)

3. zadatak

Postavka

Napisati gramatiku kojom se definišu pravila formiranja izraza u hipotetičkom programskom jeziku. Postoje dva binarna operatora: operator "$" i operator "#". Operator "$" je levo asocijativan i ima veći prioritet od operatora "#", koji je desno asocijativan. Izrazi se sastoje od identifikatora (IDENT) i konstanti (CONST) između kojih se navode dati operatori. Binarni operator se piše između svoja dva operanda. IDENT i CONST su terminalni simboli. Gramatika ne sme biti višeznačna.

Primer izraza: a$2$3 # b$3 # c

Rešenje

• <expr> → <dollar_expr> # <expr>
• <expr> → <dollar_expr>
• <dollar_expr> → <dollar_expr> $ <term>
• <dollar_expr> → <term>
• <term> → <IDENT>
• <term> → <CONST>

4. zadatak

Postavka

Na osnovu zadate gramatike konstruisati LR(0) parser. Nacrtati LR(0) karakteristični automat (prepoznavač ručki), nacrtati potisnu i kontrolnu tabelu.

• <S> → (<A>)
• <A> → <S>, b
• <A> → a

Prikazati rad parsera kada se na ulaz dovede sledeća ulazna sekvenca: ((a),b)

Rešenje

Potisna tabela

Stanje	<S>	─┤	(	<A>	)	,	b	a
∇	<S>0		(1
<S>0		─┤0
─┤0
(1	<S>2		(1	<A>1				a3
<A>1					)1
)1
<S>2						,2
,2							b2
b2
a3

Kontrolna tabela

Stanje	Akcija
∇	SHIFT
<S>0	SHIFT
─┤0	ACCEPT
(1	SHIFT
<A>1	SHIFT
)1	REDUCE(1)
<S>2	SHIFT
,2	SHIFT
b2	REDUCE(2)
a3	REDUCE(3)