# Lecture 4

###### tags: `PSD`

## Chapter 4: First-order functional language

A functional programming language is one in which the evaluation of expressions and function calls the primary means of computation.


**Examples and abstract syntax**

we will extend our expression language.

two examples:

Prim("+", Var "z", CstI 8)

Letfun("f", "x", Prim("+", Var"x", CstI 7), Call(Var "f", CstI 2))

The component of a function binding Letfun (f, x fbody, letBody) in have the concrete syntax let f x = fbody in letBody end

f is the function name
x is the parameter name
fBody is the function body, or function right-hand side
letBody is the let-body

**Run-time values: integers and closures**

A function closure is a tuple (f, x, fbody, fDeclEnv) consisting of the name of the function, the name of the function parameter, the function body expression and the function declaration environment.

**A simple environment implementation**

    type 'v env = (string * ´v) list;;

we will use a simple environment representation: a list of pairs where each pair (k,d) contains a key k and some data d.

## Lecture notes from slides

### LR versus LL parsing

LR:
- read input from Left to right, make derivations from Rightmost nonterminal
- buttom-up parsing
- difficult to hand-write parsers
- no grammar transformation required.

LL:
- read input from Right to left, make derivations from Leftmost nonterminal
- top-down parsing

### Parser state


Parser state = parser stack, containting:
- parser statw numbers: #n
- Grammar symbols: terminals and nonterminals

Parser actions:
- shift: read a symbol from input onto the stack, and go to new state
- reduce: take grammar rule rth symbol off the stack and replace them by its ith nonterminal and evaluate a semantic action
- Goto: go to a new parser state (after reduce)

### Shift/redice conflicts

When the grammar is ambiguous the parser generator does not know whether to shift or to reduce.

Then warnings ar issued by fsyacc

example:

which one should the parser chose?

to resolve shift/reduce conflicts, change the parser specification.