Kontekstivaba grammatika
Kontekstivaba grammatika on väga loomulik ja sõbralik viis hulkade spetsifitseerimiseks. Proovime siin mõned meile võib-olla juba tuttavad asjade jaoks grammatikaid 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 sellesama mitte-terminaali, et defineerida järgmist keelt: {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 kirjeldus 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 keelt, 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 grammatika, et defineeriks selliseid puud, mille väärtused on sisetipudes, 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 rekursiivne algoritm, 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