Operator-precedence parser: Difference between revisions

Revision as of 18:16, 11 May 2020

Revision as of 01:54, 7 November 2020

Line 1:

In [[computer science]], an '''operator precedence parser''' is a [[Bottom-up parsing|bottom-up parser]] that interprets an [[operator-precedence grammar]]. For example, most [[calculator]]s use operator precedence parsers to convert from the human-readable [[infix notation]] relying on [[order of operations]] to a format that is optimized for evaluation such as [[Reverse Polish notation]] (RPN).

[[Edsger Dijkstra]]'s [[shunting yard algorithm]] is commonly used to implement operator precedence parsers. Other algorithms include the precedence climbing method and the [[Pratt parser|top down operator precedence method]].<ref name="Norvell2001">{{cite web| last=Norvell | first=Theodore | year=2001 | title=Parsing Expressions by Recursive Descent | url=http://www.engr.mun.ca/~theo/Misc/exp_parsing.htm | accessdate=2012-01-24}}</ref>

== Relationship to other parsers ==

Line 90:

* the next token is ''end-of-line'', which is not an operator. the outer while loop is left.

1 is returned.

== Pratt parsing ==

Another precedence parser known as Pratt parsing was first described by Vaughn Pratt in the 1973 paper "Top down operator precedence"<ref>Pratt, Vaughan. "[https://web.archive.org/web/20151223215421/http://hall.org.ua/halls/wizzard/pdf/Vaughan.Pratt.TDOP.pdf Top down operator precedence]." ''Proceedings of the 1st Annual ACM SIGACT-SIGPLAN Symposium on Principles of Programming Languages'' (1973).</ref>, based on [[Recursive descent parser|recursive descent]]. Though it predates precedence climbing, it can be viewed as a generalization of precedence climbing <ref>{{cite web |last1=Norvell |first1=Theodore |title=Parsing Expressions by Recursive Descent |url=http://www.engr.mun.ca/~theo/Misc/pratt_parsing.htm |website=www.engr.mun.ca |quote=The purpose of this post is to [... start] with precedence climbing and refactoring it to use the command pattern until we arrive at a Pratt parser. [This is the author who coined the term "precedence climbing".]}}</ref>

Pratt designed the parser originally to implement the [[CGOL]] programming language, and it was treated in much more depth in a Masters Thesis under his supervision.<ref>Van De Vanter, Michael L. "[http://publications.csail.mit.edu/lcs/specpub.php?id=715 A Formalization and Correctness Proof of the CGOL Language System]." (Master's Thesis). MIT Laboratory for Computer Science Technical Report MIT-LCS-TR-147 (Cambridge, Massachusetts). 1975.</ref>

Tutorials and implementations:

* [[Douglas Crockford]] based the JavaScript parser in [[JSLint]] on Pratt parsing.<ref>{{cite web|author=Crockford, D|title=Top Down Operator Precedence|date=2007-02-21|url=http://crockford.com/javascript/tdop/tdop.html}}</ref>

* Comparison between Python implementations of precedence climbing and Pratt parsing: [http://www.oilshell.org/blog/2016/11/01.html "Pratt Parsing and Precedence Climbing Are the Same Algorithm" (2016) by Andy Chu]

* Tutorial using [[Python (programming language)|Python]]: [http://effbot.org/zone/simple-top-down-parsing.htm "Simple Top-Down Parsing in Python" (2008) by Fredrik Lundh]

* Tutorial using [[Java (programming language)|Java]]: [http://journal.stuffwithstuff.com/2011/03/19/pratt-parsers-expression-parsing-made-easy/ "Pratt Parsers: Expression Parsing Made Easy" (2011) by Bob Nystrom, author of Crafting Interpreters]

== Alternative methods ==