Get it on Google Play
New! Download Unionpedia on your Androidâ„¢ device!
Faster access than browser!

LR parser

+ Save concept

In computer science, LR parsers are a type of bottom-up parser that efficiently read deterministic context-free languages, in guaranteed linear time. [1]

44 relations: Alphabet (formal languages), Ambiguous grammar, Backtracking, Bottom-up parsing, Cambridge University Press, Canonical LR parser, Compiler-compiler, Computer language, Computer science, Context-free grammar, Context-free language, CYK algorithm, Dangling else, Deterministic context-free language, Donald Knuth, Earley parser, Emphasis (typography), Englewood Cliffs, New Jersey, Finite-state machine, Formal grammar, GLR parser, GNU bison, LALR parser, Left corner parser, Lexical analysis, LL parser, Morgan Kaufmann Publishers, Operator-precedence parser, Parse tree, Parsing, Prentice Hall, Prolog, Recursive ascent parser, Recursive descent parser, Shift-reduce parser, Simple LR parser, Simple precedence parser, SLR grammar, Stack (abstract data type), Substring, Symbol (formal), Terminal and nonterminal symbols, Top-down parsing, Yacc.

Alphabet (formal languages)

In formal language theory, a string is defined as a finite sequence of members of an underlying base set; this set is called the alphabet of a string or collection of strings.

New!!: LR parser and Alphabet (formal languages) · See more »

Ambiguous grammar

In computer science, an ambiguous grammar is a context-free grammar for which there exists a string that can have more than one leftmost derivation or parse tree, while an unambiguous grammar is a context-free grammar for which every valid string has a unique leftmost derivation or parse tree.

New!!: LR parser and Ambiguous grammar · See more »


Backtracking is a general algorithm for finding all (or some) solutions to some computational problems, notably constraint satisfaction problems, that incrementally builds candidates to the solutions, and abandons a candidate ("backtracks") as soon as it determines that the candidate cannot possibly be completed to a valid solution.

New!!: LR parser and Backtracking · See more »

Bottom-up parsing

In computer science, parsing reveals the grammatical structure of linear input text, as a first step in working out its meaning.

New!!: LR parser and Bottom-up parsing · See more »

Cambridge University Press

Cambridge University Press (CUP) is the publishing business of the University of Cambridge.

New!!: LR parser and Cambridge University Press · See more »

Canonical LR parser

In computer science, a canonical LR parser or LR(1) parser is an LR(k) parser for k.

New!!: LR parser and Canonical LR parser · See more »


In computer science, a compiler-compiler or compiler generator is a programming tool that creates a parser, interpreter, or compiler from some form of formal description of a language and machine.

New!!: LR parser and Compiler-compiler · See more »

Computer language

A computer language is a method of communication with a computer.

New!!: LR parser and Computer language · See more »

Computer science

Computer science deals with the theoretical foundations of information and computation, together with practical techniques for the implementation and application of these foundations.

New!!: LR parser and Computer science · See more »

Context-free grammar

In formal language theory, a context-free grammar (CFG) is a certain type of formal grammar: a set of production rules that describe all possible strings in a given formal language.

New!!: LR parser and Context-free grammar · See more »

Context-free language

In formal language theory, a context-free language (CFL) is a language generated by a context-free grammar (CFG).

New!!: LR parser and Context-free language · See more »

CYK algorithm

In computer science, the Cocke–Younger–Kasami algorithm (alternatively called CYK, or CKY) is a parsing algorithm for context-free grammars, named after its inventors, John Cocke, Daniel Younger and Tadao Kasami.

New!!: LR parser and CYK algorithm · See more »

Dangling else

The dangling else is a problem in computer programming in which an optional else clause in an if–then(–else) statement results in nested conditionals being ambiguous.

New!!: LR parser and Dangling else · See more »

Deterministic context-free language

In formal language theory, deterministic context-free languages (DCFL) are a proper subset of context-free languages.

New!!: LR parser and Deterministic context-free language · See more »

Donald Knuth

Donald Ervin Knuth (born January 10, 1938) is an American computer scientist, mathematician, and professor emeritus at Stanford University.

New!!: LR parser and Donald Knuth · See more »

Earley parser

In computer science, the Earley parser is an algorithm for parsing strings that belong to a given context-free language, though (depending on the variant) it may suffer problems with certain nullable grammars.

New!!: LR parser and Earley parser · See more »

Emphasis (typography)

In typography, emphasis is the strengthening of words in a text with a font in a different style from the rest of the text, to highlight them.

New!!: LR parser and Emphasis (typography) · See more »

Englewood Cliffs, New Jersey

Englewood Cliffs is a borough in Bergen County, New Jersey, United States.

New!!: LR parser and Englewood Cliffs, New Jersey · See more »

Finite-state machine

A finite-state machine (FSM) or finite-state automaton (FSA, plural: automata), finite automaton, or simply a state machine, is a mathematical model of computation.

New!!: LR parser and Finite-state machine · See more »

Formal grammar

In formal language theory, a grammar (when the context is not given, often called a formal grammar for clarity) is a set of production rules for strings in a formal language.

New!!: LR parser and Formal grammar · See more »

GLR parser

A GLR parser (GLR standing for "generalized LR", where L stands for "left-to-right" and R stands for "rightmost (derivation)") is an extension of an LR parser algorithm to handle nondeterministic and ambiguous grammars.

New!!: LR parser and GLR parser · See more »

GNU bison

GNU bison, commonly known as Bison, is a parser generator that is part of the GNU Project.

New!!: LR parser and GNU bison · See more »

LALR parser

In computer science, an LALR parser or Look-Ahead LR parser is a simplified version of a canonical LR parser, to parse (separate and analyze) a text according to a set of production rules specified by a formal grammar for a computer language.

New!!: LR parser and LALR parser · See more »

Left corner parser

In computer science, a left corner parser is a type of chart parser used for parsing context-free grammars.

New!!: LR parser and Left corner parser · See more »

Lexical analysis

In computer science, lexical analysis, lexing or tokenization is the process of converting a sequence of characters (such as in a computer program or web page) into a sequence of tokens (strings with an assigned and thus identified meaning).

New!!: LR parser and Lexical analysis · See more »

LL parser

In computer science, an LL parser is a top-down parser for a subset of context-free languages.

New!!: LR parser and LL parser · See more »

Morgan Kaufmann Publishers

Morgan Kaufmann Publishers is a Burlington, Massachusetts (San Francisco, California until 2008) based publisher specializing in computer science and engineering content.

New!!: LR parser and Morgan Kaufmann Publishers · See more »

Operator-precedence parser

In computer science, an operator precedence parser is a bottom-up parser that interprets an operator-precedence grammar.

New!!: LR parser and Operator-precedence parser · See more »

Parse tree

A parse tree or parsing tree or derivation tree or concrete syntax tree is an ordered, rooted tree that represents the syntactic structure of a string according to some context-free grammar.

New!!: LR parser and Parse tree · See more »


Parsing, syntax analysis or syntactic analysis is the process of analysing a string of symbols, either in natural language, computer languages or data structures, conforming to the rules of a formal grammar.

New!!: LR parser and Parsing · See more »

Prentice Hall

Prentice Hall is a major educational publisher owned by Pearson plc.

New!!: LR parser and Prentice Hall · See more »


Prolog is a general-purpose logic programming language associated with artificial intelligence and computational linguistics.

New!!: LR parser and Prolog · See more »

Recursive ascent parser

In computer science, recursive ascent parsing is a technique for implementing an LALR parser which uses mutually-recursive functions rather than tables.

New!!: LR parser and Recursive ascent parser · See more »

Recursive descent parser

In computer science, a recursive descent parser is a kind of top-down parser built from a set of mutually recursive procedures (or a non-recursive equivalent) where each such procedure usually implements one of the productions of the grammar.

New!!: LR parser and Recursive descent parser · See more »

Shift-reduce parser

A shift-reduce parser is a class of efficient, table-driven bottom-up parsing methods for computer languages and other notations formally defined by a grammar.

New!!: LR parser and Shift-reduce parser · See more »

Simple LR parser

In computer science, a Simple LR or SLR parser is a type of LR parser with small parse tables and a relatively simple parser generator algorithm.

New!!: LR parser and Simple LR parser · See more »

Simple precedence parser

In computer science, a simple precedence parser is a type of bottom-up parser for context-free grammars that can be used only by simple precedence grammars.

New!!: LR parser and Simple precedence parser · See more »

SLR grammar

In computer science, SLR grammars are the class of formal grammars accepted by a Simple LR parser.

New!!: LR parser and SLR grammar · See more »

Stack (abstract data type)

In computer science, a stack is an abstract data type that serves as a collection of elements, with two principal operations.

New!!: LR parser and Stack (abstract data type) · See more »


A substring is a contiguous sequence of characters within a string.

New!!: LR parser and Substring · See more »

Symbol (formal)

A logical symbol is a fundamental concept in logic, tokens of which may be marks or a configuration of marks which form a particular pattern.

New!!: LR parser and Symbol (formal) · See more »

Terminal and nonterminal symbols

In computer science, terminal and nonterminal symbols are the lexical elements used in specifying the production rules constituting a formal grammar.

New!!: LR parser and Terminal and nonterminal symbols · See more »

Top-down parsing

In computer science, top-down parsing is a parsing strategy where one first looks at the highest level of the parse tree and works down the parse tree by using the rewriting rules of a formal grammar.

New!!: LR parser and Top-down parsing · See more »


Yacc (Yet Another Compiler-Compiler) is a computer program for the Unix operating system developed by Stephen C. Johnson.

New!!: LR parser and Yacc · See more »

Redirects here:

LR Parser, LR grammar, LR parsers, LR parsing, LR(0), LR(0) parser, LR(1) grammar, LR(k), LR(k) grammar, Lr parser, Shift-reduce conflict.


[1] https://en.wikipedia.org/wiki/LR_parser

Hey! We are on Facebook now! »