5

I have a quite old C corporate parser / compiler code that was generated from an ancient Yacc and the original grammar source is lost (as the intermediate files) the only result the ytab.c parser generated file. That legacy piece of code need revamping but I cannot afford to recode it from scratch.

By "ancient Yacc", I mean that the parser is using tables named yyact, yypact, yypgo, yyr1, yyr2, yytoks, yyexca, yychk, yydef.

Could it be possible to mechanically retrieve / regenerate the parsing rules by deduction of the parsing tables in order to reconstruct the grammar?

Example with a little sample of an expression parser that I can process with the same ancient Yacc:

yytabelem yyexca[] ={
-1, 1,
    0, -1,
    -2, 0,
-1, 21,
    261, 0,
    -2, 8,
    };
yytabelem yyact[]={

    13,     9,    10,    11,    12,    23,     8,    22,    13,     9,
    10,    11,    12,     9,    10,    11,    12,     1,     2,    11,
    12,     6,     7,     4,     3,     0,    16,     5,     0,    14,
    15,     0,     0,     0,    17,    18,    19,    20,    21,     0,
     0,    24 };
yytabelem yypact[]={

  -248, -1000,  -236,  -261,  -236,  -236, -1000, -1000,  -248,  -236,
  -236,  -236,  -236,  -236,  -253, -1000,  -263,  -245,  -245, -1000,
 -1000,  -249, -1000,  -248, -1000 };
yytabelem yypgo[]={

     0,    17,    24 };
yytabelem yyr1[]={

     0,     1,     1,     1,     2,     2,     2,     2,     2,     2,
     2,     2,     2 };
yytabelem yyr2[]={

     0,     8,    12,     0,     6,     6,     6,     6,     6,     6,
     4,     2,     2 };
yytabelem yychk[]={

 -1000,    -1,   266,    -2,   259,   263,   257,   258,   267,   262,
   263,   264,   265,   261,    -2,    -2,    -1,    -2,    -2,    -2,
    -2,    -2,   260,   268,    -1 };
yytabelem yydef[]={

     3,    -2,     0,     0,     0,     0,    11,    12,     3,     0,
     0,     0,     0,     0,     0,    10,     1,     4,     5,     6,
     7,    -2,     9,     3,     2 };

yytoktype yytoks[] =
{
    "NAME", 257,
    "NUMBER",   258,
    "LPAREN",   259,
    "RPAREN",   260,
    "EQUAL",    261,
    "PLUS", 262,
    "MINUS",    263,
    "TIMES",    264,
    "DIVIDE",   265,
    "IF",   266,
    "THEN", 267,
    "ELSE", 268,
    "LOW",  269,
    "UMINUS",   270,
    "-unknown-",    -1  /* ends search */
};

I am looking to retrieve

stmt    : IF exp THEN stmt
        | IF exp THEN stmt ELSE stmt
        | /*others*/
        ;

exp     : exp PLUS exp
        | exp MINUS exp
        | exp TIMES exp
        | exp DIVIDE exp
        | exp EQUAL exp
        | LPAREN exp RPAREN
        | MINUS exp
        | NAME
        | NUMBER
        ;

The full parser for this example is available as a gist, it is showing a yyreds table containing the rules as a debug info that is not in the parser that I am trying to reverse.

Note : I have asked this formerly on SO, and was suggested to ask it in RE. Any help?

PS: i am not familiar with the RE question tags, feel free to correct this.

1
3

I don't have an actual answer. I've heard some rumors of a tool doing that but haven't seen anything concrete. I have, however, found a page which should be pretty helpful:

Understanding C parsers generated by GNU Bison

This document is an attempt to describe the implementation of an LALR(1) parser in C as generated by Bison 2.3. I used a simple grammar to demonstrate the working of the parser and the nature of parsing tables. You will also find a comparison of these tables to the uncompressed tabular scheme given in the popular book "Compilers - Principles, Techniques and Tools" by Aho, Sethi and Ullman, also called as the "Dragon Book" and many other books on compiler design.

See it here.

EDIT: found a script that claims to do it!

http://nah6.com/~itsme/cvs-xdadevtools/perlutils/yydecode.pl

However it seems it's intended to be used with another set of tables. Still, it might be useful for a start.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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