Readings and Exercise for Compile Time Structures-Part 1

Exercises: (Please use our publishers Gradiance System to practice)

Chapter 1: Introduction

Exercise 1.1.1, 1.1.2, 1.1.3, 1.1.4, 1.1.5 (p. 3)
Exercise 1.3.1 (p. 14-15)
Section 1.6 Programming Language Basics
Definition of Static / Dynamic policy for scope of declarations.
Exercise 1.6.1; 1.6.2; 1.6.3; 1.6.4 (p. 36)

Chapter 2: Simple Syntax-Directed Translator

Section 2.7 Symbol Tables

Chapter 3: Lexical Analysis

Exercise 3.1.1
Exercises 3.3.5, 3.3.6, 3.3.7, 3.3.8 [Reg Exprs]
Exercises 3.4.1; 3.4.2 [Transition Diagrams for Reg Exprs]
Exercise 3.7.3 [Construct DFA from Reg Expr - using your insight]

Chapter 4: Syntax Analysis

Exercise 4.2.1 [Given CFG, produce leftmost derivation, rightmost derivation, parse tree] Exercise 4.2.2 [especially g)]
4.4.2 FIRST and FOLLOW
4.5 Bottom-Up Parsing [All Sections]
4.6 Introduction to LR Parsing: Simple LR
4.6.2 Items and the LR(0) Automaton
Definition of Item Sets and the Closue of Item Sets
Fig 4.31 LR(0) Automaton for the Expr Grammar (4.1) [Disambiguated]

E'-> E
E -> E + T | T
T -> T * F | F
F -> ( E ) | id  ** note typo in text

Srart with E' -> .E [Note the dot (.) before E) and apply closure. Then identify transition states

The Function GOTO

Construct Fig 4.31 in Class. Which states are Reduce States? Which states are Shift States? Are there any Shift/Reduce States? Example 4.43 (Figure 4.34) The parse of id * id using a Stack.

4.6.3 The LR-Parsing Algorithm
Fig. 4.35 Model of an LR parser
Fig. 4.36 LR-parsing program
Fig. 4.37 Parsing table for expression grammar
Fig. 4.38 Moves of an LR parser on id * id + id

4.6.4 Constructing SLR-Parsing Tables