Tutorial 1

Exercise 1

Part 1

1. A grammar defines the syntax of a language, it consists of an alphabet, a set of rules, and an initial symbol.

2. A terminal appears in the alphabet itself while non-terminals are auxiliary symbols which can be broken down further.

3. Concrete syntax defines chains of characters, while abstract syntax defines trees composed of characters.

4. Terminals: 0 to 9, + - * div Non-Terminals: Exp, Op, Num, Digit

5. Show that the following are valid expressions: $1-2-3$: Exp -> Exp Op Exp -> Exp Op Exp Op Exp ->* 1 - 2 - 3 $1+2\ast 3$: Exp -> Exp Op Exp -> Exp Op Exp Op Exp ->* 1 - 2 * 3

   The grammar is ambigous. For $1+2\ast 3$, we could generate trees of either $(1+2)\ast 3$ or $1+(2\ast 3)$. For $1-2-3$, we could generate trees of either $1-(2-3)$ or $(1-2)-3$.

   $1+(2-3)$ is not valid as brackets are not in alphabet $-1$ is not valid as there is no valid expansion to get to this state

Part 2

1. Haskell evalutes the following values: $1-2-3=-4$ $1+2\ast 3=7$
2. The second operator is the root of the AST of the first expression. The first operator is the root of the AST of the second expression. Multiplication / division takes precedence over addition / subtraction.

Exercise 2

1. Show both are valid expressions: $-(-(1,2),3)$ e -> op(e, e) -> -(e,e) ->* -(op(e,e), n) ->* -(-(n, n), n) ->* -(-(1,2), 3) $-(1,-(2,3))$ e -> op(e,e) -> -(e,e) ->* -(n, op(e,e)) ->* -(n, -(n, n)) ->* -(1, -(2,3))

There is only one result for each expression, $-4$ and $2$.

2. Explain why $-(1,2,3)$ is not a valid expression. There is no expansion rule which has three children.

Exercise 3

Given grammar from Ex. 2:

e  ::= n | op(e, e)
op ::= + | - | * | div

Add unary minus operator:

e  ::= n | op(e, e) | -e
op ::= + | - | * | div

Allow users to write expressions in form of x

e  ::= n | op(e, e) | -e
op ::= + | - | * | div | ^

Exercise 4

Part 1

Design language $L$ in which variable identifiers must be a sequence of letters or numbers starting with a capital letter. Give a grammar for identifiers in L.

Identifier ::= Uppercase | Uppercase Char
CharSeq    ::= Char | Char CharSeq
Char       ::= Uppercase | Lowercase | Number
Uppercase  ::= A | ... | Z
Lowercase  ::= a | ... | z
Number     ::= 0 | ... | 9

Part 2

1. Identifiers must start with a lowercase letter and can be followed by (nothing or any sequence of lowercase letters, uppercase letters, or digits) and the identifier cannot be one of the keywords.
2. The result of the expression is $6$. For the other programs with errors:
   • Identifier starts with capital letter which is invalid.
   • Identifier contains ”?” which is not valid.
   • Expression includes a space in the identifier which is not valid.
   • data is a reserved keyword. It is also not well formed.
   • Function definition is not well formed.