I was trying to rule out whether this was LL(1) by checking for left-recursion in the following grammar:

$\qquad A \to 0 A 1 \mid 0 1$

Which produces:

$\qquad 0 A 1 \Rightarrow 0 0 A 1 1 \Rightarrow \dots$

But I am unsure what type of recursion this is called, since it sorta stays in the middle.

If this is not left-recursive, would you agree that this is not LL(1) because non-terminal A has 0 appear twice in FIRST(A)?


What is a name for ?

There may be a name for that recursion, but then I would have forgotten it. It does not really matter. Call it central recursion or middle recursion if you will. And you can even define it simply :

A recursive rule (or non-terminal) is said to be middle recursive iff it is recursive, but neither left recursive nor right recursive.

If I have to write a paper, and cannot find the accepted name for something, and there may be none, then I make one up and give a proper definition for it so that people can read my paper.

The point is that not everything needs to have a specific name. You give names only to entities and concepts that play a specific role in the kind of work you are doing. You example seems to be just a general case of recursion, which happens to be neither left nor right.

Left recursion is important as it plays a significant role when you study left-to-right recursive descent parsers. Hence it was given a name.

Regarding your second question, I would agree. This may even happen in the absence of recursion, with a grammar generating a finite language. $\qquad A \to 0 0 \mid 0 1$
But there are other grammars for that language. This grammar is not LL(1), but the language is.


For a given production of the form $A \rightarrow \alpha_{1} \mid \alpha_{2}$, to uniquely determine if $A$ should be expanded to $\alpha_1$ or $\alpha_2$, we need $FIRST(\alpha_1) \cap FIRST(\alpha_2) = \emptyset$.

According to Compilers- Principle, Techniques and Tools by Aho, Lam et. al.

"In general, if $A \rightarrow aP_1 \mid aP_2$ are two $A$-productions, and the input begins with a nonempty string derived from $a$, we do not know whether to expand $A$ to $aP_1$ or $aP_2$. However, we may defer the decision by expanding $A$ to $aA'$. Then, after seeing the input derived from $a$, we expand $A'$ to $P_1$ or to $P_2$."

This process is called left factoring of grammar.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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