Recursive Descent, Left Assoc

Posted 08-19-2023 at 04:39 PM by astrogeek
Updated 09-05-2023 at 07:07 PM by astrogeek (Made *input const)

Discussion here and here in the Programming forum prompted me to write a few variations of an incomplete example given in the book:

Compiler Design In C by Allen I. Holub

The example suggests a simple way to obtain a left-associative parse of a list from a recursive descent parser which implements a simple right-recursive grammar.

The example is found on pages 176-177 of the book, and is incomplete, intended to illustrate the idea, not intended as working code.

From the book, pages 176-177:

Quote:

Recursive-descent parsers can cheat and generate code as the tree is built from the top down. This cheating can give surprising results, because a list can be processed from left to right, even though the grammar would indicate otherwise...

Since you can't have left recursion in a recursive-descent parser, this technique is often useful, but it can also cause maintenance problems, because some code is generated as the tree is created, but other code must be generated as the tree is traversed. You can't apply this technique in processing expressions, for example.

As discussed in the original thread and others, it is important to not try to extend this method as a general solution, it has very specific and limited application.

One question asked was how to make the associativity visible for both the left and right cases, which is done by the example I have implemented below.

For the left-associative case, code generation must take place as the parse tree is built (here just output of tokens from the input stream) and the left-associativity is implicit in the order input tokens are parsed, left to right.

The right-associative case, the normal case for this grammar, requires that code generation takes place during depth-first, left-to-right traversal of the completed parse tree. The example below accomplishes this by noting that reversal of the parse ordering of tokens is equivalent to the desired tree traversal, so we parenthesize each recursion during the parse and write it out in reverse order once the parse is complete.

The input string is compiled in for this example, but you may easily modify the code to accept it as a runtime argument.

Error handling is limited to array bounds and NULL pointer checks, all errors abort.

Paste the below code into a file, parse.c for example, and compile with gcc -Wall parse.c -o parse. As posted the following output is produced:

Code:

$ ./parse
Processing left-assoc: ABCDE ...
ABCDE
Processing right-assoc: ABCDE ...
A(B(C(D(E))))

I hope you find it a useful example.

Code:

/*
Simple recursive descent parser
Grammar:

   stmt_list -> stmt stmt_list
              | stmt

   stmt -> [A-Z]

Implements top-down, right-recursive, left-derivation
with alternate left-associative equivalent parse suggested by
Compiler Design In C, Allen I. Holub, pg 176-177

Output is traversal of parse tree, parenthesized associativity for right case,
associativity implicit in parse ordering for left-assoc case

astrogeek - LinuxQuestions.org - Aug 2023
*/

#include <stdlib.h>
#include <stdio.h>
#include <string.h>

#define MAXPARSE 64

char * const input = "ABCDE"; //String to parse
char *inptr=input;
char parse[MAXPARSE];
char *parseptr=parse;

void pushparse(char c)
{
   if((parseptr-parse)>=(MAXPARSE - 1))
   {
      fprintf(stderr, "Parse string too long\n");
      abort();
   }
   *(parseptr++)=c;
}

void process_stmt(char *stmt)
{
   if(!stmt)
   {
      fprintf(stderr, "Empty input string\n");
      abort();
   }
   pushparse(*stmt);
}

char *stmt()
{
   return *inptr ? inptr++ : NULL;
}

void stmt_list_l()
{//Implicit left-associativity
   process_stmt(stmt());
   if(*inptr)
   {
      stmt_list_l();
   }
}

void stmt_list_r()
{//Parenthesized right associativity, traversal order
   char *remember = stmt();
   if(*inptr)
   {
      pushparse(')');
      stmt_list_r();
      pushparse('(');
   }
   process_stmt(remember);
}

void show_parse(int dir)
{
   if(dir) //right - reverse parse order == tree traversal
      for(char *rptr = parseptr - 1; rptr>=parse; rptr--)
         putchar(*rptr);
   else //left-assoc
      printf("%s", parse);
   putchar('\n');
}

void reset_parse()
{
   parseptr=parse;
   inptr=input;
   for(char *pptr = parse + MAXPARSE - 1; pptr>=parse; pptr--)
      *pptr='\0';
}

int main(int argc, char **argv)
{
   printf("Processing left-assoc: %s ...\n", input);
   stmt_list_l();
   show_parse(0);

   reset_parse();
   printf("Processing right-assoc: %s ...\n", input);
   stmt_list_r();
   show_parse(1);
   return 0;
}

Recursive Descent, Left Assoc

Comments