Kontekstivaba grammatika
Kontekstivaba grammatika on väga loomulik ja sõbralik viis hulkade spetsifitseerimiseks. Proovime siin mõned meile võib-olla juba tuttavate asjade jaoks grammatikad disainida.
Grammatika disain
Regulaaravaldise põhjal. Proovi kirjutada regulaaravaldis (a|b)*c kontekstivaba grammatikana. Loodetavasti saad üldistada. Proovi skitseerida algoritm, mis võtab sisendiks RegexNode ja trükib välja ekraanile grammatika.
Argumentide list. Kuidas spetsifitseerida komaga eraldatud sõnade list? Oletame, et meil on ainult üks sõna w, siis keel peaks olema järgmine {w, w, w, w, w, w, ...}. Kirjuta nii regulaaravaldis kui ka grammatika sellise keele jaoks. Kui oled defineerinud sellise keele, siis kasuta seda sama mitte-terminaali, et defineerida järgmine keel: {f(), f(w), f(w, w), f(w, w, w), ...}
Lausearvutuse valem. Järgnevad lõigud on võetud Rein Pranki raamatust "Sissejuhatus matemaatilisse loogikasse". Tõlgime antud kirjelduse kontekstivabaks grammatikaks.
Eeldades, et lausemuutujateks on meil X, Y ja Z, siis saame sõnu nagu näiteks (¬(X&Y)→(X∨Z)).
Kahendpuu. Oletame, et kahendpuu lehtedes on ainult arvud 0 ja 1, siis defineeri keel, kus on kõik võimalikud puud. Konstruktorite nimed on Leaf(int v) ja Node(Tree left, Tree right) ehk teiste sõnadega defineerime puude hulga järgmiselt:
- Arvudeks on meil 0 ja 1.
- Kui v on arv, siis Leaf(v) on puu.
- Kui l ja r on puud, siis Node(l,r) on samuti puu.
Keel sisaldab seega sõnu nagu Node(Leaf(1), Node(Leaf(0), Leaf(1)). Edasi modifitseeri oma grammatikat, et see defineeriks sellised puud, millel on väärtused sisetippudes, näiteks järgmine sõna Node(null, 1, Node(null, 0, null)).
- Arvudeks võtame endiselt 0 ja 1.
- Konstant null on pisike puu.
- Kui v on arv ning l ja r on puud, siis Node(l,v,r) on samuti puu.
Järjekordne puu ülesanne!
Kuna puu läbimine on meie lemmikteema, siis võiks igal võimalusel üritada seda harjutada. Proovime nüüd kirjutada rekursiivse algoritmi, mis väljastab regulaaravaldisega samaväärse grammatika. See võib meil olla väga rumal teisendus, mis iga alamavaldise jaoks loob uue mitteterminali. Näiteks on minu implementatsioonis regulaaravaldise (a|bc)* tulemuseks järgmine grammatika:
S → AS S → ε A → B A → C B → a C → DE D → b E → c