Documentation

Content

1. Scanner

   a. General description

   b. Algorithm

   c. Automaton

   d. Post processing

2. Parser

   a. General description

   b. Grammar and automaton

   c. Post processing

3. Pretty-printer

   a. General description

Scanner

General description

Scanner goal is to tokenize the SPL program into tokens defined by regular expressions:

< id, ….> - alpha (‘_’, alphaNum)*
< int, ….> - [-] (digit)+
< char, ….> - \’ alpha \’
< op, ….> - ‘+’, ‘-‘, ‘*’, ‘/‘, ‘%’, ‘==‘, ‘<’, ‘>‘, ‘<=’, ‘>=‘, ‘!=’, ‘&&‘, ‘||’, ‘:’
< br, ….> - ‘(’, ‘)‘, ‘[’, ‘]‘, ‘{’, ‘}‘
< pnc, ….> - ‘,’, ‘;’
< fld, ….> - ‘.’

Algorithm

Symbols are being read one by one, added to string and changing state of the scanner automaton. In the moment of transition from one final state k1 to another final state k2 where k1 is different than S, tuple <k1, string> is created and added to list of tokens. String is then cleared and algorithm follows until end of the input.

Automaton

Definition of the automaton can be found here.

Post processing

This is the simplest version of automaton which does not use any kind of a look ahead. This leads to some mistake being made which are then solved in a post processing method which takes list of tokens as input.

Fixes:

1. In case of operators like '==', where first sign can be alone taken as an operator, the result of automaton is '=' followed by '='. Post processing method finds symbols that can together create a longer operator and joins them into one token.

Parser

General description

Parser goal is to create an Abstract Syntax Tree for a given program. Tokens previously created by scanner are now an input to the parser.

Grammar and automaton

Parser automaton is created from modified version of original SPL grammar. For this language we have created the LL(0) parser. Modified grammar (which is also definition of the parser automaton) and other useful information for parser automaton and post processing method can be found here.

Post processing

To create an automaton there was a need to add some states to the grammar which are not suppose to be present in AST (Abstract Syntax Tree). The post processing method should delete those redundant states. The list of temporary and possible redundant states can also be found in the previous
file at the last page.

Fixes:

1. Delete temporary states.
2. Delete possible redundant states after checking whether they are useful or not.

Pretty printer

General description

Pretty printer goal is to create new version of user's program which is nicely formatted and free of comments.