代写CSCI3136、代做Python，Java，c/c++程序设计、代写data

日期：2020-07-04 10:53

Assignment 7

Consider the grammar in Figure 1 where the terminal int denotes an integer and the terminal id

S → Atoms

Atoms → 

Atoms → Atom Atoms

Atom → 0 Atom

Atom → id

Atom → int

Atom → ( Atoms )

Figure 1: A simplified grammar for Scheme.

denotes an identifier. The only other terminals in this grammar are the quote ’, the left parenthesis

(, and the right parenthesis ).

Scheme, a derivative of Lisp, is a list based language where all programs are represented by

lists. For example, a simple Scheme program

( + 1 2 )

adds two numbers together and prints out the result. A scheme interpreter, /local/bin/scheme,

is available on timberlea.cs.dal.ca. Feel free to give it a try. A program, which is zero or more

atoms is executed by evaluating each of the atoms. An atom is either an integer, an identifier, or

a list. The evaluation of an integer is the integer, and the evaluation of an identifier, for now, is

simply the identifier. The evaluation of a quoted atom is simply the atom itself. E.g., the evaluation

of ’ ( 1 2 3 ) is ( 1 2 3 ).

A list is evaluated by evaluating the first atom of the list and treating the result as a function.

Then each of the remaining atoms of the list is evaluated, and passed as parameters to the function.

For example, the evaluation of ( + 1 2 ), treats + as a function, and passes 1 and 2 to the function.

Applying + to 1 and 2 yields the result 3. Whereas, the evaluation of ( + 1 ( * 2 3 ) ), evaluates

+ and 1 as before, but then evaluates ( * 2 3 ), yielding 6, which is then passed to the + function,

which yields the result of 7.

1. [8 marks] Consider the following L-attributed grammar, based on the grammar specified

in Figure 1. Describe and justify what it is computing. Be sure to explain the purpose of

the attributes, and what each of the semantic rules is doing. Your description must include

a succinct summary of the purpose of this attribute grammar. I.e., Be sure to state what it

is supposed to do, not just how it is doing it.

1

CSCI3136 Summer 2020 Assignment 7

Symbol Attribute Type

Atoms calls: int synthesized

callable: bool synthesized

symbol table: Symbol Table inherited

Atom calls: int synthesized

callable: bool synthesized

symbol table: Symbol Table inherited

In the attribute grammar below, the symbol ? indicates a semantic rule that operates on

inherited attributes, and the ? symbol indicates a semantic rule that operates on synthesized

attributes.

S → Atoms1 ? Atoms1.symbol table = getSymbolTable()

? print(Atoms1.calls)

Atoms →  ? Atoms.calls = 0

? Atoms.callable = false

Atoms → Atom1 Atoms1 ? Atom1.symbol table = Atoms.symbol table

? Atoms1.symbol table = Atoms.symbol table

? Atoms.calls = Atom1.calls + Atoms1.calls

? Atoms.callable = Atom1.callable

Atom → 0 Atom1 ? Atom1.symbol table = Atom.symbol table

? Atom.calls = 0

? Atom.callable = false

Atom → id ? Atom.calls = 0

? Atom.callable = Atom.symbol table.isFunction(id)

Atom → int ? Atom.calls = 0

? Atom.callable = false

Atom → ( Atoms1 ) ? Atoms1.symbol table = Atom.symbol table

? if Atoms1.callable then Atom.calls = Atoms1.calls + 1

? Atom.callable = Atoms1.callable

2. [8 marks] Suppose you wanted to construct an abstract syntax tree from parse tree derived

by using the grammar specified in Figure 1. Give an S-attributed grammar that creates an

abstract syntax tree composed of the following kinds of tree nodes as illustrated in the UML

diagram below.

2

CSCI3136 Summer 2020 Assignment 7

All that is required is to create an abstract syntax tree. Observe that all you will need for

most types of nodes is just the constructor (as shown) but for ListASTNode two methods

are provided to prepend and append nodes to a list. You will need one of these methods,

depending on how you structure your attribute grammar.

Please provide both the semantic rules and the attributes using notation similar to that in

question 1.

Provide a brief explanation of how the grammar works.

3. [9 marks] Suppose that the base ASTNode class had a setNesting(int n) method that sets

the nesting level of the node in the abstract syntax tree. The nesting level is simply the number

of parentheses surrounding the symbol contained in the node. E.g., for ((a) b (c (d e)))

the outer list is at nesting 0; the atoms (a), b, and (c (d e)) are at nesting 1; atoms a, c,

and (d e) are at nesting 2; and atoms d and e are at nesting 3.

Extend the S-attributed grammar from Question 2 into an L-attributed grammar that also

sets the nesting level of each node in the abstract syntax tree as it is created.

Provide a brief explanation of how the grammar works.

3

CSCI3136 Summer 2020 Assignment 7

Marking Scheme

1. Marking scheme for Question 1

4 points 3 points 2 points 1 point 0 points

Attributes

Use of attributes

properly explained

Use of attributes

somewhat explained

No proper explanation

of attributes

Rules All semantic

rules explained

Most semantic

rules explained

Some semantic

rules explained

Few semantic

rules explained

No semantic

rules explained

Description

Purpose of

grammar is

described

Attempt made

to describe

purpose

No attempt

to describe

purpose

2. Marking scheme for Question 2

4 points 3 points 2 points 1 point 0 points

Attributes

Appropriate

attributes

specified

Somewhat

appropriate

attributes

specified

Attributes not

specified

Rules Semantic rules

are correct

Most semantic

rules are correct

Some semantic

rules are correct

Few semantic

rules are correct

No semantic

rules specified

Explanation

Function of

grammar

explained

Function of

grammar poorly

explained

Function of

grammar not

explained

3. Marking scheme for Question 3

4 points 3 points 2 points 1 point 0 points

Attributes

Appropriate

attributes

specified

Somewhat

appropriate

attributes

specified

Attributes not

specified

Rules Semantic rules

are correct

Most semantic

rules are correct

Some semantic

rules are correct

Few semantic

rules are correct

No semantic

rules specified

Explanation

Function of

grammar

explained

Function of

grammar poorly

explained

Function of

grammar not

explained

Notation

Notation differentiates

between

synthesized and

inherited

attributes

Notation does

not differentiate

between

synthesized

and inherited

attributes

4

CSCI3136: Assignment 7

Summer 2020

Student Name Login ID Student Number Student Signature

Mark

Question 1 /8

Question 2 /8

Question 3 /9

Total /25

Comments:

Assignments are due by 9:00am on the due date. Assignments must be submitted electronically

via Brightspace. Please submit a PDF for the written work. You can do your work on paper

and then scan in and submit the assignment.

Plagiarism in assignment answers will not be tolerated. By submitting their answers to this

assignment, the authors named above declare that its content is their original work and that

they did not use any sources for its preparation other than the class notes, the textbook, and

ones explicitly acknowledged in the answers. Any suspected act of plagiarism will be reported

to the Facultys Academic Integrity Officer and possibly to the Senate Discipline Committee.

The penalty for academic dishonesty may range from failing the course to expulsion from the

university, in accordance with Dalhousie Universitys regulations regarding academic integrity.