TC-1/2-Parser Code to Write

Warning

Be sure to read Bison documentations and tutorials, see RE/flex & Bison.

See the lecture notes, and read the C++ chapter of GNU Bison’s documentation.

Pay special attention to its ‘’Complete C++ Example’’ which is very much like our set up.

Take time to read all AST classes in The src/ast Directory directory to understand them well as you will build nodes in the parser and print them in the Pretty Printer.

What is to be done:

Makefile.am

Include your own testsuite in the tests directory. Some test examples are given in the tests folder (Given Test Cases). Do not hesitate to make use of them.

Include your own test suite in the tests directory, and hook it to make check. See Generating The Test Driver.

---

src/parse/tiger-factory.hxx

Implement all methods to create AST nodes on the driver with make_ methods.

As mentioned above the tiger-factory functions will be used in Bison’s actions to create the different nodes of the AST.

src/parse/tasks.cc

Complete the parse procedure to set the_program (the root of the AST) as the result of the parsing.

src/parse/parsetiger.yy

Complete parser

The parser must be able to parse tokens as described in Syntactic Specifications and Additional Syntactic Specifications.

What is Bison?

Bison is a parser generator, allowing to generate parsers of the LR family. Bison is a tool created by the GNU and maintained by Akim Demaille, the creator of the Tiger Compiler project (Fair Criticism). The goal of Bison is to write grammar rules in YACC (Yet another Compiler Compiler) format in order to be able to parse a language.

What does Bison generate?

Bison generates two files: parsetiger.hh and parsetiger.cc, which represent the parser. The parser is a class named parse::parser which contains a parse(...) method to start parsing.

What is the structure of a Bison file?

A Bison file has a special syntax because it will generate C++. Here is a Bison Grammar Outline to the documentation for more information.

How to write a Bison rule:

To write a rule with Bison you have to start from the EBNF grammar defined in the Syntactic Specifications and Additional Syntactic Specifications, then adapt it to the YACC syntax that Bison uses.

Here is an example of Bison code that parses this rule:

(* === Expressions. === *)
exp =
  (* Literals. *)
  | INT
  | STRING
  ;

In Bison syntax:

exp:
  INT
| STRING;

In this case INT and STRING are tokens created by the lexer.

During the development of your parser you will have problems with conflicts, there are two types of conflicts Shift/Reduce and Reduce/Reduce.

In order to solve these different problems, you are invited to read this documentation regarding the Bison algorithm.

For some cases such as function arguments, you will need to use recursive rules.

GLR parser

We use %glr-parser and %skeleton "glr2.cc" directives to have Bison generate a GLR parser. Thanks to GLR, some conflicts (S/R and/or R/R) can be resolved at runtime. Use %expect and %expect-rr to specify their number. For information, we allow zero R/R conflicts, and one S/R related to the “big lvalue” issue.

Trace the parsing

Use %printer to implement --parse-trace support for terminals and non-terminals (see TC-1/2-Parser Samples).

For instance,

%define api.value.type variant
%token <int> INT "integer"
%printer { yyo << $$; } <int>

You can also use the PARSE environment variable to invoke parse tracing.

---

Build the AST

To build your AST you will have to use Bison’s actions.

Here is an example of actions you can do for arithmetic operations:

/* Arithmetics.  */
exp: /* this is the production rule */
  exp "+"  exp { $$ = $1 + $3; }
| exp "="  exp { $$ = $1 == $3; }
...

Statements between brackets are called actions. They allow to link the reduction of a rule to code. What we want to do is recursively build an AST. For that, we make use of action features.

We use the $1 action feature to retrieve the parsing production of the the first symbol (here, the left-hand side exp). $3 correspond to the third symbol (the right-hand side exp); @$ retrieves the location of the rule and $$ means that the assigned expression will be the result of the production rule.

The previous code example can also be written in this way:

/* Arithmetics.  */
exp[result]:
  exp[left] "+" exp[right] { $result = $left + $right; }
| exp[left] "=" exp[right] { $result = $left == $right; }
...

The two version have the same behavior, but in this version we replaced the action features by named references. Here, $$ is replaced by $result, $1 is replaced by $left and $3 is replaced by $right.

To produce the AST you will have to use the same process but using this time the functions declared in the tiger-factory files.

/* example */
make_OpExp(/* insert the correct arguments */);
make_IfExp(/* insert the correct arguments */);

Warning

To have a full understanding of Bison’s actions read the Bison documentation about actions and action features.

Desugar Boolean operators and unary minus in concrete syntax

In the original version of the exercise, the | and & operators and the unary minus operator are desugared in abstract syntax (i.e., using explicit instantiations of AST nodes). Using TWEAST, you can desugar using Tiger’s concrete syntax instead. This second solution is advised.

More information available in the syntactic sugar section on the CCMP slides.

Support object-related syntax (Optional)

Supporting object constructs, an improvement suggested for TC-1/2 (see TC-1/2-Parser Improvements), is highly recommended.

Error recovery (Optional)

There should be at least three uses of the error token. Read the Bison documentation about it. Use %destructor to reclaim the memory bound to semantic values thrown away during error recovery.

src/parse/tiger-driver.cc

The class TigerDriver drives the lexing and parsing of input file. Its implementation in src/parse/tiger-driver.cc is incomplete.

You have to add the creation of the lexer and the parser, as well as launch the parsing.

TigerDriver acts as a bridge between the lexer, the parser and the error handling, among other things. For more information, see old/02-parser-scanner.pdf: most of what you need to know is detailed here.

---

src/ast/default-visitor.hxx

Complete the GenDefaultVisitor class template. It is the basis for following visitors in the Tiger compiler.

For more information on the visitor design pattern, refactoring.guru may help you.

src/ast/pretty-printer.*

The PrettyPrinter class must be written entirely. It must use the misc::indent features to support indentation.

src/ast/object-visitor.hxx (Optional)

Likewise, complete GenObjectVisitor. This class template is used to instantiate visitors factoring common code (default traversals of object-related nodes) and serves as a base class of ast::PrettyPrinter (and later bind::Binder).

src/ast/dumper-dot.* (Optional)

The DumperDot class is used to create a graphviz dumper of your AST.

The dumper dot, though not mandatory, is very useful for debugging as it allows to visualize its AST very simply. This part is optional an will not be tested (see TC-1/2-Parser Optional GraphViz Dumper).

An example of what the dumper dot produces:

print-42.tig

let
  var life := 42
in
  print_int(life);
  print("\n")
end

print-42.png

• TC-1/2-Parser Optional GraphViz Dumper