ECS 140A代写、代做Canvas留学生、代写Java，c++程序设计、代做c++,Python

日期：2019-01-30 10:59

ECS 140A Programming Languages

Winter 2019

Homework 2

About This Assignment

This assignment asks you to complete programming tasks using the Go programming

language.

To complete the assignment (i) download hw2-handout.zip from Canvas, (ii) modify

the .go files in the hw2-handout directory as per the instructions in this document,

and (iii) zip the hw2-handout directory into hw2-handout.zip and upload this zip

file to Canvas by the due date.

Do not change the file names, create new files, or change the directory structure in

hw2-handout.

This assignment has to be worked on individually.

We will be using Go version 1.11.4, which can be downloaded from

https://golang.org/dl/

Run the command go version to verify that you have the correct version installed:

$ go version

go version go1.11.4 <other output>

Go 1.11.4 is installed on all CSIF machines in the directory /usr/local/go/; the go

binary is, thus, at /usr/local/go/bin/go.

Consider adding /usr/local/go/bin to your PATH.

Information about using CSIF computers, such as how to remotely login to CSIF

computers from home and how to copy files to/from the CSIF computers using your

personal computer, can be found at http://csifdocs.cs.ucdavis.edu/about-us/

csif-general-faq.

Begin working on the homework early.

Apart from the description in this document, look at the unit tests provided to understand

the requirements for the code you have to write.

Post questions on piazza if you require any further clarifications. Use private posts if

your question contains part of the solution to the homework.

1

1 triangle (5 points)

Modify the unit tests in the TestGetTriangleType function

in hw2-handout/triangle/triangle test.go.

One unit test has already been written for you.

The goal is to write enough unit tests to get 100% code coverage for the code in

hw2-handout/triangle/triangle.go.

From the hw2-handout/triangle directory, run the go test -cover command to see

the current code coverage.

From the hw2-handout/triangle directory, run the following two commands to see

which statements are covered by the unit tests:

$ go test -coverprofile=temp.cov

$ go tool cover -html=temp.cov

Do NOT modify the code in hw2-handout/triangle/triangle.go.

2 min (5 points)

Modify the Min function in hw2-handout/min/min.go.

The function Min should return the minimum/lowest value in the argument arr, and

0 if the argument is nil.

Some unit tests are provided for you in hw2-handout/min/min test.go.

From the hw2-handout/min directory, run the go test command to run the unit tests.

If needed, add more unit tests in hw2-handout/min/min test.go to get 100% code

coverage for the code in hw2-handout/min/min.go.

From the hw2-handout/min directory, run the go test -cover command to see the

current code coverage.

From the hw2-handout/min directory, run the following two commands to see which

statements are covered by the unit tests:

$ go test -coverprofile=temp.cov

$ go tool cover -html=temp.cov

2

3 nfa (10 points)

A non-deterministic finite automaton (NFA) is defined by a set of states, symbols in an

alphabet, and a transition function. A state is represented by an integer. A symbol is

represented by a rune, i.e., a character. Given a state and a symbol, a transition function

returns the set of states that the NFA can transition to after reading the given symbol. This

set of next states could be empty. A graphical representation of an NFA is shown below:

In this example, {0, 1, 2} are the set of states, {a, b} are the set of symbols, and the transition

function is represented by labelled arrows between states.

If the NFA is in state 0 and it reads the symbol a, then it can transition to either state

1 or to state 2.

If the NFA is in state 0 and it reads the symbol b, then it can only transition to state

2.

If the NFA is in state 1 and it reads the symbol b, then it can only transition to state

0.

If the NFA is in state 1 and it reads the symbol a, it cannot make any transitions.

If the NFA is in state 2 and it reads the symbol a or b, it cannot make any transitions.

A given final state is said to be reachable from a given start state via a given input

sequence of symbols if there exists a sequence of transitions such that if the NFA starts

at the start state it would reach the final state after reading the entire sequence of input

symbols.

In the example NFA above:

The state 1 is reachable from the state 0 via the input sequence abababa.

The state 1 is not reachable from the state 0 via the input sequence ababab.

The state 2 is reachable from state 0 via the input sequence abababa.

The transition function for the NFA described above is represented by the expTransitions

function in hw2-handout/nfa/nfa test.go. Some unit tests have also been given to you

in hw2-handout/nfa/nfa test.go. From the hw2-handout/nfa directory, run the go test

command to run the unit tests.

3

Write an implementation of the Reachable function in hw2-handout/nfa/nfa.go that

returns true if a final state is reachable from the start state after reading an input

sequence of symbols, and false, otherwise.

If needed, write new tests, in hw2-handout/nfa/nfa test.go to ensure that you get

100% code coverage for your code.

From the hw2-handout/nfa directory, run the go test -cover command to see the

current code coverage.

From the hw2-handout/nfa directory, run the following two commands to see which

statements are covered by the unit tests:

$ go test -coverprofile=temp.cov

$ go tool cover -html=temp.cov

Working with expression AST

For parts 4 and 5, you will be using the expr package in the hw2-handout/expr

directory.

You should NOT modify any code in the hw2-handout/expr directory.

hw2-handout/expr/ast.go defines an abstract syntax tree (AST) for arithmetic expressions.

The expr.Parse function parses a string into an AST; see hw2-handout/expr/parse.go.

The expr.Eval method evaluates an expression given a mapping from variables to

values; see hw2-handout/expr/eval.go.

The expr.Format function formats an expression AST as a string;

see hw2-handout/expr/print.go.

Note the use of type switches and type assertions in this code for inspecting the concrete

types that an Expr interface type represents.

This code is also described in Chapter 7 of The Go Programming Language book:

http://gopl.io.

4 depth (10 points)

Implement the function Depth in hw2-handout/depth/depth.go that, given an AST

represented by expr.Expr, returns the maximum number of AST nodes between the

root of the tree and any leaf (literal or variable) in the tree.

Unit tests have been provided in hw2-handout/depth/depth test.go.

From the hw2-handout/depth directory, run the go test command to run the unit

tests.

4

? If needed, write new tests, in hw2-handout/depth/depth test.go to ensure that you

get 100% code coverage for your code in hw2-handout/depth/depth.go.

From the hw2-handout/depth directory, run the go test -cover command to see the

current code coverage.

From the hw2-handout/depth directory, run the following two commands to see which

statements are covered by the unit tests:

$ go test -coverprofile=temp.cov

$ go tool cover -html=temp.cov

5 simplify (20 points)

Implement the Simplify function in hw2-handout/simplify/simplify.go.

Given an arithmetic expression as an expr.Expr and an environment expr.Env, Simplify

simplifies the given expression using the values of the variables in the environment and

by performing some algebraic simplifications.

Your implementation of Simplify should perform the following simplifications:

– Any Var whose name is in the provided map should be replaced with its value.

– Any unary operator whose operand is a Literal should be replaced with a

Literal representing the result.

– Any binary operator whose operands are both Literals should be replaced with

a Literal representing the result.

– Any binary operator performing addition, where one operand is 0, should be

reduced. (0 + X = X = X + 0)

– Any binary operator performing multiplication, where one operand is 1 or 0,

should be reduced. (1 ? X = X = X ? 1 and 0 ? X = 0 = X ? 0)

No other simplifications should be performed.

Unit tests have been provided in hw2-handout/simplify/simplify test.go.

From the hw2-handout/simplify directory, run the go test command to run the unit

tests.

If needed, write new tests, in hw2-handout/simplify/simplify test.go to ensure

that you get 100% code coverage for your code in hw2-handout/simplify/simplify.go.

From the hw2-handout/simplify directory, run the go test -cover command to see

the current code coverage.

From the hw2-handout/simplify directory, run the following two commands to see

which statements are covered by the unit tests:

$ go test -coverprofile=temp.cov

$ go tool cover -html=temp.cov

5

Working with the Go AST

For parts 6, 7, and 8, you will be writing Go code that works with the abstract syntax

tree (AST) of the Go language itself.

Information about the go/ast package can be found at

https://golang.org/pkg/go/ast/, which lists the different types of AST nodes along

with their fields.

You might also find it useful to take a look at the source code for go/ast, which can

be found at https://golang.org/src/go/ast/.

Sample code illustrating how to build the AST given Go code and then print it using

ast.Print can be found at https://play.golang.org/p/1g-lt3D1N6a.

Sample code computing the number of function calls using ast.Inspect can be found

at https://play.golang.org/p/cq2OI6CA6v_n.

An alternative to ast.Inspect is to use ast.Walk, which uses the ast.Visitor interface

type.

Sample code that modifies Go code programmatically can be found at

https://play.golang.org/p/mRKeN7SZD8g.

An introduction to the go/ast package can be found at

https://zupzup.org/go-ast-traversal/.

6 branch (20 points)

Modify hw2-handout/branch/branch.go by implementing the branchCount function

that returns the count of the number of branching statements in a Go function.

Branching statements are those where the program has a choice of what to execute

next; e.g., if and for statements.

The branchCount function is called from the ComputeBranchFactor function that

takes a Go program as a string, and for each function in that program, counts the

number of branching statements in the Go function by calling branchCount.

ComputeBranchFactor returns a map[string]uint from the name of the function to

the number of branching statements it contains.

You should not need to modify the implementation of ComputeBranchFactor.

Unit tests have been provided in hw2-handout/branch/branch test.go.

From the hw2-handout/branch directory, run the go test command to run the unit

tests.

6

If needed, write new tests, in hw2-handout/branch/branch test.go to ensure that

you get 100% code coverage for your code in hw2-handout/branch/branch.go.

From the hw2-handout/branch directory, run the go test -cover command to see

the current code coverage.

From the hw2-handout/branch directory, run the following two commands to see which

statements are covered by the unit tests:

$ go test -coverprofile=temp.cov

$ go tool cover -html=temp.cov

7 rewrite (30 points)

Modify the rewriteCalls function in hw2-handout/rewrite/rewrite.go to rewrite

occurrences of calls to expr.ParseAndEval in the input Go code so as to simplify the

first argument to expr.ParseAndEval.

The definition of the function expr.ParseAndEval can be found in

hw2-handout/expr/parse and eval.go.

As an example of the rewrite, the following statement in the input Go program:

x := expr.ParseAndEval("2 + 3", env)

would be rewritten to

x := expr.ParseAndEval("5", env)

The rewriteCalls function you have to implement has to do the following:

– Identify calls to expr.ParseAndEval in the input Go code.

– If the first argument to this call is a string literal, then parse this string into an

expr.Expr.

– Simplify this expr.Expr using the simplify.Simplify function you implemented

in part 5 (using an empty expr.Env).

– Format the resulting expr.Expr into a string.

– Replace the first argument in expr.ParseAndEval with this string representing

the simplified expression in the input Go code.

Unit tests have been provided in hw2-handout/rewrite/rewrite test.go, which read

inputs and outputs from the hw2-handout/rewrite test directory.

From the hw2-handout/rewrite directory, run the go test command to run the unit

tests.

If needed, write new tests, in hw2-handout/rewrite/rewrite test.go to ensure that

you get 100% code coverage for your code in hw2-handout/rewrite/rewrite.go.

From the hw2-handout/rewrite directory, run the go test -cover command to see

the current code coverage.

7

From the hw2-handout/rewrite directory, run the following two commands to see

which statements are covered by the unit tests:

$ go test -coverprofile=temp.cov

$ go tool cover -html=temp.cov

8 bonus (10 points)

This part of the homework is extra credit. You will get full credit for Homework 2

even if you do not attempt this part of the homework.

This part is an extension of the rewrite you had to do in part 7.

Modify the rewriteCalls function in hw2-handout/bonus/bonus.go to rewrite occurrences

of calls to expr.ParseAndEval in the input Go code so as to simplify the

first argument to expr.ParseAndEval and replace the call to expr.ParseAndEval if

the expression in the first argument simplifies to a numeric constant (literal).

The definition of the function expr.ParseAndEval can be found in

hw2-handout/expr/parse and eval.go.

As an example of this “bonus” rewrite, the following statement in the input Go program:

x := expr.ParseAndEval("2 + 3", env)

would be rewritten to

x := 5

The rewriteCalls function you have to implement has to do the following:

– Identify calls to expr.ParseAndEval in the input Go code.

– If the first argument to this call is a string literal, then parse this string into an

expr.Expr.

– Simplify this expr.Expr using the simplify.Simplify function you implemented

in part 5 (using an empty expr.Env).

– If the simplified expression is an expr.Literal, then replace the call to

expr.ParseAndEval with this literal in the input Go code.

– If the simplified expression is NOT an expr.Literal, then format the resulting

expr.Expr into a string. Replace the first argument in expr.ParseAndEval with

this string representing the simplified expression in the input Go code.

Unit tests have been provided in hw2-handout/bonus/bonus test.go, which read inputs

and outputs from the hw2-handout/bonus test directory.

From the hw2-handout/bonus directory, run the go test command to run the unit

tests.

8

? If needed, write new tests, in hw2-handout/bonus/bonus test.go to ensure that you

get 100% code coverage for your code in hw2-handout/bonus/bonus.go.

From the hw2-handout/bonus directory, run the go test -cover command to see the

current code coverage.

From the hw2-handout/bonus directory, run the following two commands to see which

statements are covered by the unit tests:

$ go test -coverprofile=temp.cov

$ go tool cover -html=temp.cov