代做CS 320、代写Python，c/c++编程设计、代做Java程序、代写desktop scanner

日期：2019-03-24 10:28

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!