A powerful LL(k) covering transformation

Cited 0 time in webofscience Cited 0 time in scopus
  • Hit : 609
  • Download : 0
k-transformable grammars have been conjectured to be the uppermost class of LL(k) covering transformable grammars. PLR(k) grammars have been known as a well characterized subclass of k-transformable grammars. Being contrary to those claims, this paper shows that some PLR( k) grammars are not k-transformable, and so k-transformable grammars are not the true uppermost. A powerful LL( k) covering transformation is suggested in this paper. It is a generalization of the transformations of k-transformable grammars and PLR( k) grammars. A remarkable aspect of the new transforming process is the deterministic property, where "deterministic" means that the transformation is obtained in a single process without requiring any heuristic, unlike k-transformable grammars' transformation for which a heuristic is required. The transformable grammar class is shown to be larger than k-transformable grammars and PLR( k) grammars.
Publisher
SIAM PUBLICATIONS
Issue Date
2005
Language
English
Article Type
Article
Citation

SIAM JOURNAL ON COMPUTING, v.35, no.2, pp.359 - 377

ISSN
0097-5397
DOI
10.1137/S0097539701400154
URI
http://hdl.handle.net/10203/86354
Appears in Collection
CS-Journal Papers(저널논문)
Files in This Item
There are no files associated with this item.

qr_code

  • mendeley

    citeulike


rss_1.0 rss_2.0 atom_1.0