An Optimal Tabular Parsing Algorithm

AN OPTIMAL TABULAR PARSING ALGORITHM Mark-Jan Nederhof * University of Nijmegen, Department of Computer Science Toernooiveld, 6525 ED Nijmegen, The Netherlands markj an~cs, kun. nl Abstract In this paper we relate a number of parsing algorithms which have been developed in very different areas of parsing theory, and which include deterministic algo- rithms, tabular algorithms, and a parallel algorithm. We show that these algorithms are based on the same underlying ideas. By relating existing ideas, we hope to provide an op- portunity to improve some algorithms based on features of others. A second purpose of this paper is to answer a question which has come up in the area of tabular pars- ing, namely how to obtain a parsing algorithm with the property that the table will contain as little entries as possible, but without the possibility that two entries represent the same subderivation. Introduction Left-corner (LC) parsing is a parsing strategy which has been used in different guises in various areas of com- puter science. Deterministic LC parsing with k symbols of lookahead can handle the class of LC(k) grammars. Since LC parsing is a very simple parsing technique and at the same time is able to deal with left recursion, it is often used as an alternative to top-down (TD) parsing, which cannot handle left recursion and is generally less efficient. Nondeterministic LC parsing is the foundation of a very efficient parsing algorithm [7], related to Tomita's algorithm and Earley's algorithm. It has one disad- vantage however, which becomes noticeable when the grammar contains many rules whose right-hand sides begin with the same few grammars symbols, e.g. A ~ c~f~l I ~f~2 I ... where ~ is not the empty string. After an LC parser has recognized the first symbol X of such an c~, it will as next step predict all aforementioned rules. This amounts to much nondeterminism, which is detrimental both to the time-complexity and the space-complexity. *Supported by the Dutch Organisation for Scientific Re- search (NWO), under grant 00-62-518 A first attempt to solve this problem is to use predic- tive LR (PLR) parsing. PLR parsing allows simulta- neous processing of a common prefix c~, provided that the left-hand sides of the rules are the same. However, in case we have e.g. the rules A --* c~t31 and B --~ ~/32, where again ~ is not the empty string but now A ~ B, then PLR parsing will not improve the efficiency. We therefore go one step further and discuss extended LR (ELR) and common-prefix (CP) parsing, which are al- gorithms capable of simultaneous processing of all com- mon prefixes. ELR and CP parsing are the foundation of tabular parsing algorithms and a parallel parsing al- gorithm from the existing literature, but they have not been described in their own right. To the best of the author's knowledge, the various parsing algorithms mentioned above have not been dis- cussed together in the existing literature. The main purpose of this paper is to make explicit the …

Content truncated to 500 words