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. Allpool on RegexGrammar ülesanne, kus peaks implementeerima algoritmi, mis võtab sisendiks RegexNode ja trükib välja vastava 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-terminali, 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)).
Kahendpuu variatsioon. 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.
RegexGrammar
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 olla väga rumal teisendus, mis iga alamavaldise jaoks loob uue mitteterminali. Näiteks meie implementatsioonis on regulaaravaldise (a|bc)* tulemuseks järgmine grammatika:
S → AS S → ε A → B A → C B → a C → DE D → b E → c
Ülesande saab lahendada RegexGrammar klassis, aga sellel teste ei ole. Kontrolli lihtsalt, et main meetodi tulemus oleks õige (ülaloleva grammatikaga samaväärne).