A transformation is defined which is a modification of a classic transformation on context-free grammars. By means of this transformation, a proof is presented of the fact that any cycle-free context-free grammar can be left-to-left-corner covered by a non-left-recursive grammar. The proof method is based on the idea to transform the characteristic grammar associated with the simple syntax-directed translation scheme which defines the left-corner parse of the strings generated by the input grammar of the scheme. It is shown that the transformation yields an LL(k) grammar if and only if it is applied to an LC(k) grammar. Finally, some ideas are presented to extend the theory of covers to the semantical covering of attribute grammars.
|Title of host publication||Essays on concepts, formalisms, and tools|
|Subtitle of host publication||A collection of papers dedicated to Leo A.M. Verbeek|
|Editors||P.R.J. Asveld, A. Nijholt|
|Place of Publication||Amsterdam|
|Publisher||Centre for Mathematics and Computer Science|
|Number of pages||21|
|Publication status||Published - 1987|
|Publisher||Stichting Mathematisch Centrum|
- HMI-SLT: Speech and Language Technology
op den Akker, R. (1987). On Covers and Left-Corner Parses. In P. R. J. Asveld, & A. Nijholt (Eds.), Essays on concepts, formalisms, and tools: A collection of papers dedicated to Leo A.M. Verbeek (pp. 107-127). (CWI Tract; No. 42). Amsterdam: Centre for Mathematics and Computer Science.