Operator-precedence parser: Difference between revisions

Revision as of 04:34, 22 October 2024

Revision as of 04:36, 22 October 2024

Line 94:

== Pratt parsing ==

{{external links|section|date=August 2023}}

Another precedence parser known as Pratt parsing was first described by [[Vaughan Pratt]] in the 1973 paper "Top downDown operatorOperator precedencePrecedence",<ref>Pratt, Vaughan. "[https://web.archive.org/web/20151223215421/http://hall.org.ua/halls/wizzard/pdf/Vaughan.Pratt.TDOP.pdf Top downDown operatorOperator precedencePrecedence]." ''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>