Recursive Descent, Left Assoc
Posted 08-19-2023 at 05:39 PM by astrogeek
Updated 09-05-2023 at 08:07 PM by astrogeek (Made *input const)
Updated 09-05-2023 at 08: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:
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:
I hope you find it a useful example.
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.
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.
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))))
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; }
Total Comments 0