 |
CS 3723 Programming Languages |
Debug Runs of R-D Parsers | |
Debug Runs of R-D Parsers for Arithmetic Expressions (C and Java): Here we are adding debug code (shown in red below) to the parser code. This extra debug code shows the course of the parse, that is, the particular functions that are called. The code below also shows the level of recursive nesting of each function that is called. For each function, there is a call to a function enter at the beginning of the function, with parameter the name of the function. Similarly each function has a call to leave at the end of the function. Both functions enter and leave use a global counter level to keep track of the level of recursive nesting of each parser function. The counter is incremented by enter and decremented by leave. The functions also print blanks and vertical bars, so that we get a printout showing the course of execution of the parser. Along an unbroken vertical line with a single '+' at the top and bottom, the program is inside a given activation of the function named at the top and bottom. During that activation, the program calls and returns from other functions. It doesn't come up in this example, but in standard C, enter would have to come after declarations and there would need to be a leave before each return point. Both these parsers produce exactly the same output for the same input, so we list the output at the end only for C. The extra debug code is given in red boldface below. If you use this debug code, you might want to use a simpler version that you can get by deleting the spaces function, deleting the two calls to spaces, and deleting the global variable level.
| Parser in C, with debug code | Parser in Java, with debug code |
|---|---|
#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>
char next;
void E(void);
void T(void);
void S(void);
void F(void);
void error(int);
void scan(void);
void enter(char);
void leave(char);
void spaces(int);
int level = 0;
void main(void) {
scan();
E();
if (next != '$') error(1);
else printf("Success\n");
}
void E(void) {
enter('E');
T();
while (next == '+' || next == '-') {
scan();
T();
}
leave('E');
}
void T(void) {
enter('T');
S();
while (next == '*' || next == '/') {
scan();
S();
}
leave('T');
}
void S(void) {
enter('S');
F();
if (next == '^') {
scan();
S();
}
leave('S');
}
void F(void) {
enter('F');
if (isalpha(next)) {
scan();
}
else if (next == '(') {
scan();
E();
if (next == ')') scan();
else error(2);
}
else {
error(3);
}
leave('F');
}
void scan(void) {
while (isspace(next = getchar()))
;
}
void error(int n) {
printf("\n*** ERROR: %i\n", n);
exit(1);
}
void enter(char name) {
spaces(level++);
printf("+-%c: Enter, \t", name);
printf("Next == %c\n", next);
}
void leave(char name) {
{
spaces(--level);
printf("+-%c: Leave, \t", name);
printf("Next == %c\n", next);
}
void spaces(int local_level) {
while (local_level-- > 0)
printf("| ");
}
| /* Arith0.java: debug parser
* grammar:
* P ---> E '$'
* E ---> T {('+'|'-') T}
* T ---> S {('*'|'/') S}
* S ---> F '^' S | F
* F ---> char | '(' E ')'
*/
class Arith0 {
private int level = 0;
private GetChar getChar = new GetChar();
private char next;
private void P() {
scan();
E();
if (next != '$') error(1);
else System.out.println("Success");
}
private void E() {
enter('E');
T();
while (next == '+' || next == '-') {
scan();
T();
}
leave('E');
}
private void T() {
enter('T');
S();
while (next == '*' || next == '/') {
scan();
S();
}
leave('T');
}
private void S() {
enter('S');
F();
if (next == '^') {
scan();
S();
}
leave('S');
}
private void F() {
enter('F');
if (Character.isLetter(next)) {
scan();
}
else if (next == '(') {
scan();
E();
if (next == ')') scan();
else error(2);
}
else {
error(3);
}
leave('F');
}
private void scan() {
while (Character.isWhitespace(next =
getChar.getNextChar()))
;
}
private void error(int n) {
System.out.println("*** ERROR: " + n);
System.exit(1);
}
private void enter(char name) {
spaces(level++);
System.out.print("+-" + name +
": Enter, \t");
System.out.println("Next == " + next);
}
private void leave(char name) {
spaces(--level);
System.out.print("+-" + name +
": Leave, \t");
System.out.println("Next == " + next);
}
private void spaces(int local_level) {
while (local_level-- > 0)
System.out.print("| ");
}
public static void main(String[] args) {
Arith0 arith0 = new Arith0();
arith0.P();
}
}
|
| Common Output (C output shown, Java output is identical) | |
% arith0 a + b + c $ +-E: Enter, Next == a | +-T: Enter, Next == a | | +-S: Enter, Next == a | | | +-F: Enter, Next == a | | | +-F: Leave, Next == + | | +-S: Leave, Next == + | +-T: Leave, Next == + | +-T: Enter, Next == b | | +-S: Enter, Next == b | | | +-F: Enter, Next == b | | | +-F: Leave, Next == + | | +-S: Leave, Next == + | +-T: Leave, Next == + | +-T: Enter, Next == c | | +-S: Enter, Next == c | | | +-F: Enter, Next == c | | | +-F: Leave, Next == $ | | +-S: Leave, Next == $ | +-T: Leave, Next == $ +-E: Leave, Next == $ Success |
% arith0 ( a * b $ +-E: Enter, Next == ( | +-T: Enter, Next == ( | | +-S: Enter, Next == ( | | | +-F: Enter, Next == ( | | | | +-E: Enter, Next == a | | | | | +-T: Enter, Next == a | | | | | | +-S: Enter, Next == a | | | | | | | +-F: Enter, Next == a | | | | | | | +-F: Leave, Next == * | | | | | | +-S: Leave, Next == * | | | | | | +-S: Enter, Next == b | | | | | | | +-F: Enter, Next == b | | | | | | | +-F: Leave, Next == $ | | | | | | +-S: Leave, Next == $ | | | | | +-T: Leave, Next == $ | | | | +-E: Leave, Next == $ *** ERROR: 2 |
Revision date: 2014-01-22. (Please use ISO 8601, the International Standard.)