Referring to this Question, where an answer is stating that all Type 3 languages are LL(1), I'd like to know if all Type 3 grammars are possibly LL(1).
If not, why is it so? Are there maybe ambiguous grammars in the set of the Type 3 grammars?
$\begingroup$
$\endgroup$
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
8
Chomsky hierarchy is primarily a hierarchy of grammars, not of languages. As stated in Wikipedia:
The Chomsky hierarchy (occasionally referred to as Chomsky-Schützenberger hierarchy) is a containment hierarchy of classes of formal grammars.
Type 3 grammars are characterized by the fact that they have to have only left linear rules (i.e., productions), or only right linear rules, plus possibly an empty rule for the initial non-terminal symbol. For any language, both forms exist.
A rule is left linear iff its right hand side (RHS) is composed of a terminal symbol, possibly preceded by a single non-terminal.
A rule is right linear iff its right hand side (RHS) is composed of a terminal symbol, possibly followed by a single non-terminal.
(There are small variants of these definitions, allowing for a terminal string of any length, instead of a single terminal)
When the language is not finite, some of the rules are necessarily recursive. But a left linear rules that is recursive is necessarily left recursive. Hence the grammar is not LL(1).
Hence some type 3 grammars, even with the strict definition above, are not LL(1).
-
$\begingroup$ It is customary to consider only the right-linear grammars as type-3, because of the "natural order" of derivations. Even then the grammars are not always LL(1), because of nondeterminism. $\endgroup$ Commented Jul 21, 2014 at 12:15
-
1$\begingroup$ This answer can be completed further: 1) not all type-3 grammars are LL(1) 2) all type-3 languages are LL(1), as they can all be described by deterministic right linear grammars, which are LL(1). $\endgroup$ Commented Jul 21, 2014 at 13:02
-
$\begingroup$ @HendrikJan I trusted Wikipedia, but you are correct. I checked the original Chomsky papers, and the hierarchy is apparently defined in the 1959 paper, not the 56 paper as asserted by Wikipedia. And indeed, he considers only right-linear grammars, unlike most authors citing him. Well, I guess it is fairer to consider both as we do not all write from left to right :-). This said, I quite agree that non-determinism is another issue. Actually, given an LL(1) grammar, there are usually plenty of ways to make it non-LL(1) without changing the language. $\endgroup$– babouCommented Jul 21, 2014 at 13:11
-
$\begingroup$ @babou (1) In my intuition the type-3 grammar should work the same direction as the LL(1) one, to get a natural match. In that case nondeterminsism seems the reason that spoils LL(1). (2) Thanks for your investigations, great you checked Chomsky. Personally, I no longer follow wikipedia here: although initially defined as a grammar hierarchy, it now seems more proper to see it as a language hierarchy with both grammars and machines to underline it is such a natural concept. $\endgroup$ Commented Jul 21, 2014 at 13:56
-
2$\begingroup$ @HendrikJan: There are so many "regular" things in mathematics and TCS, I guess it's not harmful to say "regular grammar = left- or right-linear grammar" as a shorthand. (Using left-regular is probably bad, whoops.) $\endgroup$– RaphaelCommented Jul 21, 2014 at 20:16