2.Syntax.Analysis.md

Phase 2: Syntax Analysis

In the second phase of our term project, we implement a handwritten predictive parser for the SnuPL/2 language.

[[toc]]

Description

The output of the parser is an abstract syntax tree (AST) in textual and graphical form. Semantical checks (type checking, number of parameter checking, etc.) should not be implemented in this phase - with one exception: symbols must be defined before use. In addition, constraints that cannot be expressed with a context-free grammar but are part of the syntax should be checked. In SnuPL/2, these constraints include matching a declaration and end identifier of the module and the subroutines.

Your Task

A skeleton for the parser is provided so that you can focus on the interesting parts. The working example, as in the first phase, implements a parser for the SnuPL/-1 language. You can use your scanner from phase 1, or use our scanner binary for SnuPL/1 provided in the directory scanner/.

The parser skeleton can be found in snupl/src/parser.[h/cpp]. The parser already outputs an AST and contains a type manager and a nested symbol table. We recommend to use and extend the existing code, but of course you can also write your own class hierarchy - or use the language of your choice to implement your parser. In its current form, the parser parses and builds an AST for SnuPL/-1.

In the parser, you will have to modify/code the methods of the predictive parser. For SnuPL/-1, the following methods are implemented:

    /// @name methods for recursive-descent parsing
    /// @{

    CAstModule*       module(void);

    CAstStatement*    statSequence(CAstScope *s);

    CAstStatAssign*   assignment(CAstScope *s);

    CAstExpression*   expression(CAstScope *s);
    CAstExpression*   simpleexpr(CAstScope *s);
    CAstExpression*   term(CAstScope *s);
    CAstExpression*   factor(CAstScope *s);

    CAstConstant*     number(void);

    /// @}

The call sequence of the method implicitly represents the parse tree. The AST is constructed from the return values of the methods called during the parse. The many classes of the AST are defined in snuplc/src/ast.h. The implementation of the AST classes is split into three files:

• snuplc/src/ast.cpp contains the boilerplate code and (with one exception in Phase 3) does not need to be modified.
• snuplc/src/ast_semanal.cpp contains the methods related to semantic analysis that we will implement in Phase 3.
• snuplc/src/ast_tacgen.cpp contains the methods related to three-address code generation that we will implement in Phase 4.

In a first step, you may want to simply build a predictive parser that only consumes the tokens but does not build the AST (i.e., by not returning an AST node but NULL). Once your parser is working correctly, you can then start to return the correct AST nodes in a second step. The test files located in test\parser help guide you with the order of your implementation.

The type manager, implemented in snuplc/src/type.[h/cpp], does not need to be modified. You can use it to retrieve types for integer, character, boolean variables, and the composite types pointer and array. Call CTypeManager::Get()->GetInt()/GetChar()/GetBool()/GetPointer()/GetArray() to retrieve a reference to an integer, character, boolean, pointer or array type.

The symbol table is implemented in snuplc/src/symbol.[h/cpp]. Again, you do not need to modify this file, the provided functionality is sufficient for this phase of the project. Symbol tables are nested, you need to create a new nested symbol table whenever you parse a function/procedure and insert the symbols into the symbol table of the current scope.

A test program that prints the AST is provided. Build and run it as follows:

    snuplc $ make test_parser
    snuplc $ ./test_parser ../test/parser/test01.mod

In the directory test/parser/ you can find a number of files to test your parser. Similar to the first phase, we also provide the output of our reference parser. As usual, the provided test cases are rather simple and do not cover the entire SnuPL/2 syntax. We advise you to create your own test cases to examine more complex and special cases (include them in your submission!)

Materials to submit

• Source code of the parser
  Document your code properly - including Doxygen comments for all new classes, member functions, and fields. Please do not include any generated files (documentation, relocateable object files, binaries) into your GitLab repository. We will compile your code by ourselves.

• A brief report describing your implementation of the parser in PDF format
  The report must be stored as reports/2.Syntax.Analysis.pdf.
  You can use the reports from the individual phases to compiler your final report at the end of this semester. Note that the reports are almost as important as your code. Make sure to put sufficient effort into them!

Final words

We hand out a lot of code in this phase. Before you start implementing your SnuPL/2 parser, analyze the source code and operation of the provided SnuPL/-1 parser. Remember that the documentation can be built with the make doc command. You'll then find your documentation in snuplc/doc/html/index.html.

As usual: start early, ask often! We are here to help.