PROG$24310$: Programming Languages

Evaluation:

$10$ points, $10\%$ of your final grade.

Due date:

See SLATE.

Late submission: $10\%$ per day penalty, up to $3$ days.

Problem N$1(3$ points$).$

You have the following context$-$free gramma:

$S$BAA

$A$Aab$|b$

$BBa|b$

Using the grammar above, is it possible to derive a string "baababbabab" $?$

If so$,$ please provide the derivation process and build the abstract syntax tree.

Is this grammar ambiguous? If so$,$ you need to explain why it is ambiguous $($please

provide an alternative AST$)$ or explain why you cannot build an alternative AST.

Main Requirements: the derivation must be canonical $($either left$-$most or right$-$

most, but not the combination of both$).$ You must show every step of the derivation

process and use brackets $[]$ for the next symbol you are replacing.

Example: $S->[$C$]$D means on the next step you will be replacing symbol $C.$

You must maintain the proper level of all the nodes in the AST

Hint: To prove ambiguity, you must show two different ASTs that produce the same string $($you can

use non$-$canonical derivations in the proof$)$ or prove that no such derivations exist.