Logo
Unionpedia
Kommunikasjon
Tilgjengelig på Google Play
Ny! Last ned Unionpedia på din Android™-enhet!
Gratis
Raskere tilgang enn browser!
 

LR-parser

Index LR-parser

En LR-parser er innenfor informatikken betegnelsen på en type parser (syntaktisk analysator).

22 relasjoner: Bunnen-opp-parsing, CYK-algoritmen, Deterministiske kontekstfrie språk, Donald Knuth, Forbokstavord, Formell grammatikk, GLR-parser, GNU Bison, Informatikk, Kanonisk LR-parser, Kompilator-kompilator, Kontekstfri grammatikk, LALR-parser, LL-parser, Naturlig språk, Parsing, Programmeringsspråk, Rekursiv descendant parser, Simpel LR-parser, Tilbakesporing, Tre (datastruktur), Yacc.

Bunnen-opp-parsing

Bunnen-opp-parsing er en teknikk innen informatikk hvor man analyserer den grammatiske struturen til en lineært innmatet tekst, ved å identifisere og prosessere tekstens laveste nivå med detaljer først, før man går over til strukturer på det midterste nivå, og etterlater den overordnede struktur på høyeste nivå til slutt.

Ny!!: LR-parser og Bunnen-opp-parsing · Se mer »

CYK-algoritmen

Cocke-Younger-Kasami-algoritmen, vanligvis omtalt som CYK-algoritmen, er en algoritme som bestemmer hvorvidt en streng kan genereres av en gitt kontekstfri grammatikk og, i så fall, hvordan den kan genereres.

Ny!!: LR-parser og CYK-algoritmen · Se mer »

Deterministiske kontekstfrie språk

Deterministiske kontekstfrie språk er innenfor formell språkteori en delmengde av kontekstfrie språk.

Ny!!: LR-parser og Deterministiske kontekstfrie språk · Se mer »

Donald Knuth

Donald Ervin Knuth (født 10. januar 1938 i Milwaukee, Wisconsin, USA) er professor emeritus i informatikk ved Stanford University.

Ny!!: LR-parser og Donald Knuth · Se mer »

Forbokstavord

Forbokstavord eller initialord er forkortelser som er satt sammen av initialer.

Ny!!: LR-parser og Forbokstavord · Se mer »

Formell grammatikk

Formell grammatikk (også kalt kun grammatikk) er i teoretisk informatikk en mengde formasjonsregler som definerer hvilke strenger fra alfabetet til et formelt språk som er syntaktisk gyldige (det vil si grammatikalske) i dette språket.

Ny!!: LR-parser og Formell grammatikk · Se mer »

GLR-parser

GLR-parser er en forkortelse for Generalized LR, hvor L står for left-to-right (venstre-til-høyre og r står for rightmost. Det er en utvidelse av en LR-parser for å håndtere en ikke-deterministisk og tvetydig grammatikk. Det teoretiske grunnlaget for den ble gitt i 1974 i en avhandling av Bernard Lang, sammen med andre generelle kontekstfrie parsere slik som GLL. Avhandlingen beskriver en systematisk måte å lage slike algoritmer på, og uniforme resultater angående korrekthetsbevis, kompleksiteten med hensyn til grammatikkens klasser og optimaliseringsteknikker. Den første implementasjon av GLR ble beskrevet i 1984 av Masaru Tomita, og ble også kalt en parallell parser. Tomita presenterte fem stadier, selv om det andre stadium i praksis er anerkjent som GLR-parseren. Algoritmen har utviklet seg fra sin originale form, men prinsippene har forblitt uendret. Som vist i en publikasjon fra 1971, var Lang primært interessert i en enklere og mer fleksibel parser for utvidbare programmeringsspråk. Tomita's målsetning var å parse naturlige språk gjennomgående og effektivt. Alminnelige LR-parsere kan ikke håndtere den ikke-deterministiske og tvetydige natur hos naturlige språk, noe som GLR-parseren kan.

Ny!!: LR-parser og GLR-parser · Se mer »

GNU Bison

GNU Bison er en fri og åpen parsergenerator for Unix og Unix-liknende operativsystemer.

Ny!!: LR-parser og GNU Bison · Se mer »

Informatikk

Informatikk er et fagfelt med røtter i matematisk logikk, lingvistikk og elektroingeniørfag.

Ny!!: LR-parser og Informatikk · Se mer »

Kanonisk LR-parser

En kanonisk LR parser eller LR(1) parser er innenfor informatikken betegnelsen på en LR(k)-parser med k.

Ny!!: LR-parser og Kanonisk LR-parser · Se mer »

Kompilator-kompilator

Innen informatikk er en kompilator-kompilator eller kompilatorgenerator et programmeringsverktøy som frembringer en parser, en kommandotolk eller en kompilator ut fra en formell beskrivelse av et programmeringsspråk og en datamaskin.

Ny!!: LR-parser og Kompilator-kompilator · Se mer »

Kontekstfri grammatikk

Kontekstfri grammatikk er et sett med formelle regler som kan brukes til å beskrive og uttrykke både overordnet og detaljert struktur til språk og setninger.

Ny!!: LR-parser og Kontekstfri grammatikk · Se mer »

LALR-parser

En LALR-parser eller Look-Ahead LR-parser er innenfor informatikken benevnelsen på en forenklet versjon av en kanonisk LR parser.

Ny!!: LR-parser og LALR-parser · Se mer »

LL-parser

En LL-parser (Left to right, Leftmost derivation) er en toppen-ned-parser for en delmengde av konteksfrie språk.

Ny!!: LR-parser og LL-parser · Se mer »

Naturlig språk

Et naturlig språk er et språk som snakkes, skrives eller uttrykkes med tegn med det formål å kommunisere med andre mennesker.

Ny!!: LR-parser og Naturlig språk · Se mer »

Parsing

Parsing eller syntaktisk analyse er betegnelse på den prosess som analyserer en streng med symboler, enten i naturlige språk eller programmeringsspråk i henhold til reglene i en formell grammatikk.

Ny!!: LR-parser og Parsing · Se mer »

Programmeringsspråk

Hello, world!». Programmeringsspråk er en betegnelse som henviser et ikke-menneskelig og kunstig språk som benyttes utelukkende for å styre og kontrollere en datamaskin.

Ny!!: LR-parser og Programmeringsspråk · Se mer »

Rekursiv descendant parser

Innenfor informatikken er en rekursiv descendant parser en form for top-down parser som bygges fra et sett gjensidig rekursive prosedyrer, eller en ikke-rekursiv ekvivalent, hvor hver av prosedyrene implementerer en av produksjonene av grammatikken.

Ny!!: LR-parser og Rekursiv descendant parser · Se mer »

Simpel LR-parser

En simple LR-parser, eller SLR-parser, er innen informatikken en type LR-parser med små parsertabeller og en relativt enkel algoritme for parsergenerering.

Ny!!: LR-parser og Simpel LR-parser · Se mer »

Tilbakesporing

Tilbakesporing eller bactracking er en generell algoritme for å finne alle (eller noen) løsninger på enkelte beregningsproblemer, deriblant problemer som tilfredsstiller begrensninger, som inkrementelt bygger opp kandidater til løsninger, og som forkaster enhver delvis kandidat c så snart som det oppdages at c ikke kan fullføre en gyldig løsning.

Ny!!: LR-parser og Tilbakesporing · Se mer »

Tre (datastruktur)

right Trær er en av de mest brukte datastrukturene innenfor informatikken.

Ny!!: LR-parser og Tre (datastruktur) · Se mer »

Yacc

Yacc, forkortelse for «Yet Another Compiler Compiler», er et dataprogram for Unix og Unix-liknende operativsystemer.

Ny!!: LR-parser og Yacc · Se mer »

UtgåendeInnkommende
Hey! Vi er på Facebook nå! »