Partial evaluation can generate efficient LR parsers and parser generators [29]. The partial evaluator specializes an interpretive LR parser with respect to an attribute grammar and the number of lookahead characters. In an attribute grammar, each context-free production comes with an associated attribution. An (only-S) attribution is simply a piece of Scheme code that maps the attribute values of the right side nonterminals of a production to the attribute value of the left side nonterminal. To perform attribute evaluation during parsing, the specializer of the parser must copy the attribution of each production to the generated parser. There are several possibilities to do so.
The interpretive parser may call upon a Scheme interpreter interp to evaluate the attributions:
(interp (cons (attribution->definition attribution)
program)
(take rhs-length attribute-stack))
Unfortunately, this approach requires writing a quite large
interpreter. Furthermore, parser generation becomes grossly
inefficient as the specializer must specialize/interpret the interpreter which
actually runs the code to copy the attribution to the specialized program.
A much better choice consists in using eval to transform the text of the attribution into the actual function:
(apply (eval attribution (interaction-environment))
(take rhs-length attribute-stack))
Since attribution will be static, we would like to remove
eval from the residual code and simply paste in the static value of
attribution, considered as code. For example, for the attribution
(lambda ($1 $2 $3) (* $1 $3)) our specializer generates:
(let ((var-9031 ((lambda ($1 $2 $3) (* $1 $3))
(car var-9030)
(car var-9029)
(car clone-9018))))
...)))
from the apply/eval code fragment above.
Apart from binding-time issues, the main problem of specializing eval is a representation problem: If eval reflects a function, the representation of the function may not coincide with the specializer's representation of a function. Also, a reflected function should not manipulate code.