Talk:Operator-precedence parser

I've been implementing a parser based on the pseudo-code in this page, and I believe that the greater-or-equal (>=) test in the outer loop is incorrect. A strict greater-than (>) seems to work for me, but perhaps there should also an associativity test as per the inner loop. (First time contrib, apologies if this is in the wrong place or something.) Anthony —Preceding unsigned comment added by 118.68.30.163 (talk) 14:50, 13 March 2009 (UTC)

I think that for an operator that can't repeat at the same precedence level (a=b, but not a=b=c), you want to use (>) rather than (>=). Mhkay (talk) 23:39, 20 January 2015 (UTC)

I rewrote the parenthesis-insertion code to present the essence of the algorithm with less distracting C-machination (eliminated a couple of tables & some peculiar end-cases, open-coded a loop) -- and to make lines shorter, and to make gcc -Wall compile it without complaint. I'll note here that it doesn't do anything about getting operator associativity right. In particular, using the usual rules, a^b^c should come out to a^(b^c) while a-b-c should be (a-b)-c. The present program adequately parenthesizes neither. Tom Duff 19:20, 23 August 2006 (UTC)

Thanks for the cleanup, Tom, though in my defence I don't think the original Fortran code handled associativity either :-) I must admit I've never tried to work out how to implement associativity properly with this quick hack, since it's not code I'ld ever use in a real program anyway. Might be a fun exercise one quiet evening though.

Anyway, back to the current text: "To show that one grammar is operator precedence, first it should be operator grammar. Operator precedence grammar is the only grammar which can construct the parse tree even though the given grammar is ambiguous." - am I the only person having trouble parsing that sentence? If I knew what the author was trying to say I might rewrite it in English... 129.113.28.125 19:53, 24 September 2007 (UTC) (Graham)

Hi Tom, if you're talking about the C code that implements the FORTRAN I approach, I think it's vital that the flaws with the C code are pointed out. I've altered your code to support parenthesis; perhaps you could take a look. I don't know how FORTRAN I handled it or the other remaining problems. Do you? -- Ralph Corderoy (talk) 10:37, 3 December 2009 (UTC)

While I'm here, it would be a good idea for some motivated person to rewrite the pseudo-code for the railway-siding algorithm in C or something. Tom Duff 19:28, 23 August 2006 (UTC)

This is the first time I've seen an operator precedence parser explained with no stack and precedence table. The elegence of such implementations is irresistable. While i'm not about to argue with any fact in the original article, I think it warrants a shout-out. Antinice 12:12, 18 April 2007 (UTC)

I believe there is an error in the pseudocode. However, I'm not confident enough in my knowledge to change it. Shouldn't the last line in the inner while loop, lhs := the result of applying op with operands lhs and rhs, actually be part of the outer while loop? If not, ignore, but someone please review it sometime. 71.98.94.127 (talk) 02:40, 20 February 2008 (UTC)

Hi. I think, the Precedence-Climbing-Algorithm should be also included in this article. It is a fast and flexible, fully capable operator-precedence-algorithm which is less complex than the shunting-yard-algo and much faster and more flexible than the classic solution. The article, which the wikipedia-article links to, handles the precedence-climbing-algo: (http://www.engr.mun.ca/~theo/Misc/exp_parsing.htm) If nobody answers, i will add it to the article. 80.254.190.93 (talk) 08:59, 25 November 2008 (UTC)

Gang, this page is kind of a mess. Precedence climbing is much more powerful than operator precedence parsing. For example, operator precedence parsing cannot deal with operators with different precedences. He cannot deal with multiple non-terminals in a row whereas precedents climbing can. Also it should give credit to Hanson from 1980s that had an earlier implementation (lcc portable compiler guy). this page should be purely about operator precedence parsing and then we should have a different page on precedence climbing. Note: ANTLR v4 which I hope to complete soon automatically converts left recursive expression rules to precedence climbing style rules. — Preceding unsigned comment added by Parrt (talk • contribs) 00:10, 6 June 2012 (UTC)

The precedence climbing algorithm should probably be credited to Martin Richards of BCPL fame. I've read David Hansen's article and just can't convince myself that it describes precedence climbing. In any case, Richards's book on BCPL --which includes the precedence climbing algorithm-- was published earlier, so it has, well, precedence. Theodore.norvell (talk) 01:42, 11 April 2013 (UTC)

Also the version of precedence climbing currently on this page is more complex than I think it needs to be: it has a recursive call within a while loop within another while loop! Compare to my article (or Clarke's post or Richards's book) in which the recursive call is within a single loop. Theodore.norvell (talk) 01:42, 11 April 2013 (UTC)

The posted algorithm doesn't correctly handle low-precedence unary operators

The current pseudocode algorithm in the article doesn't correctly handle low-precedence unary operators. For example, "-x^2" is parsed as (-x)^2 instead of -(x^2), which is probably what would be intended. More generally, let "&" be an arbitrary prefix unary operator, and "#" be a binary operator with higher precedence than "&". Then "&x # y" should be parsed as &(x#y) but the posted algorithm parses it as (&x)#y.

Furthermore, suppose "$" is a unary postfix operator with higher precedence than "&". Then "&x$" should be parsed as &(x$) but the algorithm parses it as (&x)$, which is wrong.

Now I'm sure this problem must have been already solved in the field (or in research), but I don't know any references to a correct precedence-climbing algorithm that correctly processes unary prefix and postfix operators. In any case, though, readers should be aware that the current version of the algorithm does not handle the above cases correctly.—Tetracube (talk) 01:19, 8 October 2012 (UTC)

P.S. The algorithm explained in the link posted by User:80.254.190.93 does handle unary operators correctly (at least, unary prefix operators). Maybe it should be worked into the article somehow?—Tetracube (talk) 01:45, 8 October 2012 (UTC)

Prefix operators are like binary operators that are missing an operand. Both prefix and postfix operators of any precedence can be handled by precedence climbing. I'll implement your suggestion. Theodore.norvell (talk) 01:42, 11 April 2013 (UTC)

For anyone interested in postfix operators, I've shown how to implement them at http://www.engr.mun.ca/~theo/Misc/exp_parsing.htm . Theodore.norvell (talk) 21:27, 17 March 2014 (UTC)

Primary

This rule will allow unused (and invalid?) expressions like "- - - 5":

  primary ::= '(' expression ')' | NUMBER | VARIABLE | '-' primary  — Preceding unsigned comment added by Ngocminh.oss (talk • contribs) 08:21, 25 April 2013 (UTC) 

A bottom-up parser than can be implemented with the top down operator precedence method?

The article begins by telling us that "an operator precedence parser is a bottom-up parser...." A few sentences later we learn: "Edsger Dijkstra's shunting yard algorithm is commonly used to implement operator precedence parsers. Other algorithms include the precedence climbing method and the top down operator precedence method." This article appears to confuse three concepts with each other:

• parsers/parsing algorithms
• grammars
• the class of languages described by a grammar/parsable by an algorithm.

I propose removing "bottom-up" from the first sentence. Subsequent sections need to specify which algorithm is being considered (e.g. "An operator-precedence parser is a simple shift-reduce parser..."). Moreover, an article on operator-precedence parsers should at least name the most common algorithms and link to their corresponding wiki pages.

--Rljacobson (talk) 02:32, 11 August 2017 (UTC)

References

Merger proposal

I propose merging Simple precedence parser into Operator-precedence parser. I think the content in Simple precedence parser can easily be explained in the context of Operator-precedence parser, and a merger would not cause any article-size or weighting problems in Operator-precedence parser.Helphelp101 (talk) 22:30, 9 April 2023 (UTC)