Implementation, Syntax, and
Semantics
Organization of Programming Languages-Cheng (Fall 2005)
1
Implementation Methods
 Compilation
 Translate
high-level program to machine code
 Slow translation
 Fast execution
Source
Program
Input
Compiler
Target Program
Organization of Programming Languages-Cheng (Fall 2005)
Target
Program
Output
2
Compilation
Process
Organization of Programming Languages-Cheng (Fall 2005)
Compiler
3
Implementation Methods
 Pure
interpretation
 No translation
 Slow execution
 Becoming rare
Source
Program
Interpreter
Output
Input
Organization of Programming Languages-Cheng (Fall 2005)
4
Implementation Methods
 Hybrid
implementation systems
 Small translation cost
 Medium execution speed
Source
Program
Translator
Intermediate
Program
Intermediate
Program
Virtual Machine
Output
Input
Organization of Programming Languages-Cheng (Fall 2005)
5
Hybrid
Implementation
System
Organization of Programming Languages-Cheng (Fall 2005)
Translator
6
Programming Environments
 The
collection of tools used in software
development
 UNIX
 An older operating system and tool collection
 Borland JBuilder
 An integrated development environment for
Java
 Microsoft Visual Studio.NET
 A large, complex visual environment
 Used to program in C#, Visual BASIC.NET,
Jscript, J#, or C++
Organization of Programming Languages-Cheng (Fall 2005)
7
Describing Syntax
 Lexemes:
 Tokens:
lowest-level syntactic units
categories of lexemes
sum = x + 2 – 3
Lexemes: sum,
=,
x,
+,
2,
-,
3
Tokens: identifier, equal_sign, plus_op, integer_literal, minus_op
Organization of Programming Languages-Cheng (Fall 2005)
8
Formal Method for Describing Syntax

Backus-Naur form (BNF)
 Also equivalent to context-free grammars, developed by Noam
Choamsky (a linguist)
 BNF is a meta-language



a language used to describe another language
Consists of a collection of rules (or productions)
Example of a rule:
<assign>  < var > = < expression >
LHS: the abstraction being defined
RHS: contains a mixture of tokens, lexemes, and references to other
abstractions



Abstractions are called non-terminal symbols
Lexemes and tokens are called terminal symbols
Also contains a special non-terminal symbol called the start
symbol
Organization of Programming Languages-Cheng (Fall 2005)
9
Example of a grammar in BNF
<program>  begin <stmt_list> end
<stmt_list>  <stmt> | <stmt>; <stmt_list>
<stmt>  <var> = <expression>
<var>  A | B | C | D
<expression>  <var> + <var> | <var> - <var> |
<var>
Organization of Programming Languages-Cheng (Fall 2005)
10
Derivation

The process of generating a sentence
begin A = B – C end
Derivation:
<program> (start symbol)
=> begin <stmt_list> end
=> begin <stmt> end
=> begin <var> = <expression> end
=> begin A = <expression> end
=> begin A = <var> - <var> end
=> begin A = B - <var> end
=> begin A = B - C end
Organization of Programming Languages-Cheng (Fall 2005)
11
BNF
 Leftmost
derivation:
 the replaced non-terminal is always the leftmost
non-terminal
 Rightmost derivation
 the replaced non-terminal is always the
rightmost non-terminal
 Sentential forms
 Each string in the derivation, including
<program>
Organization of Programming Languages-Cheng (Fall 2005)
12
Derivation
begin A = B + C; B = C end
Rightmost:
<program>
(start symbol)
=> begin <stmt_list> end
=> begin <stmt>; <stmt_list> end
=> begin <stmt>; <stmt> end
=> begin <stmt>; <var> = <expression> end
=> begin <stmt>; <var> = <var> end
=> begin <stmt>; <var> = C end
=> begin <stmt>; B = C end
=> begin <var> = <expression>; B = C end
=> begin <var> = <var> + <var>; B = C end
=> begin <var> = <var> + C; B = C end
=> begin <var> = B + C; B = C end
=> begin A = B + C; B = C end
Organization of Programming Languages-Cheng (Fall 2005)
13
Parse Tree
 A hierarchical
structure that shows the derivation
process
Example:
<assign>  <id> = <expr>
<id>  A | B | C | D
<expr>  <id> + <expr>
| <id> - <expr>
| ( <expr> )
| <id>
Organization of Programming Languages-Cheng (Fall 2005)
14
Parse Tree
A = B * (A + C)
<assign>
 <id> = <expr>
 A = <expr>
 A = <id> * <expr>
 A = B * <expr>
 A = B * ( <expr> )
 A = B * ( <id> + <expr> )
 A = B * ( A + <expr> )
 A = B * ( A + <id> )
A=B*(A+C)
Organization of Programming Languages-Cheng (Fall 2005)
15
Ambiguous Grammar



A grammar that generates a sentence for which there are
two or more distinct parse trees is said to be ambiguous
Example:
<assign>  <id> + <expr>
<id>  A | B | C | D
<expr>  <expr> + <expr>
| <expr> * <expr>
| ( <expr> )
| <id>
Draw two different parse trees for
A=B+C*A
Organization of Programming Languages-Cheng (Fall 2005)
16
Ambiguous Grammar
Organization of Programming Languages-Cheng (Fall 2005)
17
Ambiguous Grammar
 Is
the following grammar ambiguous?
<if_stmt>  if <logic_expr> then <stmt>
| if <logic_expr> then <stmt> else
<stmt>
Organization of Programming Languages-Cheng (Fall 2005)
18
Operator Precedence
A=B+C*A
 How
to force “*” to have higher precedence over
“+”?
 Answer:
add more non-terminal symbols
 Observe
that higher precedent operator reside at
“deeper” levels of the trees
Organization of Programming Languages-Cheng (Fall 2005)
19
Operator Precedence
A=B+C*A
Before:
After:
<assign>  <id> + <expr>
<id>  A | B | C | D
<expr>  <expr> + <expr>
| <expr> * <expr>
| ( <expr> )
| <id>
<assign>  <id> + <expr>
<id>  A | B | C | D
<expr>  <expr> + <term>
| <term>
<term>  <term> * <factor>
| <factor>
<factor>  ( <expr> )
| <id>
Organization of Programming Languages-Cheng (Fall 2005)
20
Operator Precedence
A=B+C*A
Organization of Programming Languages-Cheng (Fall 2005)
21
Associativity of Operators
A=B+C–D*F/G
 Left-associative
 Operators of the same precedence evaluated
from left to right
 C++/Java: +, -, *, /, %
 Right-associative
 Operators of the same precedence evaluated
from right to left
 C++/Java: unary -, unary +, ! (logical
negation),
~ (bitwise complement)
 How to enforce operator associativity using BNF?
Organization of Programming Languages-Cheng (Fall 2005)
22
Associativity of Operators
<assign>  <id> = <expr>
<id>  A | B | C | D
<expr>  <expr> + <term>
| <term>
<term>  <term> * <factor>
| <factor>
<factor>  ( <expr> )
| <id>
Left-recursive rule
Organization of Programming Languages-Cheng (Fall 2005)
Left-associative
23
Associativity of Operators
<assign>  <id> = <factor>
<factor>  <exp> ^ <factor>
| <exp>
Right-recursive rule
<exp>  (<expr>) | <id>
<id>  A | B | C | D
Exercise: Draw the parse tree for A = B^C^D
(use leftmost derivation)
Organization of Programming Languages-Cheng (Fall 2005)
24
Extended BNF
 BNF
rules may grow unwieldy for complex
languages
 Extended BNF
 Provide extensions to “abbreviate” the rules
into much simpler forms
 Does not enhance descriptive power of BNF
 Increase readability and writability
Organization of Programming Languages-Cheng (Fall 2005)
25
Extended BNF

Optional parts are placed in brackets ([ ])

<select_stmt>  if ( <expr> ) <stmt> [ else <stmt> ]

Put alternative parts of RHSs in parentheses and
separate them with vertical bars



<term>  <term> (+ | -) const
Put repetitions (0 or more) in braces ({ })
<id_list>  <id> { , <id> }
Organization of Programming Languages-Cheng (Fall 2005)
26
Extended BNF (Example)
BNF:
<expr>  <expr> + <term>
| <expr> - <term>
| <term>
<term>  <term> * <factor>
| <term> / <factor>
| <factor>
<factor>  <exp> ^ <factor>
| <exp>
<exp>  ( <expr> )
| <id>
EBNF:
<expr>  <term> {(+|-)
<term>}
<term><factor>{(*|/)<factor>
}
<factor> <exp>{^ <exp>}
<exp>  ( <expr> )
| <id>
Organization of Programming Languages-Cheng (Fall 2005)
27
Compilation
Organization of Programming Languages-Cheng (Fall 2005)
28
Lexical Analyzer



A pattern matcher for character strings
The “front-end” for the parser
Identifies substrings of the source program that belong
together => lexemes
 Lexemes match a character pattern, which is
associated with a lexical category called a token
Example:
sum = B –5;
Lexeme
sum
=
B
5
;
Token
ID
(identifier)
ASSIGN_OP
ID
SUBTRACT_OP
INT_LIT (integer literal)
SEMICOLON
Organization of Programming Languages-Cheng (Fall 2005)
29
Lexical Analyzer


Functions:
 Extract lexemes from a given input string and produce
the corresponding tokens, while skipping comments
and blanks
 Insert lexemes for user-defined names into symbol
table, which is used by later phases of the compiler
 Detect syntactic errors in tokens and report such errors
to user
How to build a lexical analyzer?
 Create a state transition diagram first


A state diagram is a directed graph
Nodes are labeled with state names


One of the nodes is designated as the start node
Arcs are labeled with input characters that cause the
transitions
Organization of Programming Languages-Cheng (Fall 2005)
30
State Diagram (Example)
Letter  A | B | C |…| Z | a | b | … | z
Digit  0 | 1 | 2 | … | 9
id  Letter{(Letter|Digit)}
int  Digit{Digit}
Organization of Programming Languages-Cheng (Fall 2005)
main () {
int sum = 0, B = 4;
sum = B - 5;
}
31
Lexical Analyzer

Need to distinguish reserved words from identifiers
 e.g., reserved words: main and int

identifiers: sum and B
Use a table lookup to determine whether a possible
identifier is in fact a reserved word To determine
whether id is
a reserved word
Organization of Programming Languages-Cheng (Fall 2005)
32
Lexical Analyzer

Useful subprograms in the lexical analyzer:
 lookup


getChar


determines whether the string in lexeme is a
reserved word (returns a code)
reads the next character of input string, puts it in a
global variable called nextChar, determines its
character class (letter, digit, etc.) and puts the class
in charClass
addChar

Appends nextChar to the current lexeme
Organization of Programming Languages-Cheng (Fall 2005)
33
Lexical Analyzer
int lex() {
switch (charClass) {
case LETTER:
addChar();
getChar();
while (charClass == LETTER || charClass == DIGIT)
{
addChar();
getChar();
}
return lookup(lexeme);
break;
case DIGIT:
addChar();
getChar();
while (charClass == DIGIT) {
addChar();
getChar();
}
return INT_LIT;
break;
} /* End of switch */
} /* End of function lex */
Organization of Programming Languages-Cheng (Fall 2005)
34
Parsers (Syntax Analyzers)
 Goals
of a parser:
 Find all syntax errors
 Produce parse trees for input program
 Two
categories of parsers:
 Top down
 produces
the parse tree, beginning at the root
 Uses leftmost derivation
 Bottom
up
 produces
the parse tree, beginning at the leaves
 Uses the reverse of a rightmost derivation
Organization of Programming Languages-Cheng (Fall 2005)
35
Recursive Descent Parser
 A top-down
parser implementation
 Consists of a collection of subprograms
 A recursive descent parser has a subprogram
for each non-terminal symbol
 If there are multiple RHS for a given nonterminal,
 parser must make a decision which RHS to
apply first
 A  x… | y…. | z…. | …
 The correct RHS is chosen on the basis of the
next token of input (the lookahead)
Organization of Programming Languages-Cheng (Fall 2005)
36
Recursive Descent Parser
void expr() {
term();
<expr>  <term> {(+|-) <term>}
while (
nextToken ==PLUS_CODE ||
<term>  <factor> {(*|/) <factor>}
nextToken == MINUS_CODE
<factor>  id | ( <expr> )
)
{
lex();
term();
}
}
 lex() is the lexical analyzer function. It gets the next lexeme and puts its
token code in the global variable nextToken
 All subprograms are written with the convention that each one leaves the
next token of input in nextToken
 Parser uses leftmost derivation
Organization of Programming Languages-Cheng (Fall 2005)
37
Recursive Descent Parser
void factor() {
/* Determine which RHS */
if (nextToken == ID_CODE)
<expr>  <term> {(+|-) <term>}
lex();
<term>  <factor> {(*|/) <factor>}
else if (nextToken ==
<factor>  id | ( <expr> )
LEFT_PAREN_CODE) {
lex();
expr();
if (nextToken ==
RIGHT_PAREN_CODE)
lex();
else
error();
}
else
error(); /* Neither RHS
matches */
}
Organization of Programming Languages-Cheng (Fall 2005)
38
Recursive Descent Parser

Problem with left recursion
 A  A + B (direct left recursion)
 A  B c D (indirect left recursion)
BAb
 A grammar can be modified to remove left recursion

Inability to determine the correct RHS on the basis of one
token of lookahead
 Example: A  aC | Bd
B  ac
Cc
Organization of Programming Languages-Cheng (Fall 2005)
39
LR Parsing
 LR
Parsers are almost always table-driven
 Uses a big loop to repeatedly inspect 2-dimen
table to find out what action to take
 Table is indexed by current input token and
current state
 Stack contains record of what has been seen SO
FAR (not what is expected/predicted to see in
future)
 PDA: Push down automata:
 State diagram looks just like a DFA state diagram
 Arcs labeled with <input symbol, top-of-stack
symbol>
Organization of Programming Languages-Cheng (Fall 2005)
40
PDAs
 LR
PDA: is a recognizer
 Builds a parse tree bottom up
 States keep track of which productions we
“might” be in the middle of.
Organization of Programming Languages-Cheng (Fall 2005)
41
Example

<pgm>
-> <stmt list> $$
<stmt list>-> <stmt list> <stmt> |
<stmt>
<stmt>
-> id := <expr> |
read id | write <expr>
<expr> -> <term> |
<expr> <add op> <term>
<term>
-> <factor>
|
<term> <mult op> <factor>
<factor> -> ( <expr> ) | id |
literal
<add op> -> + | <mult op> -> * | /
Organization of Programming Languages-Cheng (Fall 2005)




read A
read B
sum := A + B
write sum
write sum / 2
42
STOP
Organization of Programming Languages-Cheng (Fall 2005)
43
Static Semantics


BNF cannot describe all of the syntax of PLs
Examples:
 All variables must be declared before they are referenced
 The end of an Ada subprogram is followed by a name, that name
must match the name of the subprogram
Procedure Proc_example (P: in Object) is
begin
….
end Proc_example


Static semantics
 Rules that further constrain syntactically correct programs
 In most cases, related to the type constraints of a language
 Static semantics are verified before program execution (unlike
dynamic semantics, which describes the effect of executing the
program)
BNF cannot describe static semantics
Organization of Programming Languages-Cheng (Fall 2005)
44
Attribute Grammars (Knuth, 1968)

A BNF grammar with the following additions:
 For each symbol x there is a set of attribute values, A(x)




Each grammar rule has a set of functions that define
certain attributes of the nonterminals in the rule


A(X) = S(X)  I(X)
S(X): synthesized attributes
– used to pass semantic information up a parse tree
I(X): inherited attributes
– used to pass semantic information down a parse tree
Rule: X0  X1 … Xj … Xn
S(X0) = f (A(X1), …, A(Xn))
I(Xj) = f (A(X0), …, A(Xj-1))
A (possibly empty) set of predicate functions to check
whether static semantics are violated

Example: S(Xj ) = I (Xj ) ?
Organization of Programming Languages-Cheng (Fall 2005)
45
Attribute Grammars (Example)
Procedure Proc_example (P: in Object) is
begin
….
end Proc_example
Syntax rule:
<Proc_def>  Procedure <proc_name>[1]
<proc_body>
end <proc_name>[2]
Semantic rule:
<proc_name>[1].string = <proc_name>[2].string
attribute
Organization of Programming Languages-Cheng (Fall 2005)
46
Attribute Grammars (Example)

Expressions of the form <var> + <var>
 var's can be either int_type or real_type
 If both var’s are int, result of expr is int
 If at least one of the var’s is real, result of expr is real

BNF
<assign>  <var> = <expr>
<expr>  <var> + <var>
| <var>
<var>  A | B | C

(Rule 1)
(Rule 2)
(Rule 3)
(Rule 4)
Attributes for non-terminal symbols <var> and <expr>
 actual_type - synthesized attribute for <var> and <expr>
 expected_type - inherited attribute for <expr>
Organization of Programming Languages-Cheng (Fall 2005)
47
Attribute Grammars (Example)




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  if ( <var>[2].actual_type = int) and
<var>[3].actual_type = int)
then int
else real
end if
Predicate: <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  lookup(<var>.string)
Note: Lookup function looks up a given variable name in the symbol table
and returns the variable’s type
Organization of Programming Languages-Cheng (Fall 2005)
48
Parse Trees for Attribute Grammars
A=A+B
<assign>
<expr>
<var>
var[2]
var[3]
A
=
A
+
B
How are attribute values computed?
1. If all attributes were inherited, the tree could be decorated in top-down
order.
2. If all attributes were synthesized, the tree could be decorated in bottomup order.
3. If both kinds of attributes are present, some combination of top-down
and bottom-up must be used.
Organization of Programming Languages-Cheng (Fall 2005)
49
Parse Trees for Attribute Grammars
A=A+B




<assign>  <var> = <expr>
<expr>.expected_type 
<var>.actual_type
<expr>  <var>[2] + <var>[3]
<expr>.actual_type 
if ( <var>[2].actual_type = int)

<var>.actual_type  lookup(A)
(Rule 4)

<expr>.expected_type 
<var>.actual_type
(Rule 1)
and <var>[3].actual_type = int)
then int
else real
end if
Predicate: <expr>.actual_type =
<expr>.expected_type
<expr>  <var>
<expr>.actual_type  <var>.actual_type
Predicate: <expr>.actual_type =
<expr>.expected_type
<var>  A | B | C
<var>.actual_type 
lookup(<var>.string)

<var>[2].actual_type  lookup(A)
(Rule 4)
<var>[3].actual_type  lookup(B)
(Rule 4)

<expr>.actual_type  either int or real
(Rule 2)

<expr>.expected_type =
<expr>.actual_type is either TRUE or
FALSE
(Rule 2)
Organization of Programming Languages-Cheng (Fall 2005)
50
Parse Trees for Attribute Grammars
Predicate test
5
2
4
1
3
Organization of Programming Languages-Cheng (Fall 2005)
4
3
51
Attribute Grammar Implementation

Determining attribute evaluation order is a complex
problem, requiring the construction of a dependency graph
to show all attribute dependencies

Difficulties in implementation
 The large number of attributes and semantic rules
required make such grammars difficult to write and read
 Attribute values for large parse trees are costly to
evaluate

Less formal attribute grammars are used by compiler
writers to check static semantic rules
Organization of Programming Languages-Cheng (Fall 2005)
52
Describing (Dynamic) Semantics
<for_stmt>  for (<expr1>; <expr2>; <expr3>)
<assign_stmt>  <var> = <expr>;
What is the meaning of each statement?
 dynamic semantics
How do we formally describe the dynamic
semantics?
Organization of Programming Languages-Cheng (Fall 2005)
53
Describing (Dynamic) Semantics

There is no single widely acceptable notation or
formalism for describing dynamic semantics

Three formal methods:
Operational Semantics
Axiomatic Semantics
Denotational Semantics



Organization of Programming Languages-Cheng (Fall 2005)
54
Operational Semantics
 Describe
the meaning of a program by executing
its statements on a machine, either simulated or
actual. The change in the state of the machine
(memory, registers, etc.) defines the meaning of
the statement.
Execute
Statement
Initial State:
Final State:
(i1,v1), (i2,v2), …
(i1,v1’), (i2,v2’), …
Organization of Programming Languages-Cheng (Fall 2005)
55
Operational Semantics
 To
use operational semantics for a high-level
language, a virtual machine in needed.
 A hardware pure interpreter would be too
expensive
 A software pure interpreter also has problems:
1. The detailed characteristics of the particular
computer
would make actions difficult to understand
2. Such a semantic definition would be
machinedependent.
Organization of Programming Languages-Cheng (Fall 2005)
56
Operational Semantics
Approach: use a complete computer simulation
1. Build a translator (translates source code to
the machine code of an idealized computer)
2. Build a simulator for the idealized computer
 Example:
C Statement:
Operational
Semantics:

for (expr1; expr2; expr3) {
…
}
expr1;
loop: if expr2 = 0 goto out
…
expr3;
goto loop
out:
…
Organization of Programming Languages-Cheng (Fall 2005)
57
Operational Semantics
 Valid
statements for the idealized computer:
iden = var
iden = iden + 1
iden = iden – 1
goto label
if var relop var goto label
 Evaluation
of Operational Semantics:
 Good if used informally (language manuals,
etc.)
 Extremely complex if used formally (e.g., VDL)
Organization of Programming Languages-Cheng (Fall 2005)
58
Axiomatic Semantics

Based on formal logic (first order predicate calculus)

Approach:
 Each statement is preceded and followed by a logical
expression that specifies constraints on program
variables


The logical expressions are called predicates or assertions
Define axioms or inference rules for each statement
type in the language

to allow transformations of expressions to other expressions
Organization of Programming Languages-Cheng (Fall 2005)
59
Axiomatic Semantics
{P} A = B + 1 {Q}
where P: precondition
Q: postcondition




Precondition: an assertion before a statement that states
the relationships and constraints among variables that are
true at that point in execution
Postcondition: an assertion following a statement
A weakest precondition is the least restrictive precondition
that will guarantee the postcondition
Example: A = B + 1 {A > 1}
 Postcondition: A > 1
 One possible precondition: {B > 10}
 Weakest precondition:
{B > 0}
Organization of Programming Languages-Cheng (Fall 2005)
60
Axiomatic Semantics


Program proof process:
 The postcondition for the whole program is the desired results.
 Work back through the program to the first statement.
 If the precondition on the first statement is the same as the
program spec, the program is correct.
An axiom for assignment statements
{P} x = E
{Q}
Axiom: P = Qx  E



(P is computed with all instances of
x replaced by E)
Example: a = b / 2 – 1 {a < 10}
Weakest precondition:
b/2 – 1 < 10
Axiomatic Semantics for assignment:
{Qx  E } x = E {Q}
Organization of Programming Languages-Cheng (Fall 2005)
=> b < 22
61
Axiomatic Semantics
 Inference
rule for Sequences:
{P1} S1 {P2}, {P2} S2 {P3}
{P1} S1; S2 {P3}
 Example:
Y = 3 * X + 1; X = Y + 3; {X < 10}
 Precondition for second statement: {Y < 7}
 Precondition for first statement: {X < 2}
{X < 2} Y = 3 * X + 1; X = Y + 3; {X < 10}
Organization of Programming Languages-Cheng (Fall 2005)
62
Axiomatic Semantics: Axioms

An inference rule for logical pretest loops
{P} while B do S end {Q}
(I and B) S {I}
{I} while B do S {I and (not B)}
where I is the loop invariant (the inductive hypothesis)
Organization of Programming Languages-Cheng (Fall 2005)
63
Axiomatic Semantics: Axioms
 Characteristics
of the loop invariant: I must meet
the following conditions:
 P => I -- the loop invariant must be true initially
 {I} B {I} -- evaluation of the Boolean must not change the validity of
I
 {I
and B} S {I}
-- I is not changed by executing the body of the
loop
 (I
and (not B)) => Q
 The loop terminates
-- if I is true and B is false, is implied
Organization of Programming Languages-Cheng (Fall 2005)
64
Loop Invariant
 The
loop invariant I is a weakened version of the
loop postcondition, and it is also a precondition.
I
must be weak enough to be satisfied prior to the
beginning of the loop, but when combined with the
loop exit condition, it must be strong enough to
force the truth of the postcondition
Organization of Programming Languages-Cheng (Fall 2005)
65
Evaluation of Axiomatic Semantics
 Developing
axioms or inference rules for all of the
statements in a language is difficult
 Utility:
 It is a good tool for correctness proofs, and
 an excellent framework for reasoning about
programs,
 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
Organization of Programming Languages-Cheng (Fall 2005)
66
Denotational Semantics
 Based
 The
on recursive function theory
most abstract semantics description method
 Originally
developed by Scott and Strachey
(1970)
Organization of Programming Languages-Cheng (Fall 2005)
67
Denotational Semantics (cont’d)
 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
Organization of Programming Languages-Cheng (Fall 2005)
68
Denotation 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
Organization of Programming Languages-Cheng (Fall 2005)
69
Denotational Sem.: Program State
 The
state of a program is the values of all its
current variables
s = {<i1, v1>, <i2, v2>, …, <in, vn>}
 Let
VARMAP be a function that, when given a
variable name and a state, returns the current
value of the variable
VARMAP(ij, s) = vj
Organization of Programming Languages-Cheng (Fall 2005)
70
Denotational Semantics

Based on recursive function theory

The meaning of language constructs are defined by the
values of the program's variables

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
Organization of Programming Languages-Cheng (Fall 2005)
71
Denotational Semantics

Decimal Numbers
 The following denotational semantics description maps decimal
numbers as strings of symbols into numeric values
 Syntax rule:
<dec_num>  0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
| <dec_num> (0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9)
 Denotational Semantics:
Mdec('0') = 0, Mdec ('1') = 1, …, Mdec ('9') = 9
Mdec (<dec_num> '0') = 10 * Mdec (<dec_num>)
Mdec (<dec_num> '1’) = 10 * Mdec (<dec_num>) + 1
…
Mdec (<dec_num> '9') = 10 * Mdec (<dec_num>) + 9
Note: Mdec is a semantic function that maps syntactic objects to a set of nonnegative decimal integer values
Organization of Programming Languages-Cheng (Fall 2005)
72
Expressions
expressions onto Z  {error}
 We assume expressions are decimal numbers,
variables, or binary expressions having one
arithmetic operator and two operands, each of
which can be an expression
 Map
Organization of Programming Languages-Cheng (Fall 2005)
73
3.5 Semantics (cont.)
Me(<expr>, s) =
case <expr> of
<dec_num> => Mdec(<dec_num>, s)
<var> =>
if VARMAP(<var>, s) == undef
then error
else VARMAP(<var>, s)
<binary_expr> =>
if (Me(<binary_expr>.<left_expr>, s) == undef
OR Me(<binary_expr>.<right_expr>, s) =
undef)
then error
...
else
if (<binary_expr>.<operator> == ‘+’ then
Me(<binary_expr>.<left_expr>, s) +
Me(<binary_expr>.<right_expr>, s)
else Me(<binary_expr>.<left_expr>, s) *
Me(<binary_expr>.<right_expr>, s)
Organization of Programming Languages-Cheng (Fall 2005)
74
Assignment Statements

Maps state sets to state sets
Ma(x := E, s) =
if Me(E, s) == error
then error
else s’ =
{<i1’,v1’>,<i2’,v2’>,...,<in’,vn’>},
where for j = 1, 2, ..., n,
vj’ = VARMAP(ij, s) if ij <> x
= Me(E, s) if ij == x
Organization of Programming Languages-Cheng (Fall 2005)
75
Logical Pretest Loops
 Maps
state sets to state sets
Ml(while B do L, s) =
if Mb(B, s) == undef
then error
else if Mb(B, s) == false
then s
else if Msl(L, s) == error
then error
else Ml(while B do L, Msl(L, s))
Organization of Programming Languages-Cheng (Fall 2005)
76
Loop Meaning
 The
meaning of the loop is the value of the
program variables after the statements in the
loop have been executed the prescribed
number of times, assuming there have been no
errors
 In essence, the loop has been converted from
iteration to recursion, where the recursive
control is mathematically defined by other
recursive state mapping functions
 Recursion, when compared to iteration, is
easier to describe with mathematical rigor
Organization of Programming Languages-Cheng (Fall 2005)
77
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, they are of little use to
language users
Organization of Programming Languages-Cheng (Fall 2005)
78
Summary
 BNF
and context-free grammars are equivalent
meta-languages
 Well-suited for describing the syntax of
programming languages
 An attribute grammar is a descriptive formalism
that can describe both the syntax and the
semantics of a language
 Three primary methods of semantics description
 Operational, axiomatic, denotational
Organization of Programming Languages-Cheng (Fall 2005)
79
Descargar

Implementation, Syntax, and Semantics