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

Ambiguous grammar

+ Save concept

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. [1]

29 relations: Chart parser, Computer science, Context-free grammar, Context-free language, Context-sensitive grammar, CYK algorithm, Dangling else, Decision problem, Deterministic context-free grammar, Deterministic pushdown automaton, GLR parser, International Colloquium on Automata, Languages and Programming, Introduction to Automata Theory, Languages, and Computation, Lecture Notes in Computer Science, LR parser, Operator associativity, Palindrome, Parikh's theorem, Parse tree, Pascal (programming language), Post correspondence problem, Programming language, Pushdown automaton, Regular language, Rohit Jivanlal Parikh, String (computer science), Syntactic ambiguity, Undecidable problem, Yacc.

Chart parser

In computer science, a chart parser is a type of parser suitable for ambiguous grammars (including grammars of natural languages).

New!!: Ambiguous grammar and Chart parser · 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!!: Ambiguous grammar 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!!: Ambiguous grammar 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!!: Ambiguous grammar and Context-free language · See more »

Context-sensitive grammar

A context-sensitive grammar (CSG) is a formal grammar in which the left-hand sides and right-hand sides of any production rules may be surrounded by a context of terminal and nonterminal symbols.

New!!: Ambiguous grammar and Context-sensitive grammar · 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!!: Ambiguous grammar 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!!: Ambiguous grammar and Dangling else · See more »

Decision problem

In computability theory and computational complexity theory, a decision problem is a problem that can be posed as a yes-no question of the input values.

New!!: Ambiguous grammar and Decision problem · See more »

Deterministic context-free grammar

In formal grammar theory, the deterministic context-free grammars (DCFGs) are a proper subset of the context-free grammars.

New!!: Ambiguous grammar and Deterministic context-free grammar · See more »

Deterministic pushdown automaton

In automata theory, a deterministic pushdown automaton (DPDA or DPA) is a variation of the pushdown automaton.

New!!: Ambiguous grammar and Deterministic pushdown automaton · 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!!: Ambiguous grammar and GLR parser · See more »

International Colloquium on Automata, Languages and Programming

ICALP, the International Colloquium on Automata, Languages and Programming is an academic conference organized annually by the European Association for Theoretical Computer Science and held in different locations around Europe.

New!!: Ambiguous grammar and International Colloquium on Automata, Languages and Programming · See more »

Introduction to Automata Theory, Languages, and Computation

Introduction to Automata Theory, Languages, and Computation is an influential computer science textbook by John Hopcroft and Jeffrey Ullman on formal languages and the theory of computation.

New!!: Ambiguous grammar and Introduction to Automata Theory, Languages, and Computation · See more »

Lecture Notes in Computer Science

Springer Lecture Notes in Computer Science (LNCS) is a series of computer science books published by Springer Science+Business Media (formerly Springer-Verlag) since 1973.

New!!: Ambiguous grammar and Lecture Notes in Computer Science · See more »

LR parser

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

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

Operator associativity

In programming languages, the associativity of an operator is a property that determines how operators of the same precedence are grouped in the absence of parentheses.

New!!: Ambiguous grammar and Operator associativity · See more »


A palindrome is a word, number, or other sequence of characters which reads the same backward as forward, such as madam or racecar.

New!!: Ambiguous grammar and Palindrome · See more »

Parikh's theorem

Parikh's theorem in theoretical computer science says that if one looks only at the number of occurrences of each terminal symbol in a context-free language, without regard to their order, then the language is indistinguishable from a regular language.

New!!: Ambiguous grammar and Parikh's theorem · 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!!: Ambiguous grammar and Parse tree · See more »

Pascal (programming language)

Pascal is an imperative and procedural programming language, which Niklaus Wirth designed in 1968–69 and published in 1970, as a small, efficient language intended to encourage good programming practices using structured programming and data structuring. It is named in honor of the French mathematician, philosopher and physicist Blaise Pascal. Pascal was developed on the pattern of the ALGOL 60 language. Wirth had already developed several improvements to this language as part of the ALGOL X proposals, but these were not accepted and Pascal was developed separately and released in 1970. A derivative known as Object Pascal designed for object-oriented programming was developed in 1985; this was used by Apple Computer and Borland in the late 1980s and later developed into Delphi on the Microsoft Windows platform. Extensions to the Pascal concepts led to the Pascal-like languages Modula-2 and Oberon.

New!!: Ambiguous grammar and Pascal (programming language) · See more »

Post correspondence problem

The Post correspondence problem is an undecidable decision problem that was introduced by Emil Post in 1946.

New!!: Ambiguous grammar and Post correspondence problem · See more »

Programming language

A programming language is a formal language that specifies a set of instructions that can be used to produce various kinds of output.

New!!: Ambiguous grammar and Programming language · See more »

Pushdown automaton

In the theory of computation, a branch of theoretical computer science, a pushdown automaton (PDA) is a type of automaton that employs a stack.

New!!: Ambiguous grammar and Pushdown automaton · See more »

Regular language

In theoretical computer science and formal language theory, a regular language (also called a rational language) is a formal language that can be expressed using a regular expression, in the strict sense of the latter notion used in theoretical computer science (as opposed to many regular expressions engines provided by modern programming languages, which are augmented with features that allow recognition of languages that cannot be expressed by a classic regular expression).

New!!: Ambiguous grammar and Regular language · See more »

Rohit Jivanlal Parikh

Rohit Jivanlal Parikh (born November 20, 1936) is a mathematician, logician, and philosopher who has worked in many areas in traditional logic, including recursion theory and proof theory.

New!!: Ambiguous grammar and Rohit Jivanlal Parikh · See more »

String (computer science)

In computer programming, a string is traditionally a sequence of characters, either as a literal constant or as some kind of variable.

New!!: Ambiguous grammar and String (computer science) · See more »

Syntactic ambiguity

Syntactic ambiguity, also called amphiboly or amphibology, is a situation where a sentence may be interpreted in more than one way due to ambiguous sentence structure.

New!!: Ambiguous grammar and Syntactic ambiguity · See more »

Undecidable problem

In computability theory and computational complexity theory, an undecidable problem is a decision problem for which it is known to be impossible to construct a single algorithm that always leads to a correct yes-or-no answer.

New!!: Ambiguous grammar and Undecidable problem · See more »


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

New!!: Ambiguous grammar and Yacc · See more »

Redirects here:

Ambiguous context-free grammar, Ambiguous grammars, Inherently ambiguous language, Unambiguous context-free grammar, Unambiguous grammar.


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

Hey! We are on Facebook now! »