Parsing expression grammars: a recognition-based syntactic foundation Export

@inproceedings{citeulike:3230, abstract = {For decades we have been using Chomsky's generative system of grammars, particularly context-free grammars (CFGs) and regular expressions (REs), to express the syntax of programming languages and protocols. The power of generative grammars to express ambiguity is crucial to their original purpose of modelling natural languages, but this very power makes it unnecessarily difficult both to express and to parse machine-oriented languages using CFGs. Parsing Expression Grammars (PEGs) provide an alternative, recognition-based formal foundation for describing machine-oriented syntax, which solves the ambiguity problem by not introducing ambiguity in the first place. Where CFGs express nondeterministic choice between alternatives, PEGs instead use prioritized choice . PEGs address frequently felt expressiveness limitations of CFGs and REs, simplifying syntax definitions and making it unnecessary to separate their lexical and hierarchical components. A linear-time parser can be built for any PEG, avoiding both the complexity and fickleness of LR parsers and the inefficiency of generalized CFG parsing. While PEGs provide a rich set of operators for constructing grammars, they are reducible to two minimal recognition schemas developed around 1970, TS/TDPL and gTS/GTDPL, which are here proven equivalent in effective recognition power.}, address = {New York, NY, USA}, author = {Ford, Bryan}, booktitle = {POPL '04: Proceedings of the 31st ACM SIGPLAN-SIGACT symposium on Principles of programming languages}, citeulike-article-id = {3230}, citeulike-linkout-0 = {http://portal.acm.org/citation.cfm?id=964011}, citeulike-linkout-1 = {http://dx.doi.org/10.1145/964001.964011}, citeulike-linkout-2 = {http://pdos.csail.mit.edu/~baford/packrat/popl04/}, comment = {slides: http://www.bford.info/pub/lang/peg-slides.pdf}, doi = {10.1145/964001.964011}, isbn = {1-58113-729-X}, keywords = {linguistics, parser}, location = {Venice, Italy}, month = {January}, number = {1}, pages = {111--122}, posted-at = {2009-06-22 16:42:26}, priority = {0}, publisher = {ACM}, title = {Parsing expression grammars: a recognition-based syntactic foundation}, url = {http://dx.doi.org/10.1145/964001.964011}, volume = {39}, year = {2004} }

TY - CONF ID - citeulike:3230 L3 - citeulike-article-id:3230 N2 - For decades we have been using Chomsky's generative system of grammars, particularly context-free grammars (CFGs) and regular expressions (REs), to express the syntax of programming languages and protocols. The power of generative grammars to express ambiguity is crucial to their original purpose of modelling natural languages, but this very power makes it unnecessarily difficult both to express and to parse machine-oriented languages using CFGs. Parsing Expression Grammars (PEGs) provide an alternative, recognition-based formal foundation for describing machine-oriented syntax, which solves the ambiguity problem by not introducing ambiguity in the first place. Where CFGs express nondeterministic choice between alternatives, PEGs instead use prioritized choice . PEGs address frequently felt expressiveness limitations of CFGs and REs, simplifying syntax definitions and making it unnecessary to separate their lexical and hierarchical components. A linear-time parser can be built for any PEG, avoiding both the complexity and fickleness of LR parsers and the inefficiency of generalized CFG parsing. While PEGs provide a rich set of operators for constructing grammars, they are reducible to two minimal recognition schemas developed around 1970, TS/TDPL and gTS/GTDPL, which are here proven equivalent in effective recognition power. CY - Venice, Italy IS - 1 SN - 1-58113-729-X AD - New York, NY, USA EP - 122 TI - Parsing expression grammars: a recognition-based syntactic foundation PB - ACM VL - 39 T2 - POPL '04: Proceedings of the 31st ACM SIGPLAN-SIGACT symposium on Principles of programming languages SP - 111 KW - linguistics KW - parser N1 - slides: http://www.bford.info/pub/lang/peg-slides.pdf AU - Ford, Bryan PY - 2004/01// UR - http://dx.doi.org/10.1145/964001.964011 ER -