Language Implementation Patterns

Pattern 3

LL(1) Recursive-Descent Parser

Purpose

This pattern analyzes the syntactic structure of the token sequence of a phrase using a single lookahead token.

This parser belongs to the LL(1) top-down parser class in particular because it uses a single token of lookahead (hence the “1” in the name). It’s the core mechanism of all subsequent parsing patterns.

Discussion

This pattern shows how to implement parsing decisions that use a single token of lookahead. It’s the weakest form of recursive-descent parser but the easiest to understand and implement. If you can conveniently implement your language with this LL(1) pattern, you should do so. Pattern 4, ​LL(k) Recursive-Descent Parser​ uses multisymbol lookahead, which is more powerful but has ...