Menu
I have a grammar and I can check whether or not is is LL(1). However, is there any way to check if the language generated by the grammar is LL(1)? And what exactly is the difference between LL(1) grammars and LL(1) languages?
537
If you have no FIRST/FIRST conflicts and no FIRST/FOLLOW conflicts, your grammar is LL(1). By seeing only the first input symbol a, you cannot know whether to apply the production S -> Xb or S -> Yc, because a is in the FIRST set of both X and Y.
Essential conditions to check first are as follows: The grammar is free from left recursion. The grammar should not be ambiguous. The grammar has to be left factored in so that the grammar is deterministic grammar.
THEOREM: A grammar is LL(1) if and only if conditions (A), (B), and (C) above are satisfied for all reachable nonterminals. The reason for restricting to reachable nonterminals is that only these will appear on top of the stack! Thus strictly speaking only these nonterminals must satisfy the conditions.
Then how is one to prove that the given grammar is not in 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).
Any grammar that is LL(1) defines an LL(1) language. By definition, a language is LL(1) if there is some grammar that generates it that is LL(1), so the fact that you have an LL(1) grammar for the language automatically means that the language is LL(1).
To elaborate, a language is a set of strings and a grammar for that language is a means of describing that language. Some languages have LL(1) grammars while others do not. However, the fact that a grammar is not LL(1) does not mean that the language it describes is not. For example, consider this grammar:
A -> ab | ac
This grammar is not LL(1) because it contains a FIRST/FIRST conflict when trying to predict the production for A when seeing terminal a. However, it describes an LL(1) language, since the language is also described by the grammar
A -> aX
X -> b | c
So the language generated by these grammars (which just contains ab and ac) is indeed LL(1).
Determining whether the language described by an arbitrary grammar is LL(1) is much harder and to the best of my knowledge the only way to do it would be to either explicitly exhibit an LL(1) grammar for the language generated by the initial grammar (which is tricky) or to mathematically prove that no such grammar exists.
Hope this helps!
89
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
