5.1 Implicit Stacking in RDP

If the language can be parsed by an RDP, then a simple method is available to implement many of the semantic analysis operations. The method illustrated here is further used extensively in Chapter 8 on Intermediate Code, for generating the Intermediate representation of the program. Several further examples of implicit stacking in RDP are given.

We shall use the following sub-grammar of an IF-THEN-ELSE construct:

if–stmt   : IF logic–expr THEN stmt–list FI
          | IF logic–expr THEN stmt–list1 ELSE stmt–list2 FI
          ;
stmt      : basic–stmt
          | if–stmt
          ;
stmt–list : stmt
          | stmt–list stmt
          ;

This grammar may have to be modified depending upon the type of the parser used. The above grammar implies the following source construct and corresponding implied actions:

Source code:

IF logic–expr THEN stmt–list FI (next:)

Source code:

IF logic–expr THEN stmt–list1 ELSE stmt–list2 FI (next:)

The execution of the logic expression puts a value True or False on the operand stack, where it can be tested by a Branch-if-False instruction. Note that the grammar implies possibility of nested IF statements at any reasonable depth of nesting. This will require that the labels like label1 or next be “stacked”, so that they are accessed only at the correct point in the parse tree. We shall see below how this is achieved.

As shown above, the labels are to be stacked because they are generated in a forward order, but needed in LIFO order.

Some of addresses (position of the labelled code) corresponding to these labels are not known when they are first encountered. For example, when generating the {Branch next:} action, the position value corresponding to the label next: is not known. Various “tricks” are used to deal with this situation.

The code in an RDP concerned with parsing an IF statement looks something like this:

statement(){
  if(nexttoken() == IF) if_statement();
  else basic_statement();
}
statement_list(){
 while(nexttoken() != EOF){
   statement();
 }
}
if_statement(){
  pIF(); pE(); pTHEN(); statement_list();
  if(nexttoken() == FI) pFI();
  else{
    pELSE(); statement_list(); pFI();
  } 
}

In order to provide the Intermediate code generation as a result of semantic analysis, we have to add code generation statements and local variable to the code for if_statement() as shown below.

if_statement(){
  char brlabel[10], flslabel[10];
  pIF(); pE();
  strcpy(flslabel, genlabel());    // added
  emit("BF", flslabel);            // added
  pTHEN(); statement_list();
  if(nexttoken() == FI){
    pFI();
    emit(flslabel, ":"); 
  }  else{
    pELSE();
    strcpy(brlabel, genlabel());   // added
    emit("BR", brlabel);           // added
    emit(flslabel, ":");	   // added
    statement_list(); pFI();
    emit(brlabel, ":");            // added
  } 
}

In the above code, genlabel() creates unique labels every time it is called and emit() puts its argument strings in the output stream.

This function will be called two times recursively while parsing the nested IF statement given above, and the generated labels and Branch operations will be as shown below.

We can see that proper nesting of the IF statements will take place.

Note that the stacking of the generated code (here in this example the labels) was done implicitly in the local variables of the recursive function dealing with the language construct and no separate stack was used for the purpose. Also, parameter passing is used between various semantic routines to pass information about the semantics of the code being handled. The code is generated after a particular syntactic construct is detected.