1. General points

We recommend that you use a recursive descent parser like the one implemented by Kenneth C Louden in his Tiny compiler; but, you are allowed to use any type of parsing method you choose. 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 in your text 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 (i.e. left factoring and left recursion removal¹).
• Convert the modified grammar and syntax tree structure to code.
• Special care should be taken when binding if-else statements.

1 The left recursion removal does not necessarily have to be removed entirely from your project for rule 18 in the Cminus grammar. Instead a backtracking method may be used.

2. Suggested Readings

1. Chapter 3
2. Chapter 4

3. Input to Build Parser

1.    <program> ::= <declaration-list> 

2.    <declaration-list> ::= <declaration-list> <declaration> |

                                      <declaration> 

3.    <declaration> ::= <var-declaration> |

                                    <fun-declaration> 

4.    <var-declaration> ::= <type-specifier> "ID" ";" |

                                      <type-specifier> "ID" "[" "NUM" "]" ; 

5.    <type-specifier> ::= "int" |

                                         "void"

6.    <fun-declaration> ::= <type-specifier> "ID" "(" <params> ")" <compound-stat>

7.    <params> ::= <param-list> |

                               "void" 

8.    <param-list> ::= <param-list> "," <param> |

                                  <param> 

9.    <param> ::= <type-specifier> "ID" |

                            <type-specifier> "ID" "[" "]" 

10.<compound-stmt> ::= "{" <local-declarations> <statement-list> "}"

11.<local-declarations> ::= <local-declarations> <var-declarations> |

                                               "empty"

12.<statement-list> ::= <statement-list> <statement> |

                                       "empty"

13.<statement> ::= <expression-stmt> |

                                <compound-stmt> |

                                <selection-stmt> |

                                <iteration-stmt> |

                                <return-stmt> 

14.<expression-stmt> ::= <expression> ";" |

                                            ";" 

15.<selection-stmt> ::= "if" "(" <expression> ")" <statement> |

                                        "if" "(" <expression> ")" <statement> "else" <statement> 

16.<iteration-stmt> ::= "while" "(" <expression> ")" <statement>

17.<return-stmt> ::= "return" ";" |

                                  "return" <expression> ";"

18.<expression> ::= <var> "=" <expression> |

                                   <simple-expression>

19.<var> ::= "ID" |

                      "ID" "[" <expression> "]"

20.<simple-expression> ::= <additive-expression> <relop> <additive-expression> |

                                               <additive-expression>

21.<relop> ::=  "<=" |

                          "<" |

                          ">" |

                          ">=" |

                          "==" |

                          "!="

22.<additive-expression> ::= <additive-expression> <addop> <term> |

                                                  <term>

23.<addop> ::= "+" |

                            "-"

24.<term> ::= <term> <mulop> <factor> |

                        <factor>

25.<mulop> ::= "*" |

                           "/"

26.<factor> ::= "(" <epxression>")" |

                          <var> |

                          <call> |

                          "NUM"

27.<call> ::= "ID" "(" <args> ")"

28.<args> ::= <arg-list> |

                        "empty"

29.<arg-list> ::= <arg-list> "," <expression> |

                           <expression>

4. Parser I/O structure

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

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.

5. Sample Output

Using the program nfact.mns two examples 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]>

6. What to hand in

The write-up should be approximately 4 pages excluding diagrams, tables and code. The assignment should have all of 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 (must be same EBNF notation as used by Kenneth C. Louden).
   • Explain the modifications to grammar (i.e. removal of left recursion and left factoring).
4. Bugs In Scanner
   • List the bugs that were found by the marker in your Scanner project
   • State explicitly which of these bugs have been corrected and which bugs have not been corrected and why.
5. Bugs in Parser
6. Solutions to Bugs in Parser
7. Description of Conventions
   • State each error message and its meaning.
   • State any other conventions that you may have produced.
8. 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.
9. Code
   • State all the modified files in this section of the report.
   • Include all code.

7. Parser Testing

The test code will only be made available after this part of the project has been marked, so that you can correct your code. It is your responsibility to develop your own tests and make sure this part of the project works. Note that you do not submit tests that you create yourself.

Parser Tests (this link is only made active after you this part of the project has been marked)