Get it on Google Play
New! Download Unionpedia on your Android™ device!
Faster access than browser!
New! Keep your concepts! » Create account

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

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

Alphabet (formal languages)

In formal language theory, a non-empty set is called alphabet when its intended use in string operations shall be indicated.

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, while an unambiguous grammar is a context-free grammar for which every valid string has a unique leftmost derivation.

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 each partial candidate c ("backtracks") as soon as it determines that c 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 science

Computer science deals with the theoretical foundations of information and computation, together with practical techniques for the implementation and application of these foundations Computer science is the scientific and practical approach to computation and its applications.

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

Context-free grammar

In formal language theory, a context-free grammar (CFG) is a formal grammar in which every production rule is of the form where V is a single nonterminal symbol, and w is a string of terminals and/or nonterminals (w can be empty).

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 some 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 exaggeration of words in a text with a font in a different style from the rest of the text—to emphasize them.

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

Finite-state machine

A finite-state machine (FSM) or finite-state automaton (plural: automata), or simply a state machine, is a mathematical model of computation used to design both computer programs and sequential logic circuits.

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 is the process of converting a sequence of characters (such as a computer program or web page) into a sequence of tokens (strings with an 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 »

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 or syntactic analysis is the process of analysing a string of symbols, either in natural language or in computer languages, conforming to the rules of a formal grammar.

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

Programming language

A programming language is a formal constructed language designed to communicate instructions to a machine, particularly a computer.

New!!: LR parser and Programming language · 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 or LIFO (last in, first out) is an abstract data type that serves as a collection of elements, with two principal operations: push, which adds an element to the collection, and pop, which removes the last element that was added.

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


A substring of a string S is another string S' that occurs "in" S. For example, "the best of" is a substring of "It was the best of times".

New!!: LR parser and Substring · 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 is a computer program for the Unix operating system.

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! »