1. Arbori de derivare.
Pentru gramatica de șiruri de paranteze echilibrate de la curs, desenați arbori de derivare pentru toate șirurile de lungime 6 (trei perechi de paranteze).
Puteți găsi o relație de recurență pentru numărul șirurilor cu n perechi de paranteze ?
2. Scrierea de gramatici
Definiți o gramatică care descrie valori de tip listă în ML (scrise cu paranteze drepte și punct-virgulă). Folosiți un terminal elt pentru elementele listei.
Definiți apoi o gramatică care permite și folosirea lui :: pentru a compune valori de tip listă.
3. Gramatici pentru expresii
Simplificați gramatica pentru expresii aritmetice de la curs, considerând doar adunarea și înmulțirea, și fără paranteze (cazul general e o sumă de produse).
Încercați să scrieți un program care citește o astfel de expresie de la intrare și îi returnează valoarea.
4. Prioritatea operatorilor
În C, operatorii relaționali <, <=, >, >= au precedență mai mare decât operatori de comparație ==
și !=. Toți acești operatori sunt asociativi la stânga.
Scrieți o gramatică neambiguă pentru expresiile formate pornind de la numere ca terminali și folosind doar operatorii amintiți (fără paranteze).
Gramatica poate fi și recursivă la stânga.
E adevărat că 3 == 3 == 3 > 2 > 1 == 1 ?
5. Fractali și L-sisteme. Un tip de gramatici sunt L-sistemele, cu care se pot descrie fractali. Studiați unul din exemplele date pentru a înțelege acest mod de descriere.