Access Restriction

Author Hunt, Harry B. ♦ Szymanski, Thomas G. ♦ Ullman, Jeffrey D.
Source ACM Digital Library
Content type Text
Publisher Association for Computing Machinery (ACM)
File Format PDF
Language English
Subject Keyword Np-complete problems ♦ Parsing ♦ Computational complexity ♦ Lr(k) grammars ♦ Context-free grammars
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.
Description Affiliation: Harvard Univ., Cambridge, MA (Hunt, Harry B.) || Princeton Univ., Princeton, NJ (Szymanski, Thomas G.; Ullman, Jeffrey D.)
Age Range 18 to 22 years ♦ above 22 year
Educational Use Research
Education Level UG and PG
Learning Resource Type Article
Publisher Date 2005-08-01
Publisher Place New York
Journal Communications of the ACM (CACM)
Volume Number 18
Issue Number 12
Page Count 10
Starting Page 707
Ending Page 716

Open content in new tab

   Open content in new tab
Source: ACM Digital Library