Index of /courseware/cse3322/2006/04impl

 Name                    Last modified       Size  Description

 Parent Directory        12-Dec-2006 14:37      -  
 slides.pdf              17-Aug-2006 18:41   1.6M  
 slides2x2.pdf           17-Aug-2006 18:41   685k  
 DP.shtml                01-Nov-2006 16:34     2k  

Implementation

Also see

[glossary].

And re notes

Imp. III, top-down parsing (p.55+):

See a [worked example].

Also see the [Algol-60 revised report] re `dangling else'.  NB. the production rules use `::=' in place of `->'.

Imp. IV-V (p.79+):

re error recovery, a real example:

[pascals.p] is a parser+compiler+interpreter for PascalS by N.Wirth. (The parser is by recursive descent.) Each procedure implementing a non-terminal of the grammar, for example,

  procedure expression(fsys: symset; var x: item); forward;

has a symbol-set parameter to skip (procedure skip) to if a parsing error is detected. When called, the symbol set parameter depends on the context, e.g.,

  expression(fsys+[thensy,dosy], x)

when called from procedure ifstatement to analyse the control expression of an `if <expression> then ... else ...'. (The `thensy' is obvious; the `dosy' is there because `if...do...' is a common error.)

Imp VII, bottom-up parsing (p.118+)

See a [worked example].

Imp VIII, SLR(1) table construction (p.140+)

See a [worked example].

Imp IX, re CYK parsing (p.158+)

Grammar in Chomsky Normal form:

E -> int

E -> E E'

E' -> P E

P -> +

dyn prog. parsing of: int+int+int
E=int		E=int+int		E=int+(int+int) E=(int+int)+int
	P=+	E'=+int		E'=+(int+int)
		E=int		E=int+int
			P=+	E'=+int
				E=int
NB. two possible parses

Imp. X, code generation (p.193+), covered in L19, week 10:

On runtime environment, see [generating code] for stack management, variable access, proc-calling -entry & -exit, and parameters;

intermediate code generation;

register allocation.

 

[Summary]

 

NB. The very final section of the .pdf `implementation' notes on the formal theory of polymorphic type checking is not examinable, although you should be able to describe, and apply, the steps by which the SML compiler infers the types of functions such as [map], foldl, curry, [trav], etc..