CSC 173 Computation and Formal Systems - Project 2

The goal of this project is to demonstrate your understanding of the formal model of context-free grammars and parsing by applying the principles of the model to a specific grammar (details below).

The goal of the project is not simply for you to write a program that parses strings from the specific required grammar. The goal is for you to demonstrate how the formal model allows you build a parser based on the grammar mechanically with almost no thinking required.

Process not product.

Given a parsable grammar, for this project you must first construct a recursive-descent parser for the grammar using parsing functions, as seen in class and in the textbook. These parsing functions come almost directly (“mechanically”) from the productions of the (parsable) grammar, as seen in class. You will demonstrate your parser by asking the user for input strings, parsing them, and printing the resulting parse tree (or an error message).

You must also implement a table-driven parser for the grammar, following the description seen in class and in the textbook, and demonstrate its use. Again: it’s not about being a creative programmer. It’s about understanding and applying the formal model. In this case, your code should be able to parse strings using any grammar given a parsing table connected to the productions of the grammar. But you will only need to show it working on one grammar.

Please read the requirements carefully.

Language

For this term, the language that we will be parsing is a very simple programming lan- guage.

Here is an informal description of the language:

• An program is zero or more statements, each followed by a semicolon.

• There are only two types of statements:
  – Assignment (“=”): assign the value of an expression to a variable – Output (“>”): print the value of an expression on the console

• Variables are named with a single letter (“a” to “z”).

• Expressions use unsigned integers, the four arithmetic operators, and parentheses, as seen in class and in the textbook.

  – The expression “<” (less than) reads and returns a number from the console.

• Whitespace (spaces, tabs, newlines) is not allowed. The entire input must be on one line, without a newline at the end.1

  Here are some well-formed expressions of this language (one per line):

      x=1;
      >123+1+2/2*3;
      a=<;b=<;>(a+b)/2;
  

  The last of these is actually a useful program. You should be able to figure out what it does. If not, please go to study session ASAP.

  In order to build a parser, we need a context-free grammar for the language and in order to use the required parsing methods (seen in class and in the textbook), that grammar must be parsable by a recursive descent or table-driven parser.

  
  Think about this yourself.
  After you have thought about it yourself, please read Appendix A. Note that you MUST

  use the grammar given in this document.
  
  

  Requirements

  Part 1: Recursive-descent parser (60%)

  Implement a recursive-descent parser that produces parse trees for expressions of the required language.

  • You MUST use the grammar given in this document.

  • The style of the parsing functions MUST be as seen in class (which is sort of like what is in the textbook; check out the code available on BlackBoard with the project description).

  • Your parsing functions MUST use functions lookahead and match as seen in class.

  • You should be able to create the parsing functions by reading the productions of the grammar with almost no thinking required.

  • The only place where thinking is required is how to use the lookahead symbol, as seen in class and in the textbook.

  • This will be boring if you do it right. I’m sorry.

    You must then demonstrate your parser by reading strings from the user, parsing them, and printing the resulting parse tree.

  • Your program must prompt the user for input.

  • You may assume that expressions are on a single line of input, and no longer than 255 characters. Note that the empty string is a valid input, so you should use fgets rather than scanf to read a line of input. See the “C for Java Programmers” guide and/or ask in study session if you need help with this.

  • If the input is not well-formed, your parser should print an error message and resume processing at the next line of input.

  • Otherwise print the parse tree as described below.

  • This phase of the program should terminate when it reads the string “quit” (with- out the quotes).
    
    

    Part 2: Table-driven parser (40%)

    Implement a table-driven parser for expressions of the required language.

    • As for Part 1: read expressions from the user, try to parse the input, print the parse tree or an error message, until “quit”.

    • Most of the infrastructure of the parser will be the same as for Part 1.

    • You MUST use the grammar given in this document.

    • You MUST use an explicit parsing table that references explicitly-represented pro- ductions (FOCS Figs. 11.31 and 11.32). That means the table must contain either indexes of productions in a list or array of productions (as seen in the textbook), or references (pointers) to the productions themselves.

    • You MUST have a function that creates and returns an instance of this table for the grammar of the required language. This function does not need to translate a grammar into a parsing table. It just needs to build and return the parsing table for the grammar that you are using. So work it out by hand, then write the code to produce it.

    • You MUST have a parsing function that takes a parsing table and an input string as arguments and does a table-driven parse. (You may have helper functions also.) Note that this function should be able to parse using any grammar, given its parsing table and productions. That is, it is independent of the grammar that it is using (but you only need to show it working with the required grammar).

    • It may be helpful to produce output like FOCS Fig. 11.34 during debugging.

      The next step would be to convert the parse trees produced by your parser(s) to expres- sion trees and then either evaulate the expressions to compute their values or generate code to compute the values later. It’s not hard to do that once you’ve built the parse trees, but you do not have to do it for this project. You will see it in CSC254 if you take that course.

      Your project MUST be a single program. This program should read the input and then call each parser (assuming you do both parts) and print the results, as described above. It is your responsibility to make it clear to us what your program is doing.
      
      

      There is no opportunity for extra credit in this project.