Gramatici

Temă pentru laborator

1. Scrieți o gramatică care generează toate șirurile de 0 și 1 care nu au doi de 1 consecutiv.

Probleme propuse

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 liste de caractere.

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

2. Scrieți o funcție care calculează mulțimea tuturor simbolurilor terminale cu care poate începe fiecare neterminal. Porniți de la mulțimea vidă pentru fiecare simbol, și actualizați, parcurgând fiecare producție, până ajungeți la un punct fix (nu mai obțineți nicio modificare).

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. 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 (vezi și exemplele de la primul curs).


Marius Minea
Last modified: Mon Dec 9 20:25:00 EET 2013