# CSE 428 : Solution of Assignment #1

## Question 1

1. ``` (x+2)*y

expression
|
|
term
/   |   \
term   * factor
|         |
factor   identifier
/    |   \     |
(expression)    y
/    |    \
expression +   term
|            |
term        factor
|            |
factor       literal
|            |
identifier      2
|
x

```
2. ``` 2*x+3/y-4

expression
/     |   \
expression -   term
/   |   \         |
expression   +   term     factor
/                /  |  \      |
term              term / factor identifier
/    |   \             |       |         |
term    *  factor      factor  identifier   4
|           |           |       |
factor     identifier   literal    y
|            |          |
literal         x          3
|
2

```
3. ``` 1
expression
|
term
|
factor
|
literal
|
1

```

## Question 2

1. ```  S::=S1S2
S1::=lambda|aS1b
S2::=lambda|bS2a
```
2. ```
S::=S1S1S1S1S1S2
S1::=a|b
S2::=lambda|aS2|bS2
```

## Question 3

1. For the string false and true and false there are two different derivation tree:
```

expression
/     |   \
exp   and  exp
/  |  \       |
exp  and exp   false
|         |
false      true

expression
/     |   \
exp   and  exp
|        /  |  \
false    exp and exp
|         |
true     false

```
2. ```     A::=B imp A| B
B::=B and C| C
C::=not C| D
D::=true|false
```

## Question 4

1. For word int * name[Number], there are two different derivation tree:
```
Declaration
/        \
Type     Declarator
|      /       /  |  \
int Declarator [ Number]
/       \
*    Declarator
|
name

Declaration
/      /     \
Type   *   Declarator
|         /       /  |  \
int    Declarator [ Number]
|
name

```
2. ```     Declaration::= Type Declarator
Type       ::= int|char
Declarator ::= * Declarator|Dec
Dec        ::= Dec '['number']'| Dec '('Type')' | '('Declarator')' | name

```
3. The grammar would be unambiguous because all the operators would, in the case of Declarator *, are all postfix. So in the start of the string there is name, and then, depending on the sequence of the operators, the left most operator is introduced last in the tree.

For instance:

```           int name *'['number']' '('int')' * '('char')'

Declaration
/       \
Type       Declarator
|       /      / |\
int Declarator (Type)
/      \
Declarator    *
/  /   |   \
Declarator (  Type   )
/  /   | \       |
Declarator [ number]     int
/       \
Declarator  *
|
name

```
All declarators are to the left of the tree except the first one. This is the only derivation tree of the expression.