Monday, March 7, 2011

Language Implementation Patterns by Terrence Parr

Rating: Lot's of information, but poorly presented.

Basic Patterns:
  • Mapping Grammars to Recursive-Descent Recognizers: convert formal language specification (grammar) into a parser.
  • LL(1) Recursive-Descent Lexer: break up character streams into tokens.
  • LL(1) Recursive-Descent Parser: make a parsing decision (choose parsing method) for the current (1) input symbol.
  • LL(k) Recursive-Descent Parser: make a parsing decision (choose parsing method) for up to k next input symbols.
  • "A language is just a set of valid sentences."
  • "To parse, then, is to conjure up a two-dimensional parse tree from a flat token sequence."

This book could have been much better. It suffers from the following problems:
  •  Code examples:
    • Incompleteness - critical functions are missing initially: code which uses match() starts on page 41, but match() implementation is shown on page 55 for the first time.
    • Names of variables and functions are cryptic/not clear and do not follow one convention: 
      • variable names: T, p, c, x, k, i, r, Integer memoI, int memo, FOLLOW_INT_in_point37, _save,
      • function names: LT(), LA(), isSpeculating(), alreadyParsedRule(), _list(), speculate_stat_alt1().
  • Critical terms are used without introduction.
  • Definitions seem chaotic/incomplete.
  • Concepts are introduced in chaotic order.
  • Some concepts seem to change meaning: current token becomes a lookahead token.
  • There is a lot of alternative terminology that is used without introducing it properly: here are my notes on  "lexer":  Lexer: a type of recognizer; aka scanner, aka lexical analyzer, aka tokenizer: reads a stream of characters and yields a stream of tokens aka input symbols, aka vocabulary symbols.

No comments:

Post a Comment