This repository was an assignment I completed for The University of Bath on February 2022. Course: MSc Computer Science Module: Foundations of Computation
Assignment Background: Context-free grammars are used extensively in modelling the syntax of programming languages. A compiler for such a language will include a parser. This is basically an algorithm to determine whether a given string belongs to the language generated by a given context-free grammar and, if so, construct a parse tree of the string. The compiler would then go on to translate this parse tree into low-level machine code.
Task: Implement two different algorithms which determine whether a context-free grammar accepts a given string and, if so, produce a parse tree for that string.
BF/Parser - implements a brute force approach to finding all possible derivations. Only works on simple strings. CYK/Parser - implements a more sophisticated approach, using the Cocke-Kasami-Younger algorithm.
Note: For this assignment I only needed to implement the algorithm code found in the two classes shown above. All other code was provided by the academic staff: