Parsing expression grammar
In computer science, a parsing expression grammar (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. The formalism was introduced by Bryan Ford in 2004 and is closely related to the family of top-down parsing languages introduced in the early 1970s.Syntactically, PEGs also look similar to context-free grammars (CFGs), but they have a different interpretation: the choice operator selects the first match in PEG, while it is ambiguous in CFG. This is closer to how string recognition tends to be done in practice, e.g. by a recursive descent parser.
- Comment
- enIn computer science, a parsing expression grammar (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. The formalism was introduced by Bryan Ford in 2004 and is closely related to the family of top-down parsing languages introduced in the early 1970s.Syntactically, PEGs also look similar to context-free grammars (CFGs), but they have a different interpretation: the choice operator selects the first match in PEG, while it is ambiguous in CFG. This is closer to how string recognition tends to be done in practice, e.g. by a recursive descent parser.
- Has abstract
- enIn computer science, a parsing expression grammar (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. The formalism was introduced by Bryan Ford in 2004 and is closely related to the family of top-down parsing languages introduced in the early 1970s.Syntactically, PEGs also look similar to context-free grammars (CFGs), but they have a different interpretation: the choice operator selects the first match in PEG, while it is ambiguous in CFG. This is closer to how string recognition tends to be done in practice, e.g. by a recursive descent parser. Unlike CFGs, PEGs cannot be ambiguous; if a string parses, it has exactly one valid parse tree. It is conjectured that there exist context-free languages that cannot be recognized by a PEG, but this is not yet proven. PEGs are well-suited to parsing computer languages (and artificial human languages such as Lojban), but not natural languages where the performance of PEG algorithms is comparable to general CFG algorithms such as the Earley algorithm.
- Hypernym
- Grammar
- Is primary topic of
- Parsing expression grammar
- Label
- enParsing expression grammar
- Link from a Wikipage to an external page
- bford.info/packrat/
- www.digitalkingdom.org/~rlpowell/hobbies/lojban/grammar/
- web.archive.org/web/20131103083443/http:/mathosproject.com/updates/convert-a-string-expression-into-a-lambda-expression/
- www.gnu.org/software/guile/manual/html_node/PEG-Parsing.html
- Link from a Wikipage to another Wikipage
- Ambiguous grammar
- Backtracking
- Bellman–Ford algorithm
- Boolean grammar
- Category:Formal languages
- Circular definition
- Commutativity
- Comparison of parser generators
- Compiler Description Language
- Computer science
- Constructed language
- Context-free grammar
- Context-free grammars
- Context-free language
- Cut (logic programming)
- CYK algorithm
- Dangling else
- Disjoint sets
- Earley algorithm
- Exponential time
- Expression (mathematics)
- Floyd–Warshall algorithm
- Formal grammar
- Formal language
- Function (mathematics)
- GLR parser
- Graph algorithms
- Greedy algorithm
- Left recursion
- Linear time
- LL(k)
- LL parser
- Logic programming
- Lojban
- LR parser
- Memoization
- Mutual recursion
- Natural language
- Nonterminal symbol
- OMeta
- Parser combinator
- Parse tree
- Parsing
- Python (programming language)
- Recursion
- Recursive descent parser
- Regular expression
- Regular expressions
- String (computer science)
- Syntactic predicate
- Terminal symbol
- Top-down parsing language
- SameAs
- 2yk1o
- Gramática de análise sintática de expressão
- m.03mdfm
- Parser packrat
- Parsing expression grammar
- Parsing Expression Grammar
- Q32271
- Грамматика, разбирающая выражение
- پارسنگ اکسپرشن گرامر
- 解析表达文法
- Subject
- Category:Formal languages
- WasDerivedFrom
- Parsing expression grammar?oldid=1122617388&ns=0
- WikiPageLength
- 25105
- Wikipage page ID
- 892899
- Wikipage revision ID
- 1122617388
- WikiPageUsesTemplate
- Template:Code
- Template:Parsers
- Template:Reflist
- Template:Short description
- Template:Tmath