On the descriptive power of simple precedence grammars Article

Milani, MT. (1991). On the descriptive power of simple precedence grammars . INTERNATIONAL JOURNAL OF COMPUTER MATHEMATICS, 39(1-2), 29-49. 10.1080/00207169108803977

cited authors

  • Milani, MT

authors

abstract

  • Simple precedence and other precedence-based grammars are traditionally defined to be without productions with the empty right-parts. Generalizing the simple precedence grammars to include productions with the empty right-parts, yields a class of grammars that defines exactly the deterministic context-free languages. Using a family of iteration theorems, it is shown that the descriptive power of the generalized simple precedence grammars increases directly as the number of the productions with the empty right-parts increases. That is, the number of productions with the empty right-parts induce an infinite hierarchy upon the class of deterministic context-free languages. The class of languages in each layer of this infinite hierarchy is characterized in terms of their number of “counting schemes” and required “middle markers”. © 1991, Taylor & Francis Group, LLC. All rights reserved.

publication date

  • January 1, 1991

published in

Digital Object Identifier (DOI)

start page

  • 29

end page

  • 49

volume

  • 39

issue

  • 1-2