Grammar for Strictness Analyser Demo
and manipulation for simple predictive parser

With lists

Clem Baker-Finch April 2003


Starting point:
==============

exp 	= num | id | if bexp then exp else exp
	| exp + exp | exp - exp | exp * exp | id(expList) | (exp)
        | exp : exp | [expList]

expList	= exp | expList, expList

bexp	= exp == exp | exp < exp | exp > exp

def	= id (parms) = exp

parms	= id | parms, parms

defs	= def | defs def

(No particular parsing reason to separate bexps from exps.)

Disambiguate:
============

exp	= if bexp then exp else exp
	| uncond

uncond	= sexp | sexp : exp

sexp	= sexp + term | sexp - term | term

term	= term * factor | factor

factor	= num | id | id (elOpt) | (exp) | [elOpt]

elOpt	= <empty> | exp exps

exps	= <empty> | exp, exps

bexp	= exp == exp | exp < exp | exp > exp

def	= id (parms) = exp

parms	= <empty> | id ids

ids	= <empty> | , id ids

defs	= def | def defs

prog	= defs

Eliminate left recursion:
========================

exp	= if bexp then exp else exp
	| uncond

uncond	= sexp uOpt

uOpt	= <empty> | : exp

sexp	= term sOpt

sOpt	= <empty> | + term sOpt | - term sOpt

term	= factor tOpt

tOpt	= <empty> | * factor tOpt

factor	= num | id | id (elOpt) | (exp) | [elOpt]

elOpt	= <empty> | exp exps

exps	= <empty> | , exp exps

bexp	= exp == exp | exp < exp | exp > exp

def	= id (parms)

parms	= <empty> | id ids

ids	= <empty> | , id ids

defs	= def | def defs

prog	= defs

Left factor:
===========

exp	= if bexp then exp else exp
	| uncond

uncond	= sexp uOpt

uOpt	= <empty> | : exp

sexp	= term sOpt

sOpt	= <empty> | + term sOpt | - term sOpt

term	= factor tOpt

tOpt	= <empty> | * factor tOpt

factor	= num | id argsOpt | (exp) | [elOpt]

argsOpt	= <empty> | (elOpt)

elOpt	= <empty> | exp exps

exps	= <empty> | , exp exps

bexp	= exp relSection

relSection = == exp | < exp | > exp

def	= id (parms)

parms	= <empty> | id ids

ids	= <empty> | , id ids

defs	= def defOpt

defOpt	= <empty> | def defOpt

Director symbols:
================

S ~ start
F ~ follow

S (exp) = {if} + S(uncond) = {(, if, num, id}
S (uncond) = S(term) = {(, num, id}
S(sOpt) = {+, -}
S (term) = S(factor) = {(, num, id}
S(tOpt) = {*}
S(factor) = {(, num, id}
S(argsOpt) = {(}
S(alOpt) = {,}
S(args) = S(exp) = {(, if, num, id}
S(bexp) = {(, if, num, id}
S(relSection) = {==, <, >}
S(def) = {id}
S(parms) = {id}
S(parmOpt) = {,}
S(defs) = S(def) = {id}
S(defOpt) = S(def) = {id}

F(sOpt) = F(exp) = { ==,<,>,then,else,comma,),id,EOF, ... }
-- urk.  Let's see if we can do without this for now.
F(tOpt) = F(exp)
F(argsOpt) = F(exp)
F(expList) = {)}
F(alOpt) = {)}
F(parms) = {)}
F(parmOpt) = {)}
F(defOpt)= {EOF