Cheap and Secure Web Hosting Provider : See Now

[Solved]: What type of recursion is this?

, , No Comments
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 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.

Best Answer from StackOverflow

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

3.2K people like this

 Download Related Notes/Documents

0 comments:

Post a Comment

Let us know your responses and feedback