A recursive descent parser is a top-down parsing technique that builds parse trees from the start symbol down to terminals. It uses one procedure for each non-terminal in the grammar, with recursive function calls to handle nested structures. Each procedure matches production rules sequentially, making it intuitive to implement.
The recursive descent parser works through a systematic process. It starts with the start symbol and calls the corresponding procedure. Each procedure attempts to match production rules by consuming terminal tokens and making recursive calls for non-terminals. The parser builds a parse tree implicitly as it successfully matches input according to the grammar rules.
Let's trace through parsing the expression 'id plus id times id'. The parser starts with E, expands to T plus E, then continues recursively. Each non-terminal calls its corresponding procedure, building the parse tree as terminals are matched and consumed from the input stream.
Recursive descent parsers have specific grammar requirements. The grammar must not have left recursion, as this would cause infinite recursion. It should satisfy the LL one property for predictive parsing, meaning we can determine which production to use with just one token of lookahead. The grammar must also be unambiguous and left-factored to avoid conflicts during parsing.
To summarize, recursive descent parsers are intuitive top-down parsing techniques that use recursive procedures to match grammar rules. They require specific grammar properties like no left recursion and LL one compatibility. Despite their limitations, they remain popular in compiler construction due to their simplicity and ease of implementation.