Grammatik analyserer et udtryk

En udtryks-parsing grammatik (PB-grammatik) er en type analytisk formel grammatik , der beskriver et formelt sprog i form af et sæt regler for genkendelse af sprogstrenge. En grammatik, der analyserer et udtryk, er i det væsentlige en rekursiv descent -parser i en rent skematisk form, der kun udtrykker syntaksen og er uafhængig af den særlige implementering eller brug af parseren. Udtryksparsende grammatikker ligner regulære udtryk og kontekstfri grammatikker (CFG'er) i Backus-Naur-notation , men har en anden fortolkning.

I modsætning til COP-grammatikker kan PB-grammatikker ikke være tvetydige : hvis en streng er parset, så er der præcis ét parsetræ. Dette gør RE-grammatikker velegnet til computersprog, men ikke til naturlige.

Definition

Formelt består den grammatik, der analyserer et udtryk af:

et endeligt sæt af N ikke-terminale symboler ;
et endeligt sæt Σ af terminalsymboler , der ikke skærer N ;
et endeligt sæt P af slutningsregler ;
udtryk e S , kaldet det indledende udtryk .

Hver inferensregel fra P har formen A ← e, hvor A er et ikke-terminalt symbol, og e er et parseudtryk. Et parse-udtryk er et hierarkisk udtryk, der ligner et regulært udtryk , der er bygget på denne måde:

Et atomart parse-udtryk består af:
- ethvert terminaltegn,
- ethvert ikke-terminalt symbol, eller
- tom streng ε.
Givet parse-udtryk e, e 1 og e 2 genererer følgende udsagn nye parse-udtryk:
- Sekvens: e 1 e 2
- Bestilt udvalg: e 1 / e 2
- Nul eller mere: e*
- En eller flere: e+
- Valgfrit: e?
- Og prædikat: &e
- IKKE prædikat: !e

Den grundlæggende forskel mellem en PB-grammatik og en COP-grammatik er, at PB-grammatikkens valgoperator er ordnet . Hvis det første alternativ virker, ignoreres alle efterfølgende . Ordnet valg er således ikke kommutativt, i modsætning til bogdefinitioner af kontekstfri grammatik og regulære udtryk. Ordret valg ligner soft cut-operatøren i nogle logiske programmeringssprog.

Som en konsekvens heraf, når en CFG konverteres direkte til en RTG, løses enhver tvetydighed deterministisk til fordel for et af de mulige parse-træer. Ved omhyggeligt at vælge den rækkefølge, som grammatiske alternativer er specificeret i, kan programmøren få betydelig kontrol over, hvilket parsetræ der vælges.

Ligesom boolske kontekstfri grammatikker har RE-grammatikker OG- og IKKE-prædikater. De hjælper til yderligere at disambiguere, hvis genbestillingen af alternativerne ikke kan frembringe det ønskede parsetræ.

Fortolkning af parse-udtryk

Hver ikke-terminal i en PB-grammatik er i det væsentlige en parserfunktion i en rekursiv descent-parser, og det tilsvarende parserudtryk er "koden" for denne funktion. Hver parsefunktion tager en streng som input og producerer et af følgende resultater:

succes, i hvilket tilfælde funktionen eventuelt kan fremføre eller "sluge" et eller flere tegn i inputstrengen
et dyk, hvor input ikke forbruges.

En ikke-terminal kan lykkes uden at absorbere input, og denne tilstand er forskellig fra fiasko.

Et atomart parse-udtryk, der består af en enkelt terminal, lykkes, hvis det første tegn i inputstrengen matcher og bruger det. Ellers er resultatet mislykket. Et atomudtryk fra en tom streng lykkes altid uden at blive fortæret. Et atomudtryk bestående af det ikke-terminale A er et rekursivt kald til den ikke-terminale funktion A .

Sekvensoperatøren e 1 e 2 kalder først e 1 og, hvis e 1 lykkes, kalder den derefter e 2 på den del af strengen, der ikke er forbrugt af e 1 og returnerer resultatet. Hvis e 1 eller e 2 fejler, fejler sekvensoperatoren e 1 e 2 også .

Udvælgelsessætningen e 1 / e 2 kalder først e 1 og, hvis e 1 lykkes, returnerer dens resultat. Ellers, hvis e 1 fejler, gendanner select-sætningen inputstrengen til tilstanden før kaldet e 1 og kalder e 2 , hvilket returnerer dets resultat.

Nul-eller-flere, en-eller-flere og valgfri operatorer forbruger henholdsvis nul eller flere, en eller flere eller nul eller en fortløbende forekomst af deres e -underudtryk . I modsætning til CFG'er og regulære udtryk er disse operatorer altid grådige og bruger så mange input-instanser, som de kan. (Regulære udtryk starter grådigt, men falder så tilbage på fiasko og forsøger at finde en kortere sekvens.) For eksempel vil udtrykket a* altid forbruge alle tilgængelige a'er, og udtrykket (a* a) vil altid mislykkes, fordi efter den første del af a* er udført, er der ingen a'er tilbage til den anden.

Endelig implementerer OG-prædikat og IKKE-prædikat syntaktiske prædikater. Udtrykket & e kalder underudtrykket e , og returnerer succes, hvis e lykkes og fejler ellers, men aldrig bruger input. Ligeledes udtrykket ! e lykkes, hvis e fejler, og fejler, hvis e lykkes, igen uden at absorbere input. Fordi udtrykket e kan være en vilkårligt kompleks konstruktion, der kan evalueres "forud" uden at forbruge inputstrengen, giver disse prædikater kraftfulde syntaktiske forberedende og disambiguerende værktøjer.

Eksempler

Den følgende RW-grammatik genkender matematiske formler med fire operationer på ikke-negative heltal.

Værdi ← [0-9]+ / '(' Udtr ')' Produkt ← Værdi (('*' / '/') Værdi)* Sum ← Produkt (('+' / '-') Produkt)* Udtr ← Sum

I eksemplet ovenfor er terminaltegnene teksttegn, der er repræsenteret af enkelt-anførselstegn, såsom '('og ')'. Et interval [0-9]er en forkortelse for ti tegn, der repræsenterer tallene 0 til 9. (Dette er den samme syntaks som for regulære udtryk). Ikke-terminale symboler er symboler, for hvilke der er outputregler: Værdi , Produkt , Sum og Udtr .

Eksemplerne nedenfor har ikke anførselstegn for at forbedre læsbarheden. Små bogstaver er terminaltegn, og store kursiv er ikke-terminaler. Ægte PB-grammatik-parsere kræver anførselstegn.

Parse-udtrykket (a/b)* matcher og bruger sekvenser af vilkårlig længde fra a og b. Regel S ← a S ? b beskriver et simpelt kontekstfrit sprog . Følgende RW-grammatik beskriver et klassisk, ikke-kontekstfrit sprog : $\{a^{n}b^{n}:n\geq 1\}$ $\{a^{n}b^{n}c^{n}:n\geq 1\}$

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

Den følgende rekursive regel matcher en standard C if/then/else-sætning, således at en valgfri else-blok altid matcher den inderste if. (I en kontekstfri grammatik ville dette føre til den klassiske dinglende andet tvetydighed.)

S ← 'hvis' C 'så' S 'andet' S / 'hvis' C 'så' S

Parsing-udtrykket foo &(bar) matcher og bruger teksten "foo", men kun hvis den efterfølges af teksten "bar". Parsing-udtrykket foo !(bar) bruger kun teksten "foo", hvis det ikke efterfølges af "bar". Udtrykket !(a+b) a tager et enkelt tegn "a", men kun hvis det ikke er det første i en rækkefølge af vilkårlig længde af a efterfulgt af b.

Den følgende rekursive regel svarer til en indlejret Pascal-kommentar. Kommentartegn er omgivet af enkelte anførselstegn for at skelne dem fra RVG-operatører.

Begynd ← '(*' Slut ← '*)' C ← Begynd N* Slut N ← C / (!Begynd !End Z) Z ← ethvert enkelt tegn

Implementering af RW-grammatik-parsere

Enhver RH grammatik kan konverteres direkte til en parser ved rekursiv afstamning. På grund af den ubegrænsede pre-parsing-kapacitet kan den resulterende parser i værste fald køre i eksponentiel tid.

Ved at huske resultatet af de mellemliggende parsing-trin og sørge for, at hver parserfunktion ikke kaldes mere end én gang for en given position af inputdataene, er det muligt at transformere enhver PB-grammatik til en packrat-parser , der altid kører i lineær tid kl. bekostning af en betydelig stigning i hukommelsesomkostninger.

En packrat-parser er en slags parser, der fungerer på samme måde som rekursiv afstamning, bortset fra at den, når den parser, husker de mellemliggende resultater af alle kald til gensidigt rekursive parsingsfunktioner. På grund af dette er packrat-parseren i stand til at parse mange kontekstfrie grammatikker og enhver PB-grammatik (inklusive nogle, der genererer ikke-kontekstfrie sprog) i lineær tid [1] .

Det er også muligt at bygge en LL-parser og en LR-parser til RW-grammatikker, men evnen til ubegrænset pre-parsing går tabt i dette tilfælde.

Fordele

REGRAMs er gode erstatninger for regulære udtryk , fordi de strengt taget er mere kraftfulde. For eksempel er et regulært udtryk grundlæggende ude af stand til at finde matchende par af parenteser, fordi det er ikke-rekursivt i modsætning til en RE-grammatik.

Enhver RH-grammatik kan parses i lineær tid ved hjælp af packrat-parseren som beskrevet ovenfor.

Parsere for sprog repræsenteret af COP-grammatikker, såsom LR-parsere, kræver et særligt leksikalsk analysetrin, der opdeler input efter mellemrum, tegnsætning og så videre. Dette er nødvendigt, fordi disse parsere bruger pre-parsing til at behandle nogle CFG'er i lineær tid. RW-grammatikker kræver ikke et separat leksikalsk analysetrin, og reglerne for det kan fastlægges sammen med andre grammatikregler.

Mange COP-grammatikker indeholder betydelige tvetydigheder, selv når de formodes at beskrive enkeltværdisprog. Problemet "hanging else" i C, C++ og Java er et eksempel på dette fænomen. Disse problemer løses ofte ved at anvende en regel uden for grammatikken. I en PB-grammatik opstår disse uklarheder aldrig på grund af prioritering.

Ulemper

Hukommelsesforbrug

Parsing af en PB-grammatik udføres normalt af en packrat-parser, der husker de ekstra parsing-trin. En sådan parsing kræver, at data lagres i forhold til længden af input, i modsætning til dybden af parse-træet for LR-parsere. Dette er en betydelig gevinst på mange områder: for eksempel har menneskeskreven kode en tendens til at have næsten konstant indlejringsdybde uanset programlængde - udtryk, der er dybere end en vis mængde, omdannes normalt.

For nogle grammatikker og nogle input kan dybden af parsetræet være proportional med længden af input, så for en evaluering, der ikke tager højde for dette mål, kan en packrat parser fremstå lige så god som en LR parser. Dette svarer til situationen med grafalgoritmer: Bellman-Ford og Floyd-Warshall har én eksekveringstid ( ), hvis kun antallet af hjørner tages i betragtning. En mere nøjagtig analyse, der tager antallet af kanter i betragtning, viser imidlertid eksekveringstiden for Bellman-Ford-algoritmen , som kun er kvadratisk i forhold til størrelsen af inputtet, ikke kubisk. $O(|V|^{3})$ $O(|V|*|E|)$

Indirekte venstre rekursion

RE-grammatikker kan ikke indeholde venstre-rekursive regler, der kalder sig selv uden linjefremrykning. For eksempel vil jeg i den ovenfor beskrevne aritmetiske grammatik gerne flytte nogle regler, så produktets og summen kan udtrykkes på én linje:

Værdi ← [0-9.]+ / '(' Udtr ')' Produkt ← Udtr (('*' / '/') Udtr)* Sum ← Udtr (('+' / '-') Udtr)* Udtr ← Produkt / Sum / Værdi

Problemet her er, at for at få et hit for Expr , skal du tjekke, om Produkt udløses , og for at kontrollere Product , skal du først tjekke Expr . Og dette er umuligt.

Venstre rekursive regler kan dog altid omskrives for at eliminere venstre rekursion. For eksempel kan en venstre-rekursiv regel gentage et eller andet udtryk i det uendelige, som i CF-grammatikken:

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

Dette kan omskrives i en PB grammatik ved hjælp af + operatoren:

string-of-a ← 'a'+

Med nogle modifikationer er det muligt at få en almindelig packrat-parser til at understøtte direkte venstrerekursion [1] [2] [3] .

Processen med at omskrive indirekte venstre-rekursive regler er imidlertid vanskelig, især når semantiske handlinger finder sted. Selvom det er teoretisk muligt, er der ingen RW-parser, der understøtter indirekte venstre rekursion, mens alle GLR-parsere gør.

Subtile grammatiske fejl

For at udtrykke en grammatik som en PB-grammatik skal dens forfatter konvertere alle tilfælde af ikke-deterministisk valg til ordnede valg. Desværre er denne proces udsat for fejl og resulterer ofte i grammatikker, der analyserer noget af input forkert.

Udtryksevne

Packrat-parsere kan ikke parse nogle utvetydige grammatikker, såsom følgende [4] :

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

Udvikling

RE-grammatikker er nye og ikke udbredt. Regulære udtryk og COP-grammatikker har på den anden side eksisteret i årtier, koden, der analyserer dem, er blevet forbedret og optimeret, og programmører har erfaring med at bruge dem.

Noter

↑ 1 2 Ford, Bryan Packrat Parsing: a Practical Linear-Time Algorithm with Backtracking . Massachusetts Institute of Technology (september 2002). Dato for adgang: 27. juli 2007. Arkiveret fra originalen 2. april 2012. (ubestemt)
↑ Alessandro Warth, James R. Douglass, Todd Millstein. Packrat-parsere kan understøtte venstre rekursion . - Synspunkter Research Institute, 2008. - Januar.
↑ Ruedi Steinmann. Håndtering af venstre rekursion i Packrat -parsere (neopr.) . - 2009. - Marts. Arkiveret fra originalen den 6. juli 2011. Arkiveret kopi (ikke tilgængeligt link) . Hentet 17. juni 2009. Arkiveret fra originalen 6. juli 2011. (ubestemt)
↑ Bryan Ford. Funktionel perle: Packrat-parsing: Enkel, kraftfuld, doven, lineær tid (engelsk) : journal. - 2002.