Search

A weakly conditional grammar is specified as a pair K=G, G' where G is a context-free grammar, and G' is a regular grammar such that a production rule of G is only applicable to the sentential form if it belongs to the language generated by G'. The nonterminal complexity VarK of the grammar K is defined as the sum of the numbers of nonterminals of G and G'. This paper studies the nonterminal complexity of weakly conditional grammars, and it proves that every recursively enumerable language can be generated by a weakly conditional grammar with no more than ten nonterminals. Moreover, it shows that the number of nonterminals in such grammars without erasing rules leads to an infinite hierarchy of families of languages generated by weakly conditional grammars.

This chapter contains sections titled: Introduction Grammars for Arithmetic Expressions Specifying Associativity and Precedence in Grammars Backus-Naur Form Syntax Diagrams Abstract Syntax Trees and Three-Address Code Noncontracting Grammars Essentially Noncontracting Grammars Converting a Context-Free Grammar to an Essentially Noncontracting Grammar Pumping Property of Context-Free Languages (Optional) Problems

An interpretation of a grammar form is called (k, i)-bounded iff all its nonterminals are substituted by at most k symbols and all its terminals are replaced by at most i words. The (k, i)-bounded grammar family of a grammar form is the collection of its (k, i)-bounded interpretations, and its (k, i)-bounded grammatical family is the corresponding family of languages. The paper gives basic properties of these families. Especially, we show the decidability of the equivalence problem for bounded grammar families, the undecidability of the membership problem for bounded language families and give some hierarchy, closure and descriptional complexity results. Finally, some consequences in normal form theory of context-free languages are presented.

It is shown that the set of all interpretations of one (or of all) context-free grammar forms modulo strong equivalence is a distributive lattice with respect to the ordering relation “is an interpretation of”. It is also established that for each context-free grammar form there exists a unique (up to “pseudo-isomorphism”) symbol-tight, strongly equivalent context-free grammar form which is minimal with respect to the number of productions.

This paper is concerned with the following problem: Given a context-free grammar G , find a context-free grammar with the fewest nonterminal symbols or with the fewest rules that is equivalent to G . A reduction procedure is presented for finding such a reduced context-free grammar that is structurally equivalent to a given G . On the other hand, it is proved that there is no finite procedure for finding such a reduced context-free grammar that is weakly equivalent to a given G .

The relationship between the set of productions of a context-free grammar and the corresponding set of defining equations is first pointed out. The closure operation on a matrix of strings is defined and this concept is used to formalize the solution to a set of linear equations. A procedure is then given for rewriting a context-free grammar in Greibach normal form, where the replacements string of each production begins with a terminal symbol. An additional procedure is given for rewriting the grammar so that each replacement string both begins and ends with a terminal symbol. Neither procedure requires the evaluation of regular begins and ends with a terminal symbol. Neither procedure requires the evaluation of regular expressions over the total vocabulary of the grammar, as is required by Greibach's procedure.

This paper deals with the question of canonical types for grammar forms and grammars. A grammar (form) is called position restricted of type (m1,…,mn+ 1) if n⩾2, each m1 is a nonnegative integer, and each production is either of the type ξ0 → u, u a terminal word, or ξ0→w1ξ1w2⋯wnξnwn+1, where each ξ is a variable and each wi is a terminal word of length mi. Thus a grammar (form) is position restricted if all productions in it but the terminal ones have the same relative position of terminals and variables. The main results are as follows. Each grammar form G1 is equivalent to a grammar form G2 of any desired position-restricted type (m1,…,mn,0), with the interpretation grammars of G2 of position-restricted type (m1,…,mn,0) being sufficient to define all languages in L(G1). The above result is no longer true if the position-restricted type is such that mn+1⩾1. The second main result is that each context-free language is defined by a grammar G of any desired position-restricted type.

Each context-free grammar can be transformed to a context-free grammar in Greibach normal form, that is, a context-free grammar where each right-hand side of a prorfuction begins with a terminal symbol and the remainder of the right-hand side consists of nonterminal symbols. In this short paper we show that for a left-regular grammar G we can obtain a right-regular grammar G’ (which is by definition in Greibach normal form) which left-to-right covers G (in this case left parses of G’ can be mapped by a homomorphism on right parses of G. Moreover, it is possible to obtain a context-free grammar G��? in Greibach normal form which right covers the left-regular grammar G (in this case right parses of G��? are mapped on right parses of G).