Re: Is the relation beetween grammar.y and bijective ?

"Joachim Durchholz" <>
28 Mar 2000 01:05:22 -0500

          From comp.compilers

Related articles
Is the relation beetween grammar.y and bijective ? (Nicolas Ratier) (2000-03-23)
Re: Is the relation beetween grammar.y and bijective ? (Joachim Durchholz) (2000-03-28)
Re: Is the relation beetween grammar.y and bijective ? (Chris F Clark) (2000-04-03)
| List of all articles for this month |

From: "Joachim Durchholz" <>
Newsgroups: comp.compilers
Date: 28 Mar 2000 01:05:22 -0500
Organization: Compilers Central
References: 00-03-103
Keywords: yacc, theory

Nicolas Ratier <> wrote:
> Is there a way to "reverse" the C program genereted by Yacc (bison).
> i.e. get the Yacc original grammar. Corrolary : Does the relation
> beetween Yacc and is bijective ?

1) Pragmatic answer: There may be a reverse function, but nobody has
written such a beast, so for practical purposes, there isn't. Besides,
I'd have trouble devising an algorithm that got the productions back out
of the tables. Hmm... well, it might still be possible.

2) Theory-based answer: The names of the productions don't make it into
the generated tables, so the best you can achieve is an equivalent

3) The relation is not really bijective, as the mapping from grammars to
parsing programs is not unique. Depending on yacc/bison version and
options, you can get vastly different C code. I wouldn't even bet that
the generated tables are the same; the exact mapping of state numbers to
leftmost derivations might be different depending on the automatic
generation of error states and such stuff.

Disclaimer: I'm not a yacc guru, I just didn't see anybody else answer


Post a followup to this message

Return to the comp.compilers page.
Search the comp.compilers archives again.