Re: Recursive descent and left recursion

Let me try one more time to extract myself from this pedantic mess
which I seem to have gotten into. Since I do not want to provide
incorrect information, and some readers have suggested that I have
confused language classes and grammar classes, I went back to a couple
of my reference books and checked the facts.


Operator precedence parsing is a subset of LR parsing, but may require
k sysmbols of lookahead, and in particular (m,k)-BRC is a subset of
LR(k), but not of LR(k-1). The set of languages accepted by operator
precedence parsers is the same set of languages accepted by LR
parsers, which the the set of deterministic context free languages.


The use of precedence within LR languages is covered in the Dragon
book and also Holub, but not Fisher, although Fisher mentions yacc
which implements precedence disambiguation. Thus, whether precedence
parsing is an extension of LR parsing or not is debatable,
particularly given the subset relationship. By the way, the original
paper on the topic is "Deterministic Parsing of Ambiguous Grammars" by
Aho, Johnson, and Ullman.


Operator precedence parsing can be used to extend LL grammars.


Recursive-descent is a term formally reserved for top-down
translations of languages (although it is permitted to include
backtracking). An LL grammar matches recursive-descent with no
backtracking (aka a top-down predictive parser). [Note, many "LL"
generators actually allow backtracking and thus support the more
general definition.] Recursive-descent can also be extended by having
certain routines implement operator precedence (or any other parsing
methodology). This is commonly done to handle expression parts of a
grammar. Again, I will leave it to your discretion as to whether you
want to call such parsers recursive-descent, I would. To implement a
recursive-descent style parser for a language which is LR but not LL,
your parser may have to scan past the last token of the production
before knowing which production to apply (to the k-th token after
depending on the k in the LR(k) of your grammar). The posting which
started this thread pointed out a way to modify a recursive-descent
parser so that it would not loop on a left-recursive grammar. (I did
not find a specific description of which languages that backtracking
recursive-descent compilers could accept. However, my intuition
suggests that it is quite large espessially if the modification is
used and left-recursive grammars are allowed. Without backtracking
the class of LL languages are a subset of the LR languages.)


Now, finally to the point I was originally attempting to make:


Many LR parser generators allow ambiguous grammars and use precedence
directives to disambiguate the resulting conflicts. If your LR parser
generator allows precedence direction, then it is advantageous to use
what I consider the "natural" way of expressing the expression
grammar, by using the precedence directives instead of auxillary
non-terminals. The resulting parser will be either smaller or faster.
The reason for this is that the parser generator is exploiting the
ambiguous nature of the grammar, and generating a parser which only
generates a subset of the legal parse trees.


- Chris
--

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