Basic results from automata theory tell us that the language L $=$ an bn cn $=\backslash$epsi $,$ abc, aabbcc, aaabbbccc, $...$ is not context free. It can be captured, however, using an attribute grammar. Give an underlying CFG and a set of attribute rules that associates a Boolean attribute ok with the root R of each

$4\mathrm{.}8$ Exercises $209$

$210$ Chapter$4$ SemanticAnalysis

cdr

$..$

quote

$..$

$.$

$.$

c$\backslash$epsi

Natural syntax tree for the Lisp expression $($cdr $($a b c$)).$

a

b

Figure $4\mathrm{.}16$

$\backslash$epsi

$\backslash$epsi

parse tree, such that R$.$ok $=$ true if and only if the string corresponding to the fringe of the tree is in L$.$