**Problem Detail:**

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)?

###### Asked By : Colton

#### Answered By : babou

**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 recursiveiff 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.

###### Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/21753

**3.2K people like this**

## 0 comments:

## Post a Comment

Let us know your responses and feedback