Recursive Descent Parser
RecentChanges Edit Search GoodStyle
Referenced By: RecursiveDescentParserCpp, RecursiveDescentParserHpp

To interpret an expression like "5 * (4 2^2)", an evaluator must evaluate from the ( to the matching ) as one factor, before evaluating the * to multiply it by 5. Then, inside the (), the evaluator must evaluate the ^ first, before the .

These techniques require recursion, to obey math precedence rules, and to interpret nested parenthesis. A RecursiveDescentParser reads each token inside a recursively declared filter system:

 - terms +-
  - factors */
   - exponents ^
    - parenthesis ()
     - terms recursion
    - terminal values 99.9

After finding a sought item and recursing thru the other possibles, the RDP then evaluates its intermediate terms, and returns them to the next layer up.

An example of an RDP, written via TestDrivenDevelopment?, appears here:

RecursiveDescentParserTest, RecursiveDescentParserCpp, RecursiveDescentParserHpp