On the Complexity of LR(k) Testing.
Saved in:
| Title: | On the Complexity of LR(k) Testing. |
|---|---|
| Authors: | Hunt, III, Harry B.1, Szymanski, Thomas G.2, Ullman, Jeffrey D.2 |
| Source: | Communications of the ACM. Dec1975, Vol. 18 Issue 12, p707-716. 10p. |
| Subjects: | Linguistic String Parser (Computer grammar), Comparative grammar, Computational linguistics, Mathematical linguistics, Programming languages, Computer programming, Exponential functions, Transcendental functions, Computer science, Logic programming |
| Abstract: | The problem of determining whether an arbitrary context-free grammar is a member of some easily parsed subclass of grammars such as the LR(k) grammars is considered. The time complexity of this problem is analyzed both when k is considered to be a fixed integer and when k is considered to be a parameter of the test. In the first case, it is shown that for every k there exists an O(nk+2) algorithm for testing the LR(k) property, where n is the size of the grammar in question. On the other hand, if both k and the subject grammar are problem parameters, then the complexity of the problem depends very strongly on the representation chosen for k. More specifically, it is shown that this problem is NP-complete when k is expressed in unary. When k is expressed in binary the problem is complete for nondeterministic exponential time. These results carry over to many other parameterized classes of grammars, such as the LL(k), strong LL(k), SLR(k), LC(k), and strong LC(k) grammars. [ABSTRACT FROM AUTHOR] |
| Copyright of Communications of the ACM is the property of Association for Computing Machinery and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.) | |
| Database: | Engineering Source |
Be the first to leave a comment!
