Re: A Simple EBNF Grammar based parser

"Chris F Clark" <>
21 Jul 2002 02:07:25 -0400

          From comp.compilers

Related articles
Re: A Simple EBNF Grammar based parser (Puneet Agarwal) (2002-07-15)
Re: A Simple EBNF Grammar based parser (Puneet Agarwal) (2002-07-15)
Re: A Simple EBNF Grammar based parser (Chris F Clark) (2002-07-21)
| List of all articles for this month |

From: "Chris F Clark" <>
Newsgroups: comp.compilers
Date: 21 Jul 2002 02:07:25 -0400
Organization: Compilers Central
References: <agqaqr$npmh8$> <> 02-07-063
Keywords: parse
Posted-Date: 21 Jul 2002 02:07:24 EDT

> No, my parser is not a recursive descent parser. Actually, it can be
> used to generate Syntax Trees by parsing a given string.

Actually, your tool is not a *parser* (or parser generator) at all.
That was the confusion. Your tool is an "AST class generator".
That's a different beast. Your tool compares to JTB or JJtree. It's
a useful thing, but it is not a parser. There is no difficulty in
generating AST classes from left recursive grammars.

> Now, is it that generation of a recursive descent parser is not
> possible for a Grammar involving Left Recursion?

Yes, that is the problem. If you generate a recursive descent parser
from a grammar with left recursion, the resulting parser will loop
when it comes to a place where it has to recognize input that matches
a left recursive rule. That is why I asked the question I did. If
your tool was a parser (rather than an AST class generator), then it
would have that problem with left recursion.

> Is it easy to generate AST's for grammars with Left Recursion.?

Yes, trivial, in fact. Generating AST classes is merely a case of
traversing the grammar. There is no problem with any kind of
recursion in that traversal.

Sorry, that I didn't understand what you had done earlier,

Chris Clark Internet :
Compiler Resources, Inc. Web Site :
3 Proctor Street voice : (508) 435-5016
Hopkinton, MA 01748 USA fax : (508) 435-4847 (24 hours)

Post a followup to this message

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