CSCI 3155: Lab Assignment 2 Solved

The purpose of this lab is to get practice with grammars and to build an interpreter for something that begins to feel more like a programming language.

From your team of 8-10 persons in your lab section, find a new partner for this lab assignment (different from your Lab 1 partner). You will work on this assignment closely with your partner. However, note that each student needs to submit and are individually responsible for completing the assignment.

Like last time, you will work on this assignment in pairs. However, note that each student needs to submit a write-up and are individually responsible for completing the assignment.

You are welcome to talk about these questions in larger groups. However, we ask that you write up your answers in pairs. Also, be sure to acknowledge those with which you discussed, including your partner and those outside of your pair.

Recall the evaluation guideline from the course syllabus.

Both your ideas and also the clarity with which they are expressed matter—both in your English prose and your code!

We will consider the following criteria in our grading:

• Howwelldoesyoursubmissionanswerthequestions? For example, a common mistake is to give an example when a question asks for an explanation. An example may be useful in your explanation, but it should not take the place of the explanation.

• How clear is your submission? If we cannot understand what you are trying to say, then we cannot give you points for it. Try reading your answer aloud to yourself or a friend; this technique is often a great way to identify holes in your reasoning. For code, not every program that "works" deserves full credit. We must be able to read and understand your intent. Make sure you state any preconditions or invariants for your functions (either in comments, as assertions, or as require clauses as appropriate).

Try to make your code as concise and clear as possible. Challenge yourself to find the most crisp, concise way of expressing the intended computation. This may mean using ways of expression computation currently unfamiliar to you.

Finally, make sure that your file compiles and runs on COG. A program that does not compile will not be graded.

1

Submission Instructions. Upload to the moodle exactly four files named as follows:

• Lab2-YourIdentiKey.pdf with your answers to the written questions (scanned, clearly legible handwritten write-ups are acceptable).

• Lab2-YourIdentiKey.scala with your answers to the coding exercises.

• Lab2Spec-YourIdentiKey.scala with any updates to your unit tests.

• Lab2-YourIdentiKey.jsy with a challenging test case for your JAVASCRIPTY interpreter.

Replace YourIdentiKey with your IdentiKey (e.g., I would submit Lab2-bec.pdf and so forth). Don’t use your student identification number. To help with managing the submissions, we ask that you rename your uploaded files in this manner.

Submit your Lab1.scala file to COG for auto-testing. We ask that you submit both to COG and to moodle in case of any issues.

Sign-up for an interview slot for an evaluator. To fairly accommodate everyone, the interview times are strict and will not be rescheduled. Missing an interview slot means missing the interview evaluation component of your lab grade. Please take advantage of your interview time to maximize the feedback that you are able receive. Arrive at your interview ready to show your implementation and your written responses. Implementations that do not compile and run will not be evaluated.

Getting Started. Clone the code from the Github repository with the following command: git clone -b lab2 https://github.com/bechang/pppl-labs.git

A suggested way to get familiar with Scala is to do some small lessons with Scala Koans (http://www.scalakoans.org/). If you haven’t looked at the ones from Lab 1, we consider you look at those, particularly AboutCaseClasses and AboutPatternMatching.

1. Feedback. Complete the survey on the linked from the moodle after completing this assignment. Any non-empty answer will receive full credit.

2. Grammars: Synthetic Examples.

(a) Consider the following grammar:

A ::= A & A | V V ::= a|b

Recall that a grammar defines inductively a set of syntactic objects (i.e., a language). We can also use judgments to define a langauge.

For this exercise, rewrite this grammar using the following two judgment forms:

A ∈AObjects meaning Syntactic object A is in the set AObjects.

V ∈VObjects meaning Syntactic object V is in the set VObjects.

(b) Show that the grammar in the previous part is ambiguous.

(c) Describe the language defined by the following grammar:

S

A

B

C

(from Sebesta, Chapter 3)

(d) Consider the following grammar:
::=

::=

::=

::=
A | B | C a A |a b B |ε c C |c
S

A B
::=

::=

::=
A a B b A b|b a B |a
Which of the following sentences are in the language generated by this grammar? For the sentences that are described by this grammar, demonstrate that they are by giving derivations.

1. baab

2. bbbab

3. bbaaaaa

4. bbaab

(from Sebesta, Chapter 3)

(e) Consider the following grammar:

S

A B
::=

::=

::=
a S c B | A |b c A |c d| A
Which of the following sentences are in the language generated by this grammar? For the sentences that are described by this grammar, demonstrate that they are by giving parse trees.

1. abcd

2. acccbd

3. acccbcc

4. acd

5. accc

(from Sebesta, Chapter 3)

3. Grammars: Understanding a Language.

(a) Consider the following two grammars for expressions e. In both grammars, operator and operand arethesame; youdonotneedtoknowtheirproductionsforthisquestion.

e ::= operand | e operator operand

e ::= operand esuffix

esuffix ::= operator operand esuffix |ε

i. Intuitively describe the expressions generated by the two grammars.

ii. Do these grammars generate the same or different expressions? Explain.

(b) Write a Scala expression to determine if ‘−’ has higher precedence than ‘<<’ or vice versa. Make sure that you are checking for precedence in your expression and not for left or right associativity. Use parentheses to indicate the possible abstract syntax trees, and then show the evaluation of the possible expressions. Finally, explain how you arrived at the relative precedence of ‘−’ and ‘<<’ based on the output that you saw in the Scala interpreter.

(c) Give a BNF grammar for floating point numbers that are made up of a fraction (e.g., 5.6 or 3.123 or -2.5) followed by an optional exponent (e.g., E10 or E-10). The exponent, if it exists, is the letter ‘E’ followed by an integer. For example, the following are floating point numbers: 3.5E3, 3.123E30, -2.5E2, -2.5E-2, and 3.5. The following are not examples of floating point numbers: 3.E3, E3, and 3.0E4.5.

More precisely, our floating point numbers must have a decimal point, do not have leading zeros, can have any number of trailing zeros, non-zero exponents (if it exists), must have non-zero fraction to have an exponent, and cannot have a ‘-’ in front of a zero number. The exponent cannot have leading zeros.

For this exercise, let us assume that the tokens are characters in the following alphabet Σ:

Σ=def {0,1,2,3,4,5,6,7,8,9,E,-,.}

Yourgrammarshouldbecompletelydefined(i.e.,itshouldnotcountonanon-terminal that it does not itself define).

4. JavaScripty Interpreter: Booleans, Strings, Variable Binding, and Conversions.

One aspect that makes the JavaScript specification complex is the presence of implicit conversions (e.g., string values may be implicitly converted to numeric values depending on the context in which values are used). In this exercise, we will explore some of this complexity by implementing an evaluator with conversions for the subset with numbers, booleans, strings, and variable binding. JavaScript has a distinguished undefined value that we will also consider. This version of JAVASCRIPTY is much like the LET language in Section 3.2 of Friedman and Wand.

expressions

values unary operators binary operators
e ::= x |n |b |str |undefined|uope1 |e1bope2

| e1 ? e2 : e3 |constx =e1; e2 |console.log(e1) v ::= n |b |undefined|str

uop ::= -|!

bop ::= ,|+|-|*|/|===|!==|<|<=||=|&&|||
variables
x
numbers (doubles)
n
booleans strings
b ::= true|false

str
Figure 1: Abstract syntax of JAVASCRIPTY

statements s ::= const x = e | e | { s(1 } | ; | s1 s2 expressions e ::= ···|(const(((x =(e(1(; e2 | (e1)

Figure 2: Concrete syntax of JAVASCRIPTY

The syntax of JAVASCRIPTY for this lab is given in Figure 1. Note that the grammar specifies the abstract syntax using notation borrowed from the concrete syntax. Also note that JAVASCRIPTY in this lab extends JAVASCRIPTY from the previous lab.

The concrete syntax accepted by the parser is slightly less flexible than the abstract syntax in order to match the syntactic structure of JavaScript. In particular, all const bindings must be at the top-level. For example,

1 + (const x = 2; x)

is not allowed. The reason is that JavaScript layers a language of statements on top of its language of expressions, and the const binding is considered a statement. A program is a statement s as given in Figure 2. A statement is either a const binding, an expression, a grouping of statements (i.e., { s1 }), an empty statement (i.e., ;), or a statement sequence (i.e., s1 s2). Expressions are as in Figure 1 except const binding expressions are removed, and we have a way to parenthesize expressions.

An abstract syntax tree representation is provided for you in ast.scala. We also provide a parser and main driver for testing. The correspondence between the concrete syntax and the abstract syntax representation is shown in Figure 3.

To make the project simpler, we also deviate slightly with respect to scope. Whereas JavaScript considers all const bindings to be in the same scope, our JAVASCRIPTY bindings each introduce their own scope. In particular, for the binding const x = e1; e2, the scope of variable x is the expression e2.

Statement sequencing and expression sequencing are right associative. All other binary operator expressions are left associative. Precedence of the operators follow JavaScript.

The semantics are defined by the corresponding JavaScript program. We also have a system function console.log for printing out values to the console and returns undefined. Its implementation is provided for you.

(a) First, write some JAVASCRIPTY programs and execute them as JavaScript programs. This step will inform how you will implement your interpreter and will serve as tests for your interpreter.

(b) Then, implement def eval(env: Env, e: Expr): Expr

that evaluates a JAVASCRIPTY expression e in a value environment env to a value. A value is one of a number n, a boolean b, a string s, or undefined.

It will be useful to first implement three helper functions for converting values to numbers, booleans, and strings.

def toNumber(v: Expr): Double def toBoolean(v: Expr): Boolean def toStr(v: Expr): String

A value environment, a map from strings to JAVASCRIPTY values, is represented by a Scala Map[String,Expr]:

type Env = Map[String, Expr] val emp: Env = Map() def get(env: Env, x: String): Expr = env(x) def extend(env: Env, x: String, v: Expr): Env = { require(isValue(v))

env + (x - v)

}

We provide the above the three functions to interface with the Scala standard library. YoumayusetheScalastandardlibrarydirectlyifyouwish,butwerecommendthatyou just use these interfaces, as they are all that you need. The emp Scala value represents an empty value environment, the get function gets the value bound to the variable named by a given string, and the extend function extends a given environment with a new variable binding.


sealed abstract class Expr

case class Var(x: String) extends Expr

Var(x) x case class ConstDecl(x: String, e1: Expr, e2: Expr) extends Expr

ConstDecl(x,e1,e2) constx =e1; e2 case class N(n: Double) extends Expr

N(n) n

case class B(b: Boolean) extends Expr

B(b) b

case class S(str: String) extends Expr

S(str) str case object Undefined extends Expr

Undefined undefined case class Unary(uop: Uop, e1: Expr) extends Expr

Unary(uop,e1) uope1 case class Binary(bop: Bop, e1: Expr, e2: Expr) extends Expr

Binary(bop, e1) e1 bope2 sealed abstract class Uop case object Neg extends Uop

Neg −

case object Not extends Uop

Not !

sealed abstract class Bop case object Plus extends Bop

Plus +

case object Minus extends Bop

Minus −

case object Times extends Bop

Times ∗

case object Div extends Bop

Div /

case object Eq extends Bop

Eq ===

case object Ne extends Bop

Ne ! ==

case object Lt extends Bop

Lt <

case object Le extends Bop

Le <=

case object Gt extends Bop

Gt

case object Ge extends Bop

Ge =

case object And extends Bop

And &&

case object Or extends Bop

Or || case object Seq extends Bop

Seq , case class If(e1: Expr, e2: Expr, e3: Expr) extends Expr

If(e1, e2, e3) e1 ? e2 : e3 case class Print(e1: Expr) extends Expr Print(e1) console.log(e1)

Figure 3: Representing in Scala the abstract syntax of JAVASCRIPTY. After each caseclass or caseobject, we show the correspondence between the representation and the concrete syntax.CSCI 3155: Lab Assignment 2 Solution
CSCI 3155: Lab Assignment 2

Thepurposeofthislabistogetpracticewithgrammarsandtobuildaninterpreterforsomething that begins to feel more like a programming language.

From your team of 8-10 persons in your lab section, find a new partner for this lab assignment (different from your Lab 1 partner). You will work on this assignment closely with your partner. However, note that each student needs to submit and are individually responsible for completing the assignment.

Like last time, you will work on this assignment in pairs. However, note that each student needs to submit a write-up and are individually responsible for completing the assignment.

You are welcome to talk about these questions in larger groups. However, we ask that you write up your answers in pairs. Also, be sure to acknowledge those with which you discussed, including your partner and those outside of your pair.

Recall the evaluation guideline from the course syllabus.

Both your ideas and also the clarity with which they are expressed matter—both in your English prose and your code!

We will consider the following criteria in our grading:

• Howwelldoesyoursubmissionanswerthequestions? For example, a common mistake is to give an example when a question asks for an explanation. An example may be useful in your explanation, but it should not take the place of the explanation.

• How clear is your submission? If we cannot understand what you are trying to say, then we cannot give you points for it. Try reading your answer aloud to yourself or a friend; this technique is often a great way to identify holes in your reasoning. For code, not every program that "works" deserves full credit. We must be able to read and understand your intent. Make sure you state any preconditions or invariants for your functions (either in comments, as assertions, or as require clauses as appropriate).

Try to make your code as concise and clear as possible. Challenge yourself to find the most crisp, concise way of expressing the intended computation. This may mean using ways of expression computation currently unfamiliar to you.

Finally, make sure that your file compiles and runs on COG. A program that does not compile will not be graded.

1

Submission Instructions. Upload to the moodle exactly four files named as follows:

• Lab2-YourIdentiKey.pdf with your answers to the written questions (scanned, clearly legible handwritten write-ups are acceptable).

• Lab2-YourIdentiKey.scala with your answers to the coding exercises.

• Lab2Spec-YourIdentiKey.scala with any updates to your unit tests.

• Lab2-YourIdentiKey.jsy with a challenging test case for your JAVASCRIPTY interpreter.

Replace YourIdentiKey with your IdentiKey (e.g., I would submit Lab2-bec.pdf and so forth). Don’t use your student identification number. To help with managing the submissions, we ask that you rename your uploaded files in this manner.

Submit your Lab1.scala file to COG for auto-testing. We ask that you submit both to COG and to moodle in case of any issues.

Sign-up for an interview slot for an evaluator. To fairly accommodate everyone, the interview times are strict and will not be rescheduled. Missing an interview slot means missing the interview evaluation component of your lab grade. Please take advantage of your interview time to maximize the feedback that you are able receive. Arrive at your interview ready to show your implementation and your written responses. Implementations that do not compile and run will not be evaluated.

Getting Started. Clone the code from the Github repository with the following command: git clone -b lab2 https://github.com/bechang/pppl-labs.git

A suggested way to get familiar with Scala is to do some small lessons with Scala Koans (http://www.scalakoans.org/). If you haven’t looked at the ones from Lab 1, we consider you look at those, particularly AboutCaseClasses and AboutPatternMatching.

1. Feedback. Complete the survey on the linked from the moodle after completing this assignment. Any non-empty answer will receive full credit.

2. Grammars: Synthetic Examples.

(a) Consider the following grammar:

A ::= A & A | V V ::= a|b

Recall that a grammar defines inductively a set of syntactic objects (i.e., a language). We can also use judgments to define a langauge.

For this exercise, rewrite this grammar using the following two judgment forms:

A ∈AObjects meaning Syntactic object A is in the set AObjects.

V ∈VObjects meaning Syntactic object V is in the set VObjects.

(b) Show that the grammar in the previous part is ambiguous.

(c) Describe the language defined by the following grammar:

S

A

B

C

(from Sebesta, Chapter 3)

(d) Consider the following grammar:
::=

::=

::=

::=
A | B | C a A |a b B |ε c C |c
S

A B
::=

::=

::=
A a B b A b|b a B |a
Which of the following sentences are in the language generated by this grammar? For the sentences that are described by this grammar, demonstrate that they are by giving derivations.

1. baab

2. bbbab

3. bbaaaaa

4. bbaab

(from Sebesta, Chapter 3)

(e) Consider the following grammar:

S

A B
::=

::=

::=
a S c B | A |b c A |c d| A
Which of the following sentences are in the language generated by this grammar? For the sentences that are described by this grammar, demonstrate that they are by giving parse trees.

1. abcd

2. acccbd

3. acccbcc

4. acd

5. accc

(from Sebesta, Chapter 3)

3. Grammars: Understanding a Language.

(a) Consider the following two grammars for expressions e. In both grammars, operator and operand arethesame; youdonotneedtoknowtheirproductionsforthisquestion.

e ::= operand | e operator operand

e ::= operand esuffix

esuffix ::= operator operand esuffix |ε

i. Intuitively describe the expressions generated by the two grammars.

ii. Do these grammars generate the same or different expressions? Explain.

(b) Write a Scala expression to determine if ‘−’ has higher precedence than ‘<<’ or vice versa. Make sure that you are checking for precedence in your expression and not for left or right associativity. Use parentheses to indicate the possible abstract syntax trees, and then show the evaluation of the possible expressions. Finally, explain how you arrived at the relative precedence of ‘−’ and ‘<<’ based on the output that you saw in the Scala interpreter.

(c) Give a BNF grammar for floating point numbers that are made up of a fraction (e.g., 5.6 or 3.123 or -2.5) followed by an optional exponent (e.g., E10 or E-10). The exponent, if it exists, is the letter ‘E’ followed by an integer. For example, the following are floating point numbers: 3.5E3, 3.123E30, -2.5E2, -2.5E-2, and 3.5. The following are not examples of floating point numbers: 3.E3, E3, and 3.0E4.5.

More precisely, our floating point numbers must have a decimal point, do not have leading zeros, can have any number of trailing zeros, non-zero exponents (if it exists), must have non-zero fraction to have an exponent, and cannot have a ‘-’ in front of a zero number. The exponent cannot have leading zeros.

For this exercise, let us assume that the tokens are characters in the following alphabet Σ:

Σ=def {0,1,2,3,4,5,6,7,8,9,E,-,.}

Yourgrammarshouldbecompletelydefined(i.e.,itshouldnotcountonanon-terminal that it does not itself define).

4. JavaScripty Interpreter: Booleans, Strings, Variable Binding, and Conversions.

One aspect that makes the JavaScript specification complex is the presence of implicit conversions (e.g., string values may be implicitly converted to numeric values depending on the context in which values are used). In this exercise, we will explore some of this complexity by implementing an evaluator with conversions for the subset with numbers, booleans, strings, and variable binding. JavaScript has a distinguished undefined value that we will also consider. This version of JAVASCRIPTY is much like the LET language in Section 3.2 of Friedman and Wand.

expressions

values unary operators binary operators
e ::= x |n |b |str |undefined|uope1 |e1bope2

| e1 ? e2 : e3 |constx =e1; e2 |console.log(e1) v ::= n |b |undefined|str

uop ::= -|!

bop ::= ,|+|-|*|/|===|!==|<|<=||=|&&|||
variables
x
numbers (doubles)
n
booleans strings
b ::= true|false

str
Figure 1: Abstract syntax of JAVASCRIPTY

statements s ::= const x = e | e | { s(1 } | ; | s1 s2 expressions e ::= ···|(const(((x =(e(1(; e2 | (e1)

Figure 2: Concrete syntax of JAVASCRIPTY

The syntax of JAVASCRIPTY for this lab is given in Figure 1. Note that the grammar specifies the abstract syntax using notation borrowed from the concrete syntax. Also note that JAVASCRIPTY in this lab extends JAVASCRIPTY from the previous lab.

The concrete syntax accepted by the parser is slightly less flexible than the abstract syntax in order to match the syntactic structure of JavaScript. In particular, all const bindings must be at the top-level. For example,

1 + (const x = 2; x)

is not allowed. The reason is that JavaScript layers a language of statements on top of its language of expressions, and the const binding is considered a statement. A program is a statement s as given in Figure 2. A statement is either a const binding, an expression, a grouping of statements (i.e., { s1 }), an empty statement (i.e., ;), or a statement sequence (i.e., s1 s2). Expressions are as in Figure 1 except const binding expressions are removed, and we have a way to parenthesize expressions.

An abstract syntax tree representation is provided for you in ast.scala. We also provide a parser and main driver for testing. The correspondence between the concrete syntax and the abstract syntax representation is shown in Figure 3.

To make the project simpler, we also deviate slightly with respect to scope. Whereas JavaScript considers all const bindings to be in the same scope, our JAVASCRIPTY bindings each introduce their own scope. In particular, for the binding const x = e1; e2, the scope of variable x is the expression e2.

Statement sequencing and expression sequencing are right associative. All other binary operator expressions are left associative. Precedence of the operators follow JavaScript.

The semantics are defined by the corresponding JavaScript program. We also have a system function console.log for printing out values to the console and returns undefined. Its implementation is provided for you.

(a) First, write some JAVASCRIPTY programs and execute them as JavaScript programs. This step will inform how you will implement your interpreter and will serve as tests for your interpreter.

(b) Then, implement def eval(env: Env, e: Expr): Expr

that evaluates a JAVASCRIPTY expression e in a value environment env to a value. A value is one of a number n, a boolean b, a string s, or undefined.

It will be useful to first implement three helper functions for converting values to numbers, booleans, and strings.

def toNumber(v: Expr): Double def toBoolean(v: Expr): Boolean def toStr(v: Expr): String

A value environment, a map from strings to JAVASCRIPTY values, is represented by a Scala Map[String,Expr]:

type Env = Map[String, Expr] val emp: Env = Map() def get(env: Env, x: String): Expr = env(x) def extend(env: Env, x: String, v: Expr): Env = { require(isValue(v))

env + (x - v)

}

We provide the above the three functions to interface with the Scala standard library. YoumayusetheScalastandardlibrarydirectlyifyouwish,butwerecommendthatyou just use these interfaces, as they are all that you need. The emp Scala value represents an empty value environment, the get function gets the value bound to the variable named by a given string, and the extend function extends a given environment with a new variable binding.


sealed abstract class Expr

case class Var(x: String) extends Expr

Var(x) x case class ConstDecl(x: String, e1: Expr, e2: Expr) extends Expr

ConstDecl(x,e1,e2) constx =e1; e2 case class N(n: Double) extends Expr

N(n) n

case class B(b: Boolean) extends Expr

B(b) b

case class S(str: String) extends Expr

S(str) str case object Undefined extends Expr

Undefined undefined case class Unary(uop: Uop, e1: Expr) extends Expr

Unary(uop,e1) uope1 case class Binary(bop: Bop, e1: Expr, e2: Expr) extends Expr

Binary(bop, e1) e1 bope2 sealed abstract class Uop case object Neg extends Uop

Neg −

case object Not extends Uop

Not !

sealed abstract class Bop case object Plus extends Bop

Plus +

case object Minus extends Bop

Minus −

case object Times extends Bop

Times ∗

case object Div extends Bop

Div /

case object Eq extends Bop

Eq ===

case object Ne extends Bop

Ne ! ==

case object Lt extends Bop

Lt <

case object Le extends Bop

Le <=

case object Gt extends Bop

Gt

case object Ge extends Bop

Ge =

case object And extends Bop

And &&

case object Or extends Bop

Or || case object Seq extends Bop

Seq , case class If(e1: Expr, e2: Expr, e3: Expr) extends Expr

If(e1, e2, e3) e1 ? e2 : e3 case class Print(e1: Expr) extends Expr Print(e1) console.log(e1)

Figure 3: Representing in Scala the abstract syntax of JAVASCRIPTY. After each caseclass or caseobject, we show the correspondence between the representation and the concrete syntax.