Sloth Parser

Due: February 19

Introduction

This is the second phase of the Sloth interpreter assignment. In this phase, you will be writing a grammar for Sloth and using ANTLR to convert it into a parser for Sloth input files.

Test Programs

You can use the same set of input files to test your parser:

Program	Description
hello.sl	Prints hello world
simple.sl	Prints 1 + 1.
area.sl	Inputs the radius of a circle and computes its area.
fact.sl	Inputs a number and computes the factorial of that number.
fibs.sl	Inputs a number N and displays the first N Fibonacci numbers.
minmax.sl	Inputs a number N, then inputs N numbers, then displays the ones with the least and greatest values.
guess.sl	A guess the number game
table.sl	Prints a 2D multiplication table
acid.sl	A program that tests out most aspects of the language, and simply outputs 42.

Syntax Analysis

The syntactic details of Sloth are described here, and will help you write the parser.

Programs in Sloth consist of zero or more statements.

Each statement can be:

An assignment
This consists of an identifier, the := operator, an expression, then a semi-colon. Example:
```
number1 := a + 3;
```
An if statement
This consists of the "if" keyword, an expression, the "then" keyword, and then a statement. Example:
```
if a < b then
    a := b;
```
An if/else statement
This consists of the "if" keyword, an expression, the "then" keyword, a statement, the "else" keyword, then another statement. Example:
```
if a < b then
    a := b;
else
    b := a;
```
A while statement
This consists of the "while" keyword, an expression, the "do" keyword, then a statement. Example:
```
while i <= 10 do
    i := i * 2;
```
A print statement
This consists of the "print" keyword, followed by an expression in parentheses, then a semi-colon. Example:
```
print("Hello");
```
A println statement
This consists of the "println" keyword, followed by an expression in parentheses, then a semi-colon. Example:
```
println("Hello");
```
A statement sequence
This consists of the "begin" keyword, 0 or more statements, and then the "end" keyword. Example:
```
begin
    x := 5;
    print(x);
end
```

Notes:

Semi-colons are only a part of assignment and print statements.
Statements used as part of if and while are single statements. To have more than one, the statement sequence is used.

Expressions are the other major part of Sloth syntax. An expression consists of literal values, identifiers and input expressions combined with parenthesis and the following operators (in order of precedence):

Parenthesis
!
* /
+ -
< <= > >= == !=
&&
||

The "input expressions" mentioned above are one of the following:

readInt()
readReal()
readString()
readBool()

All operators are binary except for ! which is unary. The operators each have the same meaning as they do in C-based languages.

Your program will parse Sloth programs using the ANTLR generated grammar. If an input program does not fit the grammar you specify, Bison will produce an error.

Building the Parser

Begin by making two small changes to your "SlothLexer.g4" file from part 1:

Change the line which says grammar SlothLexer to say lexer grammar SlothLexer instead.
Remove the line which reads program:;.

These changes will make your lexer work with the parser we will write instead of be a stand-alone grammar.

Now create the file "SlothParser.g4" and begin it with the line parser grammar SlothParser. Include this line so that it pulls its toekns from our lexer:


options {
    tokenVocab = SlothLexer;
}

The rest of this file should contain the syntax rules for Sloth programs. Call your top-level syntax rule program.

You can use the following build and clean scripts to build and clean (remove generated files) the parser and lexer. These rely on having completed the ANTLR setup instructions.

Testing

We can again use the grun test tool in order to test our grammar. The following command should run the fact.sl Sloth program through the parser:

grun Sloth program -tree < fact.sl

This should produce something like the following output, showing the structure of our code:

(program (statement print ( (expression (term "Please enter a number: ")) ) ;) (statement x := (expression (term readInt ( ))) ;) (statement counter := (expression (term x)) ;) (statement fact := (expression (term 1)) ;) (statement while (expression (expression (term counter)) > (expression (term 1))) do (statement begin (statement fact := (expression (expression (term fact)) * (expression (term counter))) ;) (statement counter := (expression (expression (term counter)) - (expression (term 1))) ;) end)) (statement println ( (expression (expression (expression (term x)) + (expression (term "! = "))) + (expression (term fact))) ) ;))

We can also use the following to generate a graphical version of the tree:

grun Sloth program -ps tree.ps < fact.sl

This creates a Postscript file called "tree.ps" with the graphical representation. This looks like this:

You may need to install a program that can read Postscript files to view them.

Submitting

Submit your SlothParser.g4 file to Canvas for this assignment.