2. The production is of the form Л -> £] \ E-. For this union operator, replace this production by the pair of productions:

AEi A E-2

Again, these productions may or may not be legal CFG productions, but their bodies are shorter than the body of the original. We may therefore apply the rules recursively and eventually convert these new productions to CFG form.

3. The production is of the form A Introduce a new variable В that appears nowhere else, and replace this production by;

ABA A e BEj

4. The production is of the form A -) {Ei)~. Introduce a new variable В that appears nowhere else, and replace this production by;

A-BA

5. The production is of the form A -> (Ei)?. Replace this production by:

A -> F. A Ei

Example 5.24: Let us consider how to convert the DTD rule

<!ELEMENT PC (MODEL, PRICE, PROCESSOR, RAM, DISK+)>

to legal CFG productions. First, we can view the body of this rule as the concatenation of two expressions, the first of which is HODEL, PRICE, PROCESSOR, RAM and the second of which is DISK+. If we create rariables for these two subexpressions, say A and B, respectively, then we can use the productions:

Pc- AB

A Model Price Processor Ram В Disk+

Only the last of these is not in legal form. We introduce another variable С and the productions:

BCB\C С Disk

In this special case, because the expression that A derive.s is just a concatenation of variables, and Disk is a single variable, we actually have no need for the variables .4 or C. We could use the following productions instead:

Pc -> Model Price Processor Ram В В -> Disk В I Disk

□

5.3.5 Exercises for Section 5.3

Exercise 5.3.1: Prove that if a string of parentheses is balanced, in the sense given in Example 5.19. then it is generated by the grammar В -> BB \ (B) \ (. Hint: Perform an induction on the length of the string.

* Exercise 5.3.2 : Consider the set of all strings of balanced parentheses of two types, round and square. An example of where these strings come from is as follows. If wc take expressions in C, which use round parentheses for grouping and for argurncnits of function calls, and use square brackets for array indexes, and drop out cwerytliing but the parentheses, we get all strings of balanced parentheses of these two types. For example,

f(a[i]*(b[i] [j],c[g(x)]),d[i])

becomes the balanced-parenthesis string ([](□[][()])[]). Design a grammar for all mid only the strings of round and square parentheses that are balanced.

! Exercise 5.3.3: In Section 5.3.1, wc considered the grammar

S ( \ SS \ iS \ iSeS

and claimed that we could test for membership in its language L by repeatedly doing the following, starting with a string w. The string w changes during repetitions.

1. If the current string begins with e, fail; w is not in L.

2. If the string currently has no es {it may have is), succeed; w is in L.

3. Otherwise, delete the first e and the i immediately to its left. Then repeat these three steps on the new string.

Prove that this process correctly identifies the strings in L.

Exercise 5.3.4: Add the following forms to the HTML grammar of Fig. 5.13:

ODOCTYPE CourseSpecs [

<!ELEMENT COURSES CCOXffiSE+)>

<!ELEMENT COURSE (CNAME, PROF, STUDENT*, TA?)> <!ELEMENT CNAHE (#PCDATA)> <!ELEMENT PROF (#PCDATA)> <!ELEMENT STUDENT C#PCDATA)> <!ELEMENT ТА (#PCDATA)> ]>

Figure 5,16: .A DTD for courses Exercise 5.3.5: Convert the DTD of Fig, 5,16 to a context-free grannnar,

5.4 Ambiguity in Grammars and Languages

As we have seen, applications of CFGs often rely on the grammar to provide the structure of files. For instance, we saw in Section 5.3 how grannnars can be used to put structure on programs and documents. The tacit assumption was that a grammar uniquely determines a structure for each string in its language. However, we shall see that not every grammar does provide unique structures.

When a grammar fails to provide unique structures, it is sometimes possible to redesign the grammar to make the structure unique for each string in the language. Unfortunately, sometimes we cannot do so. That is, there are some CFLs that are inherently ambiguous ; every grammar for the language puts more than one structure on some strings in the language,

5.4.1 Ambiguous Grammars

Let us return to our running example: the expression grammar of Fig. 5.2, This grammar lets us generate expressions with any sequence of * and -- operators, and the productions E E-\- E \ E*E allow us to generate these exjjressions in any order we choose.

* a) A list item must be ended by a closing tag </LI>.

b) An element can be an unordered list, as well as an ordered list. Unordered lists are surrounded by the tag <UL> and its closing </UL>.

! c) An element can be a table. Tables arc surrounded by <TABLE> and its closer </TABLE>. Inside these tags art; one or more rows, each of which is surrounded by <TR> and </TR>. The first row is the header, with one or more fields, each introduced by the <TH> tag (well assume these are not closed, although they should be). Subsequent rows have their fields introduced by the <TD> tag.