C H a P T E R T W O

C H A P T E R TWO Syntax and Semantic Chapter 2 Topics Introduction Organization of Language Description Describing Syntax Formal Methods of Describing Syntax The Way of Writing Grammars Formal Semantic Semantic 2 Introduction

Who must use language definitions? Other language designers Implementers Programmers (the users of the language) Syntax - the form or structure of the expressions, statements, and program units Semantics - the meaning of the expressions, statements, and program units

3 Introduction Language description syntax and semantic Syntax how to write program Semantic:

what does program mean 4 Introduction Dates represented by D (digit) and Symbol (/) DD/DD/DDDD 01/02/2001 Same -> syntax -> US Jan 2, 2001

Others Feb 1, 2001 syntax, different semantic 5 Organization of Language Description Tutorials Reference Manuals Formal Definition 6 Tutorials What

the main constructs of the language are How they are meant to be used Useful examples for imitating and adapting Introduce syntax and semantics gradually 7 Reference Manuals Describing the syntax and semantics Organized around the syntax Formal syntax and informal semantic Informal semantic : English explanations and examples to the syntactic rules Began with the Algol60 : free of ambiguities

8 Formal Definition Precise description of the syntax and semantics Aimed at specialists Attaches semantic rules to the syntax Conflicting interpretations from English explanation Precise formal notation for clarifying subtle point 9 Syntactic Elements

Character set Identifiers Operator symbols Keywords / Reserved words Comments Separator & Brackets Expression Statements 10 Describing Syntax 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) 11 A Program Fragment Viewed As a Stream of Tokens 12 Describing Syntax

Formal approaches to describing syntax: Recognizers - used in compilers Generators generate the sentences of a language (focus of this lecture) 13 Formal Methods of Describing Syntax Context-Free

Grammars Developed by Noam Chomsky in the mid1950s Language generators, meant to describe the syntax of natural languages Define a class of languages called context-free languages 14 CFG for Thai <> <>

<> <> -> -> <><><> -> | | -> | | <> -> <><><>

15 Formal Methods of Describing Syntax Backus-Naur Form (1959) Invented by Backus and Naur to describe Algol 58 BNF is equivalent to context-free grammars A metalanguage is a language used to

describe another language. 16 Backus-Naur Form (1959) BNF elements T - terminal symbols N - nonterminal symbols S - start symbol P - set of rules or production 17 BNF grammar Def: A grammar production has the form A -> where A is a nonterminal symbol is a string of nonterminal and

terminal symbols This is a rule; it describes the structure of a while statement while ( ) 18 Formal Methods of Describing Syntax A rule has a left-hand side (LHS) and a right-hand side (RHS), and consists of terminal and nonterminal symbols A grammar is a finite nonempty set of rules An abstraction (or nonterminal symbol)

can have more than one RHS | begin end 19 BNF Nonterminal

Identifier Integer Expression Statement Program Terminal The basic alphabet from which programs are constructed binaryDigit -> 0 binaryDigit -> 1 binaryDigit -> 0 | 1 Integer -> Digit | Integer Digit

Digit -> 0|1|2|3|4|5|6|7|7|8|9 Integer -> Digit Integer -> Integer Digit Integer -> Integer Integer Digit Integer -> Digit Digit 20 Formal Methods of Describing Syntax Syntactic lists are described using recursion ident | ident, A derivation is a repeated application of

rules, starting with the start symbol and ending with a sentence (all terminal symbols) 21 Formal Methods of Describing Syntax An example grammar: | ; = a | b | c | d + | - | const 22

Derivation Grammar Integer -> Digit | Integer Digit Digit -> 0|1|2|3|4|5|6|7|7|8|9 Is 352 an Integer? Integer => Integer Digit => Integer Digit Digit => Digit Digit Digit => 3 Digit Digit

=> 35 Digit => 352 23 Derivation Grammar -> = -> A | B | C -> + | *

| ( ) | Statement A=B*(A+C) Leftmost derivation => = => A = => A = * => A = B * => A = B * ( ) => A = B * ( + ) => A = B * ( A + )

=> A = B * ( A + ) => A = B * ( A + C ) 24 Formal Methods of Describing Syntax An example derivation: => => => = => a = => a = + => a = + => a = b + => a = b + const

25 Derivation Every string of symbols in the 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 A derivation may be neither leftmost nor rightmost 26

Parse Tree A hierarchical representation of a derivation = a +

const b 27 Parse Tree for the Expression x+2*y 28 Formal Methods of Describing Syntax A grammar is ambiguous if it generates a sentential form that has two or more

distinct parse trees 29 An Ambiguous Grammar | - 30 Two Different Parse Trees for the AmbExp 2 3 4 Is the Grammar Ambiguous? | const / | - 31

Is the Grammar Ambiguous? Yes | const / | const

- const / const const - const /

const 32 An Unambiguous Expression Grammar If we use the parse tree to indicate precedence levels of the operators, we cannot have ambiguity - | / const | const

- / const const const 33 Formal Methods of Describing Syntax

Derivation: => - => - => const - => const - / const => const - const / const 34 An Ambiguous If Statement The Dangling Else Grammatical Ambiguity 35 Formal Methods of Describing Syntax Extended

BNF (just abbreviations): Notation used in the course textbook Optional parts: -> ident ( )opt Alternative parts: -> [+ | -] const Put repetitions (0 or more) in braces ({ }) -> letter {letter | digit}* 36

Formal Methods of Describing Syntax Extended BNF (just abbreviations): Another frequently used notation Optional parts: -> ident [ ( )] Alternative parts: -> (+ | -) const

Put repetitions (0 or more) in braces ({ }) -> letter {letter | digit} 37 BNF and EBNF BNF: + | - | * | / | EBNF:

{[+ | -] }* {[* | /] }* 38 The Way of Writing Grammars The productions are rules for building string Parse Trees : show how a string can be built Notation to write grammar Backus-Naur Form (BNF) Extended BNF (EBNF) Syntax charts : graphical notation 39 BNF

::= + | - | ::= * | / | ::= number | name | ( ) 40 Extended BNF

::= { ( + | - ) } ::= { ( * | / ) } ::= ( ) | name | number 41 Syntax Diagram Can be used expression to visualize rules

term + term factor * / factor ( expression )

name number 42 Conventions for Writing Regular Expressions 43 Semantics or meaning Semantic : any property of a construct The semantic of an expression 2+3 Point of view An expression evaluator A type checker

An infix-to-postfix translator Semantic its value : 5 type integer string: + 2 3 44 Formal Semantic Static semantic : compile-time properties - type correctness, translation - determined from the static text of a program, without running the program on actual data. Dynamic semantic : run-time properties

- value of expression - the effect of statement - determined by actually doing a computation 45 Semantic Methods Several method for defining semantics The approaches are used for different purposes by different communities. The values of variables a and b in a+b depend on the environment. An environment consists of bindings from variable to values. 46

Assignment Draw a parse tree using BNF grammar on slide page 40 2 +3 ( 2 + 3 ) 2 + 3 * 5 ( 2 + 3 ) * 5 2 + ( 3 * 5 ) 47 Assignment (cont.)

Draw parse trees using the following grammar while expr do id := S ::= id := expr | if expr then S expr | if expr then S begin id := expr end else S if expr then if expr | while expr do S | begin SL end then S else S SL ::= S ; | S ; SL 48 Assignment (cont.) Write

the grammar in any language by using BNF or EBNF or syntax diagram Write the keywords in that languages Deadline : next class 49 References Books

Programming Languages: Principles and Paradigms Allen B. Tucker & Robert E. Noonan Concepts of Programming languages Robert W. Sebesta Java BNF http://cui.unige.ch/db-research/Enseignement/ analyseinfo/JAVA/ BNFindex.html 50

Assignment : Draw a parse tree using BNF grammar on slide page 35 using the following grammar S ::= id := expr | if expr then S

| if expr then S else S | while expr do s | begin SL end SL ::= S ; | S ; SL 2+3 (2+3) 2+3*5 (2+3)*5 2+(3*5) while expr do id := expr

begin id := expr end if expr then if expr then S else S 51