---
# System prepended metadata

title: Lecture 4
tags: [PSD]

---

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

![](https://i.imgur.com/f3ZmVmz.png)

**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**
```F#
    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 

![](https://i.imgur.com/h7hWaJ7.png)

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: 
![](https://i.imgur.com/LUVixtN.png)

which one should the parser chose?
![](https://i.imgur.com/fxOnbVt.png)

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


