Research thesis
Final thesis paper submitted to the Senate of the Technion
Conflict resolution is a fundamental problem in the Theory of Compilation. Yacc resolves conflicts by means of priorities and associativity. The main disadvantage of Yacc is that it is based on BNF grammars which do not provide intuitive way of a formal language description. Extended BNF (EBNF) improves BNF by involving regular expressions such as lists, alternatives etc. Many conflicts of BNF grammars do not occur in EBNF grammars.
Still, EBNF grammars bear conflicts that should be resolved. Moreover, in addition to standard types of conflicts (Shift/Reduce and Reduce/Reduce) two additional types (Pop/Reduce and Pop/Pop) may occur.
We propose a method of conflict resolution in EBNF grammars which generalize the approach of priorities and associativity. With our approach priorities and associativity can be specified for productions and components as well as for terminals. Automatic Priority Inference (API) is proposed for implicit assigning of priorities and associativity. Also, we propose a method for resolving Pop/Reduce and Pop/Pop conflicts.
We implemented these methods as a part of a large ongoing project Jamoos - a new object-oriented parser generator for EBNF grammars.
Microsoft Power Point Presentation: seminar.zip (67K)
The final paper, submitted to the Senate of the Technion, is available
The LaTeX sources of the final paper are available here: thesis.zip (389K)
Source code of Jamoos
Jamoos is ongoing project. In the current version of Jamoos:
The source code is available here: jamoos_source.zip (1.5M)
The current executable version is available here: jamoos.zip (537K)
Examples of parsers generated by Jamoos
Each example contains:
Parser for a formal language L
Definitions of classes corresponding to productions of a grammar G which describes L
Lexical definitions for tokens of G
Report for G which contains statistics on G, description of the parser states, detailed information regarding conflicts that occurred in G and their resolution etc.
Examples of parser inputs (can be found in the directory Inputs)
More detailed information about files generated by Jamoos can be found in Jamoos manual.