The grammar in Fig. $4.7$ generates declarations for a single numerical identifier; these declarations involve four different, independent properties of numbers.
- 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)$.
- 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}) $.
- Show that any grammar for part $(b)$ must have a total production length of at least $2^{n}$.
- What does part $(c)$ say about the feasibility of enforcing nonredundancy and noncontradiction among options in declarations via the syntax of the programming language?