[CSUSB] >> [CompSci] >> /pool/faculty/dick/cs320/sebesta/04

## 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).

Skip

## Revision Exercises

Do not attempt any exercises after number 8!