AParse is a parser generater, just like Antlr, Bison and Yacc etc.
We propose a new grammar, named AParse
, which is strictly subset of Extended Backus–Naur form (E-BNF) of Context Free Grammar (CFG). AParse is powerful enough to express most of practically used programming languages like C++, Java, Python etc. We designed a mechanism to generate a parser from AParse grammar. Parser is capable of recognizing a string S and parse a valid string in O(|S|) time in worst case.
AParse is more powerful than other parser generators like Antlr, Bison, Yacc in following criterias:
- AParse is guaranteed to be linear time parser on any possible AParse grammar.
- AParse support sequential parsing, i.e. alphabets can be fed to parser one by one. There is no need of looking ahead in alphabet sequence. The parser can recognise the invalid alphabet in sequence and throw error.
- AParse support
PossibleAlphabets()
API which returns all the acceptable alphabets at any point of time while feeding the sequential alphabets. - If there is no possiblity of ambiguity, AParse parser can construct the partial-syntax-tree as alphabets are being fed to it. This is highly useful feature for the parsing of programming languages, which are not purely context-free, and require partially parsed context to interpret a token (ex:
type
vsvariable
in C++).