An efficient extension of earley's algorithm for parsing multidimensional structures

Analysis of multidimensional structures is important to model verification in software engineering. An efficient extension of traditional Earley's algorithm was made for a two-dimensional relation structures. The parsing table was extended first so as to record two-dimensional information of symbols and relationships and to distinguish the analyzed part from un-analyzed part in an unordered set. Then the construction process of the parsing table was reformed to realize unordered parsing for two-dimensional structures. Furthermore, based on the above approaches, the predictive mechanism of looking ahead a symbol and its relationship was introduced to reduce the redundant states during the parsing process. Finally, empirical results show that the algorithm is efficient.