3 ms·
Operator precedence parsing is linear time, but it only produces a parser for a very limited set of grammars, the epsilon-free LR(1) grammars with no consecutiv
by cwzwarich 8y ago
Operator precedence parsing is linear time, but it only produces a parser for a very limited set of grammars, the epsilon-free LR(1) grammars with no consecutive nonterminals.
Precedence parsing is typically combined with another parsing method to parse a non-operator part of a grammar, or it is used with preprocessing filters that insert extra marker tokens to work around the limitations.
Most programming languages have grammars that are very close to being operator precedence languages, so in the early days of parsing there were a lot of attempts to extend precedence parsing to handle more general grammars. After SLR/LALR parsing was developed, most of this work stopped.
- mehrdadn 8y agoThanks! That sounds awfully limiting if I'm being honest, even if a language is 'mostly' well-behaved... I can't say I can see how you could use preprocessing to get around the limitations since it would seem that doing so properly would require already parsing the input. It sounds like a nice method for when it works but it doesn't really sound like it would substitute for LR?
- oso2k 8y agoNot really limiting. Crockford used it in jslint [0][1][2] to parse JavaScript, and OIL Shell also uses it [3] to parse a shell language. [0] https://youtu.be/Nlqv6NtBXcA https://youtu.be/Nlqv6NtBXcA [1] https://crockford.com/javascript/tdop/tdop.html https://crockford.com/javascript/tdop/tdop.html [2] https://en.wikipedia.org/wiki/Operator-precedence_parser https://en.wikipedia.org/wiki/Operator-precedence_parser [3] https://www.oilshell.org/blog/2017/03/31.html https://www.oilshell.org/blog/2017/03/31.html