Evaluation of a GLL Parser for Storm with Error Recovery

Sammanfattning

This thesis evaluates an existing Generalised LL (GLL) parser for the Storm programming language platform and compares it to the current Generalised LR (GLR) parser. The focus is on parsing performance, error recovery, and syntax highlighting when syntax errors are present. A simple character-based recovery mechanism is implemented for the GLL parser. The evaluation uses generated Storm inputs, both with and without introduced syntax errors. Valid inputs are measured using strict parsing, while erroneous inputs are measured using approximate parsing. Syntax highlighting is evaluated by first checking which correct inputs produce syntax colour, and then comparing how much highlighting remains after errors are introduced. The results show that the GLL parser performs especially well on valid expression-chain inputs, where it is up to 106 times faster than the GLR parser in the evaluated tests. For more deterministic inputs, the difference is smaller. With syntax errors, the results are more mixed: GLL remains faster for the simple expression grammar, but can be slower on some long erroneous inputs in the more realistic Storm language. For inputs that produce syntax-highlighted output in the baseline test, the highlighting results are mixed. GLL preserves useful highlighting in several error cases, while GLR preserves more of the expected colours in some missing-closing-brace cases. Overall, the results indicate that the GLL parser is a promising alternative to the current GLR parser in Storm, but that the recovery strategy needs further improvement before full editor integration.