Vi presenterar en ny metod för kontextfri grammatiktolkning som bygger på att generera en sekvens av grammatiker som kallas härledda grammatiker från en given sammanhangsfri grammatik och ingångssträng. Generationen av de härledda grammatikerna beskrivs av några enkla inferens regler. Vi presenterar en O(n 2 ) utrymme och O(n 3 ) tidsigenkänning algoritm, som kan utökas för att generera parse träd i O(n 3 ) tid och O(n 2 log n) utrymme. Derivativ grammatik kan ses som ett symboliskt tillvägagångssätt för att genomföra begreppet härledda språk, som introducerades av Brzozowski. Might och andra har utforskat ett operativt tillvägagångssätt för att implementera derivatspråk där den kontextfria grammatiken kodas som en samling rekursiva algebraiska datatyper i ett funktionellt språk som Haskell. Funktionell språkimplementering funktioner som knutbindning och lat utvärdering utnyttjas för att säkerställa att tolkning görs korrekt och effektivt trots komplikationer som vänster-recursion. Däremot kan vårt symboliska tillvägagångssätt med hjälp av inferensregler enkelt genomföras i vilket programmeringsspråk som helst och vi får bättre utrymme för tolkning. Reifiera härledda språk genom att koda dem symboliskt som grammatik gör det också möjligt att göra formella anslutningar för första gången mellan derivat tillvägagångssätt och klassiska tolkningsmetoder som Earley och LL / LR parsers. I synnerhet visar vi att de uppsättningar av Earley objekt som underhålls av Earley perser implicit koda derivat grammatiker och vi ger ett förfarande för att producera derivat grammatiker från dessa uppsättningar. Omvänt visar vi att vår Grammatikkännare kan omvandlas till Earley-kännaren genom att optimera en del av dess bokföring. Dessa resultat tyder på att härledda grammatiker kan ge en ny grund för sammanhangsfri grammatikigenkänning och tolkning. Med tanke på en grammatik och sträng w = t 1 t 2... t n, Vi konstruerar en sekvens av härledda grammatiker â t 1, â t 1 t 2,...................................................................................... , t 1... t n som genererar språk D t 1 (L), D t 1 t 2 (L),................................................................................... .., D t 1...t n (L). Strängen w är i L om och endast om ε kan härledas från startsymbolen S w i â w = â t 1 t 2... t n. Detta tillvägagångssätt, som ändrar derivatspråk genom att representera dem symboliskt med grammatik snarare än att koda dem som algebraiska datatyper inom ett program, är fördelaktigt eftersom det inte kräver språkfunktioner som knutbindning och lat utvärdering, och kan enkelt implementeras i alla språk. En baslinje implementering av detta tillvägagångssätt, som kallas den beskurna derivata grammatik (PrDA) algoritm, tillåter igenkänning i O(n 3 ) tid och O(n 2 ) utrymme, samma komplexitet som Earley, CYK och PWD. (2) (Avsnitt 4) Vi visar att denna igenkännare kan utökas till en parser som kräver O(n 3 ) tid och O(n 2 log n) utrymme, förbättra tidigare resultat på PWD [Adams et al. År 2016 ]. (3) (Avsnitt 5) Även om PWD har studerats i flera år har dess koppling till klassiska tolkningsalgoritmer som Earley eller LL/LR förblivit ett mysterium. Thiemann har nyligen infört ett intressant begrepp som kallas partiella derivat för att konstruera icke-deterministiska pushdown automata (NPDA) från μ-regelbundna uttryck [Thiemann 2017]. Det finns dock inget direkt sätt att få en tolkningsalgoritm från en NPDA (man kan konvertera NPDA tillbaka till en CFG och använda Earley eller CYK men i så fall, NPDA behövs inte), så kopplingen mellan PWD och klassiska tolkningsalgoritmer har förblivit oklar. I den här artikeln etablerar vi direkta och formella kopplingar mellan härledda grammatiker och klassiska tolkningsalgoritmer som Earleyalgoritm. I synnerhet visar vi att de uppsättningar av Earley objekt som underhålls av Earley igenkänning implicit koda derivat grammatiker och ge ett förfarande för att producera derivat grammatiker från Earley uppsättningar. Omvänt visar vi att PrDA-igenkänningen kan omvandlas till Earley-igenkänningen i tre steg, som var och en är bevisligen korrekt. Detta etablerar en formell relation mellan Earley igenkännaren och derivatansatsen för första gången. Dessa resultat innebär inte att Earley-igenkänningen är densamma som PrDA-igenkänningen; snarare, de föreslår att derivata grammatiker kan ge en ny grund för CFG-igenkänningsalgoritmer i den meningen att algoritmer som Earley, LL/LR och PWD kan erhållas som optimerade implementationer av baslinjederivatet grammatik som införs i detta papper.
Henriksen m.fl. REF visar en tolkningsteknik baserad på derivat för kontextfri grammatik.
Derivative grammars: a symbolic approach to parsing with derivatives
{'venue': 'PACMPL', 'journal': None, 'mag_field_of_study': ['Computer Science']}