Canonical LR-analysator - Canonical LR parser

I datavetenskap är en kanonisk LR-parser eller LR (1) parser en LR (k) parser för k = 1 , dvs med en enda lookahead- terminal . Den speciella egenskapen hos denna parser är att alla LR (k) grammatik med k> 1 kan omvandlas till en LR (1) grammatik. Dock krävs ryggbyten för att minska k och när ryggbyten ökar kan grammatiken snabbt bli stor, repetitiv och svår att förstå. LR (k) kan hantera alla deterministiska sammanhangsfria språk . Tidigare har denna LR (k) parser undvikits på grund av dess enorma minneskrav till förmån för mindre kraftfulla alternativ som LALR och LL (1) parser. Nyligen erbjuds emellertid en "minimal LR (1) parser" vars utrymmeskrav är nära LALR parsers, av flera parsergeneratorer.

Som de flesta parsers genereras LR (1) -parsern automatiskt av kompilator-kompilatorer som GNU Bison , MSTA, Menhir, HYACC ,.

Historia

1965 uppfann Donald Knuth LR (k) parser ( L eft to right, R ightmost derivation parser) en typ av skiftreducerande parser , som en generalisering av befintliga prioritetsparsrar . Denna analysator har potential att känna igen alla deterministiska sammanhangsfria språk och kan producera både vänster och höger härledning av uttalanden som påträffas i inmatningsfilen. Knuth bevisade att den når sin maximala språkigenkänningseffekt för k = 1 och tillhandahöll en metod för att omvandla LR (k), k> 1 grammatik till LR (1) grammatik.

Canonical LR (1) parsers har den praktiska nackdelen att de har enorma minneskrav för sin interna parser-tabellrepresentation. År 1969 föreslog Frank DeRemer två förenklade versioner av LR-parsern som heter LALR och SLR . Dessa parsers kräver mycket mindre minne än Canonical LR (1) parsers, men har något mindre språkigenkänningskraft. LALR (1) parsers har varit de vanligaste implementeringarna av LR Parser.

En ny typ av LR (1) parser, vissa kallar en "Minimal LR (1) parser" introducerades dock 1977 av David Pager som visade att LR (1) parsers kan skapas vars minneskrav är lika med LALR ( 1) tolkare. Nyligen erbjuder vissa parsergeneratorer Minimal LR (1) parsers, som inte bara löser minneskravsproblemet utan också det mystiska konfliktproblemet som ligger i LALR (1) parsergeneratorer. Dessutom kan Minimal LR (1) parsers använda skiftreducerande åtgärder, vilket gör dem snabbare än Canonical LR (1) parsers.

Översikt

LR (1) parseraren är en deterministisk automat och som sådan är dess operation baserad på övergångstabeller för statiskt tillstånd . Dessa kodifierar grammatiken för det språk som den känner igen och kallas vanligtvis "tolkningstabeller".

Tolkningstabellerna för LR (1) -tolkaren är parametrerade med en lookahead-terminal. Enkla tolkningstabeller, som de som används av LR (0) tolkaren, representerar grammatikregler i formuläret

A1 → A, B

vilket innebär att om vi går från tillstånd A till tillstånd B så går vi till tillstånd A1 . Efter att ha parametrerat en sådan regel med en lookahead har vi:

A1 → A, B, a

vilket innebär att övergången nu endast kommer att utföras om lookahead-terminalen är a . Detta möjliggör rikare språk där en enkel regel kan ha olika betydelser beroende på lookahead-sammanhanget. Till exempel, i en LR (1) -grammatik, övergår alla följande regler till ett annat tillstånd trots att de är baserade på samma tillståndssekvens.

A1 → A, B, a
A2 → A, B, b
A3 → A, B, c
A4 → A, B, d

Detsamma skulle inte vara sant om en lookahead-terminal inte togs med i beräkningen. Tolkningsfel kan identifieras utan att tolkaren behöver läsa hela inmatningen genom att förklara vissa regler som fel. Till exempel,

E1 → B, C, d

kan förklaras som ett fel, vilket gör att tolkaren stannar. Detta innebär att lookahead-informationen också kan användas för att fånga fel, som i följande exempel:

A1 → A, B, a
A1 → A, B, b
A1 → A, B, c
E1 → A, B, d

I detta fall A, B kommer att reduceras till A1 när lookahead är a, b eller c och ett fel kommer att rapporteras när lookahead är d.

Lookahead kan också vara till hjälp när man bestämmer när en regel ska minskas. Lookahead kan hjälpa till att undvika att minska en specifik regel om lookahead inte är giltigt, vilket sannolikt skulle innebära att det nuvarande läget ska kombineras med följande istället för det tidigare tillståndet. Det betyder i följande exempel

  • Tillståndssekvens: A, B, C
  • Regler:
A1 → A, B
A2 → B, C

tillståndssekvensen kan reduceras till

A, A2

istället för

A1, C

om lookahead efter att parsern gick till tillstånd B inte var acceptabelt, dvs ingen övergångsregel existerade. Stater kan produceras direkt från en terminal som i

X → y

vilket tillåter tillståndssekvenser att visas.

LR (1) parsers har krav på att varje regel ska uttryckas på ett fullständigt LR (1) sätt, dvs en sekvens av två tillstånd med en specifik lookahead. Det gör enkla regler som

X → y

kräver ett stort antal konstgjorda regler som i huvudsak räknar upp kombinationerna av alla möjliga tillstånd och lookahead-terminaler som kan följa. Ett liknande problem visas för att implementera icke-lookahead-regler som

A1 → A, B

där alla möjliga lookaheads måste räknas upp. Det är anledningen till att LR (1) parsers inte kan implementeras praktiskt utan betydande minnesoptimeringar.

Konstruera LR (1) tolkningstabeller

LR (1) tolkningstabeller är konstruerade på samma sätt som LR (0) tolkningstabeller med ändringen att varje artikel innehåller en lookahead- terminal . Detta innebär, i motsats till LR (0) parsers, kan en annan åtgärd utföras om objektet som ska bearbetas följs av en annan terminal.

Parserobjekt

Med utgångspunkt från produktionsreglerna för ett språk måste först uppsättningarna för detta språk bestämmas. Med enkla ord är en artikeluppsättning en lista över produktionsregler som den för närvarande bearbetade symbolen kan vara en del av. En artikeluppsättning har en-till-en-korrespondens till en parsertillstånd, medan objekten i uppsättningen, tillsammans med nästa symbol, används för att bestämma vilka tillståndsövergångar och parseråtgärder som ska tillämpas. Varje objekt innehåller en markör för att notera vid vilken tidpunkt den för närvarande bearbetade symbolen visas i den regel som objektet representerar. För LR (1) parsers är varje artikel specifik för en lookahead-terminal, så lookahead-terminalen har också noterats i varje artikel.

Antag till exempel ett språk som består av terminalsymbolerna 'n', '+', '(', ')', icke-terminalerna 'E', 'T', startregeln 'S' och följande produktionsregler:

S → E
E → T
E → (E)
T → n
T → + T
T → T + n

Objektuppsättningar kommer att genereras analogt med proceduren för LR (0) parsers. Objektuppsättningen 0 som representerar det ursprungliga tillståndet skapas från startregeln:

[S → • E, $]

Punkt "•" betecknar markören för den aktuella analyseringspositionen inom denna regel. Den förväntade terminalen för lookahead för att tillämpa denna regel noteras efter komma. Tecknet '$' används för att beteckna 'slutet av inmatningen' förväntas, vilket är fallet för startregeln.

Detta är dock inte den kompletta uppsättningen 0. Varje artikeluppsättning måste vara "stängd", vilket innebär att alla produktionsregler för varje icke-terminal efter ett "•" måste inkluderas rekursivt i artikeluppsättningen tills alla dessa icke-terminaler behandlas. Den resulterande artikeluppsättningen kallas för stängning av artikeluppsättningen vi började med.

För LR (1) för varje produktionsregel måste ett objekt inkluderas för varje möjlig lookahead-terminal som följer regeln. För mer komplexa språk resulterar detta vanligtvis i mycket stora objektuppsättningar, vilket är anledningen till de stora minneskraven för LR (1) parsers.

I vårt exempel kräver startsymbolen den icke-terminala "E" som i sin tur kräver "T", alltså kommer alla produktionsregler att visas i artikeluppsättning 0. Först ignorerar vi problemet med att hitta lookaheads och tittar bara på fallet med en LR (0), vars artiklar inte innehåller lookahead-terminaler. Så uppsättningen 0 (utan lookaheads) kommer att se ut så här:

[S → • E]
[E → • T]
[E → • (E)]
[T → • n]
[T → • + T]
[T → • T + n]

FÖRSTA och FÖLJ uppsättningar

För att bestämma lookahead-terminaler används så kallade FIRST- och FOLLOW-uppsättningar. FÖRSTA (A) är den uppsättning terminaler som kan visas som det första elementet i alla reglerkedjor som matchar icke-terminal A. FÖLJ (I) av en artikel I [A → α • B β, x] är den uppsättning terminaler som kan visas omedelbart efter icke-terminal B, där α, β är godtyckliga symbolsträngar och x är en godtycklig lookahead-terminal. FÖLJ (k, B) för en artikeluppsättning k och en icke-terminal B är föreningen av följande uppsättningar av alla föremål i k där '•' följs av B. De FÖRSTA uppsättningarna kan bestämmas direkt från stängningen av alla icke-terminaler i språket, medan FÖLJ uppsättningarna bestäms av de objekt som används av de FÖRSTA uppsättningarna.

I vårt exempel, som man kan verifiera från hela listan med artikeluppsättningar nedan, är de första uppsättningarna:

FÖRSTA (S) = {n, '+', '('}
FÖRSTA (E) = {n, '+', '('}
FÖRSTA (T) = {n, '+'}

Bestämma terminaler för lookahead

Inom artikeluppsättning 0 kan följande uppsättningar hittas:

FÖLJ (0, S) = {$}
FÖLJ (0, E) = {$, ')'}
FÖLJ (0, T) = {$, '+', ')'}

Från detta kan hela artikeluppsättningen 0 för en LR (1) parser skapas genom att skapa för varje artikel i LR (0) artikeln en kopia för varje terminal i följande uppsättning av LHS-terminalen. Varje element i följande uppsättning kan vara en giltig lookahead-terminal:

[S → • E, $]
[E → • T, $]
[E → • T,)]
[E → • (E), $]
[E → • (E),)]
[T → • n, $]
[T → • n, +]
[T → • n,)]
[T → • + T, $]
[T → • + T, +]
[T → • + T,)]
[T → • T + n, $]
[T → • T + n, +]
[T → • T + n,)]

Skapa nya artikeluppsättningar

Resten av artikeluppsättningarna kan skapas med följande algoritm

1. För varje terminal och icke-terminal symbol A som visas efter ett '•' i varje redan existerande artikeluppsättning k, skapa en ny artikeluppsättning m genom att lägga till m alla reglerna för k där '•' följs av A, men bara om m kommer inte att vara samma som ett redan existerande objekt som ställts in efter steg 3.
2. flytta alla '•' för varje regel i det nya objektet och sätt en symbol till höger
3. skapa stängningen av den nya artikeluppsättningen
4. Upprepa från steg 1 för alla nyskapade artikeluppsättningar tills inga fler uppsättningar visas

I exemplet får vi ytterligare 5 uppsättningar från artikeluppsättning 0, artikeluppsättning 1 för icke-terminal E, artikeluppsättning 2 för icke-terminal T, artikeluppsättning 3 för terminal n, artikeluppsättning 4 för terminal '+' och artikeluppsättning 5 för '(' .

Artikeluppsättning 1 (E):

[S → E •, $]

Artikeluppsättning 2 (T):

[E → T •, $]
[T → T • + n, $]
[T → T • + n, +]
·
·
·

Artikeluppsättning 3 (n):

[T → n •, $]
[T → n •, +]
[T → n •,)]

Artikeluppsättning 4 ('+'):

[T → + • T, $]
[T → + • T, +]
[T → • n, $]
[T → • n, +]
[T → • + T, $]
[T → • + T, +]
[T → • T + n, $]
[T → • T + n, +]
·
·
·

Artikeluppsättning 5 ('('):

[E → (• E), $]
[E → • T,)]
[E → • (E),)]
[T → • n,)]
[T → • n, +]
[T → • + T,)]
[T → • + T, +]
[T → • T + n,)]
[T → • T + n, +]
·
·
·

Från artikeluppsättningarna 2, 4 och 5 kommer flera objektuppsättningar att produceras. Den fullständiga listan är ganska lång och kommer därför inte att anges här. Detaljerad LR (k) -behandling av denna grammatik finns t.ex. i [1] .

Gå till

Utseendet på ett LR (1) -objekt används bara direkt när man överväger att minska åtgärder (dvs. när • markören är i höger ände).

Den kärnan av en LR (1) objekt [S → a A • B e, c] är LR (0) objektet S → a A • B e. Olika LR (1) -artiklar kan dela samma kärna.

Till exempel i artikeluppsättning 2

[E → T •, $]
[T → T • + n, $]
[T → T • + n, +]

parsern krävs för att utföra reduktionen [E → T] om nästa symbol är '$', men att göra ett skift om nästa symbol är '+'. Observera att en LR (0) -tolk inte skulle kunna fatta detta beslut, eftersom den bara tar hänsyn till kärnan i artiklarna och därmed skulle rapportera en förändring / minskad konflikt.

Ett tillstånd som innehåller [A → α • X β, a] kommer att flytta till ett tillstånd som innehåller [A → α X • β, a] med etiketten X.

Varje stat har övergångar enligt Goto.

Skiftåtgärder

Om [A → α • b β, a] är i tillstånd I k och I k flyttar till tillstånd I m med etikett b, så lägger vi till åtgärden

action [I k , b] = "shift m"

Minska åtgärder

Om [A → α •, a] är i tillstånd I k , då vi lägga åtgärden

åtgärd [I k , a] = "minska A → α"

Referenser

externa länkar