Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Finding a language that is not LL(1)?

I've been playing around with a lot of grammars that are not LL(1) recently, and many of them can be transformed into grammars that are LL(1).

However, I have never seen an example of an unambiguous language that is not LL(1). In other words, a language for which any unambiguous grammar for the language is not LL(1)), nor do I have any idea how I would go about proving that I had found one if I accidentally stumbled across one.

Does anyone know how to prove that a particular unambiguous language is not LL(1)?

like image 252
templatetypedef Avatar asked Jul 28 '11 07:07

templatetypedef


People also ask

How do you tell if a grammar is not LL 1?

If the grammar is ambiguous (at least one sentence has more than one parse tree), then the grammar is not in LL(1).

How do you know if a language is LL 1?

Simple answer:A grammar is said to be an LL(1),if the associated LL(1) parsing table has atmost one production in each table entry. As [S,b] contains two Productions there is a confusion as to which rule to choose.So it is not LL(1).

Which may be a cause for a grammar not to be LL 1 )?

For a given grammar to be not LL(1), there may be various reasons, like the grammar may be left recursive or left factored or the LL(1) parsing table has multiple entries. As specified above the various reasons for a grammar to not be LL(1), if the grammar is not LL(1), it may or may not be ambiguous.

Are all regular languages LL 1?

Every regular language has right linear grammar and this is LL(1). Thus, LL(1) grammar generates all regular languages.


1 Answers

I was thinking about the question a while and then found this language at Wikipedia:

S -> A | B
A -> 'a' A 'b' | ε
B -> 'a' B 'b' 'b' | ε

They claim the language described by the grammar above cannot be described by LL(k) grammar. You asked about LL(1) only and this is pretty straightforward. Having first symbol only, you don't know if the sequence is 'ab' or 'aab' (or any more recursive one) and therefore you cannot choose the right rule. So the language is definitely not LL(1).

Also for every sequence generated by this grammar there is only one derivation tree. So the language is unambiguous.

The second part of your question is a little harder. It is much easier to prove the language is LL(1), than the opposite (there is no LL(1) grammar describing the language). I think you just create a grammar describing the language, then you try to make it LL(1). After discovering a conflict which cannot be resolved you somehow have to take advantage of it and create a proof.

like image 180
Binus Avatar answered Oct 16 '22 05:10

Binus