# Language1

### Constructing Nest

I made this as part of my teaching materials for CS 381 : Summer 2011 at OSU where I was the instructor. It shows how to create a very small interpretor for a toy stack language.

#### Example operations

We are starting with an extremely simple language, given by simple operations on a stack. for e.g

```
1 2 + => 3
2 2 * => 4
2 3 dup => 2 3 3
2 1 + dup * => 9
1 2 3 swap => 1 3 2
0 1 2 3 pop => 0 1 2
```

Can you guess what these evaluate to?

`2 3 4 + *`

`2 3 swap 4 swap + *`

`1 dup 2 + + 3 swap dup + swap pop`

Concatenative languages are simple Turing-complete languages that have very minimal syntax. They provide a set of primitives to operate on the program stack, and little else.

Try writing the BNF rules for this language. Remember, the rules are extremely easy. Do not spend too much time thinking about it.

#### Parsing

```
module Main where
```

So, here is our starting point. It starts by looking at a provided string, and parses into a nested
structure given by the data type `Nest`

. Our nesting is provided by square brackets.

```
import Text.ParserCombinators.Parsec
data Nest = W String
| I Int
| Nested [Nest]
deriving (Show)
```

Read a line and Parse it, returning the Nest data structure.

```
readLine :: String -> IO Nest
readLine input = case parse parseExpr "nest" input of
Left err -> error (show err)
Right q -> return q
```

Parse a number of words or nested structures.

```
parseExpr = do
x <- many parseSingle
return $ Nested x
```

Parse either a single word or a pair of nested brackets `[]`

```
parseSingle :: Parser Nest
parseSingle = do
spaces
x <- (try parseInt) <|> (try parseWord) <|> (try parseNest)
spaces
return x
```

Parse a nested structure starting with `[`

and ending with `]`

```
parseNest :: Parser Nest
parseNest = do
char '['
e <- parseExpr
char ']'
return e
parseInt :: Parser Nest
parseInt = do
i <- many1 digit
return $ I (read i)
```

Parse a simple word without any spaces or nesting between them.

```
parseWord :: Parser Nest
parseWord = do
w <- many1 (noneOf " \n\r\t[]")
return $ W w
```

### Run these commands and see what they print out.

```
readLine ""
readLine "1 2 3"
readLine "1 2 + 3 dup"
readLine "[1 [2 +]] dup"
```

#### Are there any surprises?

Our language has the following literals,

- numbers such as 1 2 3 …
- combinators (functions)
- pop, swap, dup, + -

##### Can you write the BNF notation for this language?

Remember, a BNF notation for a simple expression language looks like this

```
<digit> ::= 1 | 2 | 3 | ... | 0
<num> ::= <digit> | <digit> <num>
<expr> ::= <expr> + <expr>
| <expr> - <expr>
| <num>
```

Do we need anything representing `<expr>`

in our *BNF*?