Efficient implementation of Relational Parser

Parser relacyjny jest parserem uogólnionym, który wspiera wszystkie typy gramatyk bezkontekstowych w złożoności asymptotycznej równie dobrej co najlepsze uznane parsery - O(n), O(n^2), O(n^3) dla odpowiednio LR-regularnych, jednoznacznych i niejednoznacznych gramatyk. wyróżniający się zwięzłym matematycznym zapisem i wyjątkową własnością wykorzystywania jedynie niemodyfikowalnych (ang. immutable) struktur danych. Poniższa praca wprowadza pojęcia potrzebne do zrozumienia działania algorytmu, a następnie prezentuje implementację parsera w języku C++, opisując użyte struktury danych i różne optymalizacje sprawiające, że parser jest efektywny. Wydajność parsera jest zestawiona z kilkoma innymi konkurentami, pokazując potencjał parsera w praktycznych zastosowaniach. Ostatnie rozdziały opisują pomysły na dalszy rozwój implementacji.

Relational Parser is a generalized parser which can handle all types of context free grammars in complexity matching the current best state-of-the-art generalized parsers -- for -regular, unambiguous and ambiguous grammars, respectively. It features a clean mathematical formulation of the algorithm with a standout property of using only immutable data structures. This thesissets forth concepts needed to understand the algorithm and then presents aC++ implementation of Relational Parser, describing data structures andvarious optimizations making the parser efficient.Performance of the reference implementation is compared against severalcompetitors, assessing the potential of the parser in practical applications.Finally, the last sections feature ideas for further development of the parser.