Gramatici

Vom considera gramatici în care neterminalii sunt notați cu litere mari, și terminalii cu orice alte caractere. Gramatica e reprezentată ca un dicționar care asociază fiecărui neterminal lista producțiilor după care poate fi transformat; fiecare producție e reprezentată prin lista simbolurilor din partea dreaptă. Un neterminal are deci asociat o listă de șiruri (sau o listă de liste de caractere). În unele probleme vom considera simplificat gramatici cu o singură producție pentru fiecare neterminal.

1. Scrieți o funcție care fiind dat un neterminal produce lista tuturor șirurilor de simboluri în care se poate transforma neterminalul după ce se aplică n producții (oricare, în orice ordine). Gramatica e dată ca dicționar de la neterminale (caractere) la producții pentru acel neterminal (o listă de șiruri, câte un șir pentru fiecare producție).
Indicații Scrieți mai întâi o funcție care ia un șir de simboluri și returnează lista șirurilor în care se poate transforma, aplicând o singură regulă.
Următoarea funcție ajutătoare produce un șir în care caracterul de la indicele i din șirul s1 e înlocuit cu șirul s2. Indicii pornesc de la 0, la fel ca în C:

let replace s1 i s2 =
  let i1 = i + 1 in
  (String.sub s1 0 i) ^ s2 ^ (String.sub s1 i1 (String.length s1 - i1))

Scrieți apoi o funcție care adaugă la o listă de șiruri toate șirurile obținute înlocuind caracterul de la poziția i din șirul s cu fiecare din producțiile pe care dicționarul dict le conține pentru acel caracter (dacă caracterul nu e neterminal, funcția va returna aceeași listă).
În final, adaptați funcția fold din exemplul cu fractalul dragon pentru a aplica funcția de mai sus repetat pentru fiecare caracter dintr-un șir, acumulând șirurile rezultate într-o listă.

2. Scrieți o funcție care calculează pentru fiecare neterminal mulțimea tuturor simbolurilor terminale cu care poate începe o derivare a acelui neterminal.
Indicație Lucrați cu un dicționar de la neterminale (caractere) la mulțimi de terminale (caractere) cu care poate începe o derivare a neterminalului. Creați inițial (cu funcția map din modulul Map) un dicționar care conține pentru fiecare neterminal mulțimea vidă de caractere.
Scrieți apoi o funcție care, pornind de la un astfel de dicționar produce un dicționar actualizat, adăugând pentru fiecare producție a unui neterminal mulțimea simbolurilor cu care poate începe o derivare a acelei producții (terminalul, respectiv mulțimea deja calculată pentru neterminal). Folosiți funcția mapi din modulul Map: astfel, puteți scrie o funcție de transformare care are acces atât la valoarea din dicționar (mulțimea curentă) cât și la cheie (și prin intermediul ei, la mulțimea producțiilor pentru neterminal).
Aplicați funcția repetat până ajungeți la un punct fix (rezultatul nu mai diferă de argument). Determinați egalitatea cu funcția equal din modulul Map, dând ca funcție de comparare equal din modulul Set.
De exemplu, pentru gramatica S → A | cB ; A → aS | B ; B → bB | ε, inițializăm S ; → ∅ ; A → ∅ ; B → ∅ . În primul pas, obținem: S → { c }; A → { a } ; B → { b }. În al doilea pas, avem: S → { a, c } ; A → { a, b } ; B → { b } . În pasul trei, avem: S → { a, b, c } ; A → { a, b } ; B → { b }, apoi mulțimile nu se mai modifică.

3. O expresie se poate scrie în formă postfix, de exemplu 3 2 + 5 - (adică (3 + 2) - 5) sau 3 2 5 + -, adică 3 - (2 + 5), după gramatica:

Expr ::= numar Rest
Rest ::= ε | Expr op Rest

Scrieți o funcție care citește de la intrare o expresie în formă postfix cu operanzi întregi și returnează valoarea ei.

4. 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. Scrieți o funcție care citește un termen definit după următoarea gramatică:

Term ::= nume | nume ( Term RestTerm )
RestTerm ::= ε | , Term RestTerm

6. Un tip de gramatici sunt L-sistemele, cu care se pot descrie fractali. Alegeți unul din exemplele date și scrieți un program care dezvoltă de n ori simbolul inițial pentru a desena fractalul, ca în exemplul cu dragonul.

7. Modificați programul de la exercițiul anterior pentru a genera recursiv direct șirul de comenzi de desenare, fără a mai construi explicit n expandari succesive ale șirului de simboluri (ne)terminale.

Marius Minea

Last modified: Wed Dec 16 10:00:00 EET 2015