Parsing and lexical analysis dictionary
---------------------------------------
Most of it from the "dragon book" (DRB).

symbol
  Unit making up a language. Can be either a terminal (token) or a
  nonterminal.

token
  Basic symbols from which strings of the language are formed.
  (Synonym for terminal when we talk about programming languages.)
  
terminal
  Basic symbols from which strings of the language are formed.

nonterminal
  Syntactic variables that denote sets of strings. They define sets of
  strings that help define the language generated by a grammar. They
  also impose a hierarchical structure on the language that is useful
  both for syntax analysis and translation.

start symbol
  A nonterminal defining the set of all valid strings defined by the grammar.

production
  Specifies how terminals and nonterminals can be combined to form
  strings. Consists of a nonterminal, followed by an arrow, followed
  by a string of nonterminals and terminals. For example:
       expr -> expr op expr

bottom-up parsing

shift-reduce parsing
  A bottom-up syntax analysis technique.

LR parsing
  Efficient, bottom-up syntax analysis technique that parse a large
  class of context-free grammars.

  denoted LR(k) where
   L: left-to-right scanning of input
   R: constructing a rightmost derivation in reverse
   k: number of input symbols of look-ahead

LR parser
  Consists of input, output, stack, driver program and a parsing table
  with two parts (action and goto). The driver program is the same for
  all LR parsers, only the parsing table changes.

  The stack is used to store strings of the form
  s0,X1,s1,X2,s2,...,Xm,sm where Xi are grammar symbols and si are
  state symbols that summarize the contents of the stack below it. The
  combination of the current input symbol and the state symbol on top
  of the stack are used to index the parsing table and determine the
  shift-reduce parsing decision. In an implementation, the state
  symbols need not appear on the stack.

  The parsing table consists of two parts, a parsing action function
  (action) and a goto function (goto). 

  LR parser driver program in pseudo-code:
    1. get sm, the state of the stack
    2. get ai, the current input symbol
    3. lookup action(sm, ai) which can be one of four actions:
	      * shift s, where s is a state:
		      I,  push ai and s onto stack
		      II, advance input symbol
	      * reduce by a grammar production A -> b,
		      I,   pop r (state, symbol) pairs from the stack where
		           r is the length of b
		      II,  push (goto(sm-r,A), A) onto stack,
		      III, perform semantic action associated with production
	      * accept, terminate because parsing is complete
	      * error, call error recovery routine

  Full description of algorithm on pp. 218 in DRB.

SLR
  see SimpleLR parsing.

SimpleLR parsing
  LR parsing that is easy to implement but that may fail to produce
  parsing table for which LALR and CanonicalLR succeeds.

CanonicalLR parsing
  Powerful but more expensive (than SLR and LALR) LR parsing.

LALR parsing
  Look-Ahead LR parsing. Intermediate in power and cost between
  SimpleLR and CanonicalLR. Will work on most programming-language
  grammars and can be implemented efficiently.

item
  see LR(0) item.

LR(0) item
  A production of a grammar with a dot at some position of the right
  side. Intuitively, an item indicates how much of a production we
  have seen at a given point in the parsing process.

  An item can be represented by a pair of integers, the first
  giving the number of the production and the second the position in
  the production.

FIRST(rhs)
  Set of tokens that appears as first symbols in string(s) generated 
  from rhs. rhs is right-hand-side of a production for a nonterminal.

  Algorithm is on pp. 189 in DRB.

FOLLOW(A)
  Set of terminals that can appear immediately to the right of A in some
  sentential form, that is, the set of terminals a such that there exists
  a derivation of the form S => xAaB for some x and B. 

  Algorithm is on pp. 189 in DRB.

CLOSURE(I)
  pp. 222 in DRB.

  Set of items constructed from I (set of items)
  
GOTO(I, X)
  pp. 224


