Editing Parsing expression grammar (section)

{{short description|Type of grammar for describing formal languages}}
In [[computer science]], a '''parsing expression grammar''' ('''PEG''') is a type of [[formal grammar#Analytic grammars|analytic]] [[formal grammar]], i.e. it describes a [[formal language]] in terms of a set of rules for recognizing [[string (computer science)|strings]] in the language. The formalism was introduced by Bryan Ford in 2004<ref name="For04">
{{cite conference
| first = Bryan
| last = Ford
| title = Parsing Expression Grammars: A Recognition Based Syntactic Foundation
| book-title = Proceedings of the 31st ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages
| publisher = [[Association for Computing Machinery|ACM]]
| date = January 2004
| url = https://bford.info/pub/lang/peg.pdf
| doi = 10.1145/964001.964011
| isbn = 1-58113-729-X
|pages=111–122
}}</ref> and is closely related to the family of [[top-down parsing language]]s introduced in the early 1970s.
Syntactically, PEGs also look similar to [[context-free grammar]]s (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 grammar|ambiguous]]; a string has exactly one valid [[parse tree]] or none. It is conjectured that there exist context-free languages that cannot be recognized by a PEG, but this is not yet proven.<ref name="For04" /> PEGs are well-suited to parsing computer languages (and artificial human languages such as [[Lojban]]) where multiple interpretation alternatives can be disambiguated locally, but are less likely to be useful for parsing [[natural language]]s where disambiguation may have to be global.<ref name="pegs">
{{cite journal
| first= Bryan |last=Ford
| title = Packrat parsing: simple, powerful, lazy, linear time, functional pearl
|journal=ACM SIGPLAN Notices
| date = September 2002
| url = http://pdos.csail.mit.edu/~baford/packrat/icfp02/packrat-icfp02.pdf
| doi=10.1145/583852.581483
|volume=37 |issue=9
}}
</ref>