# parsing left linear CF grammars

In Introduction to Formal Languages by György E. Révész a polynomial time algorithm that can convert a left linear grammar to a right linear one is presented.

Trying to understand when it is useful I read that left linear grammars are generally harder to parse than right linear grammars.

Is this statement true?

I'm asking because I would say that there is no difference between recognizing the two in terms of hardness, but I found arguments about a difference between them.

In particular in these slides on page 8, the author argues that "left linear grammar are evil" and provides the following example:

Grammar

A → Babc

B → Cb | D

...

with $w = abbabc$.

The motivation seems to be that after checking for abbabc it is necessary to check the first part abbabc if can be derived from B that has 2 rules associated: Cb and D, while it could be done easily with a right linear grammar.

• Or to put it another way, the author (whose credentials are not readily apparent) finds it hard to understand the Thompson construction and therefore insists that grammars which use it must be eliminated. Personally, I admit that I do not understand how the standard library implementation of exp manages to converge accurately to the correct value, but that does not mean that I'm going to avoid exponentiating anything other than integer powers.
– rici
Mar 22, 2017 at 22:54
• I don't understand the sense of your sarcasm with the "flat world" example. Since I did not find any other source, I found legit to ask people more expert than me about this doubt that came in my mind. If you don't want to contribute, just don't.
– abc
Mar 22, 2017 at 22:57
• @newbie: Sorry. I see this argument all the time, and my frustration is probably showing. My second comment is possibly a better summary of my opinion. But that doesn't avoid the observation that it is important to evaluate opinions found on the internet. It is clear that left-linear grammars are not only readily parseable but also frequently parsed, and there are a lot of sources, probably including the textbook you have in your hands, with more credibility.
– rici
Mar 22, 2017 at 23:04