În 2014, cu doamna profesor Dana Lupșa:
Exemplu examen:
(3p) Dati o g.i.c (forma simplificata) care descrie sintaxa instr. if. a.i.
if a>b then max:=a else max:=b
este un cuvant al gramaticii.
a) atributati gramatica:
introduceti (cel putin) atributul cod
cod - cod intermediar cu 3 adrese, reprez cvadruple
b) dati arborele de derivare
c) descrieti evaluarea atributului cod pentru exemplul dat
(2p) 2. Se cere sa se scrie cate un AF care accepta:
$$ L1 = { b^{2n} | n \in \mathbb{N} * } $$
$$ L2 = { b^{3n} | n \in \mathbb{N} * } $$
Apoi un AF care accepta $ L1 \cup L2 $.
(2p) 3. Fie $ L = {a^n b^n c^n | n \in N } $
a) Este L - limbaj regular? b) Dar i.c? (Justificati a) Demonstrati b))
(2p) 4. Fie gramatica cu regulile de productie:
S -> a S b S | c
Este de tip LR(1)?
Timp de ore: 2h.
Ce poate sa apara pe biletul de examen?
probleme de tipul celor la seminar
probleme de tipul celor de la curs.
Teorie (max 1Pct)
Exemple simple aplicative pentru definitii (teorie): definitii si/sau exemple
Combinatii (aplicatii de teorie)
Sigur se da le ex. scris:
Fiecare subiect va contine: 1 problema de analiza sintactica (2 sau 3 puncte)
Nu se da la ex. scris:
lex/flex/yacc/bison
nu se da nimic cu ASM
determinare AF determinist cu numar minim de stari
de scris definitii/algoritmi (ci doar de folosit/aplicat: daca ii scriem - doar pentru a justifica aplicarea lor)
Foaia de ajutor:
coala A4
ambele fete ale unei foi de hartie
scrisa de mana (personala)
scrieti numele, grupa, data pe foaie
va fi predata impreuna cu lucrarea
Rezolvare:
Pentru subiectul postat săptămâna trecută:
<instr_if> -> if then else
-> id > id
-> id := id
a)
-> id1 > id2
.varn .cod | id1.varn | id2.varn | .varn |
-> id1 := id2
.cod -> if then else
<instr_if>.et_else .et_after .cod .cod() || | g= | .varn | false | .et_else |
|| <instr_atrib>1.cod || | goto | | | <instr_if>.et_after |
|| <instr_if>.et_else || 2.cod || <instr_if>.et_after
b) Îi un arbore, doar că sub fiecare nod intern îi o căsuță cu atributele lui. c) E o gramatică S-atributată, deci evaluarea se poate face de jos în sus. Se începe de la frunze și se propagă valorile atributelor în sus către părinți, ai căror atribute depind doar de atributele copiilor lor. (cred)
$ L_1 = { b^{2n} | n \in \mathbb{N} * } $
$$ L_2 = { b^{3n} | n \in \mathbb{N} * } $$
$$ L_1 \cup L_2 = { b^{2n} | n \in \mathbb{N} * } \cup { b^{3n} | n \in \mathbb{N} } $$
a) nu este limbaj regular pentru că nu este nici limbaj independent de context. b) nu este limbaj independent de context pentru că.
- Item set-urile de LR(0):
| $ | c | b | a | S | |
|---|---|---|---|---|---|
| 0 | s3 | s2 | s1 | ||
| 1 | acc | acc | acc | acc | |
| 2 | s3 | s2 | s4 | ||
| 3 | r(S → c) | r(S → c) | r(S → c) | r(S → c) | |
| 4 | s5 | ||||
| 5 | s3 | s2 | s6 | ||
| 6 | r(S → a S b S) | r(S → a S b S) | r(S → a S b S) | r(S → a S b S) |
Bine că există
toolul acesta.
Spared me a loooot of work.
Subiect grupa 235:
- Dați câte o reprezentare în cod intermediar cu trei adrese,
reprezentare cvadruple și reprezentare triplete, pentru următoarea
expresie:
$$ A:=(B+C)*D $$
- Fie limbajul:
$$ L = { a^n | n \in \mathbb{N} \text{, n - patrat perfect} } $$
Este regular? Demonstrați.
- Dați un APD care acceptă limbajul:
$$ L = {w w^{sim}| w \in({a,b}*)} $$
(Puteți da o g.i.c și apoi să construiți APD echivalent aplicând
algoritmul de trecere.)
- Fie gramatica cu regulile de producție:
$$ S \rightarrow a S_1 b S | a S | i $$
$$ S_1 \rightarrow a S_1 b S_1 | i $$
Este de tip LR(1)?