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

The grammar in Fig. 4.7 generates declarations for a single numerical identifier; these declarations involve four different, independent properties of numbers. stmt declare id optionList optionList optionList option \ e option -» mode | scale | precision | base mode -¥ real | comple x scale -> fixed | floating precision -> single | doubl e base -> binary | decimal Figure 4.7: A grammar for multi-attribute declarations

a) Generalize the grammar of Fig. 4.7 by allowing n options Ai, for some fixed n and for i = 1,2... ,n, where Ai can be either ai or bi. Your grammar should use only 0(n) grammar symbols and have a total length of productions that is 0(n).

! b) 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 0( n x n!). You must do better: a total production length that is 0(n2 n ) .

!! c) Show that any grammar for part (b) must have a total production length of at least 2 n .

d) Wha t does part (c) say about the feasibility of enforcing nonredundancy and noncontradiction among options in declarations via the syntax of the programming language?

Fig. 4.7