《Programming Language Pragmatics》第四章笔记

Semantic Analysis

semantics concerns its meaning. Meaning is important for at least two reasons: it allows us to enforce rules (e.g., type consistency) that go beyond mere form, and it provides the information we need in order to generate an equivalent output program.

Semantic rules are further divided into static and dynamic semantics

Both semantic analysis and intermediate code generation can be described in terms of annotation, or decoration of a parse tree or syntax tree.

Attribute grammars provide a formal framework for the decoration of a tree. This framework is a useful conceptual tool even in compilers that do not build a parse tree or syntax tree as an explicit data structure.

The Role of the Semantic Analyzer

The role of the semantic analyzer is to enforce all static semantic rules and to annotate the program with information needed by the intermediate code generator.

Dynamic Checks

Many compilers that generate code for dynamic checks provide the option of disabling them if desired.


The compiler then generates code to check the assertions at run time. An assertion is a statement that a specified condition is expected to be true when execution reaches a certain point in the code.

Static Analysis

In general, compile-time algorithms that predict run-time behavior are known as static analysis.

static analysis may enable code improvement:

  • alias analysis
  • escape analysis
  • subtype analysis

Attribute Grammars

To tie these expressions to mathematical concepts (as opposed to, say, floor tile patterns or dance steps), we need additional notation. The most common is based on attributes.

In a compiler or interpreter for a full programming language, the attributes of tree nodes might include:

  • for an identifier, a reference to information about it in the symbol table
  • for an expression, its type
  • for a statement or expression, a reference to corresponding code in the compiler’s intermediate form
  • for almost any construct, an indication of the file name, line, and column where the corresponding source code begins
  • for any internal node, a list of semantic errors found in the subtree below

Evaluating Attributes

The process of evaluating attributes is called annotation or decoration of the parse tree.

Synthesized Attributes 合成属性

synthesized attributes: their values are calculated (synthesized) only in productions in which their symbol appears on the left-hand side.

Inherited Attributes

In general, we can imagine (and will in fact have need of) attributes whose values are calculated when their symbol is on the right-hand side of the current production. Such attributes are said to be inherited.

Attribute Flow

they define a set of valid trees, but they don’t say how to build or decorate them.

the order in which attribute rules are listed for a given production is immaterial; attribute flow may require them to execute in any order.

An algorithm that decorates parse trees by invoking the rules of an attribute grammar in an order consistent with the tree’s attribute flow is called a translation scheme.

One-Pass Compilers

A compiler that interleaves semantic analysis and code generation with parsing is said to be a one-pass compiler

Action Routines

An ad hoc translation scheme that is interleaved with parsing takes the form of a set of action routines.

An action routine is a semantic function that the programmer (grammar writer) instructs the compiler to execute at a particular point in the parse.

Space Management for Attributes

If we are building an explicit parse tree, then the obvious approach is to store attributes in the nodes of the tree themselves.

For a bottom-up parser with an S-attributed grammar, the obvious approach is to maintain an attribute stack

For a top-down parser with an L-attributed grammar, we have two principal options:

  • uses an attribute stack
  • “shortcutting” copy rules

Tree Grammars and Syntax Tree Decoration

attribute grammars can also be used to decorate syntax trees.

Summary and Concluding Remarks