Attribute Grammar For Simple Assignment Statement

Copyright (C) R.A. van Engelen, FSU Department of Computer Science, 2000-2003


 

Overview

  • Static semantics
  • Dynamic semantics
  • Attribute grammars
  • Abstract syntax trees
  • Putting theory into practice:
    • Java recursive descent parsers
Note: Study Chapter 4 of the textbook upto and including Section 4.3.

Static and Dynamic Semantics

  • Syntax concerns the form of a valid program, while semantics concerns its meaning
  • Static semantic rules are enforced by a compiler at compile time
    • Implemented in semantic analysis phase of the compiler
    • Context-free grammars are not powerful enough to describe certain rules, such as checking variable declaration with variable use
    • Examples: Type checking; Identifiers are used in appropriate context; Check subroutine call arguments; Check labels
  • Dynamic semantic rules are enforced by the compiler by generating code to perform the checks
    • Examples: Array subscript values are within bounds; Arithmetic errors; Pointers are not dereferenced unless pointing to valid object; A variable is used but hasn't been initialized
    • Some languages (Euclid, Eiffel) allow programmers to add explicit dynamic semantic checks in the form of assertions, e.g.
    • assert denominator not= 0
    • When a check fails at run time, an exception is raised

 
 

Example Attribute Grammar

ProductionSemantic rule
<E1> -> <E2> + <T> <E1> -> <E2> - <T> <E> -> <T> <T1> -> <T2> * <F> <T1> -> <T2> / <F> <T> -> <F> <F1> -> - <F2> <F> -> ( <E> ) <F> -> unsigned_intE1.val := E2.val + T.val E1.val := E2.val - T.val E.val := T.val T1.val := T2.val * F.val T1.val := T2.val / F.val T.val := F.val F1.val := -F2.val F.val := E.val F.val := unsigned_int.val
  • The attribute of a (non)terminal holds the subtotal value of the subexpression described by the (non)terminal
  • Nonterminals are indexed in the attribute grammar (e.g. ) to distinghuish multiple occurrences of the nonterminal in a production

 

Decorated Parse Trees

  • A parser produces a parse tree that is decorated with the attribute values
    Example decorated parse tree of showing attribute values
  • The attribute of a node holds the subtotal value of the subexpression down the node

 

Synthesized Attributes

  • Synthesized attributes hold values used by the parent node and flow upwards
     
    ProductionSemantic rule
    <E1> -> <E2> + <T>E1.val := E2.val + T.val

 

Inherited Attributes

  • Inherted attributes are defined by the parent node and flow downwards
     
    ProductionSemantic rule
    <E> -> <T> <TT> <TT1> -> + <T> <TT2>    <TT> -> eTT.st := T.val; E.val := TT.val TT2.st := TT1.st + T.val;    TT1.val := TT2.val TT.val := TT.st

 
 

S- and L-Attributed Grammars

  • A grammar is called S-attributed if all attributes are synthesized
  • A grammar is called L-attributed if the parse tree traversal is left-to-right and depth-first
    • An essential grammar property for a one-pass compiler, because semantic rules can be applied directly during parsing and parse trees do not need to be kept in memory
ProductionSemantic rule
<E> -> <T> <TT> <TT1> -> + <T> <TT2>    <TT1> -> - <T> <TT2>    <TT> -> e <T> -> <F> <FT> <FT1> -> * <F> <FT2>    <FT1> -> / <F> <FT2>    <FT> -> e <F1> -> - <F2> <F> -> ( <E> ) <F> -> unsigned_intTT.st := T.val; E.val := TT.val TT2.st := TT1.st + T.val;    TT1.val := TT2.val TT2.st := TT1.st - T.val;    TT1.val := TT2.val TT.val := TT.st FT.st := F.val; T.val := FT.val FT2.st := FT1.st * F.val;    FT1.val := FT2.val FT2.st := FT1.st / F.val;    FT1.val := FT2.val FT.val := FT.st F1.val := -F2.val F.val := E.val F.val := unsigned_int.val

 

Example Decorated Parse Tree

  • Fully decorated parse tree of

 

Constructing Abstract Syntax Trees

ProductionSemantic rule
<E> -> <T> <TT> <TT1> -> + <T> <TT2>    <TT1> -> - <T> <TT2>    <TT> -> e <T> -> <F> <FT> <FT1> -> * <F> <FT2>    <FT1> -> / <F> <FT2>    <FT> -> e <F1> -> - <F2> <F> -> ( <E> ) <F> -> unsigned_intTT.st := T.ptr; E.ptr := TT.ptr TT2.st := mk_bin_op("+", TT1.st, T.ptr);   TT1.ptr := TT2.ptr TT2.st := mk_bin_op("-", TT1.st, T.ptr);   TT1.ptr := TT2.ptr TT.ptr := TT.st FT.st := F.ptr; T.ptr := FT.ptr FT2.st := mk_bin_op("*", FT1.st, F.ptr);   FT1.ptr := FT2.ptr FT2.st := mk_bin_op("/", FT1.st, F.ptr);   FT1.ptr := FT2.ptr FT.ptr := FT.st F1.ptr := mk_un_op("-", F2.ptr) F.ptr := E.ptr F.ptr := make_leaf(unsigned_int.val)
  • : constructs binary operator AST-node and returns pointer
  • : constructs unary operator AST-node and returns pointer
  • : constructs AST-leaf and returns pointer

 

Example Decorated Parse Tree With AST

  • Decorated parse tree of with constructed AST

 

Recursive Descent Parser for L-Attributed Grammar

  • Productions for each nonterminal are implemented as a subroutine
  • Subroutine returns synthesized attributes of the nonterminal
  • Subroutine takes inherited attributes of the nonterminal as subroutine arguments
ProductionSemantic rule
<E> -> <T> <TT> <TT1> -> + <T> <TT2>    <TT> -> eTT.st := T.val; E.val := TT.val TT2.st := TT1.st + T.val;   TT1.val := TT2.val TT.val := TT.st
function E()   Tval := T()   TTst := Tval   TTval := TT(TTst)   return TTvalfunction TT(TT1st)   case (input_token())   of '+': Tval := T()           TT2st := TT1st + Tval           TT2val := TT(TT2st)           TT1val := TT2val   otherwise: TT1val := TT1st   return TT1val  
Putting theory into practice:
  • Click [here] to view an example recursive descent parser written in Java to evaluate simple arithmetic expressions.
  • Click [here] to view an example recursive descent parser written in Java to translate simple arithmetic expressions to LISP with a Java implementation of an AST for expressions.
Exercise 1: Find information on the C/C++ macro defined in . What is the purpose of this macro?
Exercise 2: Augment the following grammar of nested parenthesis with semantic rules to count the number of opening parenthesis:
e
such that the synthesized attribute holds the number of opening parenthesis.
Exercise 3: Draw a decorated parse tree of the input using the augmented grammar of Exercise 2.
Exercise 4: Write (on paper) a recursive descent parser (in Pseudo code or any other programming language) for the augmented grammer of Exercise 2.
Exercise 5: Is the augmented grammar of Exercise 2 L-attributed (yes or no)?

Assignment statements

index

An assignment statement gives a value to a variable. For example,

gives the value 5.

The value of a variable may be changed. For example, if has the value 5, then the assignment statement

will give the value 6.

The general syntax of an assignment statement is

where:

  • the must be declared;
  • the may be a simple name, or an indexed location in an array, or a field (instance variable) of an object, or a static field of a class; and
  • the expression must result in a value that is compatible with the type of the . In other words, it must be possible to cast the expression to the type of the variable.

Examples:

An assignment "statement" is not really a statement (although it is typically used that way), but is an expression. The value of the expression is the value that is assigned to the variable. For example, the expression

sets all of , , and to zero.

One thought on “Attribute Grammar For Simple Assignment Statement

Leave a Reply

Your email address will not be published. Required fields are marked *