21 Jan 1997 23:30:52 -0500

Related articles |
---|

[2 earlier articles] |

Re: Recursive descent and left recursion hogan@rintintin.Colorado.EDU (1997-01-15) |

Re: Recursive descent and left recursion dlmoore@ix.netcom.com (David L Moore) (1997-01-16) |

Re: Recursive descent and left recursion cfc@world.std.com (1997-01-16) |

Re: Recursive descent and left recursion fjh@murlibobo.cs.mu.OZ.AU (1997-01-16) |

Re: Recursive descent and left recursion cfc@world.std.com (1997-01-17) |

Re: Recursive descent and left recursion will@ccs.neu.edu (William D Clinger) (1997-01-17) |

Re: Recursive descent and left recursion cfc@world.std.com (Chris F Clark) (1997-01-21) |

Re: Recursive descent and left recursion schoebel@eicheinformatik.uni-stuttgart.de (1997-01-25) |

From: | Chris F Clark <cfc@world.std.com> |

Newsgroups: | comp.compilers |

Date: | 21 Jan 1997 23:30:52 -0500 |

Organization: | Compilers Central |

References: | 97-01-099 97-01-126 97-01-144 |

Keywords: | parse, LL(1) |

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

--

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.