OOC:en:3.3 The Recognizer

来自 ChinaUnix Wiki

At the top level expressions are recognized by the function sum() which internally calls on scan() and returns a representation that can be manipulated by process() and reclaimed by delete(). If we do not use yacc we recognize expressions by the method of recursive descent where grammatical rules are translated into equivalent C functions. For example: a sum is a product, followed by zero or more groups, each consisting of an addition operator and another product. A grammatical rule like

   sum : product { +|— product }...

is translated into a C function like

   void sum (void) 
   { 
       product(); 
       for (;;) 
       { switch (token) { 
         case ’+’: 
         case ’—’: 
           scan(0), product(); continue; 
         } 
         return; 
       } 
   }

There is a C function for each grammatical rule so that rules can call each other. Alternatives are translated into switch or if statements, iterations in the grammar produce loops in C. The only problem is that we must avoid infinite recursion.

token always contains the next input symbol. If we recognize it, we must call scan(0) to advance in the input and store a new symbol in token.