> .ROLE
PROGRAMMER
> .DETAILS
PART I:
You must implement an LL(1) parser to recognize valid and invalid datalog programs according to the Datalog grammar definition. LL(1) is understood as a left to right scan of the input to create a left derivation using only the next token as a look ahead (e.g. a deterministic top-down parser that chooses the rule to expand based on the current token). The parser implementation must also be recursive meaning it either uses the runtime stack to keep track of rules in the parse or it manages a stack or rules directly similar to the parse table. Either solution works; although, using the runtime stack is much more direct and simple (i.e., create a method for every rule in the grammar).
Further, at least 10 test inputs must be created to test the functionality of the parser. The tests are individual files containing datalog programs (valid or invalid). The tests should cover corner cases and include, in the comments of the datalog test input, an explanation of what is being tested with the expected output. Further, all the tests must be automatic; automatic means the tests run without any user input and reports to the console the status of every test: pass or fail. The tests must be documented and justified: what does the test accomplish.
PART II:
As the parser traverses the input file reading tokens, collect data from the tokens to store the program input as a collection of instances of classes. If the input is a valid datalog program, then use the class instances to generate output detailing the input data. Classes should be created for at least the following parts of the language: datalogProgram, rule, predicate, parameter, and expressions. Expressions may be a subclass of Parameter. Expressions require a tree structure to represent arbitrarily nested expressions.
The datalog program class should use lists of object instances to collect schemes, facts, rules, or queries. The output for this part of the project must be generated from the datalogProgram class member variables after the parsing is complete. Implementing toString methods for the different classes is one of several ways to generate the program output.
> .TECHNOLOGY
C++, VISUAL STUDIO