Pattern 4LL(k) Recursive-Descent Parser

Purpose

This pattern analyzes the syntactic structure of the token sequence of a phrase using k>1 lookahead tokens.

An LL(k) parser augments the previous pattern with up to a fixed number of lookahead tokens, k.

Discussion

The strength of a recursive-descent parser depends entirely on the strength of its lookahead decisions. A single token of lookahead is pretty weak in that we usually have to contort grammars to make them LL(1). By allowing a larger (but still fixed) lookahead buffer, we get a parser strong enough for most computer languages. This includes configuration files, data formats, network protocols, graphics languages, and many programming languages. Some programming languages present tougher ...

Get Language Implementation Patterns now with O’Reilly online learning.

O’Reilly members experience live online training, plus books, videos, and digital content from 200+ publishers.