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

Parsing expression grammar

+ Save concept

In computer science, a parsing expression grammar, or PEG, is a type of analytic formal grammar, i.e. it describes a formal language in terms of a set of rules for recognizing strings in the language. [1]

48 relations: Addison-Wesley, Ambiguity, Ambiguous grammar, Association for Computing Machinery, Backtracking, Bellman–Ford algorithm, Boolean grammar, Circular definition, Commutative property, Comparison of parser generators, Compiler Description Language, Computer science, Constructed language, Context-free grammar, Context-free language, Cut (logic programming), CYK algorithm, Dangling else, Earley parser, Expression (mathematics), Floyd–Warshall algorithm, Formal grammar, Formal language, Function (mathematics), GLR parser, Greedy algorithm, Left recursion, List of algorithms, LL parser, Logic programming, Lojban, LR parser, Memoization, Mutual recursion, Natural language, OMeta, Parse tree, Parser combinator, Parsing, PDF, Recursion, Recursive descent parser, Regular expression, String (computer science), Syntactic predicate, Terminal and nonterminal symbols, Time complexity, Top-down parsing language.

Addison-Wesley

Addison-Wesley is a publisher of textbooks and computer literature.

New!!: Parsing expression grammar and Addison-Wesley · See more »

Ambiguity

Ambiguity is a type of meaning in which several interpretations are plausible.

New!!: Parsing expression grammar and Ambiguity · 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!!: Parsing expression grammar and Ambiguous grammar · See more »

Association for Computing Machinery

The Association for Computing Machinery (ACM) is an international learned society for computing.

New!!: Parsing expression grammar and Association for Computing Machinery · See more »

Backtracking

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!!: Parsing expression grammar and Backtracking · See more »

Bellman–Ford algorithm

The Bellman–Ford algorithm is an algorithm that computes shortest paths from a single source vertex to all of the other vertices in a weighted digraph.

New!!: Parsing expression grammar and Bellman–Ford algorithm · See more »

Boolean grammar

Boolean grammars, introduced by Okhotin, are a class of formal grammars studied in formal language theory.

New!!: Parsing expression grammar and Boolean grammar · See more »

Circular definition

A circular definition is one that uses the term(s) being defined as a part of the definition or assumes a prior understanding of the term being defined.

New!!: Parsing expression grammar and Circular definition · See more »

Commutative property

In mathematics, a binary operation is commutative if changing the order of the operands does not change the result.

New!!: Parsing expression grammar and Commutative property · See more »

Comparison of parser generators

This is a list of notable lexer generators and parser generators for various language classes.

New!!: Parsing expression grammar and Comparison of parser generators · See more »

Compiler Description Language

Compiler Description Language, or CDL, is a programming language based on affix grammars.

New!!: Parsing expression grammar and Compiler Description 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!!: Parsing expression grammar and Computer science · See more »

Constructed language

A constructed language (sometimes called a conlang) is a language whose phonology, grammar, and vocabulary have been consciously devised for human or human-like communication, instead of having developed naturally.

New!!: Parsing expression grammar and Constructed language · 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!!: Parsing expression 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!!: Parsing expression grammar and Context-free language · See more »

Cut (logic programming)

The cut, in Prolog, is a goal, written as !, which always succeeds, but cannot be backtracked.

New!!: Parsing expression grammar and Cut (logic programming) · 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!!: Parsing expression 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!!: Parsing expression grammar and Dangling else · 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!!: Parsing expression grammar and Earley parser · See more »

Expression (mathematics)

In mathematics, an expression or mathematical expression is a finite combination of symbols that is well-formed according to rules that depend on the context.

New!!: Parsing expression grammar and Expression (mathematics) · See more »

Floyd–Warshall algorithm

In computer science, the Floyd–Warshall algorithm is an algorithm for finding shortest paths in a weighted graph with positive or negative edge weights (but with no negative cycles).

New!!: Parsing expression grammar and Floyd–Warshall algorithm · 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!!: Parsing expression grammar and Formal grammar · See more »

Formal language

In mathematics, computer science, and linguistics, a formal language is a set of strings of symbols together with a set of rules that are specific to it.

New!!: Parsing expression grammar and Formal language · See more »

Function (mathematics)

In mathematics, a function was originally the idealization of how a varying quantity depends on another quantity.

New!!: Parsing expression grammar and Function (mathematics) · 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!!: Parsing expression grammar and GLR parser · See more »

Greedy algorithm

A greedy algorithm is an algorithmic paradigm that follows the problem solving heuristic of making the locally optimal choice at each stage with the intent of finding a global optimum.

New!!: Parsing expression grammar and Greedy algorithm · See more »

Left recursion

In the formal language theory of computer science, left recursion is a special case of recursion where a string is recognized as part of a language by the fact that it decomposes into a string from that same language (on the left) and a suffix (on the right).

New!!: Parsing expression grammar and Left recursion · See more »

List of algorithms

The following is a list of algorithms along with one-line descriptions for each.

New!!: Parsing expression grammar and List of algorithms · See more »

LL parser

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

New!!: Parsing expression grammar and LL parser · See more »

Logic programming

Logic programming is a type of programming paradigm which is largely based on formal logic.

New!!: Parsing expression grammar and Logic programming · See more »

Lojban

Lojban (pronounced) is a constructed, syntactically unambiguous human language, succeeding the Loglan project.

New!!: Parsing expression grammar and Lojban · 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!!: Parsing expression grammar and LR parser · See more »

Memoization

In computing, memoization or memoisation is an optimization technique used primarily to speed up computer programs by storing the results of expensive function calls and returning the cached result when the same inputs occur again.

New!!: Parsing expression grammar and Memoization · See more »

Mutual recursion

In mathematics and computer science, mutual recursion is a form of recursion where two mathematical or computational objects, such as functions or data types, are defined in terms of each other.

New!!: Parsing expression grammar and Mutual recursion · See more »

Natural language

In neuropsychology, linguistics, and the philosophy of language, a natural language or ordinary language is any language that has evolved naturally in humans through use and repetition without conscious planning or premeditation.

New!!: Parsing expression grammar and Natural language · See more »

OMeta

OMeta is a specialized object-oriented programming language for pattern matching, developed by Alessandro Warth and Ian Piumarta in 2007 under the Viewpoints Research Institute.

New!!: Parsing expression grammar and OMeta · 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!!: Parsing expression grammar and Parse tree · See more »

Parser combinator

In computer programming, a parser combinator is a higher-order function that accepts several parsers as input and returns a new parser as its output.

New!!: Parsing expression grammar and Parser combinator · See more »

Parsing

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!!: Parsing expression grammar and Parsing · See more »

PDF

The Portable Document Format (PDF) is a file format developed in the 1990s to present documents, including text formatting and images, in a manner independent of application software, hardware, and operating systems.

New!!: Parsing expression grammar and PDF · See more »

Recursion

Recursion occurs when a thing is defined in terms of itself or of its type.

New!!: Parsing expression grammar and Recursion · 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!!: Parsing expression grammar and Recursive descent parser · See more »

Regular expression

A regular expression, regex or regexp (sometimes called a rational expression) is, in theoretical computer science and formal language theory, a sequence of characters that define a search pattern.

New!!: Parsing expression grammar and Regular expression · 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!!: Parsing expression grammar and String (computer science) · See more »

Syntactic predicate

A syntactic predicate specifies the syntactic validity of applying a production in a formal grammar and is analogous to a semantic predicate that specifies the semantic validity of applying a production.

New!!: Parsing expression grammar and Syntactic predicate · 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!!: Parsing expression grammar and Terminal and nonterminal symbols · See more »

Time complexity

In computer science, the time complexity is the computational complexity that describes the amount of time it takes to run an algorithm.

New!!: Parsing expression grammar and Time complexity · See more »

Top-down parsing language

Top-Down Parsing Language (TDPL) is a type of analytic formal grammar developed by Alexander Birman in the early 1970s in order to study formally the behavior of a common class of practical top-down parsers that support a limited form of backtracking.

New!!: Parsing expression grammar and Top-down parsing language · See more »

Redirects here:

PEG parser, Packrat parser, Packrat parsing, Parsing Expression Grammar, PyPEG, Text parsing.

References

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

OutgoingIncoming
Hey! We are on Facebook now! »