CSCI3136 Assignment 7
Instructor: Alex Brodsky Due: 9:00am, Friday, July 3, 2020
Consider the grammar in Figure 1 where the terminal int denotes an integer and the terminal id
S → Atoms → Atoms → Atom → Atom → Atom → Atom →
Atoms
ε
Atom Atoms ′ Atom
id
int
( 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
(+12)
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
Symbol Attribute
Assignment 7
Type
Atoms synthesized synthesized
calls: int
callable: bool
symbol table: Symbol Table
Atom calls: int callable: bool
inherited synthesized 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
print(Atoms1.calls)
Atoms1.symbol table = getSymbolTable()
Atoms → ε
Atoms.callable = false
Atoms → Atom 1 Atoms 1
Atoms.calls = 0
Atom 1 .symbol table = Atoms .symbol table
Atoms 1 .symbol table = Atoms .symbol table
Atoms.calls = Atom1.calls + Atoms1.calls
Atoms.callable = Atom1.callable
Atom→′Atom1
Atom.calls = 0
Atom 1 .symbol table = Atom .symbol table Atom.callable = false
Atom → id
Atom.callable = Atom.symbol table.isFunction(id)
Atom.calls = 0
Atom → int
Atom.callable = false
Atom → ( Atoms1 )
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.
Atom.calls = 0
Atoms 1 .symbol table = Atom .symbol table
if Atoms1.callable then Atom.calls = Atoms1.calls + 1
Atom.callable = Atoms1.callable
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
Marking Scheme
1. Marking scheme for Question 1
Summer 2020
Assignment 7
4 points
3 points
2 points
1 point
0 points
Attributes
Use of attributes properly ex- plained
Use of attributes somewhat ex- plained
No proper ex- planation of at- tributes
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 differ- entiates between synthesized and inherited attributes
Notation does not differen- tiate between synthesized
and inherited attributes
4
CSCI3136: Assignment 7
Summer 2020
Student Name
Login ID
Student Number
Student Signature
Mark
Question 1 Question 2 Question 3
/8 /8 /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.