Re: Recursive descent and left recursion

> All true... but now you go on to add a mis-impression of your own,
> because you confuse LR parsing with operator precedence parsing:


True, enough, and I thank you for the correction. Operator precedence
parsing is a separate class of parsing than LR, and not a complete
subset. (I can't remember which, but there are some precedence
parsing techniques which can parse non-LR languages.) However, there
is a subset of generalized operator precedence parsing which is LR,
and that subset includes the abilities to parse expressions
"naturally", and is trivially implemented by appropriate resolution of
shift/reduce conflicts.


> Yes, but only if your LR parsing tool/technique allows operator
> precedence grammars -- and you can do that with LL parsing too, if you
> have an LL parsing tool/technique that supports operator precedence
> grammars. Certainly it's not that hard to write an operator
> precedence recursive descent parser.


However, an operator precedence parser is not an LL parser, even if it
is implemented in recursive descent. To be precise, there is no
connection between LL languages and recursive descent parsers. With a
language that supports backtracking (or by simulating it), you can
write recursive descent parsers for any language. [In addition,
backtracking is not the only way to extend recursive descent to handle
non-LL language.] The class of LL languages is defined by their
ability to be recognized left-to-right with only K tokens of left
context. Precedence parsing requires right context, that is you must
look at tokens which follow the production you wish to recognize
before deciding whether the production has been completed or not.
Parsing with a fixed amount of right context is the property of LR
languages, which is what makes them hard to create a simple recursive
descent parser for, since that parser may have to look at the
production to be applied in a specific right context before it can
decide whether to parse it as that production or not. [If I
understand correctly, the precedence parsers which are not LR need
unbounded right context. That is, you may have to read the entire
input stream before you can determine whether a particular production
should be applied or not.]


> Perhaps you meant "... without having to left-factor your grammar"?


Although, perhaps that is what I should have said, (and I thank you
for giving me the benefit of the doubt) I was trying to address the
recursion issue directly. That is any recursion is legal in LR
parsing, although some recursive constructs will generate shift/reduce
conflicts, which need to be resolved using techniques borrowed from
precedence parsing. [There are also left recursive grammars which are
not LL that do not generate conflicts, and thus are properly LR.]


Thus, if your parser generator supports precedence parsing techniques
(and I do stand corrected here in that precedence techniques can be
added to LL parser generators also, although I don't think I've ever
seen it done, which may just be my lack of exposure), then you can
write your expression parts of your grammar naturally.


Moreover, if you can do so, it is useful to eliminate the
non-terminals in your grammar which represent precedence levels as
they will make your parser either smaller or faster.


Now, hopefully, I have not added too many more mistakes by my longer
note on this topic.


-Chris
--

Return to the comp.compilers page.
Search the comp.compilers archives again.