top-down parsing
recursive descent
lookahead
FIRST, FOLLOW sets
LL grammars
LL(1)-ness
 - eliminating left-recursion
   L -> L , id | id
 - eliminating common prefixes
   E -> id := E | id (E) 

bottom-up parsing
examples
 - JJTree
 - YACC
note: left recursion is good!
LR handles
state machines can recognize handles (i.e., regular set)

Classes of Languages

CFL, ACFL, DCFL, LR, LL, ...

Right Associative production rules
- better for bottom-up parsing, where shift-reduce is used
- example:
    E -> E * F
    E -> F
    F -> F + T
    F -> T
- if time, explain LR handles, relationship to NFA handle recognizers

Left Associative production rules
- better for top-down parsing (and recursive descent parsing)
- example:
    E -> F * E
    E -> F
    F -> F + T
    F -> T
- consider the recursive descent program if we use right assoc. production,
    E -> E * F

E() { 

  call E();  // goes into infinite loop, here.

  consume("*");

  call F();

}

Yacc/Lex (70's Ritchie, Johnson) generates C program
Bison/Flex - from GNU project
JJTree (Java)

Well-formed checks
(DTD) validating parsers
RelaxNG or XMLSchema validating parsers (NEW)

CFL theory.

Pumping lemma for CFLs

[tree picture]
u = vwxyz

and we pump strings w,y simultaneously.

Homomorphism

Σ^1 and Σ^2 are two alphabets.

h(a) -> w, where w is a string in Σ^2

h(s) is defined for strings (via concatenation)
h(L) is defined for languages.

Examples.

a^n b^n is a CFL.

HTML is a CFL.

L = { ww | where w in Σ* } is not.
Consider L intersect a+b+a+b+ = a^m b^n a^m b^n

XML is not a CFL.
CFL's are closed under homomorphism and inverse homomorphism.

Proof:
Through a series of homomorphisms we can reduce and eliminate all but the first
element tag and and its matching end tag into the language,
L = { ww | w in Σ* }

How do we parse XML if it's not a CFL?
The answer lies in semantically smart tokenizers.

[ draw picture of lexer, parser architecture ]

Show IOStream as event model.
Define Lexer using similar event model, but returns tokens, not chars.

class TokenStream {

 public static TokenStream create (IOStream);

 public Token getToken() throws NoMoreTokensException;

 public static NoMoreTokensException extends Exception {}

}


So define the CFG for XML over an alphabet of token rather than over the
alphabet of characters.  Then to determine if an input is accepted, either the
tokenizer can be made "smart enough" to detect matching element names or a
final semantic check can be used.

Most programming languages are not CFLs.

Some are easier to separate concerns, thus processing lex, parsing, sematic
analysis stage-wise.

Why important:

1. compilation phases work better when resources are tight
2. incremental compilation is easier more likely to be correct (e.g., IDEs)

in decreasing order of difficulty/less problematic:  
C - consider typedef nightmare
C++ - still have typedef nightmare
Ada -  but compilation units - linker prob's cannot be done easily
Pascal, Java, CLU, others...
Lisp, Scheme, Prolog - trivial lex and syntax but unwieldy semantics