LALR-analysator - LALR parser

Inom datavetenskap är en LALR-parser eller Look-Ahead LR-parser en förenklad version av en kanonisk LR-parser för att analysera en text enligt en uppsättning produktionsregler som anges i en formell grammatik för ett datorspråk . ("LR" betyder avledning från vänster till höger, längst till höger .)

LALR-analysatorn uppfanns av Frank DeRemer i sin doktorsavhandling 1969, Praktiska översättare för LR (k) -språk , i sin behandling av de praktiska svårigheterna vid den tiden för att implementera LR (1) -parsers. Han visade att LALR-parseraren har mer språkigenkänningsförmåga än LR (0) -parseraren, samtidigt som det kräver samma antal tillstånd som LR (0) -parseraren för ett språk som kan kännas igen av båda parsrarna. Detta gör LALR-tolkaren till ett minneseffektivt alternativ till LR (1) -tolkaren för språk som är LALR. Det bevisades också att det finns LR (1) språk som inte är LALR. Trots denna svaghet är kraften i LALR-analysatorn tillräcklig för många vanliga datorspråk, inklusive Java , även om referensgrammatiken för många språk inte är LALR på grund av att den är tvetydig .

Den ursprungliga avhandlingen gav ingen algoritm för att konstruera en sådan analysator med en formell grammatik. De första algoritmerna för LALR-parsergenerering publicerades 1973. 1982 publicerade DeRemer och Tom Pennello en algoritm som genererade mycket minneseffektiva LALR-parsers. LALR-tolkare kan genereras automatiskt från en grammatik av en LALR-tolkningsgenerator som Yacc eller GNU Bison . Den automatiskt genererade koden kan förstärkas med handskriven kod för att öka kraften i den resulterande tolkaren.

Historia

1965 uppfann Donald Knuth LR-parsern ( L eft to Right, R ightmost derivation ). LR-analysatorn kan känna igen vilket deterministiskt sammanhangsfritt språk som helst i linjär avgränsad tid. Den högsta avledningen har mycket stora minneskrav och att implementera en LR-parser var opraktiskt på grund av det begränsade minnet på datorer vid den tiden. För att lösa denna brist föreslog Frank DeRemer 1969 två förenklade versioner av LR-parsern, nämligen Look-Ahead LR (LALR) och Simple LR-parseraren som hade mycket lägre minneskrav till kostnaden för mindre språkigenkänningseffekt, med LALR-analysatorn är det mest kraftfulla alternativet. 1977 uppfanns minnesoptimeringar för LR-parsern, men ändå var LR-parsern mindre minne än de förenklade alternativen.

1979 tillkännagav Frank DeRemer och Tom Pennello en serie optimeringar för LALR-parsern som ytterligare skulle förbättra dess minneseffektivitet. Deras arbete publicerades 1982.

Översikt

I allmänhet hänvisar LALR-tolkaren till LALR (1) -tolkaren, precis som LR-tolkaren i allmänhet avser LR (1) -tolkaren. "(1)" betecknar en-token lookahead för att lösa skillnader mellan regelmönster under parsning. På samma sätt finns det en LALR (2) parser med två-token lookahead och LALR ( k ) parsers med k- token lookup, men dessa är sällsynta vid faktisk användning. LALR-parsern är baserad på LR (0) -parsern, så den kan också betecknas LALR (1) = LA (1) LR (0) (1 symbol för lookahead, LR (0)) eller mer generellt LALR ( k ) = LA ( k ) LR (0) (k symboler för lookahead, LR (0)). Det finns faktiskt en tvåparametrarfamilj av LA ( k ) LR ( j ) parsers för alla kombinationer av j och k , som kan härledas från LR ( j  +  k ) parser, men dessa ser inte praktisk användning.

Som med andra typer av LR-parsers är en LALR-parser ganska effektiv när det gäller att hitta den enda korrekta nedifrån och upp-analysen i en enda vänster-till-höger-skanning över ingångsströmmen, eftersom den inte behöver använda backtracking . Att vara en lookahead-analysator per definition använder den alltid en lookahead, med LALR (1) som det vanligaste fallet.

Förhållande till andra analysatorer

LR-analysatorer

LALR (1) tolkaren är mindre kraftfull än LR (1) tolkaren och mer kraftfull än SLR (1) tolkaren, även om de alla använder samma produktionsregler . Förenklingen som LALR-parsern introducerar består i att slå samman regler som har identiska kärnobjektuppsättningar , eftersom under LR (0) tillståndsbyggnadsprocessen är lookaheads inte kända. Detta minskar parserens kraft eftersom det inte känner till lookahead-symbolerna kan förvirra parsern om vilken grammatikregel som ska väljas nästa, vilket resulterar i att minska / minska konflikter . Alla konflikter som uppstår vid tillämpning av en LALR (1) parser på en entydig LR (1) -grammatik reducerar / minskar konflikter. SLR (1) parser utför ytterligare sammanslagning, vilket introducerar ytterligare konflikter.

Standardexemplet på en LR (1) -grammatik som inte kan analyseras med LALR (1) -parseraren, som uppvisar en sådan minskning / minskning av konflikt, är: 

  S → a E c
    → a F d
    → b F c
    → b E d
  E → e
  F → e

I LALR-tabellkonstruktionen kommer två stater att slås ihop till ett tillstånd och senare kommer utseendeshuvuden att vara tvetydiga. Den enda staten med lookaheads är: 

  E → e. {c,d}
  F → e. {c,d}

En LR (1) parser skapar två olika tillstånd (med icke-motstridiga lookaheads), som inte är tvetydiga. I en LALR-analysator har denna stat motstridiga handlingar (med tanke på lookahead c eller d, reducera till E eller F), en "minska / minska konflikt"; ovanstående grammatik kommer att förklaras tvetydig av en LALR-analysator och konflikter kommer att rapporteras.

För att återhämta sig löses denna tvetydighet genom att välja E, eftersom den förekommer före F i grammatiken. Den resulterande tolkaren kommer emellertid inte att kunna känna igen den giltiga ingångssekvensen b e c, eftersom den tvetydiga sekvensen e creduceras till (E → e) csnarare än rätt (F → e) c, men b E cinte finns i grammatiken.

LL-analysatorer

LALR ( j ) parsers är ojämförliga med LL ( k ) parsers : för alla j och k båda större än 0 finns LALR ( j ) grammatik som inte är LL ( k ) grammatik och omvänt. I själva verket är det obestämbart om en given LL (1) -grammatik är LALR ( k ) för någon .

Beroende på förekomsten av tomma derivat kan en LL (1) -grammatik vara lika med en SLR (1) eller en LALR (1) -grammatik. Om LL (1) -grammatiken inte har några tomma härledningar är det SLR (1) och om alla symboler med tomma härledningar har icke-tomma härledningar är det LALR (1). Om det finns symboler som bara har en tom härledning kan grammatiken vara eller inte vara LALR (1).

Se även

Anteckningar

Referenser

externa länkar

  • Parsing Simulator Denna simulator används för att generera parsingtabeller LALR och lösa bokens övningar.
  • JS / CC JavaScript-baserad implementering av en LALR (1) parsergenerator, som kan köras i en webbläsare eller från kommandoraden.
  • LALR (1) tutorial , en flash-kortliknande tutorial om LALR (1) parsing.