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