Homework #3

Due: Friday January 27th at 11:59pm

This homework is intended to serve as an introduction to understanding the process of syntactical analysis. Specifically, we will look at requirements needed to build a parser that makes up the syntactical analysis phase.

Getting started

For each assignment, a Git repository will be created for you on GitHub. However, before that repository can be created for you, you need to have a GitHub account. If you do not yet have one, you can get an account here: https://github.com/join.

To actually get your private repository, you will need this invitation URL:

When you click on an invitation URL, you will have to complete the following steps:

  1. You will need to select your CNetID from a list. This will allow us to know what student is associated with each GitHub account. This step is only done for the very first invitation you accept.

Note

If you are on the waiting list for this course you will not have a repository made for you until you are admitted into the course. I will post the starter code on Ed so you can work on the assignment until you are admitted into the course.

  1. You must click “Accept this assignment” or your repository will not actually be created.

  2. After accepting the assignment, Github will take a few minutes to create your repository. You should receive an email from Github when your repository is ready. Normally, it’s ready within seconds and you can just refresh the page.

  3. You now need to clone your repository (i.e., download it to your machine).

    • Make sure you’ve set up SSH access on your GitHub account.

    • For each repository, you will need to get the SSH URL of the repository. To get this URL, log into GitHub and navigate to your project repository (take into account that you will have a different repository per project). Then, click on the green “Code” button, and make sure the “SSH” tab is selected. Your repository URL should look something like this: git@github.com:mpcs51300-win23/hw3-GITHUB-USERNAME.git.

    • If you do not know how to use git clone to clone your repository then follow this guide that Github provides: Cloning a Repository

If you run into any issues, or need us to make any manual adjustments to your registration, please let us know via Ed Discussion.

Empty Repository?

There is no starter code for this homework assignment. You may use the code provided in the module 3 zip file to help with the implementation of your parser. Make sure to git add, commit, and push your final solutions.

The Cal Language Grammar

Here is the Extended Backus-Naur form (EBNF) for the Cal Language. Use this grammar as guideline to implement the parser. In the EBNF below, non-terminals are highlighted in blue with a = instead of an -> as shown in class. The notation { ... } means zero or more of the symbols defined in the braces. You’ll notice a series of semi-colons lined up at the end of each line in the EBNF. Please ignore those semi-colons because they are needed to signal the end of a production. The language does contain semicolons to signal the end of a statement but those are terminals and are indicated as ';'. The terminals are highlighted in green with single quotes.

Program = Block 'eof'                       ;
Block = {Statement}                         ;
Statement = Let | Assignment | Print        ;
Let = 'let' 'id' '=' Expression ';'         ;
Assignment = 'id' '=' Expression ';'        ;
Print = 'print' Expression ';'              ;
Expression = Term ExpressionPrime           ;
ExpressionPrime = '+' Term ExpressionPrime  ;
ExpressionPrime = '-' Term ExpressionPrime  ;
ExpressionPrime = 'ε'                       ;
Term = Factor TermPrime                     ;
TermPrime = '*' Factor TermPrime            ;
TermPrime = '/' Factor TermPrime            ;
TermPrime = 'ε'                             ;
Factor = 'INT' | 'id'                       ;

Programming Question: Simple Parser

In homework #2 you created a scanner for the toy language, Cal. For this assignment, you will create a recursive decent parser for the language. Make sure to watch the video on recursive decent parsing.

Use the code provided in module 3 zip folder, as a template for creating your parser. To get started, you will to use your lexer from homework #2, and connect it with the parser you are building for this assignment. If your lexer is not working by Monday January 23rd then you need to let me know immediately so Professor Samuels can help you fix it. DO NOT wait until a few days before the homework is due to say your lexer is not working because you’ll be on own at that point. However, I will help you get it working before the weekend so you can finish this assignment.

For this assignment, there should be a method/function called Parse that is called to parse through the token stream and returns true if an error occurred during parsing; otherwise Parse returns false if no errors were found. You are not building a parse/abstract syntax tree for this assignment. Here’s some template code, to help you get started thinking about the implementation:

type Parser struct {
   //IMPLEMENT ME
 }

 func New(tokens []ct.Token) *Parser {
   // IMPLEMENT ME
   return &Parser{}
 }

 func (p *Parser) Parse() bool {
  // IMPLEMENT ME
   return false

 }

You may update the Parser struct with additional fields to help you implement the parser. The New initializes and allocates a new parser. You should think of the argument tokens as the list of tokens generated by the scanner.**Assume that you will not see any illegal tokens in this slice.** In the compiler project for this course, we will explain how to handle that situation but for now assume you are given valid tokens. The Parse() method will verify the tokens make up a structurally valid Cal program by using a recursive decent parser . You can modify this code as you please. You do need to print out any lexical and parse errors that you find with the following structure

syntax error(LINE NUMBER): MESSAGE

where LINE NUMBER is the line number for the token that produced the error and MESSAGE is a helpful error message. You can either collect all possible errors in the program or exit early if you find one syntax error (the latter is easier to implement).

Building, Running, and Testing the Parser

You will need to provide a README file that clearly and explicitly explains how we can build and run your parser program on the CS linux servers. Your parser is required to work correctly on a CS linux machine. Your parser program is required to take in a single command line file that represents a Cal program. For example, if we had a file called simple1.cal that contained the following code

let a = 23;
let c = a + 4;
print c;

then we can run the program as follows in Go and Python, assuming your scanner’s main code lives in a file parser.go/ parser.py

$ go run parser.go simple1.cal
$ python3 parser.py simple1.cal

If no errors are found then the parser prints nothing. However, if we had the following program

let a = +;
let print = 4;

then running the program should print a helpful error message with the line number

$ go run parser.go simple1.cal
syntax error(1): expected expression but found "+"
$ python3 parser.py simple1.cal
syntax error(1): expected expression but found "+"

Notice how this implementation is exiting early on the first syntax error found. Also, there’s no specific error message you need to produce. As long as it’s helpful in telling the programmer what went wrong then it’s fine.

How you organize the structure of your code in your repository is up to you.

Grading

For this assignment, the weights will be:

  • Parser:Completeness 60%

  • Parser:Correctness 30%

  • Parser:Design & Style 10%

Design, Style and Cleaning up

Before you submit your final solution, you should, remove

  • any Printf statements that you added for debugging purposes and

  • all in-line comments of the form: “YOUR CODE HERE” and “TODO …”

  • Think about your function decomposition. No code duplication. This homework assignment is relatively small so this shouldn’t be a major problem but could be in certain problems.

As you clean up, you should periodically save your file and run your code through the tests to make sure that you have not broken it in the process.

Submission

Before submitting, make sure you’ve added, committed, and pushed all your code to GitHub. You must submit your final work through Gradescope (linked from our Canvas site) in the “Homework #3” assignment page via two ways,

  1. Uploading from Github directly (recommended way): You can link your Github account to your Gradescope account and upload the correct repository based on the homework assignment. When you submit your homework, a pop window will appear. Click on “Github” and then “Connect to Github” to connect your Github account to Gradescope. Once you connect (you will only need to do this once), then you can select the repsotiory you wish to upload and the branch (which should always be “main” or “master”) for this course.

  2. Uploading via a Zip file: You can also upload a zip file of the homework directory. Please make sure you upload the entire directory and keep the initial structure the same as the starter code; otherwise, you run the risk of not passing the automated tests.

Depending on the assignment, once you submit your work, an “autograder” will run. This autograder should produce the same test results as when you run the code yourself; if it doesn’t, please let us know so we can look into it. A few other notes:

  • You are allowed to make as many submissions as you want before the deadline.

  • Please make sure you have read and understood our Late Submission Policy.

  • Your completeness score is determined solely based on the automated tests, but we may adjust your score if you attempt to pass tests by rote (e.g., by writing code that hard-codes the expected output for each possible test input).

  • Gradescope will report the test score it obtains when running your code. If there is a discrepancy between the score you get when running our grader script, and the score reported by Gradescope, please let us know so we can take a look at it.