Answers/Solutions to Exercises in Chapter 5, Exercise 11

E11: Rewrite the recursive descent parser used in this chapter to display in a schematic way how the system stack "looks like" during the execution --- when a function is entered display the "new activation frame" and when the function is exited display
the "previous activation frame". Use the indentation to indicate how the stack grows (moving the indentation to the right) and how it shrinks (moving the indentation to the left). Then execute the program with the input string being "..a..". Compare your result with the diagrams shown in the book.

S11: Below is the modified program and its output.

#include <iostream.h>
extern "C" {
 #include <stdio.h>
 #include <stdlib.h>
 #include <string.h>
}
#define dot 1
#define id  2
#define error 3

#define TRACE(a) trace_enter(#a)
#define RETURN(a,b) return(trace_exit(#a,b))
char indent[300]="";
int indi=0;

int A(char*,int&);
int B(char*,int&);
int NextToken(char*,int&);
void trace_enter(char*);
int trace_exit(char*,int);

// function main --------------------------
int main() 
{
TRACE(main);
	
   int spp=0;
   char s[]="..a..";

   if (A(s,spp))
     cout << "syntax correct\n";
   else
     cout << "syntax error\n"; 
   RETURN(main,0);
}//end main

// function A ------------------------------
int A(char* s,int& spp)  
{
TRACE(A);
	
   if (!B(s,spp))
     RETURN(A,0);
   if (NextToken(s,spp) != id)
     RETURN(A,0);
   if (!B(s,spp))
     RETURN(A,0);
   RETURN(A,1);
}//end A

// function B ------------------------------
int B(char* s,int& spp)
{
TRACE(B);
	
   int spp1 = spp;

   if (NextToken(s,spp) != dot) {
     spp = spp1;
     RETURN(B,1);
   }
   if (!B(s,spp)) {
     spp = spp1;
     RETURN(B,1);
   }
   RETURN(B,1);
}//end B


// function NextToken ------------------------
int NextToken(char* s,int& spp)
{
TRACE(NextToken);
	
   if (s[spp]=='.') {
     spp++;
     RETURN(NextToken,dot);
   }else if ('a'<=s[spp] && s[spp]<='c') {
     while('a'<=s[spp] && s[spp]<='c') spp++;
     RETURN(NextToken,id);
   }else 
     RETURN(NextToken,error);
}//end NextToken



// function trace_enter -----------------------
void trace_enter(char* fce)
{
   indent[indi++]=' ';
   indent[indi]='\0';
   printf("%sentering %s\n",indent,fce);
}//end trace_enter




// function trace_exit -----------------------
int trace_exit(char* fce,int ret)
{
   printf("%sexiting %s\n",indent,fce);
   indent[--indi]='\0';
   return ret;
}//end trace_exit

Output:

 entering main
  entering A
   entering B
    entering NextToken
    exiting NextToken
    entering B
     entering NextToken
     exiting NextToken
     entering B
      entering NextToken
      exiting NextToken
     exiting B
    exiting B
   exiting B
   entering NextToken
   exiting NextToken
   entering B
    entering NextToken
    exiting NextToken
    entering B
     entering NextToken
     exiting NextToken
     entering B
      entering NextToken
      exiting NextToken
     exiting B
    exiting B
   exiting B
  exiting A
 exiting main
syntax correct

Back to Answers/Solutions Index                          Back to Answers/Solutions for Chapter 5 Index