M.Sc Thesis

M.Sc StudentBekkerman Anna
SubjectConflict Resolution and Operator Priorities in Extended BNF
DepartmentDepartment of Computer Science
Supervisor ASSOCIATE PROF. Joseph Gil


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. Furthermore, in addition to standard types of conflicts (Shift/Reduce and Reduce/Reduce) two other types (Pop/Reduce and Pop/Pop) may occur.

We propose a conflict resolution method that is universal for all four types of conflicts which may occur in EBNF grammars. Our method generalizes the popular approach of priorities and associativity. With our method priorities and associativity can be explicitly specified for productions and components as well as for tokens. In addition, Automatic Priority and Associativity Inference (APAI) is proposed for implicit assignment of priorities and associativity. A runtime APAI is also proposed that performs a one-symbol lookahead for determining the actual parsing route in order to identify priority of the shifted token when more than one possible parsing routes exist for the input. The runtime APAI enriches the context information and provides the power of LR(2) without enlarging parsing tables. A set of original algorithms are designed for supporting the proposed conflict resolution method.

We implement these algorithms in a framework of a large ongoing project Jamoos - a new object-oriented parser generator for EBNF grammars.