Type Checking - Introduction to Compiler Construction in a Java World - page 164

write a context-free grammar describing the language under consideration here. Attribute
grammars come to our rescue. Augmenting our context-free grammar with an attribute
describing the length of a letter sequence, we can use these values to make sure that the
sequences of a , b , and c have the same length.
We associate a synthesized attribute size with the non-terminals aSequence, bSequence,
and cSequence, and a condition at the root of the parse tree that the size attribute for each
of the letter sequences has the same value. If the input consists of a single character, size
is set to 1; if it consists of a sequence followed by a single character, size for the parent
character is set to the size of the child character plus one. Added to the root is the condition
that the sizes of the sequences be the same. Here is the augmented grammar:
letterSequence ::= aSequence bSequence cSequence
condition : size(aSequence) = size(bSequence) = size(cSequence)
aSequence ::= a
size(aSequence) 1
j aSequence a
size(aSequence) size(aSequence) + 1
bSequence ::= b
size(bSequence) 1
j bSequence b
size(bSequence) size(bSequence) + 1
cSequence ::= c
size(cSequence) 1
j cSequence c
size(cSequence) size(cSequence) + 1
The augmented attribute grammar successfully parses legal strings such as aabbcc , but
does not parse illegal sequences such as abbcc ; such illegal sequences satisfy the BNF part
of the grammar, and do not satisfy the condition required of the attribute values.
Another approach is to pass information from one part of the parse tree to some node,
and then have it inherited down into other parts of the tree. Let size be a synthesized
attribute for the sequence of a 's, and iSize be the inherited attribute for the sequences of
b 's, and c 's. We synthesize the size of the sequence of a 's to the root of the parse tree, and
set the iSize attribute for the b sequence and the c sequence to this value and inherit it
down the tree, decrementing the value by one every time we see another character in the
sequence. When we reach the node where the sequence has a child consisting of a single
character, we check if the inherited iSize attribute equals one. If so, the size of the sequence
must be the same as the size of the a sequence; otherwise, the two sizes do not match and
the parsing is unsuccessful. The following attribute grammar clarifies this:
letterSequence ::= aSequence bSequence cSequence
iSize(bSequence) size(aSequence)
iSize(cSequence) size(aSequence)
aSequence ::= a
size(aSequence) 1
j aSequence a