Modify the attribute grammar of Example 3.6 in Sebesta so that it uses only a si

Question

Modify the attribute grammar of Example 3.6 in Sebesta so that it uses only a single (synthesized) attribute.

An Attribute Grammar for Simple Assignment Statements

Syntax rule: <assign> <var> = <expr>
Semantic rule: <expr>.expected_type <var>.actual_type

Syntax rule: <expr> <var>[2] + <var>[3] Semantic rule: <expr>.actual_type

Predicate:

if (<var>[2].actual_type = int) and (<var>[3].actual_type = int)

then int else real

end if
<expr>.actual_type == <expr>.expected_type

Syntax rule: <expr> <var>
Semantic rule: <expr>.actual_type <var>.actual_type Predicate: <expr>.actual_type == <expr>.expected_type

Syntax rule: <var> A | B | C
Semantic rule: <var>.actual_type look-up(<var>.string)

The look-up function looks up a given variable name in the symbol table and returns the variable’s type.

Explanation / Answer

An attribute grammar may be informally defined as a context-free grammar that has been extended to provide context sensitivity using a set of attributes, assignment of attribute values, evaluation rules, and conditions. A finite, possibly empty set of attributes is associated with each distinct symbol in the grammar. Each attribute has an associated domain of values, such asintegers, character and string values, or more complex structures. Viewing the input sentence (or program) as a parse tree, attribute grammars can pass values from a node to its parent, using a synthesized attribute, or from the current node to a child, using an inherited attribute. In addition to passing attribute values up or down the parse tree, the attribute values may be assigned, modified, and checked at any node in the derivation tree. The following examples should clarify some of these points. Examples of Attribute Grammars We will attempt to write a grammar to recognize sentences of the form anbncn. The sentences aaabbbccc and abc belong to this grammar but the sentences aaabbbbcc and aabbbcc do not. Consider this first attempt to describe the language using a context-free grammar: ::= ::= a | a ::= b | b ::= c | c As seen in Figure 3.1, this grammar can generate the string aaabbbccc . It can also generate the string aaabbbbcc ,As has already been noted in Chapter 1, it is impossible to write a contextfree grammar to generate only those sentences of the form anbncn. However, it is possible to write a context-sensitive grammar for sentences of this form. Attribute grammars provide another approach for defining context-sensitivity. If we augment our grammar with an attribute describing the length of aletter sequence, we can use these values to ensur e that the sequences of a’s, b’s, and c’s all have the same length.The first solution involves a synthesized attribute Size that is associated with the nonterminals , , and . W e add the condition that, at the root of the tree, the Size attribute for each of the letter sequences has the same value. If a character sequence consists of a single character, Size is set to 1; if it consists of a character sequence followed by a single character, Size for the parent character sequence is the Size of the child character sequence plus one. We have added the necessary attribute assignments and conditions to the grammar shown below. Notice that we differentiate a parent sequence from a child sequence by adding subscripts to the nonterminal symbols. ::= condition : Size () = Size () = Size () ::= a Size () 1 | 2 a Size () Size ( 2) + 1 ::= b Size () 1 | 2 b Size () Size ( 2) + 1 ::= c Size () 1 | 2 c Size () Size ( 2) + 1 This attribute grammar successfully parses the sequence aaabbbccc since the sequence obeys the BNF and satisfies all conditions in the attribute grammar. The complete, decorated parse tree

Related Questions

Navigate

• Browse (All)
• Browse M
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.