Doubts in backtracking function animation, for call sequence flow.
by ajiten from LinuxQuestions.org on (#6DBW3)
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/
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/