Contents

• REGULAR LANGUAGES
  • Regular Expressions
  • Non-Deterministic Finite-State Automata
  • Deterministic Finite-State Automata
  • DFA minimisation
  • Further Properties of Regular Languages
  • Grammars
  • Regular Grammars
  • Converting an FSA to a Regular Grammar
  • Limitations of Regular Languages
  
  
• CONTEXT-FREE LANGUAGES
  • The Chomsky Hierarchy
  • Grammars for Programming Languages
  • Derivations and Parse Trees
  • Modifying Grammars
  • PUSH-DOWN AUTOMATA
  • Proving that a Language is not Context-Free
  • The Closure of Context-Free Languages
  • Decision Problems for Context-Free Languages
  
  
• TOP-DOWN PARSING
  • Recursive Descent Parsing
  • Lookahead
  • Implementing a Parser
  • The Parsers
  • Early's Parser
  • Unger's Method
  
  
• BOTTOM-UP PARSING
  • Bottom-Up (Shift-Reduce) Parsing
  • items
  • Handle-recognising DFAs and LR(0) Parsers
  • SLR(1) Parsers
  • Parsers
  • Parsers
  • Tomita's Parser
  • CYK Method
  
  
• About this document ...

REFERENCES

The Art of Compiler Design by T. Pittman & J. Peters (Prentice-Hall, 1992).

Lex and Yacc by T. Mason and D. Brown (Addison-Wesley, 1992).

Additional References

Introduction to Compiler Construction with UNIX by A Schreiner & H Friedman (Prentice Hall, 1985).

Introduction to Compiling Techniques by J. Bennett (McGraw-Hill, 1990).

Compilers: Principles, Techniques and Tools by A. Aho, R. Sethi & J.Ullman (Addison-Wesley, 1986).

Introduction to Languages and the Theory of Computation by J. Martin (McGraw-Hill, 1991).

Compiler Design in C by A. Holub (Prentice-Hall, 1990).

The theory and practice of compiler writing by J.Tremblay & P. Sorenson. (McGraw-Hill, 1985).

Elements of the Theory of Computation by H. Lewis & C. Papadimitriou. (Prentice-Hall, 1981).

Crafting a Compiler by C. Fischer & R. LeBlanc. (Benjamin/Cummings, 1988).

Syntax of Programming Languages by R. Backhouse. (Prentice-Hall, 1979).