rolisz's site

Subiecte LFTC

În 2014, cu doamna profesor Dana Lupșa:

Exemplu examen:

(3p) Dati o g.i.c (forma sim­pli­fi­ca­ta) care descrie sintaxa instr. if. a.i.

if a\>b then max:=a else max:=b

este un cuvant al gramaticii.

a) atributati gramatica:

b) dati arborele de derivare

c) descrieti evaluarea atribu­tu­lui 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? (Jus­ti­fi­cati a) Demon­strati 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?

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:

Foaia de ajutor:

Rezolvare:

Pentru subiectul postat săptămâna trecută:

1.

<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)

  1. $ L_1 = { b^{2n} | n \in \mathbb{N} * } $

2014-01-23_22h36_37

$$ L_2 = { b^{3n} | n \in \mathbb{N} * } $$

2014-01-23_22h37_58

$$ L_1 \cup L_2 = { b^{2n} | n \in \mathbb{N} * } \cup { b^{3n} | n \in \mathbb{N} } $$

2014-01-23_22h56_52 3. $ L = { a^n b^n c^n | n \in \mathbb{N} } $

a) nu este limbaj regular pentru că nu este nici limbaj in­de­pen­dent de context. b) nu este limbaj in­de­pen­dent de context pentru că.

  1. Item set-urile de LR(0):

lr0-automaton

LR(0) Table
$ 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)

Pentru că nu sunt conflicte, gramatica este LR(0), deci este și în LR(1).

Bine că există toolul acesta. Spared me a loooot of work.

Subiect grupa 235:

  1. Dați câte o reprezentare în cod in­ter­me­di­ar cu trei adrese, reprezentare cvadruple și reprezentare triplete, pentru următoarea expresie:

$$ A:=(B+C)*D $$

  1. Fie limbajul:

$$ L = { a^n | n \in \mathbb{N} \text{, n - patrat perfect} } $$

Este regular? Demon­strați.

  1. 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.)

  1. Fie gramatica cu regulile de producție:

$$ S \rightar­row a S_1 b S | a S | i $$

$$ S_1 \rightar­row a S_1 b S_1 | i $$

Este de tip LR(1)?