Skip to Main Content
Language Implementation Patterns
book

Language Implementation Patterns

by Terence Parr
December 2009
Intermediate to advanced content levelIntermediate to advanced
380 pages
9h 2m
English
Pragmatic Bookshelf
Content preview from Language Implementation Patterns
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 ...

Become an O’Reilly member and get unlimited access to this title plus top books and audiobooks from O’Reilly and nearly 200 top publishers, thousands of courses curated by job role, 150+ live events each month,
and much more.
Start your free trial

You might also like

Implementation Patterns

Implementation Patterns

Kent Beck

Publisher Resources

ISBN: 9781680500097Errata Page