Reconciling Unger’s parser as a top-down parser for CF grammars for experimental purposes
Lukasz Kwiatkowski · 2005
Current parsing techniques are not appropriate when it comes to large scale software analysis. The techniques that are used in industry (LR, LL, LALR) do not support full CF grammars and require severe changes to the grammar, moreover they are not compositional. The current replacement of generalized (scannerless) LR parsing being developed at CWI in Amsterdam is heavily used within research groups, such as the Free University Amsterdam. However also this technique has its limitations. The literature considers top-down parsing as a preferred method for deriving parse trees. In this study a neglected parsing technique, Unger’s algorithm, is reconsidered as the point of departure for building a general top-down parser. The algorithm presented by Stephen H. Unger in 1968 requires exponential time in the worst case however incorporation of a known parsings table reduces the time requirement to polynomial space. Combination of the known parsings table along with a number of heuristic optimizations was applied to the Unger’s method. Empirical results obtained from tests on the full context-free IBM VS Cobol II grammar present a significant performance improvements, still however not sufficient to use the technique in the industrial environment. Support for the full CF syntax and the transparent, top-down, approach in deriving parse-trees makes the technique suitable for experimenting with solutions to overcome the limitations of the current parsing techniques.