3
Contributors
2
Replies
19
Views
2 Years
Discussion Span
Last Post by Schol-R-LEA
1

write a program for left recursion?

Setting aside the fact that you are asking us to do your work for you, which is against the general policy of Daniweb, this sentence (fragment) doesn't make much sense.

I assume what you meant was that you need to write a parser that handles left recursion in the target grammar. There are two basic approaches to doing this, but neither of them a simple, and they certainly aren't something even the wizards of Daniweb could just whip up, at least not without knowing the grammar in question.

The first approach is to write a bottom-up parser, assuming an LR(k) grammar. However, writing a such a parser by hand simply isn't feasible; they are usually generated, which means you would need to write a parser generator rather than a parser per se. That, needless to say, is a lot of work, and we'd need to see the grammar first to know just what type of parser would be suitable.

The other alternative is to convert the left recursions to right recursions, making it feasible to write a top-down recursive-descent LL(k) parser, which is pretty much the only type suitable for writing by hand. That isn't an easy thing to get right, and no matter what the working grammar will still differ subtly for the language's reference grammar. This is probably what you wanted, but if so, where's the grammar to transform?

Edited by Schol-R-LEA

This topic has been dead for over six months. Start a new discussion instead.
Have something to contribute to this discussion? Please be thoughtful, detailed and courteous, and be sure to adhere to our posting rules.