Feriozi, Dan T.

A new method of analyzing and parsing the strong LL(k) class of the deterministic context-free grammars is presented. The method is shown to be efficient when applied to many typical parsing applications such as compilers for common programming languages. Another advantage of the method is that it uses the familiar LL(1) parse table as a base. Parse conflicts that are found in the LL(1) parse table are treated as exceptions, and are resolved by consulting another table. This extension to the traditional LL(1) methodology increases its power significantly. Both the space and the time efficiency of the new method are shown to be much greater than that of the standard strong LL(k) method, when used on common grammars. Since the recognition problem for the strong LL(k) grammars is known to be NP-complete, the worst-case complexity of the new method is exponential, as is the case with the standard method. However, the complexity of the new method is highly dependent on the form of the grammar that is being analyzed. Both the space requirements and the time complexity of the new method are polynomial functions of the size of the input to the problem for common grammars, such as those used for programming languages. This is in contrast to the standard method that has been used for parsing the strong LL(k) languages. That method always uses space and time that is an exponential function of the size of the input.