Exercise 9      Name       ____________________   Points __/25

Document last modified: 
 

<!ELEMENT exp ( (exp, plus, exp) | (exp, times, exp) | (lparen, exp, rparen) | a | b | c )>

1. (9) For the above EBNF give the parse trees for the following XML.

   i. a + b

   <exp>                                                <exp><a/></exp>     <plus/>     <exp><b/></exp> </exp>

   <exp>              /    |      \      <exp><plus/><exp>         |                     |     <a/>                <b/>

   ii. a * b + c

   <exp>      <exp>         <exp><a/></exp>         <times/>         <exp><b/></exp>     </exp>     <plus/>     <exp><c/></exp> </exp>

   <exp>                                   /     |       \                          <exp>   <plus/> <exp>                      /        |     \             |               <exp><times/><exp>  <c/>                    |                     |                <a/>               <b/>

   iii. (a + b) * c

   <exp>     <exp>         <lparen/>         <exp>             <exp><a/></exp>             <plus/>             <exp><b/></exp>         </exp>         <rparen/>      </exp>     <times/>     <exp><c/></exp> </exp>

   <exp>                        /      |        \                 <exp><times/><exp>              /      |      \                |   <lparen/><exp> <rparen> <c/>                  /   |     \       <exp><plus/><exp>           |                      |        <a/>               <b/>

2. (6) Give the XML for the following using the definition of <exp> above:
   1. a * (b + c)

      <exp>    <exp><a/></exp>     <times/>     <exp>         <lparen/>         <exp>             <exp><b/></exp>             <plus/>             <exp><c/></exp>         </exp>         <rparen/>      </exp>  </exp>

   2. (a + b) * (b + c)

<exp>     <exp>         <lparen/>         <exp>             <exp><a/></exp>             <plus/>             <exp><b/></exp>         </exp>         <rparen/>      </exp>     <times/>     <exp>         <lparen/>         <exp>             <exp><b/></exp>             <plus/>             <exp><c/></exp>         </exp>         <rparen/>      </exp> </exp>

<!ELEMENT digit (zero | one | two | three)>
<!ELEMENT unsigned (digit+)>                                            Iterative
<!ELEMENT unsigned (digit | (unsigned, digit))>                    Recursive
<!ELEMENT signed ((plus, unsigned) | (minus, unsigned))>
<!ELEMENT plus EMPTY>
<!ELEMENT minus EMPTY>
<!ELEMENT zero EMPTY>
<!ELEMENT one EMPTY>
<!ELEMENT two EMPTY>
<!ELEMENT three EMPTY>

3. (6) Complete the above DTD of a grammar with the following rules:
    
1. <integer> as the set of all strings of <signed> or <unsigned>.

   <!ELEMENT integer (signed | unsigned)>

    

2. <decimal> as the set of all strings of <integer> followed by a ‘.’ and optionally followed by an <unsigned>.

   <!ELEMENT decimal (integer, period, unsigned?)>
   <!ELEMENT period EMPTY>

    

3. <twoorthreedigits> as the set of all strings of two or three <digit>.

   <!ELEMENT twoorthreedigits (digit, digit, digit?)>

    

4. (4) The following is XML for an <unsigned> 123:

<!DOCTYPE unsigned SYSTEM "ex9.dtd">                 Using iterative
    <unsigned>
        <digit>
            <one/>
        </digit>
        <digit>
            <two/>
        </digit>
        <digit>
            <three/>
        </digit>
    </unsigned>

<!DOCTYPE unsigned SYSTEM "ex9.dtd">                 Using Recursive
<unsigned>
    <unsigned>
        <unsigned>
            <digit><one/></digit>
        </unsigned>
        <digit><two/></digit>
     </unsigned>
     <digit><three/></digit>
</unsigned>
 

1. Give the XML for a <signed> +123.         Using Iterative

<!DOCTYPE signed SYSTEM "ex9.dtd">
<signed>
    <plus/>
    <unsigned>
        <digit>
            <one/>
        </digit>
        <digit>
            <two/>
        </digit>
        <digit>
            <three/>
        </digit>
    </unsigned>
</signed>
 

2. Give the XML for a <decimal> -12.4.        Using Iterative

<!DOCTYPE signed SYSTEM "ex9.dtd">
    <decimal>
        <integer>
            <signed>
                <minus/>
                <unsigned>
                    <digit>
                        <one/>
                    </digit>
                    <digit>
                        <two/>
                    </digit>
                </unsigned>
            </signed>
        </integer>
        <period/>
         <unsigned>
             <digit>
                <four/>
             </digit>
         </unsigned>
    </decimal>