PRELIM EXAM

Syntax and Semantics

Introduction

• Syntax

  • Form and structure of the program code

• Semantics

  • Meaning of the program code

    • meaning of expressions, statements, control structures

• Syntax and semantics provide a language’s definition

  • Users of a language definition

    • Implementers

    • Programmers (the users of the language)

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 of syntactic unit of a language

  • *, sum, begin

• A token is a category of lexemes

  • identifiers

Formal Definition of languages

• Generators (Grammars)

  • A device that generates sentences of a languages

  • One can determine if the syntax of a particular sentence is syntactically correct by comparing it to the structure of the generator

• Recognizers (Parser)

  • A recognition device reads input strings over the alphabet of the language and decides whether the input strings belong to the language

    • syntax analysis part of a compiler

BNF / Context- Free Grammars

• Context-Free Grammars (CFG)

  • Developed by Noam Chomsky in the mid-1950s

  • Language generators, meant to describe the syntax of natural languages

  • Define a class of languages called context-free languages

• Backus-Naur Form (1959)

  • Invented by John Backus to describe Algol 58

• BNF and CFG represent equal concepts

BNF - CFG Fundamentals

• In BNF, abstractions are used to represent classes of syntactic structures-they act like syntactic variables (also called nonterminal symbols, or just nonterminals)

• Terminals are lexemes or tokens

• A rule has a left-hand side (LHS), which is a nonterminal, and a right-hand side (RHS), which is a string of terminals and/or nonterminals

BNF / CFG Grammar Rules

• An abstraction (or nonterminal symbol) can have more than one RHS

<stmt> -> <single_stmt> | begin <stmt_list> end

BNF - CFG Fundamentals

• Nonterminals are often enclosed in angle brackets

  • Example of BNF rules:

  <ident_list> → identifier | identifier , <ident_list>
  <if_stmt> → if <logic_expr> then <stmt>
  

• Grammar: a finite non-empty set of rules

• A start symbol is a special element of the nonterminals of a grammar

CFG Formal Definition

• A context-free grammar G is defined by the 4-tuple G = (V, Σ, R, S) where

  1. V is a finite set; each element v in V is called a non-terminal character or a variable. Each variable represents a different type of phrase or clause in the sentence

  2. Σ is a finite set of terminals, disjoint from V, which make up the actual content of the sentence. The set of terminals is the alphabet of the language defined by the grammar G

  3. R is a finite relation from V to (V + Σ)*, where the asterisk represents the Kleene star operation. The members of R, are called the (rewrite) rules or productions of the grammar. (also commonly symbolized by a P)

  4. S is the start variable (or the start symbol), used to represent the whole sentence (or program). It must be an element of V

Example: Describing List

• Sytanctic lists are described using recursion

<ident_list> → ident
							| ident ',' <ident_list>

Derivation

• A derivation is a repeated application of rules, starting with the start symbol and ending with a sentence (all terminal symbols)

An example Grammar

<program> → <stmts>
<stmts> → <stmt> | <stmt> ';' <stmts>
<stmt> → <var> '=' <expr>
<var> → 'a' | 'b' | 'c' | 'd'
<expr> → <term> '+' <term> | <term> '-' <term>
<term> → <var> | 'const'

An Example Derivation

<program> => <stmts> => <stmt>
					=> <var> = <expr>
					=> a = <expr>
					=> a = <term> + <term>
					=> a = <var> + <term>
					=> a = b + <term>
					=> a = b + const

Derivations - Some Notions

• Every string of symbols in a derivation is a sentential form

• A sentence is a sentential form that has only terminal symbols

• A leftmost derivation is one in which the leftmost nonterminal in each sentential form is the one that is expanded. Accordingly a rightmost derivation for the rightmost nonterminal

  • A derivation may be neither leftmost nor rightmost

Parse Tree

• A parse tree represents a hierarchical representation of a derivation by means of a tree

• Example:

Ambiguity in Grammars

• A grammar is ambiguous if and only if it generates a sentential form (the language generated by the grammar comprises at least one word) that has two or more distinct parse trees

Example for Ambiguous Grammar

<expr> → <expr> <op> <expr> | const
<op> → ‘+' | '-'

word: const – const + const

Unambiguous Grammar

• Grammar on the example before in ambiguous form:

  • We get some form of operator precedence

  <expr> → <expr> - <term> | <term>
  <term> → <term> + const | const
  

Associativity of Operators

• Operator associativity can also be indicated by a grammar

• Example:

<expr> -> <expr> + <expr> | const
(ambiguous)
<expr> -> <expr> + const | const
(unambiguous) 

Extended BNF

• Optional Parts are placed in brackets []

<proc_call> -> ident [(<expr_list>)]

• Alternative parts of RHS are placed inside parentheses and separated via vertical bars

<term> -> <term> (+|-) const

• Repetitions (0 or more) are placed inside braces {}

<ident> -> letter {letter|digit}

BNF and EBNF Examples

• BNF

  <expr> → <expr> + <term>
  				| <expr> - <term>
  				| <term>
  <term> → <term> * <factor>
  				| <term> / <factor>
  				| <factor>
  

• EBNF

  <expr> → <term> {(+ | -) <term>}
  <term> → <factor> {(* | /) <factor>}
  

Variations in EBNF

• Alternative RHS are put on separate lines

• Use of colon instead of →

• Use of opt for optional parts

• Use of oneof for choices

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-maker”

  • Still 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 values of AGs:

  • Static semantics specification for static semantics checks

Attribute Grammars - Definition

• Def: An attribute grammar is a context-free grammar 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

• Let $X_0 -> X_1...X_n$ be a rule

• Functions of the form $S(X_0) = f(A(X_1), ..., A(X_n))$ define synthesized attributes

• Initially, there are intrinsic attributes on the attributes on the leaves

Attribute Grammars: An Example

• Syntax

  <assign> -> <var> = <expr>
  <expr> -> <var> + <var> | <var>
  <var> -> id
  

• Attributes

  • actual_type: synthesized with the non-terminals <var> and <expr>

  • expected_type: inherited with the non-terminal <expr>