0
$\begingroup$

In the slides' based animation given for backtracking, here (with code here, in the web-page ); have few doubts, in the code restated below, and the execution as shown in the call #5.

#include <stdio.h>
char *next;
int calls = 0;

int eat(char c) {
  calls++;
  if (*next == c) {
    next++;
    return 1;
  }
  return 0;
}
  
int e() {   
    char* save = next;    
    if(eat('(')&&e()&& 
    eat('+')&&e()&&eat(')')) 
        return 1;   
    else next = save;    
    if(eat('(')&&e()&&eat('*') 
    && e()&&eat (')'))  
        return 1;   
    else next = save;    
    if (v()) 
        return 1;   
    else 
        next = save;    
    return 0; 
}
int v() {
    char* save = next;
    calls++;

    if (eat('x')) return 1;
    else next = save;

    if (eat('y')) return 1;
    else next = save;

    return 0;
}

void main()
{
  next = "((((x*x)*x)*x)*x)";
  printf("%i\n", e());
  printf("%i\n", calls);
}

Request correction, and comments, for my analysis, and doubts, below:

  1. In the code, the two operators, i.e. '+', '*'; are of equal precedence. Though, am confused if am correct in describing the grammar for the code.

e -> (e + e) | (e * e) | v

v -> x | y

  1. For the call #5, unable to understand how the execution flow jumped to the the second if statement, though tried multiple times to figure out the same.
$\endgroup$

1 Answer 1

1
$\begingroup$

It took me a few minutes to figure out what functions $e()$ and $v()$ do but after some careful reading I got to the conclusion they implement a recursive descent parser whose language $\mathcal{L}$ is the one made of arithmetic expressions on identifiers $x$ and $y$.

Regarding your first question, I don't think operators $*$ and $+$ share the same precedence; the language accepted by the parser corresponds to arithmetic expressions having fully specified parenthesis (adding numbers to the language matched by $v()$, "$1+2*3$" is clearly not in $\mathcal{L}$, while "$(1+(2*3))$" is). To my understanding $e()$ implements the rules of regular arithmetic, that is, $*$'s precedence is greater that $+$'s. I reached this conclusion observing that missing parenthesis are not allowed and precedence is not enforced by the parser but rather by properly nested parens. Consequently, a bottom-up grammar generating this kind of precedence is $\mathcal{G}$:

  • $E \rightarrow E + T \text{ }|\text{ } T$
  • $T \rightarrow T * F \text{ }|\text{ } F$
  • $F \rightarrow (E) \text{ }|\text{ } num$

(with some adjustments you can easily get the LL1, that is top-down, version.)

Regarding your second question, the parser (via call 4) first tries to consume a sequence of characters of the shape $( \text{ } E \text{ } + \text{ } E \text{ })$ (but fails because no parenthesis is present), then (via call 5) it tries to consume $(\text{ }E \text{ }*\text{ }E\text{ })$ failing for the same reason. Eventually, it will try to consume $x$ via function $v()$ in call 6, with success.

I hope this explanation helps.

$\endgroup$
1

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.