edited by
408 views
0 votes
0 votes

The grammar in Fig. $4.7$ generates declarations for a single numerical identifier; these declarations involve four different, independent properties of numbers.

  1. Generalize the grammar of Fig. $4.7$ by allowing $n$ options $A_{i}$, for some fixed $n$ and for $i = 1,2\cdot\cdot\cdot, n$, where $A_{i}$ can be either $a_{i}$ or $b_{i}$. Your grammar should use only $O(n)$ grammar symbols and have a total length of productions that is $O(n)$. 
  2. The grammar of Fig. $4.7$ and its generalization in part $(a)$ allow declarations that are contradictory and/or redundant, such as: declare foo real fixed real floating. We could insist that the syntax of the language forbid such declarations; that is, every declaration generated by the grammar has exactly one value for each of the $n$ options. If we do, then for any fixed $n$ there is only a  finite number of legal declarations. The language of legal declarations thus has a grammar (and also a regular expression), as any finite language does. The obvious grammar, in which the start symbol has a production for every legal declaration has $n!$ productions and a total production length of $O(n \times n!)$. You must do better: a total production length that is  $(n2^{n}) $.
  3. Show that any grammar for part $(b)$ must have a total production length of at least $2^{n}$.
  4. What does part $(c)$ say about the feasibility of enforcing nonredundancy and noncontradiction among options in declarations via the syntax of the programming language? 
edited by

Please log in or register to answer this question.

Related questions

0 votes
0 votes
0 answers
2
admin asked Aug 17, 2019
192 views
Extend the idea of Question $4.2.4$ to allow any regular expression of grammar symbols in the body of a production. Show that this extension does not allow grammars to de...