Change of associativity for a given right-recursive grammar

Question

In section 3.7.1, of the book titled: Compiler design in C, by Allen I. Holub (made available freely online, by the author here, & the page #19 of errata, here), have on page #176, the mention of grammar, for a right-recursive list:

stmt_list -> stmt stmt_list | stmt
stmt -> A | B| C

while on the previous page, the left recursive version is given:

stmt_list -> stmt_list stmt| stmt
stmt -> A | B| C

(But, am concerned here with the right-recursive version.)

The figure 3.4, on page #176, shows the corresponding parse tree for a right-recursive list(grammar).

On page #177, there is code listing 3.1 for: Left Associativity with a Right-Recursive Grammar; given below:

Code listing 3.1

1 stmt_list() 
2 { 
3  /* Code is generated as you create the tree, before the subtree is 
4  * processed. 
5  */
6 
7   remember= stmt(); 
8 
9   process_stmt(remember); 
10 
11  if(not_at_eoi())
12       stmt_list(); 
13  }
14 
15  stmt() 
16  { 
17       return(read()); 
18  }

Want to adapt the above grammar for practical usage, so as to see it's ramifications.

Hence, modify the above to handle arithmetic expressions, with two precedence classes of operators, i.e. addop, mulop; with addop having two operators: {+,-}; & mulop having having two operators {*,/}. The precedence of mulop operators > precedence of addop operators. Also, in each precedence class, associativity, can be either left-to-right, or right-to-left; as the implementation in code. As am considering, the right-recursive grammar, as in the book; so have:

expr -> term + expr | term - expr | term
term -> factor * term | factor / term | factor
factor -> digit factor | digit
digit -> 0|1|2|...|9

The corresponding right-recursive grammar, now has two possible implementations:

1. left-to-right associativity of the operators, in the same precedence class, shown below in First.
2. right-to-left associativity of the operators, in the same precedence class, shown below in Second.

Code listing: First

1 expr() 
2 { 
3     remember= term();
4     process_stmt(remember);
5     if(not_at_eoi())  expr(); 
6 }
7 term() 
8 {
9     remember= factor();
10    process_stmt(remember); 
11    if(not_at_eoi()) term();
12 }
13  
14 factor()
15 { 
16    remember= digit();
17    process_stmt(remember);
18    if(not_at_eoi()) factor();
19 }
20 digit()
21 {
22    return read();
23 }

So, by the code First, for the below arithmetic expression:

200+300+400-50*10/5*2

the parse tree would have the sequence of operators, of the same precedence class, processed by left-to-right associativity, as shown by the order imposed by the enclosing parenthesis:

((200+300)+400)-(((50*10)/5)*2))
=> 900 - ((100)*2)
=> 700

But, in the next listing (3.2), the author by the below code states to achieve, right-to-left associativity, in the right-recursive grammar.

After the below listing, will state code: Second, that will give for my arithmetic expression handling grammar, with two precedence classes of operators (addop, mulop); the Right-to-left associativity of operators, in the same precedence class.

Code listing (3.2)

1 stmt_list() 
2 { 
3  /* Code is generated as you create the tree, before the subtree is 
4  * processed. 
5  */
6 
7   remember= stmt(); 
8 
9   if(not_at_eoi())  
10          stmt_list();
11
12  process statement( remember); 
13  }
14 
15  stmt () 
16  { 
17       return( read() ); 
18  }

Code listing: Second

1 expr() 
2 { 
3     remember= term();
4     if(not_at_eoi())  expr();
5     process_stmt(remember);
6 }
7 term() 
8 {
9     remember= factor();
10    if(not_at_eoi()) term(); 
11    process_stmt(remember);
12 }
13 factor()
14 { 
15    remember= digit();
16    if(not_at_eoi()) factor();
17    process_stmt(remember);
18 }
19 digit()
20 {
21    return read();
22 }

So, now (as per the book) the given arithmetic expression:

200+300+400-50*10/5*2

would have the parse tree, with Right-to-left associativity. Hence, would have the sequence of operators processed as shown by the order imposed by the enclosing parenthesis:

((200+(300+(400-((50*(10/(5*2)))))
=> ((200+(300+(400-((50)))
=> 850

Have main issue with being unable to see how the change of associativity occurs with change of position, of the line:

process_stmt(remember);

, wrt the recursive call.

---

Also, as an off-topic, want to state that: as the gcc compiler follows for the given two (precedence) classes of operators, & inside the two precedence classes having left-to-right associativity, so get the expected answer, on compilation of a program for the above arithmetic expression as:

700

Answer 1

It took me quite a while to figure what the author of the book was pointing out and specifically what you are asking for, but I think I eventually managed to get it.

The author stated that lists are associative, while intuitively this is correct I don't think this is necessarilly a useful thing to know; especially at this stage of learning. I think an handy way to reason about associativity in this context is to simply focus on what is processed first. In general, left associativity implies processing elements on the left of something (generally an operator) before you process the rest. Conversely, right associativty implies processing right elements and than switch back to left elements, finishing the computation.

A simple example could be following: $1+2+3$ corresponds to $(1+2)+3$; $+$ is left associative because elements on its left are processed (summed) first. Conversely, $1^{2^3}$ (that is 1^2^3) is right associative and involves the computation of right elements w.r.t. the ^ symbol first, backtracking to left elements only after.

To the best of my knoledge other books like the Red Dragon Book (by Alfred Aho et al.) and Modern Compiler Design in (C|Java|ML) (by Andrew Appel) postpone this discussion after having tackled lists and covert it only after the reader is acquainted with bottom-up parsing.

The point of switching from a right-recursive to a left-recursive grammar, in bottom-up parsing is gaining efficiency and making the parser faster: this is due to the fact reductions will occur in the order that keeps the stack as empty as possible.

In the context of top-down parsing, like in your case, you need to hack the parser, forcing it to analyze the input in the proper way, forcing the processing of some branches before others are tackled. The author acknowledges this is a maintainance problem (pg. 177, bottom) and in my eyes this is a case of premature optimization.

If you have read the chapter covering compiler-compilers you should know that once the grammar has been designed the compiler-compiler (let it be top-down or bottom-up) will generate the code for matching the language you defined. In that case, are you going to hack the output parser for enforcing the proper processing order? What I am suggesting is the following: do not focus on this topic too much because (as the author mentions) in chapter 4 he/she will show a way for getting rid of recursion and provide a grammar that matches the language. I think the take-away is: changing from left to right recursion you can tell which elements are processed first, and that could be a handy trick for forcing some computation order.