Recursive Descent Parser - Example Parser

Example Parser

The following EBNF-like grammar (for Niklaus Wirth's PL/0 programming language, from Algorithms + Data Structures = Programs) is in LL(1) form:

program = block "." . block = {"procedure" ident ";" block ";"} statement . statement = [ident ":=" expression | "call" ident | "begin" statement {";" statement} "end" | "if" condition "then" statement | "while" condition "do" statement ] . condition = "odd" expression | expression ("="|"#"|"<"|"<="|">"|">=") expression . expression = term {("+"|"-") term} . term = factor {("*"|"/") factor} . factor = ident | number | "(" expression ")" .

Terminals are expressed in quotes. Each nonterminal is defined by a rule in the grammar, except for ident and number, which are assumed to be implicitly defined.