Som enhver grammatisk analysator (eller syntaksanalysator ) sigter en LR-analysator med at kontrollere, om en tegnstreng (typisk indeholdt i en fil) faktisk har strukturen i en grammatik, der er specificeret på forhånd. Denne verifikation ledsages normalt af handlinger. En typisk handling er dannelsen af en anden karakterstreng eller endda et analysetræ. Således anvendes den grammatiske analyse generelt til kompilering (transformation af en kildekode til maskinkode). Fra et teoretisk beregningsmæssigt synspunkt er en LR-parser ( L eft til højre, R ightmost afledning ) en parser for ikke-kontekstuelle grammatikker, der læser input fra venstre til højre (deraf L i venstre mod højre) og producerer en højre afledning (deraf navnet Rightmost, hvilket betyder, at de mønstre, der er specificeret af grammatikken, søges blandt suffikser af rækkefølgen af læste ord, derfor til højre for denne sekvens). Denne analyse blev opfundet i 1965 af Donald Knuth (forfatteren af den berømte bog: Kunsten at programmere ). Vi taler også om en LR-analysator ( k ), hvor k repræsenterer antallet af "forventede" symboler (undersøgt i den analyserede streng uden at blive forbrugt), der bruges til at tage parseringsbeslutninger. Da k normalt er 1, udelades det ofte. En ikke-kontekstuel grammatik kaldes LR ( k ), hvis der er en LR ( k ) parser til den.
En LR-parser siges at udføre bottom-up-analyse, fordi den forsøger at udlede de øverste niveau-produktioner af grammatikken ved at bygge dem fra blade .
Mange programmeringssprog er beskrevet af LR (1) eller lignende, grammatikker, og derfor bruges LR-parsere ofte af kompilatorer til at analysere kildekoden .
Når vi refererer til en LR-parser, taler vi typisk om en parser, der er i stand til at genkende et bestemt sprog specificeret af en ikke-kontekstuel grammatik . Imidlertid anvendes udtrykket i almindelig anvendelse til et driverprogram, der kan kaldes med en bestemt tabel, og som producerer en bred vifte af forskellige LR-parsere. I stedet skal vi kalde disse generatorprogrammer parsere .
LR-parsing har flere fordele:
LR-parsere er vanskelige at fremstille i hånden; de er generelt bygget af parsergeneratorer eller kompilatorer af compilere . Afhængigt af hvordan parsertabellen genereres kaldes disse parsere simple LR-parsere (SLR'er til Simple LR - parsere ), LR - parsers med blik fremad (LALRs til LR-parser med blik fremad ) og kanoniske parsers . Disse typer af parsere kan behandle stadig større sæt grammatikker; LALR-parsere kan behandle flere grammatikker end spejlreflekskameraer. Kanoniske parsere arbejder på flere grammatikker end LALR parsers. Den velkendte Yacc producerer LALR-parsere.
Selvom forvirring er almindelig, bør man ikke forveksle en LR-analysator med en LR-analysatorgenerator. For eksempel er Yacc-værktøjet, som netop er blevet nævnt, ikke en LR-analysator strengt taget, men faktisk en generator af LR-analysatorer . De to begreber er kendetegnet ved deres input-output. En LR-parsergenerator tager som input en grammatik og producerer kildekoden til LR-parseren til denne grammatik (og / eller alarmer / fejl i forbindelse med den iboende tvetydighed af grammatikken, der er angivet som input). Mens en korrekt LR-analysator tager som input en tegnstreng og producerer som output en dom (vedrørende strengets overensstemmelse med den grammatik, der bruges til at producere denne analysator) og muligvis et produktionsprodukt (et analysetræ, en anden streng).
Konceptuelt er en LR-parser et rekursivt program, der kan bevises korrekt ved direkte beregning, og som effektivt kan implementeres af en bottom-up-parser , som er et sæt gensidigt rekursive funktioner, ligesom en top-down- parser . Imidlertid introduceres og implementeres LR-parsere ved konvention ved hjælp af tabelbaserede stakmaskiner, hvor opkaldstakken til det underliggende rekursive program manipuleres eksplicit.
En stigende parser baseret på en parsetabel kan gengives skematisk ved figur 1. Følgende viser en ret afledning opnået af denne parser.
For at forklare, hvordan en LR-grammatikparser fungerer, bruger vi den lille grammatik, der består af regler (1) til (5) nedenfor, forudsat at startsymbolet er E. Som en påmindelse angiver store bogstaver i regler som nedenfor store bogstaver ikke-terminale symboler ; andre symboler (små bogstaver, tegnsætning, tal) angiver terminalsymboler . Terminal symboler er de ikke-brudende syntaktiske enheder, hvorfra teksten, der er givet som input til parseren, er konstrueret. Disse enheder leveres til vores grammatiske analysator LR af en anden analysator, kaldet en leksikalanalysator (som vi ikke har at gøre med her), som har funktionen til at opdele teksten, der er givet som input i en sekvens af terminalsymboler. Behandlingsflowet er derfor som følger: teksten givet som input er opdelt i terminalsymboler af lexeren, der sender disse symboler til LR-analysatoren, som vi foreslår at studere. For at forenkle præsentationen antager vi, at de terminalsymboler, der udsendes Lexer, er tilgængelige i en buffer (kaldet buffer ). For eksemplet nedenfor er terminalerne symbolerne + , * , - , 0 , 1 . I modsætning til terminalsymboler betegner ikke-terminale symboler sekvenser af symboler (terminal eller ej). Disse sekvenser er defineret gennem ikke-kontekstuelle regler (såsom følgende), som tilsammen danner en grammatik:
(1) E → E * B (2) E → E + B (3) E → B (4) B → 0 (5) B → 1Reglerne (4) (5) betyder, at B kan være en 0 eller 1. Reglen E → E + B betyder, at en E kan være en sekvens af formen E + B. Vi kan bemærke denne reglers rekursive karakter. Symbolet E griber ind i sin egen definition. Generelt er der rekursion, når et ikke-terminal symbol er både til venstre og til højre for en regel. En grammatik (et sæt regler) kan derfor være misdannet, hvis der er cirkularitet. Typisk inducerer en regel E → E cirkularitet, eller for eksempel E → F med F → E. I vores eksempel er der ingen problematisk cirkularitet, fordi E kan være af form B og i sig selv af form 0 eller 1, hvilket gør det muligt at komme ud af sløjfen.
Vi vil være interesserede i at vide, om input 1 + 1 faktisk er en forekomst af vores grammatik ved hjælp af en LR-type tilgang.
For at fortsætte i overensstemmelse med denne LR-tilgang tilføjer vi først til grammatikken reglen (0) nedenfor for at formalisere, at grammatikens start er E.
(0) ACCEPT → E $
Vi opnår således en beriget grammatik . Bemærk, at symbolerne ACCEPT og $ er generiske symboler (ikke specifikke for vores grammatik). $ -Symbolet er et slut på streng-symbolet (for programmører: det er den berømte EOF .. End of File). Med hensyn til symbolet ACCEPT introduceres det for automatisk at kunne afslutte genkendelsesprocessen. I litteraturen, som i diskussionen af det generelle tilfælde nedenfor, kaldes symbolet ACCEPT ofte S (for Start).
Regel (0) gør det derfor både muligt at formalisere, at E er det sande startsymbol, og også at finde det endelige acceptkriterium, som er: i slutningen af analysen må analysestakken kun indeholde ACCEPT og bufferen indeholdende strengen, der skal analyseres skal være tom (dette illustreres nedenfor).
Endelig spørger, om strengen 1 + 1 er en afledning af grammatikken, der består af reglerne (1) til (5), med E som startsymbol, er som at spørge, om strengen 1 + 1 $ er en afledning af den berikede grammatik bestående af regler (0) til (5), men med ACCEPT som startsymbol.
Så vores LR-analysator bruger en stak, som derfor adlyder en LIFO (Last In First Out) -logik. Den bruger også en buffer, der indeholder terminalsymbolerne i kæden til at analysere. Oprindeligt er analysatorstakken tom, og dens buffer indeholder den post, der skal analyseres, enten her:
$ 1 + $ 1
Symbolet længst til venstre for bufferen (dermed L for venstre i navnet LR) fjernes fra bufferen. Her er dette symbol 1. Dette symbol er placeret på stakken. Buffers læstehoved er placeret på følgende symbol, derfor på + symbolet. Stakken ser sådan ud (i denne stakrepræsentation antager vi, at symbolerne kommer ind fra toppen):
| 1 |
Som i hvert trin ser analysatoren på stakken som et mønster M dannet af rækken af symboler, der findes i stakken, startende fra bunden af stakken og opad. Det kontrollerer, om et suffiks s af dette mønster M er identisk med den højre del af en regel N → s af grammatikken. I så fald betyder det, at det ikke-terminale symbol N er blevet genkendt. Analysatoren udfører derefter denne handling: den popper symbolerne, der danner suffikset s, så stabler N i stedet. Det vil således blive erstattet i stablen alle symbolerne i s den eneste symbol N . Dette aspekt kommer mere tydeligt ud nedenfor, når stakken indeholder flere symboler. Det kan bemærkes, at denne operation, kaldet reduktion , udføres på symbolet eller symbolerne på toppen af stakken, det vil sige på det eller de sidste symboler, der er læst / genkendt; det vil sige i den yderste del af kæden, som analyseres. Dette er hvor afledningen foretages mest til højre (deraf R for højre længste i benævnelsen LR).
For øjeblikket kan vi se, at stakmønsteret M koger ned til det enkelte symbol 1, som er nøjagtigt den rigtige del af reglen (5). Dette symbol 1 kan derfor ses som en afledning af B ifølge regel (5). Analysatoren erstatter 1 med B i stakken (mere præcist, den springer 1, højre del af (5) og stabler B venstre del af (5)). Denne operation udført af analysatoren kaldes en reduktion . Det producerer analysetræet modsat. Stakken bliver:
| [B] |
Mønster B , som den rigtige del af regel (3), er en afledning af E af (3). Analysatoren udfører en yderligere reduktion ved at frasortere B og derefter stable E som specificeret af regel (3). Analysetræet er givet af figuren overfor. Stakken bliver:
| [E] |
Stakmønsteret, der består af det enkelte symbol E , indeholder ikke et suffiks, der matcher den højre side af en lineal. Der er derfor ingen reduktion mulig. Analysatoren fjerner derefter et nyt tegn fra bufferen, nemlig + symbolet (som læsehovedet stod på). Dette afspilningshoved bevæger sig til det næste symbol, som er det andet og sidste 1. Stakken bliver:
| [+] |
| [E] |
Her er stakmønsteret E + . Intet suffiks i dette mønster matcher højre side af en lineal. Så ingen reduktion er mulig. Derfor fjernes et nyt symbol, den sidste 1, fra bufferen og stables i stakken. Læst hovedet på bufferen er placeret på $, slut symbol. Stakken bliver:
| [1] |
| [+] |
| [E] |
Her er stakmønsteret E + 1 . Det eneste suffiks af dette mønster, der svarer til en højre del, er som ovenfor suffikset bestående af det eneste symbol 1. Det er den rigtige del af (3). Denne 1 erstattes af B med samme reduktion.
| [B] |
| [+] |
| [E] |
Her det mønster er E + B . Nu er E + B i sig selv et suffiks af E + B. Da suffikset E + B er det samme som den højre del af (2). Dette suffiks (derfor det komplette mønster) er ikke stablet. Analysatoren popper derfor 3 symboler. Den stabler på plads E, venstre symbol for linealen (2). Stakken bliver:
| [E] |
Som ovenfor indeholder stakmønsteret, der består af det enkelte symbol E, ikke et suffiks, der matcher en lige del af reglen. Der er derfor ingen reduktion mulig. Analysatoren fjerner det sidste symbol fra bufferen, nemlig $. Bufferen er nu tom. Batteriet er i følgende tilstand:
| [$] |
| [E] |
Stakmønsteret er E $, som er den rigtige del af reglen (0). Analysatoren reducerer i henhold til regel (0):
| [ACCEPTERE] |
Her indeholder stakken kun accept symbolet ACCEPT; Desuden er bufferen tom. Denne situation betyder, at vores fil 1 + 1 $ faktisk har formularen E $, og at det derfor kontrollerer den berigede grammatik. Som et resultat er 1 + 1-kæden faktisk en afledning af reglerne i den oprindelige grammatik, der består af reglerne (1) til (5). Parseren stopper ved at meddele accept af den givne streng som input.
I kapitlet, der følger LR-tilgangen, som vi netop har beskrevet, er formaliseret med en automat. I stedet for at stable symboler er de på en ækvivalent måde tilstande for en automat, som placeres i stakken.
Parseren er en statsmaskine. Den består af:
LR-parsingsalgoritmen fungerer som følger:
De to LR (0) analysetabeller i denne grammatik ser sådan ud:
| stater | handlinger | forbindelser | ||||||
| * | + | 0 | 1 | $ | E | B | ||
| 0 | s1 | s2 | 3 | 4 | ||||
| 1 | r4 | r4 | r4 | r4 | r4 | |||
| 2 | r5 | r5 | r5 | r5 | r5 | |||
| 3 | s5 | s6 | iht | |||||
| 4 | r3 | r3 | r3 | r3 | r3 | |||
| 5 | s1 | s2 | 7 | |||||
| 6 | s1 | s2 | 8 | |||||
| 7 | r1 | r1 | r1 | r1 | r1 | |||
| 8 | r2 | r2 | r2 | r2 | r2 | |||
Den aktioner tabellen er indekseret af tilstanden af parseren og ved en terminal (herunder den særlige terminal $ som angiver afslutningen på input stream). Den indeholder tre typer handlinger:
Den forgrening tabel er indekseret af tilstanden af parseren og af en ikke-terminal. Det angiver den næste tilstand for parseren, hvis den faktisk har genkendt denne ikke-terminal.
I henhold til tabellen ovenfor, hvis vi er i tilstand 0 og buffers nuværende symbol er terminalsymbolet +, skal vi skifte til tilstand 2, hvilket betyder at tilstand 2 er stablet på tilstandsstakken (og så bliver den aktuelle tilstand) . Samtidig går bufferen til det næste symbol.
Ifølge denne tabel, hvis vi er i tilstand 4, skal vi uanset buffers nuværende symbol udføre en reduktion i henhold til regel 3 (som er E → B). Dette betyder, at de sidst læste symboler svarer til sekvensen til højre for denne regel (sekvens reduceres her til B) og derfor har vi netop genkendt symbolet til venstre (her E). Vi skal så springe fra stakken med stater så mange stater, da der er symboler til stede til højre for reglen (her kun en, da der kun er B), hvilket fører til at opnå en ny top på stakken s, som kort er den aktuelle tilstand . Men straks skal analysatoren overveje, at den har genkendt symbolet til venstre for reglen, dvs. her E. Analysatoren skal derefter bruge forgreningstabellen til at placere sig i den tilstand, der er angivet i linje s og i henhold til kolonne E i forgreningstabellen . For eksempel, hvis s er tilstand 0, indikerer forgreningstabellen tilstand 3 for parret (0, E). Tilstand 3 stables derefter straks og bliver den aktuelle tilstand (alt sker som om E havde været et symbol tilføjet kortvarigt foran bufferen og straks forbrugt).
Tabellen nedenfor illustrerer hvert trin i processen til parsering af udtrykket: 1 + $ 1. I denne tabel repræsenterer tilstanden elementet øverst i stakken (elementet længst til højre), og den næste handling bestemmes ved at henvise til handlinger / forgreningstabel ovenfor. En $ føjes til slutningen af inputstrengen for at indikere slutningen af strømmen.
| stat | Input flow | Output flow | Batteri | Næste handling |
|---|---|---|---|---|
| 0 | $ 1 + $ 1 | [0] | Forskydning 2 | |
| 2 | + $ 1 | [0.2] | Rabat 5 | |
| 4 | + $ 1 | 5 | [0.4] | Rabat 3 |
| 3 | + $ 1 | 5.3 | [0.3] | Forskydning 6 |
| 6 | $ 1 | 5.3 | [0.3.6] | Forskydning 2 |
| 2 | $ | 5.3 | [0,3,6,2] | Rabat 5 |
| 8 | $ | 5.3.5 | [0,3,6,8] | Rabat 2 |
| 3 | $ | 5.3.5.2 | [0.3] | Accept |
Når parseren starter, starter den altid med tilstand 0 på stakken:
[ 0 ]Den første terminal, parseren ser, er '1'. I henhold til handlingstabellen skal den gå til tilstand 2. Hvilket giver stakken:
[ 0 2 ]Toppen af stakken, som er den aktuelle tilstand for analysatoren, er til højre, så her er den 2. For en bedre forståelse tilføjer vi stakens tilstande, i parentes og kursiv, den del af grenen skaft fastgjort til det. Dette giver følgende notation for den samme stak:
[ 0 () 2 (1) ]
I tilstand 2 siger handlingstabellen, at uanset den næste terminal, i inputstrømmen, er det nødvendigt at foretage en reduktion med grammatikregel nummer 5. Dette betyder, at parseren lige har genkendt den rigtige del af regelnummer 5, som er faktisk tilfældet.
Så i dette tilfælde skriver vi 5 til outputstrømmen, fjerner en tilstand fra stakken. Toppen af stakken bliver 0, og vi har netop genkendt en B. Analysatoren anvender straks forgreningstabellen. For parret (0, B) angiver dette derefter tilstand 4. Denne tilstand er stablet, som om vi lige havde læst en B fra 0. Stakken, der er resultatet af disse operationer, er:
[ 0 () 4 (B-1) ]I tilstand 4 indikerer handlingstabellen, at der skal foretages en reduktion af regel 3 (til opfølgning produceres antallet af denne regel, 3, i outputstrømmen). Analysatoren fjerner så mange tilstande fra stakken, da der er symboler til højre for reduktionsreglen. Så her er der kun én, da regel 3 kun har et symbol til højre. Den nye top af stakken bliver midlertidigt til tilstand 0. Analysatoren bruger straks "grene" -delen af tabellen. For tilstand 0 og symbolet E, som netop er blevet genkendt, angives det, at den tilstand, hvor position skal være, er tilstand 3. Denne tilstand er stablet (som for et skift) og bliver den nye aktuelle tilstand:
[ 0 () 3 ( E - B-1)]Den næste terminal, som parseren ser i inputstrømmen, er et '+'. Ifølge handlingstabellen skal den gå til tilstand 6:
[ 0 () 3 (E - B-1) 6 (+) ]Den resulterende stak kan fortolkes som historien om en tilstandsmaskine , der netop har læst en ikke-terminal E efterfulgt af en '+' terminal. Overgangstabellen for denne automat defineres af offset-handlingerne i handlingstabellen såvel som af grenhandlingerne i gren-tabellen.
Den næste terminal er nu '1'. Dette betyder, at vi foretager en offset og går til tilstand 2:
[ 0 () 3 (E - B-1) 6 (+) 2 (1) ]Ligesom det forrige '1' er denne reduceret til B; men forgreningen til parret (6, B) er 8; denne tilstand er stablet, hvilket resulterer i følgende stak:
[ 0 () 3 (E - B-1) 6 (+) 8 (B-1) ]Stakken svarer til en liste over tilstande for en endelig automat, der har læst en ikke-terminal E efterfulgt af et '+' og en ikke-terminal B. I tilstand 8 foretager vi en reduktion med reglen 2. Dette har tre symboler til højre. Vi fjerner de tre øverste tilstande i stakken, der svarer til de tre symboler på højre side af regel 2. Den øverste del af stakken er midlertidigt 0 . Vi har lige genkendt den venstre del af regel 2, det vil sige en E. Forbindelsestabellen for parret (0, E) angiver tilstand 3. Denne er stablet, stakken bliver:
[ 0 () 3 ((E - B-1) + (B-1)) ]
I sidste ende læses '$' symbolet på slutningen af strengen på inputstrømmen, hvilket ifølge handlingstabellen (nuværende tilstand er 3), at parseren accepterer strengindgangen. Syntaksetræet er det, der er knyttet til toppen af staktilstanden, her: ((E - B -1) + (B -1)) ... se også figuren dens repræsentation i grafform.
Reglerne, der er skrevet til outputstrømmen, er [5, 3, 5, 2], hvilket faktisk er en rigtig afledning af kæden "1 + 1" baglæns.
Opbygningen af disse parseringstabeller er baseret på forestillingen om LR (0) -elementer (simpelthen kaldet emner her), som er grammatikregler med et specielt punkt tilføjet et eller andet sted i den rigtige del, dette særlige punkt repræsenterer en mulig tilstand for analysatoren mulig fælles situation). For eksempel for reglen E → E + B kan vi have følgende fire emner (situationer):
E → • E + B E → E • + B E → E + • B E → E + B •Hvert element repræsenterer en tilstand (en situation) for parseren. Elementet E → E • + B indikerer for eksempel, at parseren har genkendt en streng svarende til E på inputstrømmen, og at den forventer at læse terminalsymbolet + efterfulgt af en anden streng, der svarer til ikke-terminal B.
Et emne som E → E + B • hvor markøren • er placeret yderst til højre for linealens højre del , betyder at hele den højre del er blevet genkendt som en afledning af det venstre symbol. En sådan genstand kræver derfor en reduktion.
Reglerne for formularen A → ε har kun et punkt A → •. Da ε betegner en tom streng, følger det faktisk, at • ε svarer til ε • hvilket svarer til •.
Det er ikke altid muligt at karakterisere parserens aktuelle tilstand med et enkelt element. I vores eksempel er der efter at have læst en streng svarende til en E faktisk to mulige situationer repræsenteret af elementerne: E → E • * B og E → E • + B.
Derfor karakteriserer vi analysatorens tilstand ikke ved et enkelt emne, men ved et sæt emner.
Efter vores eksempel er den aktuelle tilstand efter at have genkendt E det sæt {E → E • + B, E → E • * B}, som indikerer, at analysatoren er i stand til at læse symbolet + eller symbolet *.
Et emne med et punktum foran en ikke-terminal, såsom E → E + • B, indikerer at parseren forventer at finde denne ikke-terminal (i dette tilfælde B, i dette eksempel). For at sikre, at varesættet indeholder alle mulige regler, skal parseren indeholde alle de emner, der beskriver, hvordan denne ikke-terminale B skal parses. Dette betyder, at hvis der er regler som B → 0 og B → 1, skal varesættet også omfatte B → • 0 og B → • 1. Generelt kan det formuleres som:
Hvis der er et element i formularen A → v • Bw i varesættet , og hvis der er en regel med formularen B → w ', skal elementet B → • w' også findes i artikelsættet .Alle varesæt kan udvides, indtil de tilfredsstiller denne regel: Bliv ved med at tilføje de relevante emner, indtil alle ikke-terminaler forud for perioder tages i betragtning. Med andre ord tilføjes emner, indtil et fast punkt er nået (enhver tilføjelse i henhold til ovenstående regel efterlader sættet uændret). Den minimale udvidelse (det minimale faste punkt) kaldes lukning af et sæt emner, og vi vil skrive det ferm ( I ) hvor jeg er et sæt emner. Vi vil se nedenfor, at en tilstand af parseren af en grammatik er en lukning af emner. Kun lukninger, der er tilgængelige fra den oprindelige tilstand (den oprindelige lukning), overvejes i handlinger og forbindelsestabellen. Den oprindelige tilstand introduceres ved at tilføje en generisk regel som beskrevet i det følgende kapitel.
For at have en indledende lukning, der udgør parserens oprindelige tilstand, øges grammatikken med følgende regel:
(0) S → Ehvor S er det nye startsymbol og E den gamle. Parseren bruger denne regel til reduktion nøjagtigt, når den accepterer inputstrengen.
For vores eksempel vil vi tage den samme grammatik med denne stigning. Er:
(0) S → E (1) E → E * B (2) E → E + B (3) E → B (4) B → 0 (5) B → 1Det er med denne forstærkede grammatik, at vi vil bestemme sæt af varer og overgange mellem dem.
Det første trin i konstruktionen af en handlinger og grene-tabel består i at bestemme tilstande (sæt af lukkede emner) såvel som overgangene mellem disse tilstande i analysatorautomaten. Metoden består i at bestemme den oprindelige tilstand for denne automat og derefter gradvis beregne alle de tilgængelige tilstande. Overgange bestemmes som om denne automat kunne læse terminaler og ikke-terminaler.
Oprindelig tilstand. Den oprindelige tilstand for denne automat er lukningen af det første element i den tilføjede regel: S → • E:
Varesæt 0 S → • E + E → • E * B + E → • E + B + E → • B + B → • 0 + B → • 1'+' Foran elementerne angiver dem, der er tilføjet til lukningen. De originale genstande uden '+' kaldes kernen i varesættet.
Startende fra den oprindelige tilstand (Sæt af emner 0) bestemmer vi alle de tilstande, der kan nås ved en overgang (efterfølgere). Vi opnår derefter et nyt sæt stater, hvorfra vi starter igen for at bestemme nye efterfølgere. Dette gentages, indtil der opnås et fast punkt (som nødvendigvis nås, da antallet af lukninger er endeligt). Lad os specificere processen med at beregne overgange og efterfølgere.
Beregning af en overgang fra efterfølgerstaten.
De mulige overgange fra et sæt Q- emner kan findes ved at se i det sæt af emner på symbolerne (terminal og ikke-terminal), der er umiddelbart efter perioden. Hvis der er et sådant symbol, sig x, for at finde den tilstand (sæt af emner), som symbolet x fører fra tilstanden Q, fortsætter vi som følger:
I tilfælde af varesættet 0 er symbolerne umiddelbart efter perioden terminalerne '0' og '1' og ikke-terminalerne E og B. De resulterende overgange er som følger ...
For terminal '0' når overgangen successortilstanden:
Varesæt 1 B → 0 •og til terminal '1':
Varesæt 2 B → 1 •For ikke-terminal E:
Varesæt 3 S → E • + E → E • * B + E → E • + Bog for ikke-terminal B:
Varesæt 4 E → B •Lukning tilføjer ikke nye ting i alle tilfælde. Vi fortsætter proceduren, indtil intet andet sæt emner kan findes. Fra sæt af punkterne 1, 2 og 4 vil der ikke være nogen overgange, da intet punkt er foran et symbol. På den anden side for sæt 3, ser vi, at punktet er foran terminalerne '*' og '+'. Fra sæt af emner 3 (eller tilstand 3) fører symbolet '*' til overgangen til tilstand 5:
Varesæt 5 E → E * • B + B → • 0 + B → • 1og for '+' fører det til tilstand 6:
Varesæt 6 E → E + • B + B → • 0 + B → • 1For sæt af emner 5 skal vi overveje terminalerne '0' og '1' og den ikke-terminal B. For terminalerne ser vi, at sætene med lukkede emner henholdsvis er lig med sætene af emner 1 og 2 allerede bygget. For den ikke-terminale B giver overgangen:
Varesæt 7 E → E * B •For sæt af emner 6 skal vi også overveje terminalerne '0' og '1' og den ikke-terminal B. Som før er sæt af emneresultaterne for terminalerne lig med sætene af emner 1 og 2, der allerede er bygget . For ikke-terminal B fører overgangen til:
Varesæt 8 E → E + B •Disse sæt af emner 7 og 8 har ingen symboler bag deres punkter, og derfor er det slut, vi har nået et fast punkt. Overgangstabellen til automaten ser nu ud som:
| Sæt med genstande | * | + | 0 | 1 | E | B |
|---|---|---|---|---|---|---|
| 0 | 1 | 2 | 3 | 4 | ||
| 1 | ||||||
| 2 | ||||||
| 3 | 5 | 6 | ||||
| 4 | ||||||
| 5 | 1 | 2 | 7 | |||
| 6 | 1 | 2 | 8 | |||
| 7 | ||||||
| 8 |
Fra denne tabel og disse sæt varer bygger vi handlingstabellen og forgreningstabellen som følger:
Læseren kan verificere, at dette faktisk giver handlingstabellen og grenen, som vi så tidligere.
Bemærkning om LR (0) vs. SLR og LALRKun trin 4 i ovenstående procedure frembringer reduktionshandlinger, og derfor optager alle reduktionshandlinger hele rækker i tabellen, så reduktioner forekommer uanset det næste symbol i inputstrømmen. Dette er grunden til, at dette er LR (0) parseringstabellerne : de forventer ikke (det vil sige, de ser ikke på noget symbol på forhånd) for at beslutte, hvilken reduktion der skal foretages.
En grammatik, der har behov for forventning for at tydeliggøre reduktioner, har brug for rækker fra analysetabellen, der indeholder forskellige reduktionshandlinger i forskellige kolonner, og ovenstående procedure er ikke i stand til at oprette sådanne rækker.
Forbedringer af LR (0) -konstruktionsproceduren (såsom SLR og LALR ) kan konstruere reduktionshandlinger, der ikke optager hele rækker. De kan derfor analysere flere grammatikker end LR (0) parsers.
For at illustrere en sådan tvetydighed, lad os overveje denne meget enkle (berigede) grammatik (symbolet S spiller rollen som ACCEPTEN i det indledende eksempel):
som sigter mod at genkende den tomme streng ε eller strengen reducerer til x.
At vide, at i et emne • ε svarer til • starttilstanden for automaten baseret på varelukning er som følger:
S → • A $ A → • x A → •Det sidste punkt henviser til en reduktion, da markøren er til højre for en højre del. For det andet angiver det andet punkt, at analysatoren kan læse terminalsymbolet x. For at vælge mellem disse to muligheder har analysatoren behov for forventning. For en sådan grammatik vil det være et spørgsmål om at undersøge / høre indholdet af bufferens læstehoved (uden at fjerne det fra bufferen). Hvis en rapport indeholder et element af formularen N → ω • (hvor ω er et ord), og bufferens læstehoved indeholder et symbol s, som er et af terminalsymbolerne, der straks kan følge N, så udføres reduktionen. Ellers udfører man et skift. Dette forudsætter at man på forhånd beregner følgende symboler på en ikke-terminal. Her Følgende (A) = {$} og efter (0) har vi: Følger (S) = Følger (A) = {$}.
Antag for eksempel, at vi analyserer:
x $
I starten er stakken tom, bufferen indeholder x $ og dens læsehoved peger på x. Vi er i staten repræsenteret af de 3 punkter ovenfor. Emnet A → • kommanderer en øjeblikkelig reduktion, mens A → • x kommanderer et skift efter forbrug på x. Men x, symbol på legehovedet, tilhører ikke Followers (A) = {$}, hvilket betyder at x ikke er et symbol, der kan følge en afledning af A. Hvis vi reducerer i henhold til punkt A → • vil det betyde, at x kan følge A, i modsætning til det faktum, at kun $ kan følge A. Derfor kan vi ikke reducere i henhold til A → • og derfor anvender vi skiftet angivet med punkt A → • x. Så x stables og fjernes fra bufferen. X reduceres derefter til A. Derefter tages $ symbolet ud af bufferen og stables. Stakmønsteret A $ reduceres til S med en tom buffer, som afslutter analysen.
Automaten er konstrueret på en sådan måde, at den ikke garanteres at være deterministisk. Men når reduktionshandlinger føjes til handlingstabellen, kan det ske, at en celle allerede indeholder en offset-handling ( offset-reduktionskonflikt ) eller en reduktionshandling ( reduktion-reduktionskonflikt ). Vi kan dog bevise, at dette kun sker i grammatikker, der ikke er LR (0).
Offset / reduktionskonfliktEt lille eksempel på en ikke-LR (0) grammatik med en skiftreduktionskonflikt er:
(1) E → 1 E (2) E → 1Blandt sæt sæt finder vi følgende:
Varesæt 1 E → 1 • E E → 1 • E → • 1 E E → • 1Der er en forskydning / reduktionskonflikt, fordi analysatoren ifølge punkt E → 1 •, hvor markøren er helt til højre, skal foretage en reduktion (E er blevet genkendt). Men også i henhold til punkt E → • 1 (ellers E → • 1 E) skal analysatoren foretage et skift ved at forbruge terminal 1. Vi har derfor en forskydning / reduktionskonflikt.
Reduktion / reduktionskonfliktEt lille eksempel på en ikke-LR (0) grammatik med en reduktion-reduktionskonflikt er:
(1) E → A 1 (2) E → B 2 (3) A → 1 (4) B → 1I dette tilfælde opnår vi følgende sæt varer:
Varesæt 1 A → 1 • B → 1 •Der er en reduktion-reduktionskonflikt for dette sæt af emner, fordi der i cellerne i handlingstabellen for dette sæt af emner på samme tid ville være en reduktion med regel 3 og en anden med regel 4.
LøsningOvenstående to eksempler kan løses ved at lade parseren bruge et sæt sekvenser (se LL-parsing ) fra ikke-terminal A til at beslutte, om en af reglerne fra A skal anvendes til rabat; det vil anvende regel A → w for en reduktion ved følgende symbol i indgangsstrømmen er i alle suites A . Denne løsning fører til det, der kaldes SLR- analyse (simpel LR-analyse).