Search code examples
compiler-constructiongrammarformal-languages

An attribute grammar to identify constant expression


Suppose we want to identify assignments in which a constant value is assigned to a variable. E.g., for the two assignments

x = 1 * 5;

y = x + 2;

we would like to recognize that x and y are assigned the constant values 5 and 7, and we want to recognize y as constant as long as the value of x used in the assignment to y comes from a unique, constant assignment to x.

How can we design an attribute grammar to identify this for a CFG. Can constant assignments like this be recognized by an attribute grammar throughout the scope of the program.


Solution

  • That's not really something you want to do during the parse.

    You could certainly catch some of the possible constant expressions, although you'd have a hard time turning 4 + x + -4 into x (if that's within the scope of what you're trying to do). But the real problem you face is loops, because if a variable is used inside a loop you have no idea whether it might be modified before the next iteration until you have parsed the entire loop.

    If your language doesn't have goto or other basically uncontrollable loop constructs, you could conceivably be able to synthesize attributes down through the entire subtree once you reach the end of the loop body. But that's far from simple, because the parse tree doesn't really capture control flow as well as a control flow graph does. So it's easier to wait until you have the entire parse tree available and then build the control flow graph, from which you can trace definition-use chains. (These are all terms which you should be able to search for, either in your textbook or, if necessary, on the internet.)