6.7. Rules of graph translation.   

(1) Optimize graph: 


      <exp>::=  <simple exp>

              | <simple exp><relational opr><simp exp>

 
graph_symbol7a.eps
(2) Change each graph into procedure declaration to process that graph/ symbol.

procedure parse_expression(.....);

(3) Sequence of elements  

graph_symbol5.eps 

            begin

                  T(1);T(2);T(3);...

            end;

Perform sequence of statements that handle each element = T(i).

i.e.  process 1,  then 2  etc.

The begin-end are needed because the sequence forms a block.

(4) Choice of elements  

graph_symbol4.eps 

  This can be translated into

           case sym of

                L1:T(1);

                L2:T(2);

                      :

                Ln:T(n)

           end;

where the next symbol in the sentence is compared against Li = first symbol(s) of construct i. In fact, there may be more than one first symbol for i since i may be a choice.
Note: First(i) = First(j) i != j
Therefore Rule 1 holds.
Why is the case not a good construct for this graph structure?

(5) Iteration of elements  

graph_symbol6.eps 

  Zero or more occurences


       while sym in L do T();

                        L = set of first();

Example:  

graph_symbol6b.eps 

      input(ch)

      n  0;

      while ch in ['0'..'9'] do

      begin

            n  n*10 + ord(ch)- ord('0')

            input(ch)

      end

Alternatively (and fairly common)  

graph_symbol6a.eps 

      repeat

              T(i);

      until not sym in L;

                  = one or more occurrences


Example:

         repeat

              input(ch);

              n  n*10 + ord(ch) - ord('0');

         until not ch in ['0'..'9'];

(6) Non-terminals  

graph_symbol1.eps 

A non-terminal symbol == another graph can be translated into a call

to the procedure which parses that symbol.

      sentence::=<subject><predicate>


      procedure sentence;

      begin

            subject(   );

            predicate(   );

      end

(7) Terminals  

graph_symbol2.eps 

Terminal symbols:  where we apply base level rules.

For correct grammar, the next symbol must be 'x'.


 Therefore

      if sym = x then

           getsym /* symbol ok - get next symbol */

      else

           /*  error has occurred in input sequence

              since it is not what it should be */

Error recovery is quite an art in most compiler writing and many "spurious errors" can be generated as the compiler tries to get back into step with the syntax.

Pascal Example: 


           var i,for:integer;

                    ^

                    identifier expected

                    ^ ':' expected

                   ^ ';' expected

                begin

                        for i:=1 to 10 do

                           write( , )

                end.

                  ^ Statement must end with a ';','end'

                    'else' or 'until'.


                UNEXPECTED END OF FILE.