Grammatik som analyserar ett uttryck

En expression-parsing grammatik (PB-grammatik) är en typ av analytisk formell grammatik som beskriver ett formellt språk i termer av en uppsättning regler för att känna igen språksträngar. En grammatik som analyserar ett uttryck är i huvudsak en rekursiv descent -parser i en rent schematisk form som endast uttrycker syntaxen och är oberoende av den speciella implementeringen eller användningen av parsern. Uttrycksanalyserande grammatiker liknar reguljära uttryck och kontextfria grammatiker (CFG) i Backus-Naur-notation , men har en annan tolkning.

Till skillnad från COP-grammatik kan PB-grammatik inte vara tvetydig : om en sträng tolkas, så finns det exakt ett analysträd. Detta gör RE-grammatik lämpliga för datorspråk, men inte för naturliga.

Definition

Formellt består grammatiken som analyserar ett uttryck av:

Varje slutledningsregel från P har formen A ← e, där A är en icke-terminal symbol och e är ett analysuttryck. Ett parse-uttryck är ett hierarkiskt uttryck som liknar ett reguljärt uttryck som är byggt så här:

  1. Ett atomär analysuttryck består av:
    • vilket terminaltecken som helst,
    • någon icke-terminal symbol, eller
    • tom sträng ε.
  2. Givet parse-uttryck e, e 1 och e 2 genererar följande satser nya parse-uttryck:
    • Sekvens: e 1 e 2
    • Beställt urval: e 1 / e 2
    • Noll eller mer: e*
    • En eller flera: e+
    • Valfritt: e?
    • Och predikat: &e
    • INTE predikat: !e

Den grundläggande skillnaden mellan en PB-grammatik och en COP-grammatik är att PB-grammatikens valoperator är ordnad . Om det första alternativet fungerar ignoreras alla efterföljande . Ordnat val är alltså inte kommutativt, till skillnad från bokdefinitioner av kontextfria grammatiker och reguljära uttryck. Ordnat urval liknar soft cut-operatören i vissa logiska programmeringsspråk.

Som en konsekvens, när en CFG konverteras direkt till en RTG, löses alla tvetydigheter deterministiskt till förmån för ett av de möjliga analysträden. Genom att noggrant välja i vilken ordning grammatiska alternativ specificeras, kan programmeraren få avsevärd kontroll över vilket parseträd som väljs.

Liksom booleska sammanhangsfria grammatiker har RE-grammatiker OCH- och INTE-predikat. De bidrar till att ytterligare disambiguera om omordningen av alternativen inte kan ge det önskade analysträdet.

Tolkning av parse-uttryck

Varje icke-terminal i en PB-grammatik är i huvudsak en parserfunktion i en rekursiv descent-parser, och motsvarande parseruttryck är "koden" för den funktionen. Varje analysfunktion tar en sträng som indata och ger ett av följande resultat:

En icke-terminal kan lyckas utan att absorbera input, och detta tillstånd skiljer sig från fel.

Ett atomärt analysuttryck som består av en enda terminal lyckas om det första tecknet i inmatningssträngen matchar och förbrukar det. Annars är resultatet misslyckat. Ett atomuttryck från en tom sträng lyckas alltid utan att förbrukas. Ett atomuttryck som består av det icke-terminala A är ett rekursivt anrop till den icke-terminala funktionen A .

Sekvensoperatören e 1 e 2 anropar först e 1 och, om e 1 lyckas, anropar sedan e 2 på den del av strängen som lämnats oförbrukad av e 1 och returnerar resultatet. Om e 1 eller e 2 misslyckas, då misslyckas sekvensoperatorn e 1 e 2 också .

Urvalssatsen e 1 / e 2 anropar först e 1 och, om e 1 lyckas, returnerar dess resultat. Annars, om e1 misslyckas , återställer select-satsen inmatningssträngen till tillståndet före anropet av e1 och anropar e2 , vilket returnerar dess resultat.

Operatörerna noll-eller-fler, en-eller-fler och valfria operatorer förbrukar noll eller fler, en eller flera, eller noll eller en på varandra följande förekomst av deras e -underuttryck . Till skillnad från CFG:er och reguljära uttryck är dessa operatorer alltid giriga och konsumerar så många indatainstanser de kan. (Reguljära uttryck börjar girigt, men faller sedan tillbaka på misslyckanden och försöker hitta en kortare sekvens.) Till exempel kommer uttrycket a* alltid att konsumera alla tillgängliga a:n, och uttrycket (a* a) kommer alltid att misslyckas eftersom efter den första delen av a* exekveras, finns det inga a:n kvar för den andra.

Slutligen implementerar AND-predikat och NOT-predikat syntaktiska predikat. Uttrycket & e kallar underuttrycket e , och returnerar framgång om e lyckas och misslyckas annars, men förbrukar aldrig input. Likaså uttrycket ! e lyckas om e misslyckas, och misslyckas om e lyckas, återigen utan att absorbera input. Eftersom uttrycket e kan vara en godtyckligt komplex konstruktion som kan utvärderas "i förväg" utan att konsumera inmatningssträngen, tillhandahåller dessa predikat kraftfulla syntaktiska förberedande och disambiguerande verktyg.

Exempel

Följande RW-grammatik känner igen matematiska formler med fyra operationer på icke-negativa heltal.

Värde ← [0-9]+ / '(' Expr ')' Produkt ← Värde (('*' / '/') Värde)* Summa ← Produkt (('+' / '-') Produkt)* Expr ← Summa

I exemplet ovan är terminaltecken texttecken som representeras av enkla citattecken, såsom '('och ')'. Ett intervall [0-9]är en förkortning för tio tecken som representerar siffrorna 0 till 9. (Detta är samma syntax som för reguljära uttryck). Icke-terminalsymboler är symboler för vilka det finns utdataregler: Value , Product , Sum , och Expr .

Exemplen nedan har inga citattecken för att förbättra läsbarheten. Små bokstäver är terminaltecken, och versaler kursiv är icke-terminaler. Verkliga PB-grammatiktolkare kräver citattecken.

Analysuttrycket (a/b)* matchar och konsumerar sekvenser av godtycklig längd från a och b. Regel S ← a S ? b beskriver ett enkelt sammanhangsfritt språk . Följande RW-grammatik beskriver ett klassiskt, icke-kontextfritt språk :

S ← &(A 'c') 'a'+ B !('a' / 'b' / 'c') A ← 'a' A? 'b' B ← 'b' B? 'c'

Följande rekursiva regel matchar en standard C if/then/else-sats så att ett valfritt else-block alltid matchar det innersta if. (I en kontextfri grammatik skulle detta leda till den klassiska dinglande tvetydigheten.)

S ← 'om' C 'då' S 'annat' S / 'om' C 'då' S

Analysuttrycket foo &(bar) matchar och konsumerar texten "foo", men bara om den följs av texten "bar". Analysuttrycket foo !(bar) förbrukar texten "foo" endast om det inte följs av "bar". Uttrycket !(a+b) a tar ett enda tecken "a", men bara om det inte är det första i en godtycklig längd av a följt av b.

Följande rekursiva regel motsvarar en kapslad Pascal-kommentar. Kommentartecken omges av enkla citattecken för att skilja dem från RVG-operatörer.

Börja ← '(*' Slut ← '*)' C ← Börja N* Slut N ← C / (!Börja !Sluta Z) Z ← vilket enskilt tecken som helst

Implementering av RW-grammatikparsers

Vilken RH-grammatik som helst kan direkt omvandlas till en parser genom rekursiv härkomst. På grund av den obegränsade pre-parsing-förmågan kan den resulterande parsern köras, i värsta fall, i exponentiell tid.

Genom att komma ihåg resultatet av de mellanliggande analysstegen och se till att varje parserfunktion inte anropas mer än en gång för en given position av indata, är det möjligt att omvandla vilken PB-grammatik som helst till en packrat-parser som alltid körs i linjär tid kl . kostnaden för en betydande ökning av minneskostnaderna.

En packrat-parser är en sorts parser som fungerar på ett liknande sätt som rekursiv descent, förutom att den, när den analyserar, kommer ihåg de mellanliggande resultaten av alla anrop till ömsesidigt rekursiva parsningsfunktioner. På grund av detta kan packrat-parsern tolka många sammanhangsfria grammatiker och all PB-grammatik (inklusive några som genererar icke-kontextfria språk) i linjär tid [1] .

Det är också möjligt att bygga en LL-parser och en LR-parser för RW-grammatik, men möjligheten till obegränsad föranalys går förlorad i detta fall.

Fördelar

REGRAM är bra substitut för reguljära uttryck eftersom de är strikt mer kraftfulla. Till exempel kan ett reguljärt uttryck i grunden inte hitta matchande par av parenteser eftersom det är icke-rekursivt, till skillnad från en RE-grammatik.

Vilken RH-grammatik som helst kan analyseras i linjär tid med packrat-parsern enligt beskrivningen ovan.

Parsers för språk som representeras av COP-grammatiker, såsom LR-parsers, kräver ett speciellt lexikal analyssteg som delar upp inmatningen enligt mellanslag, interpunktion och så vidare. Detta är nödvändigt eftersom dessa tolkar använder föranalys för att bearbeta vissa CFGs i linjär tid. RW-grammatik kräver inte ett separat lexikal analyssteg, och reglerna för det kan fastställas tillsammans med andra grammatikregler.

Många COP-grammatiker innehåller betydande tvetydigheter, även när de ska beskriva språk med ett värde. Problemet "hängande annat" i C, C++ och Java är ett exempel på detta fenomen. Dessa problem löses ofta genom att tillämpa en regel utanför grammatiken. I en PB-grammatik uppstår aldrig dessa oklarheter på grund av prioritering.

Nackdelar

Minnesförbrukning

Parsningen av en PB-grammatik görs vanligtvis av en packrat-parser som kommer ihåg de extra parsingstegen. Sådan analys kräver att data lagras i proportion till längden på inmatningen, i motsats till djupet på analysträdet för LR-parsare. Detta är en betydande vinst på många områden: till exempel tenderar människoskriven kod att ha nästan konstant kapsdjup oavsett programlängd – uttryck som är djupare än en viss mängd refaktoreras vanligtvis.

För vissa grammatiker och vissa indata kan djupet på analysträdet vara proportionellt mot längden på inmatningen, så för en utvärdering som inte tar hänsyn till detta mått kan en packrat-parser verka lika bra som en LR-parser. Detta liknar situationen med grafalgoritmer: Bellman-Ford och Floyd-Warshall har en exekveringstid ( ) om bara antalet hörn beaktas. En mer noggrann analys, med hänsyn till antalet flanker, visar dock exekveringstiden för Bellman-Ford-algoritmen , som endast är kvadratisk med storleken på ingången, inte kubisk.

Indirekt vänsterrekursion

RE-grammatiker kan inte innehålla vänsterrekursiva regler som kallar sig utan radavancemang. Till exempel, i den aritmetiska grammatiken som beskrivs ovan, skulle jag vilja flytta några regler så att produktens företräde och summan kan uttryckas på en rad:

Värde ← [0-9.]+ / '(' Expr ')' Produkt ← Expr (('*' / '/') Expr)* Summa ← Expr (('+' / '-') Expr)* Expr ← Produkt / Summa / Värde

Problemet här är att för att få en träff för Expr , måste du kontrollera om produkten aktiveras , och för att kontrollera produkten måste du först kontrollera Expr . Och detta är omöjligt.

Men vänsterrekursiva regler kan alltid skrivas om för att eliminera vänsterrekursion. Till exempel kan en vänsterrekursiv regel upprepa ett uttryck på obestämd tid, som i CF-grammatikregeln:

string-of-a ← string-of-a 'a' | 'a'

Detta kan skrivas om i en PB-grammatik med +-operatorn:

sträng-av-a ← 'a'+

Med vissa modifieringar är det möjligt att göra en vanlig packrat-parser till stöd för direkt vänsterrekursion [1] [2] [3] .

Processen att skriva om indirekta vänsterrekursiva regler är dock svår, särskilt när semantiska handlingar äger rum. Även om det är teoretiskt möjligt, finns det ingen RW-parser som stöder indirekt vänsterrekursion, medan alla GLR-parsrar gör det.

Subtila grammatiska fel

För att uttrycka en grammatik som en PB-grammatik måste dess författare konvertera alla instanser av icke-deterministiskt val till ordnat val. Tyvärr är denna process felbenägen och resulterar ofta i grammatik som analyserar en del av inmatningen felaktigt.

Uttrycksförmåga

Packrat-tolkare kan inte analysera vissa entydiga grammatiker, såsom följande [4] :

S ← 'x' S 'x' | 'x'

Utveckling

RE-grammatiker är nya och inte allmänt använda. Reguljära uttryck och COP-grammatik har å andra sidan funnits i årtionden, koden som analyserar dem har förbättrats och optimerats, och programmerare har erfarenhet av att använda dem.

Länkar

Anteckningar

  1. ↑ 1 2 Ford, Bryan Packrat Parsing: en praktisk linjär-tidsalgoritm med bakåtspårning . Massachusetts Institute of Technology (september 2002). Datum för åtkomst: 27 juli 2007. Arkiverad från originalet den 2 april 2012.
  2. ↑ Alessandro Warth, James R. Douglass, Todd Millstein. Packrat Parsers kan stödja  vänsterrekursion . - Synpunkter Research Institute, 2008. - Januari.
  3. ↑ Ruedi Steinmann. Hantera vänsterrekursion i Packrat Parsers  (neopr.) . - 2009. - Mars. Arkiverad från originalet den 6 juli 2011. Arkiverad kopia (inte tillgänglig länk) . Hämtad 17 juni 2009. Arkiverad från originalet 6 juli 2011. 
  4. ↑ Bryan Ford. Funktionell pärla: Packrat Parsing: Enkel, kraftfull, lat, linjär tid  (engelska)  : journal. – 2002.