Operator-precedence parser: Difference between revisions

Revision as of 15:51, 29 January 2024

Latest revision as of 20:16, 15 August 2025

(7 intermediate revisions by 4 users not shown)

Line 1:

{{Short description|Bottom-up parser that interprets an operator-precedence grammar}}

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.

== Relationship to other parsers ==

Line 10:

Operator-precedence parsers are not used often in practice; however they do have some properties that make them useful within a larger design. First, they are simple enough to write by hand, which is not generally the case with more sophisticated right shift-reduce parsers. Second, they can be written to consult an operator table at [[Run time (program lifecycle phase)|run time]], which makes them suitable for languages that can add to or change their operators while parsing. (An example is [[Haskell (programming language)|Haskell]], which allows user-defined infix operators with custom associativity and precedence; consequently, an operator-precedence parser must be run on the program ''after'' parsing of all referenced modules.)

[[Raku (programming language)|Raku]] sandwiches an operator-precedence parser between two [[recursive descent parser]]s in order to achieve a balance of speed and dynamism. [[GNU Compiler Collection|GCC]]'s C and C++ parsers, which are hand-coded recursive descent parsers, are both sped up by an operator-precedence parser that can quickly examine arithmetic expressions. Operator -precedence parsers are also embedded within [[compiler-compiler]]-generated parsers to noticeably speed up the recursive descent approach to expression parsing.<ref name="Harwell2008">{{cite web| last=Harwell | first=Sam | date=2008-08-29 | title=Operator precedence parser | url=https://theantlrguy.atlassian.net/wiki/spaces/ANTLR3/pages/2687077/Operator+precedence+parser | publisher=ANTLR3 Wiki | access-date=2017-10-25}}</ref>

== Precedence climbing method ==

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>

Line 102:

* 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 [[Rust (programming language)|Rust]]: [https://matklad.github.io/2020/04/13/simple-but-powerful-pratt-parsing.html "Simple but Powerful Pratt Parsing" (2020) by Aleksey Kladov]

* Tutorial using [[Rust (programming language)|Rust]]: [https://williamr.dev/posts/pratt-parsing/ "The Pratt Parsing Technique" (2024) by William Rågstad]

* 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] {{Webarchive|url=https://web.archive.org/web/20150228044653/http://effbot.org/zone/simple-top-down-parsing.htm |date=2015-02-28 }}

* 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]

Line 113 ⟶ 114:

=== Full parenthesization ===

Another approach is to first fully parenthesize the expression, inserting a number of parentheses around each operator, such that they lead to the correct precedence even when parsed with a linear, left-to-right parser. This algorithm was used in the early [[Fortran#FORTRAN|FORTRAN I]] compiler:<ref name="Padua2000">{{cite journal |last1=Padua |first1=David |title=The Fortran I Compiler |year=2000 |journal=Computing in Science & Engineering |volume=2 |issue=1 |pages=70–75 |url=http://polaris.cs.uiuc.edu/publications/c1070.pdf |doi=10.1109/5992.814661 |bibcode=2000CSE.....2a..70P |archive-date=2020-06-17 |access-date=2016-03-29 |archive-url=https://web.archive.org/web/20200617113640/http://polaris.cs.uiuc.edu/publications/c1070.pdf |url-status=dead }}</ref>

<blockquote>

Line 189 ⟶ 190:

* [http://groups.google.com/group/comp.compilers/browse_thread/thread/442ca111b2dfb38d/5390237263b3625b?#5390237263b3625b Example C++ code by Keith Clarke for parsing infix expressions using the precedence climbing method]

* {{cite journal| last=Samelson | first=Klaus | author-link=Klaus Samelson |author2=Friedrich L. Bauer |author2-link=Friedrich L. Bauer |date=February 1960 | title=Sequential formula translation | journal=Communications of the ACM | volume=3 | issue=2 | pages=76–83 | doi=10.1145/366959.366968| doi-access=free }}

* [https://web.archive.org/web/20160817143616/http://radovan-augustin.info/techpapers/parser/Parser.pdf Parser for expression with infix notation using precedence lists]

{{Parsers}}