LALR(1)

Den aktuelle version af siden er endnu ikke blevet gennemgået af erfarne bidragydere og kan afvige væsentligt fra den version , der blev gennemgået den 23. marts 2019; checks kræver 2 redigeringer .

LALR (1) (LA fra engelsk lookahead - preview) - bottom-up parsing algoritme .

Det er en udvidelse af SLR(1) -algoritmen . I nogle tilfælde fungerer det, når det ikke er muligt at bygge en SLR(1)-parse-tabel for en given grammatik på grund af skift-reducer eller reducer-reducer konflikter. Således er klassen af grammatikker parset af LALR(1) bredere end klassen af SLR(1) grammatikker.

Parsingalgoritmen (udførelse af analysatoren i henhold til inputstrømmen) er den samme for både LALR(1) og SLR(1) og er bredere end for LR(0) . Kun algoritmerne til at konstruere parsetabellen ved hjælp af grammatik i processen med at generere analysatoren er forskellige.

Beskrivelse

Lad der være en grammatik, der ikke er parset på grund af skift-reducer eller fold-reducer konflikter ved hjælp af SLR(1) algoritmen.

I dette tilfælde transformeres grammatikken som følger:

den ikke-terminal, hvorpå foldningen, der forårsagede konflikten, opstod, søges. Lad os kalde det A.
nye ikke-terminaler A1, A2, …, An introduceres, en for hver forekomst af A i højre side af reglerne.
overalt i de rigtige dele af reglerne erstattes A med den tilsvarende Ak.
regelsættet med A til venstre gentages n gange for hver Ak.
regler med et A på venstre side fjernes, og dermed fjernes A fra grammatikken.

For den transformerede grammatik (den er isomorf i forhold til den originale), forsøges der at bygge en SLR(1)-parsetabel.

Handlingen er baseret på det faktum, at Follow(A) er foreningen af alle Follow(Ak). I hver specifik tilstand har den nye grammatik ikke længere A, men en af Ak, det vil sige, at Follow-sættet for denne tilstand har færre elementer end for A i den originale grammatik.

Dette resulterer i færre forsøg for LALR(1) på at sætte en "cast" i en celle i parsing-tabellen, hvilket reducerer risikoen for konflikter med casts, nogle gange helt af med dem, og laver en grammatik, der ikke parses af SLR (1) parset efter transformationer.

Sættet Follow(Ak) kaldes lookahead-sættet for A og k-te møde i reglerne, deraf navnet på algoritmen.

LALR(1) og fuld LR(1)

Skift-reducer og fold-reducer konflikter kan forblive efter LALR(1) grammatiktransformationen. Dette betyder, at der er behov for en fuld LR(1)-parser til denne grammatik, som er meget mere kompleks (LR(0)/SLR(1)/LALR(1)-algoritmerne bevarer absolut ingen information om den allerede parsede del af inputstrømmen, mens som fuld LR(1) gør, og derfor vanskeligere), men kan parse enhver kontekstfri entydig grammatik.

Ifølge nogle oplysninger (specificer!), kan alle LL(1) -grammatikker konverteres til en form, der er parset af LALR(1).

Praktisk anvendelse

Anvendes i parsergeneratoren yacc og dens derivater, såsom GNU bison.

Størstedelen af faktisk brugte programmeringssprog har LALR(1)-grammatikker, det vil sige, at denne type parsere er nok til at parse de fleste af de virkelig brugte sprog.

GNU C-kompileren bruger yacc til at bygge parseren. Måske (tilstedeværelsen af strengen grammar.y og yacc i kroppen af det eksekverbare modul), gør Microsoft det samme for at bygge sin C-compiler .