Homework Assignments

Homework assignments consist of compiler implementation projects and standalone homeworks. We will use the CS submit system for homework turn-in. Please follow the directions on homework requirements and the procedures on how to submit your homework electronically.

General Requirements for Homework Assignments

In your homework submission, you should have the following:

  1. You should provide a README Wiki page (on 406/534 Wiki) to describe your submission files: your README should summarize your project, describe the purpose of the files in your submission; how to run your programs, what are the command lines, what are the input, what output will be generated; list any of your testing input and input files, and the sample results;
  2. In your README, it should have a section called "Report" written in plain English prose style. In the Report section, you should describe briefly what you have done in your homework, descriptions of your algorithms, any design and implementation work, and a summary of what you have learned.
  3. You should have the following honor pledge section written at the beginning of your README:
    ``On my honor, I abide by the University Honor Code and the submitted project is my own work.''
    Homework without the above honor pledge will not be graded.
  4. You should submit your README on your Wiki page. You may refer to the example README as template. Your README will account for 10% of your grading.

DIRECTIONS FOR ONLINE HOMEWORK SUBMISSION

To submit your homework, do the following step by step:

1. login to your account on mercury.cs.uml.edu and create a new directory, say "myhw1":
mkdir myhw1

2. upload all your homework files in to the directory you created in Step 1, say "myhw1"

3. change directory to the higher level directory above your directory, for example:
cd myhw1
cd ..

4. type "submit cs406 hw1 myhw1", here: cs406 is the course account, "hw1" is the submission code for hw#1, use "hw2" for hw#2, etc).

5. now, submit command should report success or failure

If you have problems with submit, please email cs406 for help *before* the due date.

HW#1: Exploring Scribbler, Due 9/15, 11:59pm

In this HW, you will investigate the Scribbler robot device and summarize your findings on your Wiki page. The information you get will be used as design guide later to build your Chirp-Scribbler compiler which will target Scribbler. You need to do the following:

  • Read Scribbler PDF documentaton from the Scribbler CD: including the Scribbler Start-Up Guide v1.0.pdf, BASIC Stamp Manual v2.1.pdf, What's a Microcontroller v2.2.pdf, to understand Scribbler hardware, PBASIC commands, and the StampEditor software to program Scribbler. The reference PDF files can be found on the Scribbler CD, which is also posted online - read the GoogleGroup message for URL link to online copy of Scribbler CD.
  • Experiment with PBASIC commands by using StampEditor to test your .BS2 code, run your program to control Scribbler peripherals, such as sensors, motors, LEDs, etc.
  • Write the Scribbler Report Wiki page and report the following:
    1. Description of Scribbler hardware features, including the microcontroller, memory, and peripheral devices.
    2. Description of Scribbler hardware-software interface of the above devices, use small code examples (BS2 code) to show how PBASIC commands can be used to control Scribbler hardware.
    3. Describe the usage of Parallax software tool chain to program Scribbler. Based on your knowledge on compiler design, address the question: how will you build the Chirp-Scribbler compiler? Highlight the steps you will take in your plan.
  • Post your report on Wiki, use your FirstName+LastName initials as prefix in the page name. For this HW, your Wiki page will be your online submission.

HW#2, Due 9/24, 11:59pm

  • EaC Exercises: Section 2.3 1(a), 1(c), 2(a), 2(b); Section 2.4 1.

To submit, use submission code "hw2".

LAB#1, Due 10/1, 11:59pm

In LAB#1 of the Chirp-Scribbler compiler project, you will use ANTLR to create the Chirp lexer and use the generated lexer class to process source Chirp programs. You need to do the following:

  • Define lexer .g file to specify Chirp tokens, including comments, special symbols, keywords, IDs, numbers, white spaces, etc. Refer to the Chirp V2 specification on the Resources page for Chirp lexical tokens.
  • Use ANTLR to create your lexer. You should write proper driver code to process input Chirp program (file name from command line) and output its token stream. You should print out the token type name (not int number) and the text for each token.
  • Create your own set of test Chirp programs to verify your lexer can recognize all Chirp tokens. Submit your test files as part of Lab 1.
  • Finally, your lexer should print out the following stat: the total count of all tokens scanned, the count of keywords and the count of names (Identifiers).

To submit LAB#1, use submission code "lab1".

LAB#2, Chirp Front-End: Parser and Verifier
Part I Due 10/15 11:59pm
Part II Due 10/29 11:59pm

In LAB#2, you will build the parser and semantics verifier for the Chirp-Scribbler compiler project. To help you manage building the Chirp front-end, we divide it into two parts:

  • Part I: Parser and AST Tree

      • In Part I, you will:

    • Write parser ANTLR .g file to specify Chirp v2 grammar rules. You should include the lexer rules from LAB#1 to build the complete parser. Your .g should be compiled by ANTLR successfully to generate the parser class. Note : you may need to modify some of the rules in Chirp Spec to be accepted by ANTLR. You should develop and test your .g files incrementally and create different input test cases to test your parser. List your test coverage in your Wiki Report and submit your testcase files in your submission.
    • Use JDOM to generate AST tree. On successful parse, your parser should display and print out the generated AST tree. Use the given expr parser sample code as example to learn how to use JDOM and generate AST in ANTLR. Describe your tree structure in your Wiki Report.
    • Use submission code "lab2p1" to submit Part I.

  • Part II: Symbol Table and Verifier

      • In Part II, you will build Symbol Table and Chirp Verifier to check the semantics of Chirp-Scribbler program and report semantics errors. You will:

    • Create proper Symbol Table and IR tree representation to build the Chirp Verifier.
    • Your verifier should check the following:
      1. Variable, array and function names are consistently defined and used, eg, no two variables or functions can have the same name; variables used in functions must be defined; variable names cannot be used as functions and vice versa.
      2. Arithmetic evaluation is done only on numeric data types.
      3. Function call and function prototype definition are matched. The correct number and type of arguments and return value are used.
      4. The void functions cannot return value and cannot be used in expression evaluation.
      5. Non-void functions will return a result value.
      6. The return value of non-void functions must be used (not discarded).
      7. System interface functions are supported directly, ie, they can be used without definition.
      8. There should be one function named "main" and its prototype should be "void main()".
    • For error reporting, your verifier should print out source line number and symbols involved in the error.
    • To test your Verifier, you should write Chirp programs with the above listed errors. Describe your error checks and testing procedures on your Wiki Report. You may share or exchange test files with other students. You can also contribute test files on the ClassCommon Wiki page.
    • use submission code "lab2p2" to submit Part II.

LAB#3, ChirpIL and Sribbler Code Generation
Part I Due 11/17 11:59pm
Part II Due 11/26 11:59pm

In LAB#3, you will: 1) convert the AST tree IR generated in LAB#2 into low-level 3-address intermediate form, called ChirpIL, and 2) generate PBASIC BS2 commands for ChirpIL IR. At the end of this lab, you will have a complete Chirp compiler to compile Chirp program and run the output BS2 code on Scribbler robot. This lab is divided into two parts:

  • Part I: Generate ChirpIL 3-address code

      • In Part I, you will:

    • Translate the AST tree IR into low-level 3-address ChirpIL code. You should first read EaC Ch7 and the ChirpIL and Code Generation document . You should design the IRGen - the ChirpIL IR generator to translate the AST tree into ChirpIL instructions.
    • Your IRGen should translate Chirp statements and expressions into basic blocks. It should maintain a list of basic blocks generated for each function. Furthermore, for each function, you should have a unique entry block, and a unique exit block which contains a single "return" instruction. Chirp return statement should be translated into jmp instruction to the exit block.
    • Your should build your IRGen with translators for different Chirp statement and expression types. Document the code shape of ChirpIL you generate in your wiki report. The generated ChirpIL IR should follow the specified ChirpIL grammar.
    • To test your IRGen, you should develop test chirp programs with different type of Chirp statments and expressions, and verify your IRGen will generate the desired code form. Describe your test cases in your Wiki Report and submit your test files in your submission.
    • Use submission code "lab3p1" to submit Part I.

  • Part II: Simple PBASIC Code Generator from ChirpIL

      • In Part II, you will build the simple code generator to emit PBASIC BS2 commands from ChirpIL IR in Part I. You should refer to the ChirpIL and Code Generation document for guidelines on code generator. You will:

    • Design and implement the CodeGen code generator targeting Scribbler microcontroller. Your CodeGen should translate ChirpIL instructions to matching PBASIC BS2 commands. Only simple branch and goto BS2 commands are allowed for control flow, no higher-level loops should be used in the generated code.
    • Generate data definition BS2 code for variable operands, including arrays. Use name mangling techniques to implement variables in different scopes. You should use the SymbolTable type information in Lab#2 to decide the size of the storage and generate suitable BS2 data statement.
    • Generate BS2 I/O code for System.Scribbler system functions. You should refer to the Hack's Hints for the Scribbler Robot and BASIC Stamp Reference Manual for target BS2 commands.
    • Generate necessary Scribbler I/O pin data definition and start-up code. Your output BS2 code should now be able to compile using the Parallax BasicStamp editor.
    • Develop robot control programs to compile with your compiler, download and run your output BS2 on Scribbler robot. Discuss your experiment results in your Wiki Report, indicate what you can compile and run on hardware.
    • Use submission code "lab3p2" to submit Part II.

HW#3, Due 12/11 11:59pm

  • EaC Exercises: Section 8.3 2(a), 2(b), 2(c); Section 8.6 1(a), 2.

To submit, use submission code "hw3".