Doubts in backtracking function animation, for call sequence flow.

ajiten · 07-28-2023, 08:58 AM

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.

Code:

#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

2. 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.

[1]: https://www.cs.york.ac.uk/fp/lsa/lectures/backtrack.pdf
[2]: https://www.cs.york.ac.uk/fp/lsa/lectures/backtrack.c
[3]: https://www.cs.york.ac.uk/fp/lsa/

NevemTeve · 07-28-2023, 11:50 AM

ad1

Code:

e -> '(' e '+' e ')' | '(' e '*' e ')' | v
v -> 'x' | 'y'

ad2
Guess you mean how the stepping-back happens. Well the `next= save` statement undoes the effect of the previous statements.

ajiten · 07-28-2023, 12:35 PM

Quote:

Originally Posted by NevemTeve

Code:

e -> '(' e '+' e ')' | '(' e '*' e ')' | v
v -> 'x' | 'y'

Guess you mean how the stepping-back happens. Well the `next= save` statement undoes the effect of the previous statements.

Thanks a lot, but the input given in main() is: next = "((((x*x)*x)*x)*x)"
So, the grammar should be:

Code:

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

But, the rules are supporting your grammar, as in the function : e()

Code:

if (eat('(') && e() && eat('+') && e() && eat(')')) return 1;
  else next = save;

  if (eat('(') && e() && eat('*') && e() && eat(')')) return 1;
  else next = save;

and the function : v()

Code:

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

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

But, why the input then is not instead:

Code:

 next = "'(''(''(''(''x''*''x'')''*''x'')''*''x'')''*''x'')'"

Seems that for terminal symbols : (, ), +, *, the input is inside quotes, as character input; just like the input is inside double quotes, as it is a string of characters.

Edit: Have verified at : https://stackoverflow.com/a/3683613, still want to keep my response, as a good reminder.

================================

Q.2. So, by stepping-back, the else branch is "implicitly' taken; that executes the (retracting/backtracking) `next= save` statement to undo the effect of the previous statement (i.e., in the earlier if statement).
It would have been better had the slides shown the else branch's backtracking action explicitly, though now it is obvious.

NevemTeve · 07-28-2023, 12:58 PM

Sorry for the misunderstanding, I'll use bold/blue for character-literals:

Code:

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

ajiten · 07-28-2023, 01:23 PM

Quote:

Originally Posted by NevemTeve

Sorry for the misunderstanding, I'll use bold/blue for character-literals:

Code:

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

Please tell why you removed single quotes, from enclosing all terminal symbols (i.e., the character-literals); as have understood that in C, they are enclosed by the same; just like a string is enclosed by double quotes.

NevemTeve · 07-28-2023, 02:04 PM

Ideally, you use different notations for meta-characters and literal characters. Maybe an example helps.

without distinction you couldn't guess which characters are literals:

Code:

S -> (A(B|C)D)

with distinction:

Code:

S -> ( A '(' B | C ')' D )

or

Code:

S -> (A(B|C)D)

ajiten · 07-28-2023, 02:16 PM

Quote:

Originally Posted by NevemTeve

Ideally, you use different notations for meta-characters and literal characters. Maybe an example helps.

without distinction you couldn't guess which characters are literals:

Code:

S -> (A(B|C)D)

with distinction:

Code:

S -> ( A '(' B | C ')' D )

or

Code:

S -> (A(B|C)D)

But, here in the grammar, no meta-characters are there; none. The confusion can arise only when same symbol is used for both: meta-character, character-literal.
Might be you mean to say that in the grammar, there is no need to enclose character literal, with single quotes. Then, if am correct, am clear.

NevemTeve · 07-28-2023, 02:22 PM

> But, here in the grammar, no meta-characters are there; none.

How about the |vertical bar that means 'or'?

Code:

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