sunnuntai 19. lokakuuta 2008

PEG - kielioppi

Minulla on ensimmäisen vaiheen toteutus hyvässä (rauhallisessa) vauhdissa. Ihan maistiaisiksi esittelen raakile-kieliopin lojban-teksteille. Näen jo, että siinä on puutteita ainakin tiettyjen "terminaattoritapausten" tunnistamisessa. Mutta haluan täydentää ja päivittää sitä iteratiivisesti, koska sen koko kasvaa joka tapauksessa ainakin viisikertaiseksi, ennen kuin se tukee "koko lojban-kieltä". Täydelliseen PEG (Parsing Expression Grammar) -kielioppiin verrattuna on huomioitava, että tämä kielioppi ei etene merkkitasolle asti, vaan teen "tokenizing"-operaation ensin, eli erittelen bridin sanat toisistaan. Lisäksi käytän erikoisfunktiota esim. tunnistamaan gismut.

Toinen kielioppi on edellisen kieliopin "metakielioppi", jonka avulla luen ohjelmallisesti ajonaikaisesti tuon lojban-kieliopin ja alustan "sääntöoliot" metakieliopin suorittaman parsimisen tuloksena. Metakielioppi sen sijaan on C++ -tasolla "kovakoodattu"


//
// PEG Grammar for a small subset of lojban language
//
// V.0.1
//
// ========= Notation =========
//
// [Symbol] := [Rule]
// &( ) and predicate
// !( ) not predicate
// ( )+ one or more
// ( )* zero or more
// ( )? zero or one
// E1 | E2 ordered choice
// E1 E2 sequence
//
//

// High level syntax

EBridi := (EBridiStart)? EBridiBody (EConnBridi)* // multiple connected bridi
EBridiStart := ".i" | "ni'o" // bridi start cmavo
EConnBridi := EBridiConnective EBridiBody // connected extension
EBridiConnective := ".ije" | "ri'a" | "ki'i" // bridi connectors
EBridiBody := (EBridiComp)+ // multiple
EBridiComp := ESumtiComp | ESelbriComp // Sumti- or selbri-phrase

// Selbri syntax

ESelbriComp := ("cu")? (ESpatiTempAttr)? (EConversCmavo)? EBrivla
EConversCmavo := "se" | "te" | "ve" | "xe"

// Sumti syntax

ESumtiComp := ESumtiPhrase | ESumtiTcita
ESumtiPhrase := ESingleSumtiPhr (EConnectedSumti)?
EConnectedSumti := ESumtiConnective ESingleSumtiPhr
ESumtiConnective := ".e" | ".a" | "joi" | "ce" | "ce'o"
ESingleSumtiPhr := (ESpatiTempAttr)? (ESumtiObject) (EIndirectDescrip)?
ESpatiTempAttr := "mu'o" | "ca" | "pu" | "ba" | "vi" | "va" | "vu" | "ga'u" | "ni'a" | "ca'u" | "ti'a"
ESumtiObject := EProSumti | ENamePhrase | ESelbriPlace | EAbstraction
EProSumti := "ko'i" | "ko'a" | "ko'e" | "fo'a" | "ri"
ENamePhrase := "la" EName (EProSumAssign)?
ESelbriPlace := (EPlaceTag)? EBrivlaEpress (EProSumAssign)?
EBrivlaEpress := EArticle EBrivla
EPlaceTag := "fa" | "fe" | "fi" | "fo" | "fu"
EArticle := "lo" | "le" | "lo'i" | "lei" | "le'i"
EBrivla := EGismu | ELujvo
EProSumAssign := "goi" EProSumti
EAbstraction := EArticlAbstract EAbstrPhrase
EArticlAbstract := "lenu" | "lonu"
EAbstrPhrase := EBrivla | EBridiBody
EIndirectDescrip := EAssosiation | ERelativeClause
EAssosiation := EAssosCmavo ESingleSumtiPhr
EAssosCmavo := "pe" | "po" | "po'e" | "po'u" | "ne" | "no'u"
ESumtiTcita := ESpatiTempAttr ESpatiTempExpr
ESpatiTempExpr := EAbstraction | EBrivlaEpress
ENamePhrase := ExplicitFunction_N
EGismu := ExplicitFunction_G
ELujvo := ExplicitFunction_L




//
// PEG Grammar for the PEG Grammar syntax
// "a meta grammar"
//
// V.0.1
//
// ========= Notation =========
//
// [Symbol] := [Rule]
// &( ) and predicate
// !( ) not predicate
// ( )+ one or more
// ( )* zero or more
// ( )? zero or one
// E1 | E2 ordered choice
// E1 E2 sequence
//
//

EGrammarLine := ECommentLine | ERuleClause
ECommentLine := "//" ECommentText
ERuleClause := ESymbol ":=" ERule (ECommentLine)?
ERule := ESequence | EChoice
ESequence := (ESequenceTerm)+
EChoice := EChoiceTerm EMoreChoice
ESequenceTerm := ESimppelTerm | EOperatorTerm
ESimppelTerm := ESymbol | ETerminal
EOperatorTerm := EZOne | EZMore | EOneMore | ENot | EAnd
EZOne := "(" ESimppelTerm ")?"
EZMore := "(" ESimppelTerm ")*"
EOneMore := "(" ESimppelTerm ")+"
ENot := "!(" ESimppelTerm ")"
EAnd := "&(" ESimppelTerm ")"
ESymbol := ExplicitFunction_S
ETerminal := ExplicitFunction_T

2 kommenttia:

JuSa kirjoitti...

PEG - jäsentelijä

Lyhyesti kerrottuna PEG-parseri on melko uusi keksintö. Se Top-Down -parseri. Tutkittavaa lausetta tai ilmaisua aletaan analysoida, ei ensimmisestä merkistä, vaan sen koko rakenteesta alkaen, tunkeutuen yhä syvemmälle. Esitetyistä esimerkeistä näkee, että käytetty symboli määrillään aina alempana. Haarautumiset tapahtuvat vain "ordered choice" tyyppisissä säännöissä, jossa valitaan yksi esitetysistä vaihoehdoista. Jos tarkempi analyysi osoittaa sen vääräksi, palataan takaisin ja koitetaan toista. PEG sopii paljon paremmin lojban -brinin jäsentelyyn kuin esimerkiksi C++-lähdetiedoston analysointiin, koska yksi bridi on aina kohtuullisen lyhyt lause.

PEG:istä löytyy helposti lisää guuglaamalla.

Anonyymi kirjoitti...

Parhaat keksinnöt ovat yksinkertaisia. PEG-kielioppi ei varmaan ole kaukana ihmisajattelun luontaisesta hierarkisesta hahmosta, mutta on helposti luettavissa.

Lähes samanlaisen hahmorakenteen voisi kuvata XML-Schemallakin, koska siinä on Regular Expression -tarkastus. Tietysti pitäisi olla erillinen ohjelma joka parsii tekstin tai muuttaa kieliopin tähän PEG-muotoon.