Parsing input based on grammar rules
Hi guys, I'm new to the forum here, hoping to contribute as I can. I have a question though.
I have set grammar rules, some being recursive. I am to create a basic top down parser from scratch (i.e. not using JavaCC or anything like that). I was told to use a queue to create the parse tree.
I am kind of unsure how to start this.. If i tokenize the input, then that's not really top down right?
I am thinking i have to recursively expand the grammar rules and constantly check if the leaves match the input string, is this correct? I have looked into recursive descent, but i'm not sure if I can use that here.
Could anyone point me in the right direction here?
Re: Parsing input based on grammar rules
Tokenizing and parsing aren't really related. Tokenizing is just taking a string (or something similar) and figuring out what it is, like an operator, number, variable name, etc. Parsing is getting the computer to figure out what order those tokens should be used based off of your grammer.
You can either tokenize your entire string first or you can tokenize each token as your parser looks for the next token.
I've never personally created a top-down parser, but you can take a look at LL parsers to see an example of a top-down parser algorithm.