Chapter 3 Describing Syntax and Semantic

          

Syntax:the form or structure of the

expressions, statements, and program units

•Semantics: the meaning of the expressions,

statements, and program units

•Syntax and semantics provide a language’s

definition–Users of a language definition

·         Other language designers

·         Implementers

·         Programmers (the users of the language)

The General Problem of Describing Syntax:

Terminology

•A sentence is a string of characters over some alphabet

•A language is a set of sentences

•A lexeme  is the lowest level syntactic unit of a

language (e.g., *, sum, begin)

•A token is a category of lexemes (e.g.,

identifier)

Formal Definition of Languages

•Recognizers

–     A recognition device reads input strings over the alphabet of

the language and decides whether the input strings belong

to the language

Example: syntax analysis part of a compiler

Generators

–A device that generates sentences of a language

–One can determine if the syntax of a particular sentence is

syntactically correct by comparing it to the structure of the

generator

Formal Methods of Describing Syntax

•Formal language-generation mechanisms,

usually called grammars, are commonly used

to describe the syntax of programming languages.

Attribute Grammars

Static Semantics

•

Nothing to do with meaning

•

Context-free grammars (CFGs) cannot describe

all of the syntax of programming languages

•

Categories of constructs that are trouble:

- Context-free, but cumbersome (e.g.,

types of operands in expressions)

- Non-context-free (e.g., variables must

be declared before they are used)

Attribute Grammars

•

Attribute grammars (AGs) have additions to

CFGs to carry some semantic info on parse

tree nodes

•

Primary value of AGs:

–

Static semantics specification

–

Compiler design (static semantics checking)

Attribute Grammars

: Definition

•

Def

: An attribute grammar is a context-free

grammar

G= (S,N,T,P) with the following

additions:

–For each grammar symbol x

there is a set

A(x) of attribute values

–

Each rule has a set of functions that define certain

attributes of the nonterminals in the rule

–

Each rule has a (possibly empty) set of predicates

to check for attribute consistency

1-25

Attribute Grammars: Definition

•

Let X0→X1... Xnbe a rule

•Functions of the form

S(X0) = f(A(X1), ... ,A(Xn))

Define synthesized attributes

•Functions of the form

I(Xj) = f(A(X0), ... , A(Xn)),

for i <= j <= n, define

inherited attributes

•Initially, there are

intrinsic attributes

on the leaves

1-26  Attribute Grammars:

An Example

• Syntax rule:

<proc_def>

→

procedure <proc_name>[1]

<proc_body> end <proc_name>[2];

•

Predicate:

<proc_name>[1]string == <proc_name>[2].string

Attribute Grammars:

An Example

•Syntax

<assign>→<var> = <expr>

<expr>→<var> + <var> | <var>

<var>→A|B|C

•

actual_type

: synthesized for

<var>and<expr>

•expected_type

: inherited for

<expr>

Attribute Grammar

(continued)

•

Syntax rule:

<expr>

→

<var>[1] + <var>[2]

Semantic rules:

<expr>.actual_type

←

<var>[1].actual_type

Predicate:

<var>[1].actual_type == <var>[2].actual_type

<expr>.expected_type == <expr>.actual_type

•Syntax rule:

<var>→id

Semantic rule:

<var>.actual_type←lookup (<var>.string)

Operational Semantics (continued)

•Uses of operational semantics:

- Language manuals and textbooks

- Teaching programming languages

•Two different levels of uses of operational semantics:

- Natural operational semantics

- Structural operational semantics

•Evaluation

- Good if used informally (language

manuals, etc.)

- Extremely complex if used formally (e.g.,VDL)

Denotational Semantics

•Based on recursive function theory

•The most abstract semantics description

method

•Originally developed by Scott and Strachey

(1970)

Denotational Semantics -

continued

•The process of building a denotational

specification for a language:

- Define a mathematical object for each language

entity

–Define a function that maps instances of the

language entities onto instances of the

corresponding mathematical objects

•The meaning of language constructs are defined

by only the values of the program's variables

Denotational Semantics:

program state

•The state of a program is the values of all its

current variables

s = {<i1, v1>, <i2, v2>, ..., <in, vn>}

•LetVARMAP

be a function that, when given a

variable name and a state, returns the current

value of the variable

VARMAP(ij, s) = vj

Evaluation of Denotational Semantics

•Can be used to prove the correctness of

programs

•Provides a rigorous way to think about

programs

•Can be an aid to language design

•Has been used in compiler generation systems

•Because of its complexity, it is of little use to

language users

Axiomatic Semantics

•Based on formal logic (predicate calculus)

•Original purpose: formal program verification

•Axioms or inference rules are defined for each

statement type in the language (to allow

transformations of logic expressions into more

formal logic expressions)

•The logic expressions are called

assertions

Axiomatic Semantics (continued)

•An assertion before a statement (a

precondition

) states the relationships and

constraints among variables that are true at

that point in execution

•An assertion following a statement is a

postcondition

•A weakest precondition

is the least restrictive

precondition that will guarantee the

postcondition

Evaluation of Axiomatic Semantics

•Developing axioms or inference rules for all of

the statements in a language is difficult

•It is a good tool for correctness proofs, and an

excellent framework for reasoning about

programs, but it is not as useful for language

users and compiler writers

•Its usefulness in describing the meaning of a

programming language is limited for language

users or compiler writers

Denotation Semantics vs Operational

Semantics

•In operational semantics, the state changes

are defined by coded algorithms

•In denotational semantics, the state changes

are defined by rigorous mathematical

functions