bison - LEX -YACC parser for infix-to-prefix translation

Question

Translation schemes:

expr -> {print("+")} expr + term
      | {print("-")} expr - term
      | term
term -> {print("*")} term * factor
      | {print("/")} term / factor
      | factor
factor -> digit {print(digit)}
        | (expr)

Above grammar will print the expression in prefix form. For this grammar it is not possible to write the parser. how could we write the lex and yacc program to convert infix to prefix. I follow this lex and yacc program to convert infix to prefix but not getting proper output. Any idea how to write the parser.

Answer 1

Since you can't output operator tokens until after you reduce rules with them (recognize them), you'll need to save the string for the expression before the operator (rather than outputting it as you see it) so it can be emitted after the operator. This means that your rules need to build strings with the translation and only output the string only after parsing a complete expression.

There are a number of ways of building strings in C. You can use asprintf or malloc + strcpy/strcat/sprintf, and then worry about when to properly free stuff afterwards. Or you can use some sort of string pool that tracks the memory for you and can deal with cleanup.