# What type of recursion is this?

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.