CODEWITHSUNDEEP
parsinglexerlr-grammarassociativitypostfix-operator
Ian
Ian

Reputation: 19

Postfix and right-associative operators in LR(0) parsers

Is it possible to construct an LR(0) parser that could parse a language with both prefix and postfix operators? For example, if I had a grammar with the + (addition) and ! (factorial) operators with the usual precedence then 1+3! should be 1 + 3! = 1 + 6 = 7, but surely if the parser were LR(0) then when it had 1+3 on the stack it would reduce rather than shift?

Also, do right associative operators pose a problem? For example, 2^3^4 should be 2^(3^4) but again, when the parser have 2^3 on the stack how would it know to reduce or shift?

If this isn't possible is there still a way to use an LR(0) parser, possibly by altering the grammar to add brackets in the appropriate places?

Upvotes: 1

Views: 756

Answers (1)

templatetypedef
templatetypedef

Reputation: 373512

LR(0) parsers have a weakness in that they can only parse prefix-free languages, languages where no string in the language is a prefix of any other. This generally makes it a bit tricky to parse expressions like these, since something like 5 is a prefix of 5!. This also explains why it's hard to get right-associative operators - given a production like

S → F | F ^ S

the parser will have a shift/reduce conflict after seeing an F because it can't tell whether to extend it or to reduce again. This is related to the prefix-free property mentioned earlier.

This weakness of LR(0) is one of the reasons why people don't use it much in practice. SLR(1) and LALR(1) parsers can usually parse these grammars because they have a token of lookahead that lets them decide whether to shift or reduce. In the above case, the parsers wouldn't encounter shift/reduce conflicts because when deciding whether to reduce an F or shift a ^, they can see to shift the ^ because there's no correct string where a ^ should appear after an S.

Upvotes: 1

Related Questions