Top-Down Parsing with recursive grammar

Question

I have an assignment in school which tells us to create a Top-Down Parser in Java which follows this grammar:

    assign = id , '=' , expr , ';' ;
    expr = term , [ ( ’+’ | ’-’ ) , expr ] ;
    term = factor , [ ( ’*’ | ’/’) , term] ;
    factor = int | ’(’ , expr , ’)’ ;

I think I have understood the basics concepts of parsing, such as "if we have an id, check if the next token is a '=' and the next is an expr, and if the next after that is a ';'". Correct?

Now, if I want to check if the incoming input is an expression:

I check the tokens to see if a term is there, then if a "+ token" OR "- token" is there, and finally if an "expr" is there. But, if I check if there's an "expr" there, it's going to loop, and eventually check again if there's an "expr", and again, and again.

I don't see how I can get that too work? Can someone help me?

Kind regards,

I created a scanner to read the input stream and return each token it has read to a parser. The parser then checks if the token returned fits somewhere in the grammar, and continues the parsing from there, analysing the next token returned to see if it continuously follows the grammar rules. When I get to the check if there's an expression, the grammar says that an expression needs an expression in the end. This way, the "expression check" will loop into itself to see if it's an expression, and that loop will be infinite in my eyes. Understand the problem? Hard to explain .. :) — Murmeel, Nov 12 '15 at 09:41
I mean , show some codes, you shouldn't expect someone to do it all for you — nafas, Nov 12 '15 at 09:47
I understand you. The question is not about how to write the code. It's about making me understand how it works. I can write code just fine, but it's hard to implement something unless I know how it can work out. I've done some research and I think I might have found the answer I've been looking for. If not, I'll see if I can provide you with something to help you help me :) Thank you, Murmeel — Murmeel, Nov 12 '15 at 09:56
Check out my SO answer on how to write a recursive descent parser: http://stackoverflow.com/questions/2245962/is-there-an-alternative-for-flex-bison-that-is-usable-on-8-bit-embedded-systems/2336769#2336769 In particular, it explains how to handle parsing of a recursive form, and repeated forms. — Ira Baxter, Nov 12 '15 at 10:27
@Murmeel: sometimes when you don't understand a programming concept, the easiest thing to do is simply implement it and see what happens (make sure you have good debugger and know how to use it). The act of stepping through your implemention is often pretty instructive. Either it will become obvious what you implemented does the right thing, or it will become obvious it does not. In either case, you learn something. Why agonize when you can try a prototype easily? — Ira Baxter, Nov 12 '15 at 10:35

score 0 · Accepted Answer · answered Nov 12 '15 at 10:33

OP seems worried that if his code for the expr rule calls the parsing rule for expr, it will get caught in an infinite loop.

He need not worry!

It takes a bit of thought, but what actually happens when that call C1 is made, is that the called expr rules tests for a term. If that is the last term in the set of summands that comprise the expr, there will be no following plus/minus and the C1 call will terminate and return to the parent parsing routine, which will then be complete. No loop.

If it is not the last term, the term will get parsed, plus/minus will be seen, and the C1 instance will make another call C2 back to expr. This recursion acts like one loop iteration, and gets treated as we have described.

Should work just fine.

You, Sir, got that brain of mine going. I nailed it. Thank you. — Murmeel, Nov 12 '15 at 18:23

Top-Down Parsing with recursive grammar

1 Answers1