CS 320—Week 8 Homework—Due W 3/27 11:59pm
Write your answers to the problems in the space indicated. Scan your solution and submit
to Gradescope as a PDF file. You will receive an email about the Gradescope account.
You may do this from your phone using free scanning apps, or with a desktop scanner.
Do NOT edit this file and move things around, the format must remain the same.
Problem One (Monad Do Expressions)
This problem will exercise your understanding of the “assembly language” of Haskell’s do
expression syntax. “Translation” in this exercise refers to converting between the forms
(i), (ii) and (iii) shown on the last page. Use bound variables x, y, and z (as necessary).
(A) Show what phase (i) of the translation for example ex9’ in
MonadLectureCode2.hs would look like (this is in the Maybe Monad).
(B) Show what phases (i) and (ii) of the translation for example ex14 in
MonadLectureCode2.hs would look like (this is in the Maybe Monad).
(C) Show what phases (i) and (ii) of the translation for example ex4 in
MonadLectureCode3.hs would look like (this is in the Checked Monad).
Name: BU ID (no dashes):
S -> E
E -> E + T | T
T -> T * F | F
F -> P ^ F | P
P -> - P
P -> 1 | 2 | 3
Problem Two (Derivations and Parse Trees)
This problem concerns context-free grammars and the relationship between
parse trees and derivations, using the grammar shown at right.
(A) Give a left-most derivation of the string
3 * 2 + - 3 ^ 1 .
(B) Give a right-most derivation of the string
3 * 2 + - 3 ^ 1 .
(D) Suppose we consider the parse tree you created in part
(C). If you walk around the tree in preorder, and each time
you touch a non-terminal, you add a derivation step to a
derivation, what kind of derivation would result?
(E) Considering the same process as in (D), what kind of traversal of a tree would
correspond to a right-most derivation (see at the link on traversals posted with lecture 2)?
(F) Give a short, informal proof of the following statement: If a grammar is not
ambiguous, then for any string w in the language, every derivation of w has the same
length (same number of derivation steps). Hint: think about the relationship between
derivations and parse trees.
In (A) and
(B) you do
not need to
give the
number of
the rule, nor
underline
the nonterminal
being
rewritten at
each step.
See the YT
video for
hints on
how to do
(D) and (E).
(C) Give a parse tree for the string
3 1 + - 2 .
Problem Three (Context-Free Grammars and Languages)
This problem will have you write context-free grammars and also think about how to
characterize context-free languages.
For parts (A) and (B), give an intuitive description of the language generated by the given
context-free grammars, where T = { a, b }.
(A) S -> a A | b A -> a S | b A | ?
(B) S -> a S b S | b S a S | ?
For parts (C) and (D), give a context-free grammar for the language specified.
(C) The language of matching delimiters over the alphabet:
{ } [ ] ( )
The following are in the language: (()) ({}) {()}{}
and the following are not: ({)} {{{}}) ?
(D) The language { an bm an | n ≥ 0 and m>1}, i.e., strings aaa..abbb…baaa..a with at least
one b, and starting and ending with substrings of a’s of the same length.
The following are in the language: b abbbba aaabbaaa
and the following are not: aaba aaaa (i) =>(ii) =>(iii) =>
This page for reference ONLY, please do not scan and submit this page!
因為專業，所以值得信賴。如有需要，請加QQ：99515681 或郵箱：99515681@qq.com?
微信：codinghelp
)
)