Introduction

• 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
• A token is a category of lexemes

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

• 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

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 :

An attribute grammar is a context-free grammar G = (S, N, T, P) with the following additions:

1. For each grammar symbol x there is a set A(x) of attribute values
2. Each rule has a set of functions that define certain attributes of the nonterminals in the rule
3. Each rule has a (possibly empty) set of predicates to check for attribute consistency

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>

Semantics

• There is no single widely acceptable notation or formalism for describing semantics
• Several needs for a methodology and notation for semantics:

1. Programmers need to know what statements mean
2. Compiler writers must know exactly what language constructs do
3. Correctness proofs would be possible
4. Compiler generators would be possible
5. Designers could detect ambiguities and inconsistencies

Operational Semantics

• 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

• To use operational semantics for a high-level language, a virtual machine is needed
• Uses of operational semantics:

1. Language manuals and textbooks
2. Teaching programming languages

• Two different levels of uses of operational semantics:

1.    Natural operational semantics
2.    Structural operational semantics

• Evaluation

1.    Good if used informally (language manuals)
2.    Extremely complex if used formally

Denotational Semantics

• Based on recursive function theory
• The most abstract semantics description method
• Originally developed by Scott and Strachey (1970)
• The process of building a denotational specification for a language:

1. Define a mathematical object for each language entity
2. 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