HW#2 --- last modified September 29 2021 14:51:54.

Solution set.

Due date: Oct 11

Files to be submitted:

Purpose: To get familiar with writing simple interpreters, to become familiar with lex and yacc, and rust.

Related Course Outcomes:

The main course outcomes covered by this assignment are:

CLO5 -- Read and produce context-free grammars.

CLO6 -- Write recursive-descent parsers for simple languages.

CLO8 -- Write interpreters for simple languages that involve arithmetic expressions, bindings of values to names, and function calls.

CLO10 -- Understand the implementation of procedure calls and stack frames.


This assignment consists of two parts, a written exercises and a coding part. I want you to put answers to the exercises below in a file Hw2.pdf which should be included in the Hw2.zip file you submit. In addition, you should have a readme.txt file listing the team mates you had for the assignment. Remember to receive any credit you must work in a single group (not two groups) with at most three people (can have smaller groups) in the group. Please remember the maximum upload size is 10Mb, so if your PDF contains images make sure to scale/compress them. I.e., BMP bad (uncompressed), jpg, png, etc good (compressed).

For the exercise part of the homework, I'd like you to do the following problems modified out of the textbook:

  1. Problem 2.14 modified so can also have braces {}.
  2. Problem 3.7.
  3. Problem 3.14.

For the coding part of the assignment, I'd like you to write two interpreters, one using Lex/Yacc (or Flex/Bison) and C, and the other using Rust. Put the first in a C subfolder of your HW2.zip and the latter in a Rust subfolder. The programs in the language I'd like you to interpret consist of sequences of statements delimited by newlines.

A statement can either be an assignment_statement or a print_statement.

A assignment_statement consists of a variable followed by = followed by an expression. A variable is the letter X followed by zero or more digits. For example, X123. An expression is either a string literal such as "hi there" or is one of the operations FIRST, REST, CONS from HW1 (and with same intended meanings) followed by white space, followed by a variable trailed by optional white space. In the case of CONS, after the first variable there should be whitespace and a second variable trailed by optional white space. For example,

X21 = CONS X10 X2

A print_statement consists of the keyword PRINT followed by white space followed by a variable trailed by optional white space . For example,


Token scanning for your project should be done using Lex, you should come up with a LR(1) grammar for the above and implement it using Yacc.

After interpreting an assignment, your interpreter should be storing a new string value for the variable that was assigned according to either the value of the literal assigned or based on the operation and the values of the variables on the right hand side of the =. A PRINT statement should be interpreted to output to stdout, the value of the given variable.

Your Lex/Yacc/C project should have a Makefile. Typing:

make all

Should output an executable string_lang. This program should be runnable from the command line with a syntax like:

string_lang program_file_name

Here program_file_name should be the name of a file consisting of a program using lines like the above. For example,

string_lang my_program.txt

Your program when run, should process the file line by line and interpret the line using the semantics for statements given above. If a line is not parsable, your program should output:

Syntax Error (line number)

and stop.

Your rust program should operate in the same way. It should be compiled using a Makefile (or cargo if you like) as well and should produce an executable string_lang as well. Rather than use a utilities like Lex/Yacc, I want you to write the rust version as a recursive descent parser/interpreter.

Point Breakdown
Written Problems (1pt each scale 0 - not close to correct, 0.5 - mainly correct, 1 correct). 3pts
Makefile's correctly compile programs (both C and Rust) 1pt
C program tokens correctly scanned using Lex 1pt
C program grammar rules correctly parsed using Yacc 1pt
C program output and error handling correct 1pt
Rust program correctly scans for tokens 1pt
Rust program implements grammar rules using recursive descent 1pt
Rust program output and error handling correct 1pt