1. General points

We recommend that you use a recursive descent parser like the one implemented by Kenneth C in his Tiny compiler but you are allowed to use any type of parsing method you choose. Louden in his Tiny compiler. Below are the steps to follow regardless of what parsing method you use.

• Read over the grammar in Appendix A.2.
• After understanding the grammar, it will be necessary to design a syntax tree structure for C- suitable for generation by a parser (see section 3.7 for an example of a syntax tree structure for the Tiny language). It is important to take your time during this stage to develop a suitable syntax tree structure because it is the basis for the rest of the compiler. When this step is complete you should have produced diagrams for your report, which outline the major nodes, relations, and their attributes needed for parsing.
• The grammar may now be modified according to the parse method being used.
• Convert the modified grammar and syntax tree structure to code.

2. Suggested Readings

1. Appendix A.2 up to BNF rule 29
2. Chapter 3
3. Chapter 4

3. Parser I/O structure

It is the task of the parser to determine the syntatic structure of a program from the tokens produced by the scanner and to explicitly construct a parse tree (syntax tree) that represents this structure.

Sequence of tokens       

                                                  Syntax Tree

Usually the sequence of tokens is not an explicit input parameter, but the parser calls a scanner procedure such as getToken to fetch the next token from the input as it needed during the parsing process. The parser object should return a parse tree that can be used by the semantic analysis. This handling of tokens to construct a parse tree can be observed in the Tiny code.

4. Sample Output

Using the program nfact.mns two expamples of the output produced by the parser are shown. Feel free to make additions that you deem necessary.

[EFS]>cat nfact.mns
/**************
  recursive N factorial.  Used
  for testing recursion.  Also
  used to make sure that the
  answer from recursive n! is the
  same as iterative n!.
**************/

/* recursively call n!*/
int nfact(int n)
{
  if( n == 0 )
  {
    return 1;
  }
  else
  {
    return(n*nfact(n-1));
  }

  return 0;
}

void main(void)
{
  int n;
  n = input();
  n = nfact(n);
  output(n);
}
[EFS]>

[EFS]>cminus nfact.mns
 
CMINUS COMPILATION: nfact.mns
 
Syntax tree:
  INT Func: nfact
    INT PARAM: n
    Compound Block
      If
        Op: ==
          Id: n
          Const: 0
      Then
        Compound Block
          Return
            Const: 1
      else
        Compound Block
          Return
            Op: *
              Id: n
              CALL: nfact
                Op: -
                  Id: n
                  Const: 1
      endif
      Return
        Const: 0
  VOID Func: main
    VOID PARAM: (null)
    Compound Block
      INT VAR: n
      Assign:
        Id: n
        Input()
      Assign:
        Id: n
        CALL: nfact
          Id: n
      Output:
        Id: n
[EFS]>

[EFS]>c- nfact.mns
 
*********C- COMPILATION: nfact.mns*********
 
 and creating syntax tree...
 
Syntax tree:
  Function; id:nfact return type:int
  Function parameter list:
    Integer Declaration; id:n
    CompStmtK:
      If
        Op: ==
          Integer Variable; id:n
          Const: 0
      Then
        CompStmtK:
          ReturnK:
            Const: 1
      Else
        CompStmtK:
          ReturnK:
            Op: *
              Integer Variable; id:n
              CallK; name: nfact
                Call argument list:
                Op: -
                  Integer Variable; id:n
                  Const: 1
      Endif
      ReturnK:
        Const: 0
  Function; id:main return type:void
    Function Parameter list:Void
    CompStmtK:
      Integer Declaration; id:n
      Assignment:
        Integer Variable; id:n
        CallK; name: input
          Void argument list.
      Assignment:
        Integer Variable; id:n
        CallK; name: nfact
          Call argument list:
          Integer Variable; id:n
      CallK; name: output
        Call argument list:
        Integer Variable; id:n
[EFS]>

5. What to hand in

The writeup should be approximately 2 pages excluding diagrams, tables and code. The assignment should have the following sections:

1. Description of the solution
   • A Description of the main functions.
2. Description of the Parse-tree data structure.
   • State the file where the declaration of syntax tree nodes can be found in.
   • A description of the main syntax tree nodes.
   • Include diagrams of the syntax tree structure. You can use a format similar to page 135-138.
3. The C- Grammar
   • List the grammar used (explain your notation if it is not EBNF).
   • Explain the modifications to grammar (i.e. removal of left recursion and ambiguity).
4. Bugs in Code
5. Solutions to these Bugs
6. Description of Conventions
   • State each error message and its meaning.
   • State any other conventions that you may have produced.
7. Compiling and Running Cminus code
   • Show how you compile and run your Cminus code using descriptions and/or examples.
   • Show how you run a compiled Cminus program using descriptions and/or examples.
   • Explanation of the syntax tree produced by the parser.
8. Code
   • State all the modified files in this section of the report.
   • Include all code.