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.
In computer science, a chart parser is a type of parser suitable for ambiguous grammars (including grammars of natural languages).
Computer science deals with the theoretical foundations of information and computation, together with practical techniques for the implementation and application of these foundations.
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.
In formal language theory, a context-free language (CFL) is a language generated by a context-free grammar (CFG).
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.
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.
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.
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.
In formal grammar theory, the deterministic context-free grammars (DCFGs) are a proper subset of the context-free grammars.
In automata theory, a deterministic pushdown automaton (DPDA or DPA) is a variation of the pushdown automaton.
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.
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.
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.
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.
In computer science, LR parsers are a type of bottom-up parser that efficiently read deterministic context-free languages, in guaranteed linear time.
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.
A palindrome is a word, number, or other sequence of characters which reads the same backward as forward, such as madam or racecar.
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.
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.
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.
The Post correspondence problem is an undecidable decision problem that was introduced by Emil Post in 1946.
A programming language is a formal language that specifies a set of instructions that can be used to produce various kinds of output.
In the theory of computation, a branch of theoretical computer science, a pushdown automaton (PDA) is a type of automaton that employs a stack.
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).
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.
In computer programming, a string is traditionally a sequence of characters, either as a literal constant or as some kind of variable.
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.
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.
Yacc (Yet Another Compiler-Compiler) is a computer program for the Unix operating system developed by Stephen C. Johnson.