Parsing plays an important role in static program analy-
sis: during this step a structural representation of code is created upon
which further analysis is performed. Parser generator tools, being pro-
vided with syntax specification, automate parser development. Language
documentation often acts as such specification. Documentation usually
takes form of ambiguous grammar in Extended Backus-Naur Form which
most parser generators fail to process. Automatic grammar transforma-
tion generally leads to parsing performance decrease. Some approaches
support EBNF grammars natively, but they all fail to handle ambigu-
ous grammars. On the other hand, Generalized LL parsing algorithm
admits arbitrary context-free grammars and achieves good performance,
but cannot handle EBNF grammars. The main contribution of this pa-
per is a modification of GLL algorithm which can process grammars in
a form which is closely related to EBNF (Extended Context-Free Gram-
mar). We also show that the modification improves parsing performance
as compared to grammar transformation-based approach.
Also contains a full GLL implementation.