Is it possible to reverse a grammar?

Question

For given context-free grammar is it possible to obtain a "reversed grammar"?

By "reversed grammar" I mean a grammar which would accept language consisting of reversed words from the original grammar language.

For example following grammar

root = r1 [r2] *r3
r1   = "a"
r2   = "b"
r3   = "cd"

when reversed would look like this:

root = *r3 [r2] r1
r1   = "a"
r2   = "b"
r3   = "dc"

The reason I'm asking this is that I would like to parse string backwards (from end to begin). And for that I would need "reversed grammar".

So is there a systematical way of obtaining "reversed grammar"?

Will reverting every rule work? It seems so to me. But I expected that such a "lemma" would be stated somewhere while I didn't found anything. So maybe it only appears so in simple examples?

Answer 1

FWIW, Grune & Jacobs' Parsing Techniques 2nd ed. 2008 (p. 68) defines reversal of a grammar differently (as turning lhs to rhs, start to a terminal and adding a new start), in terms of bottom-up and top-down parsing and production/reduction duality.

However, can't see why a reversed string can't be parsed with the grammar reversed as you describe. If what you need is the parse results for an unreversed string (assuming you just can't have the input string in normal order and have to parse backwards), you might also need to reverse the parse results, e.g. AST.

Hope this helps.

P.S. "language consisting of reversed words" -- looks like you're implying a language consisting of reversed strings; for reversed words you don't need to reverse the root's rhs.

P.P.S. A grammar is a tree, which is a graph, so you may find tree/graph reversal methods useful.

Answer 2

The set of context-free languages is closed under the operation of string reversal, which is a mathematical way of saying that if you have a context-free language, then the language which consists of the same strings backwards is also context-free. The proof is simple, and is based precisely on the transformation indicated: take a context-free grammar and reverse every right-hand-side; the resulting grammar is obviously context free and accepts the reverse of the strings accepted by the original grammar. Formal proofs can be found easily in standard textbooks on formal language theory or in the internet. [1]

The same is true of regular languages, using a very similar construction.

In practical terms, however, there is a problem: while the grammar constructed for the reverse of the language is clearly context free, it may not be LR(1). It's easy to construct an example of an LR(1) grammar whose reverse is not:

S -> a A
S -> b B
A -> a
A -> A a
B -> a
B -> B a

That recognizes the regular language b?a* whose reverse is a*b?, but the grammar parses the string of a's differently, depending on whether the string starts (ends, in the case of the reversal) with a b. In this simple case, the language is regular, and therefore the reverse language is also regular, so both can be parsed left-to-right by some grammar. However, that is not always the case, and in any event you usually parse a string in order to obtain the parse tree, not just to determine whether the string is valid.

In short, you can construct a context-free grammar for the reversal of a language by reversing all the right-hand sides, but the resulting grammar might not be as easy to parse. (Or it might be easier.)

---

Notes

1. A good search to start with might be context free language closure properties.