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

Recently Viewed Presentations

  • Time Management - Physician Assistant Education Association

    Time Management - Physician Assistant Education Association

    Describe different strategies for effective time management. Evaluate their time management style. Apply time management strategies to reconcile shifting priorities within a day. Analyze tasks common to program directors, prioritize those tasks, and develop a strategy to efficiently complete them....
  • Mosquito Assessment and Control Unmanned Aerial Systems (MAC-UAS)

    Mosquito Assessment and Control Unmanned Aerial Systems (MAC-UAS)

    Purpose: Document change of a particular site over time with regard to standing water or other land use relevant to mosquito management. Aerial Photographic Monitoring (March 8, 2017) (August 10, 2017) Visual Assessment of Mosquito Habitat.
  • Presentation title here - University of New South Wales

    Presentation title here - University of New South Wales

    Multidisciplinary care in general Practice: The Teamwork Study Mark Harris, Centre for Primary Health Care and Equity Investigators 1.1 Chief Investigators CIA Professor Mark Harris CIB Dr Judy Proudfoot CIC Professor Justin Beilby CID Professor Patrick Crookes CIE E/Prof Geoffrey...
  • The Jacksonville 2050 High School Civil Engineering Competition

    The Jacksonville 2050 High School Civil Engineering Competition

    Each high school will be assigned at least one Professional Mentor/Advisor. All mentors/advisors will have a civil engineering degree or a related degree in engineering or construction and will help students with leadership, the use of technology, data gathering, presentations,...
  • SEM vs ESEM

    SEM vs ESEM

    Tractive effort (?) is the lesser of: Maximum tractive effort (the amount of force that can be accommodated by the tire-pavement interface) Engine-generated tractive effort (function of engine torque, transmission and differential gearing, drive wheel radius)
  • Exploring Tools and Techniques for Distributed Continuous ...

    Exploring Tools and Techniques for Distributed Continuous ...

    Exploring Tools and Techniques for Distributed Continuous Quality Assurance Adam Porter [email protected] University of Maryland Quality Assurance for Large-Scale Systems Modern systems increasingly complex Run on numerous platform, compiler & library combinations Have 10's, 100's, even 1000's of configuration options...
  • Imperialism - Montgomery Township School District

    Imperialism - Montgomery Township School District

    Imperialism in AfricaAfrica in the Early 1800s In the early 1800s, Africa was three times the size of Europe; its many people spoke hundreds of languages and had developed varied governments. In the early 1800s, North Africa and the Sahara...
  • Making Content Comprehensible for English Language Learners

    Making Content Comprehensible for English Language Learners

    With your table group use your laptops to search for 6 strategies, materials, or resources that are believed to help an English Language Learner (ELL) gain access to learning or understand the content in the classroom.