CSC$388$B Programming Languages

HW$1$ must be submitted electronically. Each assignment must be prepared with a word

processor. Acceptable file formats are: ASCI text $($like those prepared with NOTEPAD$),$ MS

Word, and PDF$.$ You should clear with me in advance any other formats.

When you prepare your homework, do not try to make it fancy. The focus is not on the form, but

on the content. "Typewriter graphics" are fine. You can scan handwritten diagrams or figures as

far as they are readable. Scanned handwritten text is not acceptable. If I cannot read something, I

will assume that it is wrong.

$1.(40$ points$)$ Using the grammar in Example $3\mathrm{.}4$ show a parse tree and a leftmost derivation for

each of the following statements $($make sure that you do not omit parentheses in your

derivations$)$:

A $=$ A $*$ B $*($C $+($A $*$ B$))$

$2.(30$ points$)$ Consider the following grammar $($S is the start symbol; $1$ and $0$ are terminal

symbols; A and B are nonterminal symbols$)$:

S $->1$B $|0$C

B $->0$C $|0$

C $->1$B $|1$

Which of the following sentences are in the language generated by the grammar $($show

derivations$)?$ If a sentence cannot be generated by the grammar, explain why.

a$)100110$

b$)101010$

c$)011010$

d$)010101$

$5.(30$ points$)$ For the following grammar and the right sentential form F $*$ id $+$ id$,$ draw a parse

tree and show the phrases, the simple phrases, as well as the handle $($E$,$ T$,$ and F are nonterminal

symbols; id is a terminal symbol$).$ Explain.

E $->$ E $+$ T $|$ T

T $->$ T $*$ F $|$ F

F $->($E$)|$ id