First, $S_3$ is unreachable. But even if you include it, its production rule messes up with the order of $a$'s and $b$'s.
Second, once the production has reached $S_1$, it can't escape $S_1$, so this would allow only strings where $i=j$. Also, the production rule from $S_2$ can be used only once because it sends you directly back to $S_1$. And the same happens with $S_3.$ These rules are more restrictive than the property that you want $(|i-j|\bmod 2 = 0)$. For example, they don't generate the string $a^6b^2$.
Of course, it still remains to take into account character $c$.
You have the right idea, but you’ve lost the relationship between the part to the left of the $\$$ and the part to the right of it: you cannot express it in terms of Kleene stars. For instance, when you apply the production $T\to WTba$ $n$ times, you get the same number of $W$s as you do $ba$s, so you don’t get $W^*T(ba)^*$.
First, it’s clear that the language produced by $W$ is $abb^*$: the only possible derivations starting with $W$ have the form
$$W\Rightarrow^nWb^n\Rightarrow abb^n$$
for $n\ge 0$. Now let’s look at a derivation that starts by using the production $S\to WTba$. Since we know what $W$ does, we should concentrate on $T$: we can apply the production $T\to WTba$ $n$ times for any $n\ge 0$, but eventually we must apply $T\to\$$ in order to get rid of the $T$. Thus, we get derivations of the form
$$S\Rightarrow WTba\Rightarrow^n WW^nT(ba)^nba\Rightarrow WW^n\$(ba)^nba$$
for each $n\ge 0$. This will evidently generate the language described by the expression
$$(abb^*)^n\$(ba)^n\,,\tag{1}$$
where $n$ can be any positive integer.
The other half of the language can be analyzed similarly. $V$ generates everything of the form $baa^*$, so we end up with everything of the form
$$(ab)^n\$(baa^*)^n\tag{2}$$
for $n\ge 1$. Let $L_1$ be the language described by $(1)$ and $L_2$ the language described by $(2)$, so that we want the language $L=L_1\cup L_2$. $L$ can be described in just this way, but the description can perhaps be made a little nicer if we notice that $L_2$ can be obtained from $L_1$ (and vice versa) in a fairly simple way. Let
$$f:\{a,b\}\to\{a,b\}:x\mapsto\begin{cases}
a,&\text{if }x=b\\
b,&\text{if }x=a\,,
\end{cases}$$
and let $\hat f$ be the natural extension of $f$ to $\{a,b\}^*$. (E.g., $\hat f:(abbbab)=baaaba$.) Then
$$L_2=\{\hat f(v)\$\hat f(u):u\$v\in L_1\}\,,$$
and
$$L_1=\{\hat f(v)\$\hat f(u):u\$v\in L_2\}\,.$$
Thus, $L$ can be described simply in terms of $(1)$ and $\hat f$.
Best Answer
A "left-recursive" grammar means that the parser can get into a loop in the parsing rules without making any progress consuming the input. Imagine that each production is a subroutine that might eat some tokens or call some other subroutines. For example, consider this production:
This means that the
exprparser will first call thenumberparser (which might consume some tokens), then try to eat a+token (and fail if the next token is not of that type) and then call thenumberparser again to consume more tokens. If that is all successful, theexprparser will yield success.Now consider this left-recursive production:
The first thing the
exprparser will do is to call itself recursively, putting itself into an unproductive infinite loop.In contrast, consider this production, which is not left-recursive:
The first thing the parser will do is try to consume an open parenthesis token, and it will call itself recursively only if that is successful. It can never get into an infinite loop doing this because there are only so many parentheses and it has to eat one each time before it can recurse; eventually it must run out of parentheses and then the recursion will stop. Your
Expr = [0-9]+ / '(' Expr ')'example is similarly safe.Here is a portion of the left-recursive grammar you showed:
If the next token is not
[0-9]+, then theexprparser will callsum, which will immediately callexpragain, and the parser will be in an infinite loop.Usually you can rewrite rules like
sumin a non-left-recursive form. In this case it will look something like this:This is not left-recursive because the
more_termsparser must consume a*or a+token before it can call itself recursively; it is impossible for the parser to get into an infinite loop by doing this. Similarly theexprparser callsterm, buttermwill not call back toexprwithout consuming a parenthesis.In general the transformation says to turn a left-recursive grammar like this:
into a non-left-recursive one like this:
I don't know if there are any good online resources (I suppose there must be) but if you like Perl, chapter 8 of Higher-Order Perl is available online and discusses precisely this point.
Also, I hope it is not insulting to suggest that you read the Wikipedia article about left recursion, and perhaps the article about recursive descent parsing, which is the name for the technique your parser generator is trying to use.