Sebesta Chapter 4 -- Compilation

	http://www.csci.csusb.edu/dick/cs320/sebesta/04.html

Content

	4.1 Introduction
	4.2 Lexical Analysis
	4.3 The Parsing Problem

	4.4 Recursive-Descent Parsing
	4.5 Bottom-Up Parsing

	Revision Exercises

Introduction

	Reasons for splitting lexical analysis from parsing

Lexical Analysis

	A stream of characters is input and
		a stream of tokens come out
	token
	pattern recognition
	regular expressions
	State Diagrams
	UNIX tool: lex

The Parsing Problem

	Recognise syntactice units and
		construct data structures that encodes the incoming program.
			Container of names (easier)
			Syntax tree(tougher)

	Too approaches
		Top-down
		Bottom-up

	->wise person uses a tool.
		Tools: yacc, bison, ...
	

Recursive Descent Parsing

Skip but
	Notice how very easy it is to turn most grammars into a
		program that parses the incoming data.  If you can
		write the EBNF for something you have the structure
		of a program to process the data.
	Here is the simplest coding:
	A::= ...		void A() { .... }
	 ... #A ...		while(an_A_is_next()) A();
	 ....A | B ....		if(an_A_is_next()) A(); else B();

	Unless the grammar has left recursion like this
		A ::= A "+" B | C.
	the mapping works well.
	But you can replace these definitions by a routine transformation.
	In the above case we have:
		A ::= C #("+" B).

Bottom-Up Parsing

Skip

Revision Exercises

Do not attempt any exercises after number 8!