31-10-2012, 04:51 PM
Recursive descent parsing
Recursive descent.ppt (Size: 72 KB / Downloads: 126)
Some notes on recursive descent
The starter code that I gave you did not exactly fit the grammar that I gave you
Both work, both are correct
Many things can be coded either recursively or iteratively
I gave you an iterative grammar and recursive code
Recognizers and parsers
A recognizer tells whether a given string “belongs to” (is correctly described by) a grammar
A parser uses a grammar to construct a parse tree from a given string
One kind of parser is a recursive descent parser
Recursive descent parsers have some disadvantages:
They are not as fast as some other methods
It is difficult to provide really good error messages
They cannot do parses that require arbitrarily long lookaheads
And some advantages:
They are exceptionally simple
They can be constructed from recognizers simply by doing some extra work—specifically, building a parse tree
Recursive descent parsers are great for “quick and dirty” parsing jobs
The Stack
One easy way to do recursive descent parsing is to have each parse method take the tokens it needs, build a parse tree, and put the parse tree on a global stack
Write a parse method for each nonterminal in the grammar
Each parse method should get the tokens it needs, and only those tokens
Those tokens (usually) go on the stack
Each parse method may call other parse methods, and expect those methods to leave their results on the stack
Each (successful) parse method should leave one result on the stack