Recursive Descent Parser
A recursive descent parser is a computer program designed to take input as a language, such as a list of tokens generated by the lexer, interactive online commands, markup tags, sequential source program instructions, or some other form of defined interface, and convert it into an abstract data structure that can be handled by other programs, such as other parts of a compiler. Usually this conversion involves breaking the input up into usable parts that is done using recursion. It is basically a translator and is usually part of a compiler. This particular type of parser, a recursive descent parser, uses recursive procedures to model the parse tree that is to be constructed that is it is an algorithm that calls itself within some part of executing its own task. It can be as simple as taking a string of input and cutting off the first part of the string and loading it into a string list. Turbo Pascal is an example of a recursive descent parser.
There are typically three subsections to a recursive descent parser. The first part of the algorithm divides the problem into one or more simpler or smaller parts of the overall problem. In particular for each nonterminal in the grammar, a procedure that parses a nonterminal is constructed that processes the right-hand side of the production.
Each of these constructed procedures can accept input, match terminal symbols, or call other procedures to accept input and match terminals in the right-hand side of a production. Because the right-hand side of the production itself is a nonterminal, the body of the procedure will consist of a call to itself. The second subsection invokes the function to be performed over and over on each part. The third subsection combines the solutions of the individual parts into a solution for the overall problem. In recursive descent parsing the grammar is thought of as a program with each production as a recursion or recursive procedure. So there would be a procedure corresponding to the nonterminal program.
LL(1) parsing is often described as table-driven recursive descent parsing. This is a top-down parsing method that proceeds by expansion of productions, beginning with a start symbol. Recursive descent parsing has the same restrictions as the general LL(1)-grammar type parsing method. This particular type of parsing is most effective and appealing when the language is LL(1), when a quick compiler is called for, and where there is no tool available.
This is the complete article, containing 407 words
(approx. 1 page at 300 words per page).
