Gramatici

1. Palindrom Fie următoarea gramatică: S ::= . | aSa | bSb | zSz
Scrieți un program (în C sau ML) care determină dacă caracterele care apar în intrare (până la linie nouă) formează un șir generat de gramatică sau nu.
În ML apelul input_char stdin returnează un caracter citit de la intrare (sau generează excepția End_of_file; în acest exercițiu nu se cere s-o tratăm).

2. Litere mari și mici Fie următoarea gramatică: S ::= ε | ASa | BSb | ... | ZSz
Scrieți un program (în C sau ML) care determină dacă caracterele care apar în intrare (până la linie nouă) formează un șir generat de gramatică sau nu.
Indicație: Scrieți o funcție care are ca parametru caracterul citit (apelată dacă acesta e majusculă).

3. Enumerarea șirurilor Putem asocia fiecărui șir s de paranteze echilibrate un număr N(s) în felul următor: N(ε) = 0, N( (S1)S2 ) = 2N(S1) (2 N(S2)+1)
a) Demonstrați că funcția N e o bijecție
b) Scrieți o funcție care citește de la intrare un șir de paranteze echilibrate și returnează numărul său (sau -1 în caz de eroare).
c) Scrieți o funcție care ia ca parametru un număr nenegativ și tipărește șirul de paranteze echilibrate asociat cu numărul respectiv.

4. Din prefix în postfix Scrieți o funcție care citește o expresie aritmetică în format prefix și o tipărește în format postfix. Puteți modifica funcția de la curs.

5. Expresie postfix Gramatica pentru o expresie postfix: Expr ::= num | Expr Expr op poate fi rescrisă astfel:
 Expr ::= num RestE
 RestE ::= ε | Expr op RestE
Scrieți o funcție care citește de la intrare o expresie în formă postfix cu operanzi întregi și returnează valoarea ei.
Indicații: Remarcăm că dacă există RestE, începe cu o expresie, deci cu un număr. Derivarea (și prelucrarea) pentru RestE continuă deci atât timp cât în intrare apare o cifră (începutul unui număr); altfel, caracterul e pus înapoi și returnăm valoarea calculată.
De exemplu, pentru expresia 3 2 + 11 9 - *, calculul va decurge astfel:
Expr → 3 RestE →[apare cifră]→ 3 Expr1 op RestE → ... (apel recursiv)
  Expr1 → 2 RestE →[nu apare cifră] → 2
(revenire) 3 Expr1 op RestE → 3 2 + RestE →[calcul]→ 5 RestE →[apare cifră]→ 5 Expr2 op RestE → ... (apel recursiv)
  Expr2 → ... → 11 9 − →[calcul]→ 2
(revenire) 5 Expr2 op RestE → 5 2 * RestE →[calcul]→ 10 RestE →[nu apare cifră]→ 10

Gramatici reprezentate cu dicționare

Dicționarele sunt o reprezentare naturală pentru gramatici.
Partea dreaptă a unei reguli e un șir de simboluri (o listă de simboluri; sau dacă simbolurile sunt caractere, un șir de caractere).
Fiecare neterminal va fi o cheie în dicționar și e asociat cu o listă de reguli (listă de liste, sau listă de șiruri).
De exemplu: 'E' → ["n"; "E+E"; "E*E" ] sau 'E' → [ ['n']; ['E';'+';'E']; ['E'; '*'; 'E'] ]
Un terminal nu se transformă mai departe, deci nu e cheie în dicționar.

6 Transformă un șir Scrieți o funcție care un dicționar reprezentând o gramatică și un șir de simboluri și returnează lista (sau mulțimea) tuturor șirurilor care se pot obține din șirul dat aplicând o singură regulă de producție din gramatică (înlocuind un singur neterminal).

7 Transformări succesive. Fie o gramatică cu câte o singură regulă pentru fiecare neterminal, reprezentată ca dicționar (un neterminal e asociat cu un șir de simboluri).
a) Scrieți o funcție care ia ca parametru dicționarul gramaticii și un șir și tipărește șirul obținut înlocuind fiecare neterminal din șir după regula din gramatică.
b) Scrieți apoi o funcție similară cu un parametru suplimentar k care tipărește șirul obținut după k transformări succesive (de la punctul a) aplicate șirului.

Marius Minea
Last modified: Sat Dec 9 19:20:00 EET 2017