Operator-precedence parser: Difference between revisions

Revision as of 03:43, 16 February 2019

Revision as of 09:01, 11 March 2019

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_parserPratt 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 ==

An operator-precedence parser is a simple [[shift-reduce parser]] that is capable of parsing a subset of [[LR parser|LR(1)]] grammars. More precisely, the operator-precedence parser can parse all LR(1) grammars where two consecutive [[nonterminal]]s and [[empty_stringempty string|epsilon]] never appear in the right-hand side of any rule.

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; consequentially, an operator-precedence parser must be run on the program ''after'' parsing of all referenced modules.)

Line 105:

* add <code>((</code> at the beginning of each expression and after each left parenthesis in the original expression; and

* add <code>))</code> at the end of the expression and before each right parenthesis in the original expression.

Although not obvious, the algorithm was correct, and, in the words of [[Donald Knuth|Knuth]], “The resulting formula is properly parenthesized, believe it or not.”<ref name="Knuth1962">{{cite journal |last1=Knuth |first1=Donald E. |title=A HISTORY OF WRITING COMPILERS |year=1962 |publisher=Edmund C. Berkeley |journal=COMPUTERSComputers and AUTOMATIONAutomation |volume=11 |issue=12 |pages=8–14 |url=https://archive.org/details/bitsavers_computersA_13990695}}</ref>

</blockquote>