2
$\begingroup$

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.

Improve this question
$\endgroup$
3
  • $\begingroup$ 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. $\endgroup$
    – rici
    Commented Mar 22, 2017 at 22:54
  • $\begingroup$ 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. $\endgroup$
    – abc
    Commented Mar 22, 2017 at 22:57
  • $\begingroup$ @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. $\endgroup$
    – rici
    Commented Mar 22, 2017 at 23:04

1 Answer 1

Reset to default
2
$\begingroup$

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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.