LR parser ( eng. LR parser ) er en parser til kildekoderne for programmer skrevet i et eller andet programmeringssprog, der læser inputstrømmen fra venstre (Venstre ) til højre og producerer den længst til højre (Højre ) produktion af en kontekstfri grammatik . Udtrykket LR( k )-analyzer bruges også , hvor k udtrykker antallet af ulæste preview -tegn i inputstrømmen, på baggrund af hvilke beslutninger træffes under analysen. Normalt er k 1 og udelades ofte.
Syntaksen for mange programmeringssprog kan defineres af en grammatik, der er LR(1) eller tæt på den, og af denne grund bruges LR-parsere ofte af compilere til at udføre kildekodeparsing.
Typisk henvises der til en parser i forhold til navnet på det sprog, hvis kildekode den analyserer, for eksempel "C++ parser" parser C++ kildekode .
En LR-parser kan genereres ud fra en kontekstfri grammatik af et program kaldet en parser-generator , eller den kan skrives i hånden af en programmør. En kontekstfri grammatik klassificeres som LR( k ), hvis der er en LR( k )-parser for den, som bestemt af parser-generatoren.
LR-parseren siges at være bottom-up-parsing , fordi den forsøger at udlede produktionen af grammatikken på øverste niveau ved at bygge den ud af blade .
Et deterministisk kontekstfrit sprog er et sprog, som der er en form for LR( k ) grammatik for. Hver LR( k ) grammatik kan automatisk konverteres til en LR( 1 ) grammatik for det samme sprog, mens LR( 0 ) grammatik for nogle sprog muligvis ikke eksisterer. LR( 0 )-sprog er deres egen undergruppe af deterministiske.
En LR-parser er baseret på en algoritme drevet af en parse-tabel , en datastruktur, der indeholder syntaksen for det parsede sprog. Så udtrykket LR-parser refererer faktisk til en klasse af parsere, der kan parse næsten ethvert programmeringssprog, som en parse-tabel er tilvejebragt for. Parsetabellen genereres af parsergeneratoren.
LR-parsing kan generaliseres som vilkårlig parsing af et kontekstfrit sprog uden tab af ydeevne, selv for LR(k)-grammatikker. Dette skyldes, at de fleste programmeringssprog kan udtrykkes med en LR( k ) grammatik, hvor k er en lille konstant (normalt 1). Bemærk, at parsing af ikke-LR(k) grammatikker er en størrelsesorden langsommere (kubisk i stedet for kvadratisk med hensyn til inputstrømstørrelse).
LR-parsing kan anvendes på flere sprog end LL-parsing og er også bedre til fejlrapportering, hvilket betyder, at den registrerer syntaksfejl, hvor inputtet ikke matcher grammatikken så tidligt som muligt. I modsætning hertil kan LL(k) (eller værre, selv LL(*))-parsere forsinke detektering af en fejl til en anden gren af grammatikken på grund af rollback, hvilket ofte gør det vanskeligt at lokalisere en fejl på steder med almindelige lange præfikser.
LR-parsere er vanskelige at skabe i hånden og er normalt skabt af en parser-generator eller compiler-kompiler . Afhængigt af hvordan parsetabellen blev oprettet, kan disse parsere kaldes simple LR-parsere (SLR), lookahead LR-parsere (LALR) eller kanoniske LR-parsere . LALR-parsere har betydeligt større genkendelseskraft end SLR-parsere . Samtidig har tabeller til SLR-analyse samme størrelse som til LALR-analyse, hvorfor SLR-analyse ikke længere bruges. Kanoniske LR-parsere har lidt mere genkendelseskraft end LALR-parsere, men kræver meget mere tabelhukommelse, så de bruges sjældent. .
| Formelle sprog og formelle grammatikker | |
|---|---|
| Generelle begreber | |
| Type 0 | |
| Type 1 |
|
| Type 2 | |
| Type 3 |
|
| parsing | |