In Introduction to Formal Languages by Gyrgy E. Rvsz 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  BabcB  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.
parsing left linear CF grammars
formal languages;formal grammars
Left- and right-linear grammars define regular languages, and it is straight-forward to convert the grammar into a form appropriate to build an NFA which can recognise the language.That doesn't say anything about the ease of parsing the grammar, in the sense that parsing transforms a string into a parse tree which relates the various syntactic parts of the string. While we can prove that the regular language can be recognised in linear time and constant space, we cannot say much about the parse tree because there is no guarantee that the parse tree for a given string is unique. In other words, left- and right-linear grammars can be, and often are, ambiguous.What we can say is that the transformation from left- to right-linear form does not preserve the parse tree; if the intention was to build a particular parse of each string, then the transformation will not help us.Left-linear grammars cannot be parsed with an LL(k) parser, because no left-recursive grammar can be. However, there is no guarantee that the transformed right-linear grammar will be amenable to LL(k) parsing.Either a left- or a right-linear grammar might be LR(1), although there are no guarantees. (But every LL(k) grammar is LR(k) so a grammar which is not LR(1) is also not LL(1).) If the intention is to parse, and not just recognise, it seems reasonable to use a grammar which actually reflects the intended syntactic structure, to the extent possible given the constraints of different parsing algorithms. While it is evident that there are people who feel that their failure to understand the LR parsing algorithm somehow makes it less valuable (or even evil), that is not borne out by any objective metric: LR(k) parsers run in linear time and space, just like LL(k) parsers, and can be constructed in polynomial time if the grammar is LR(k). There are readily available tools which will compute the necessary tables for an LR(1) parser, and the parsing algorithm itself, given the tables, is just a few lines of simple code.