Algorithm-Program

Algorithm-Program

Programming Languages (formal languages) -- How to describe them? -- How to use them? (machine and human) Syntax: Describe the structures of programs Grammars -- Ambiguous (sometimes) solution: using unambiguous only Semantics: Describe the meaning of programs Textbook, manuals -Confusing (always) solution: denotation semantics (for nuts only) 02/07/20 IT 327

1 English Grammar The man hit the ball. subject verb object The man saw the girl with a telescope.

subject verb object The purpose of grammar: To tell whether a sentence is valid.(old fashion) Chomsky: To have a device that can generate all valid sentences of the target language (from a root). 02/07/20 IT 327 2 Noam Chomsky (1928 - )

Syntactic Structures (1957) Generative Grammar 02/07/20 A valid sentence is generated from the root according to some fixed rules (grammar). IT 327 3 Directly copied from Chomskys book 02/07/20 IT 327 4 Syntactic Structures

the man hit the ball S NP VP T N Verb the man hit 02/07/20

IT 327 NP T N the ball 5 A generative grammar in Syntactic Structures root S NP non-terminal symbols

VP T + N Verb + NP T the | a N man | ball | car Verb 02/07/20 NP + VP

terminal symbols .. hit | take | took | run | ran .. IT 327 6 Grammar 1 Backus-Naur Form, BNF Grammar 2 ::= ::= ::= ::= ::= ::= loves | hates|eats ::= the

::= a | the ::= man | car| ball ::= dog | cat | rat ::= hit | took ::= | ::= | ::= ::= loves | hates|eats |hit | took ::= a | the ::= the ::= dog | cat | rat | man | car | ball 02/07/20 IT 327 7 Deviation: the sequence of processes that generate a sentence ::= ::= ::=

::= the ::= man | car | ball := hit | took Grammar 1 the the man the man the man hit the man hit the man hit the the man hit the ball the man hit the ball 02/07/20 IT 327

8 (American Heritage Dict.) Parse: v. To break (a sentence) down into its component parts of speech with an explanation of the form, function, and syntactical relationship of each part. the dog loves the cat 02/07/20 the loves dog the cat loves the dog the cat IT 327 9

::= ::= ::= loves | hates|eats ::= a | the ::= dog | cat | rat Grammar A Parse Tree the dog the loves dog the cat 02/07/20 IT 327 loves the cat

doesnt have a parse tree 10 Restrictions on Grammars Diagram in terms of the sizes of the set of restrictions Unrestricted Grammars (type-0) Context Sensitive (type-1) Context Free (type-2) Right/Left Linear Grammars (type-3) Why context sensitive grammars have less restrictions than context free grammars?

02/07/20 IT 327 11 Chomsky Hierarchy Diagram in terms of the sizes of the language families Regular Expressions (type-3) Context-free languages (type-2) Context-sensitive languages (type-1) Computable (formal) languages (type-0) 02/07/20

IT 327 12 A grammar for Arithmetic Expression Example: ((a+b)*c) Is this expression valid? ::= + | * | ( ) | a | b | c ( ) ( * ) (( ) * ) (( + ) * ) ((a + ) * ) ((a +b) * )

((a+b)*c) Yes 02/07/20 IT 327 13 ( A Parse Tree for ((a+b)*c) ) *

( ) c + a 02/07/20 IT 327 b 14 Parse Trees for a+b*c ?

+ * + a c a * b b c What is the meaning of a+b*c 02/07/20

IT 327 15 Grammars in BNF (Backus-Naur Form) A BNF grammar consists of four parts: The finite set of tokens (terminal symbols) The finite set of non-terminal symbols The start symbol The finite set of production rules ::= ::= ::= ::= the ::= man | ball ::= hit | took 02/07/20 IT 327

16 Constructing Grammars float a; boolean a, b, c; int a, b; Using divide and conquer to simplify the job. 1. Data types, variable names (identifiers) 2. Statements, programs One variable, one type, but this is not grammars job to make sure) 02/07/20 IT 327 17

Using divide and conquer ::= ; Primitive type names ::= boolean | byte | short | int | long | char | float | double ::= | , ::= | = 02/07/20 IT 327 18 Programs stored in files are just sequences of characters, but we want to prepare them into tokens before further analysis. Tokens are atoms of the program

Tokens: e.g. Reserved words identifiers (const, x, fact) keywords (if, const) operators (==) constants (123.4), etc. How to divide a program (a sequence of characters in a file) into a sequence of tokens? 02/07/20 IT 327

19 Lexical Structure & Phrase Structure Grammars so far have defined phrase structure: how a program is built from a sequence of tokens We also need to use grammars to define lexical structure: how a text file is divided into tokens 02/07/20 IT 327 20 Separate Grammars Usually there are two separate grammars to construct a sequence of tokens from a file of characters (Lexical Structure) ::= |

::= | | ::= | | ::= | | | to construct a parse tree from a sequence of tokens (Phrase Structure) 02/07/20 IT 327 21 Separate Compiler Passes Scanner tokens string parser parse tree (more to do afterwards) 02/07/20 IT 327

22 Historical Note #1 Early languages sometimes did not separate lexical structure from phrase structure Early Fortran and Algol dialects allowed spaces anywhere, even in the middle of a keyword Other languages like PL/I or early Fortran allow keywords to be used as identifiers This makes them difficult to scan and parse It also reduces readability 02/07/20 IT 327 23 Historical Note #2 Some languages have a fixed-format lexical structure -column positions are significant. Examples:

One statement per line (i.e. per card) First few columns for statement label Etc. Early dialects of Fortran, Cobol, and Basic Almost all modern languages are free-format: column positions are ignored (exception: Python) 02/07/20 IT 327 24 Backus-Naur Form, BNF Some use or = instead of ::= Some leave out the angle brackets and use a distinct typeface for tokens Some allow single quotes around tokens, for example to distinguish | as a token from | as a meta-symbol Interesting operator!!

Or not! Sir, please Step away from the ASR-33 02/07/20 IT 327 25 EE+T |E-T |T TT*F|T/F|F F(E)| a | b | c Backus-Naur Form, BNF ::= + | ::= * | ::= ( ) | a | b | c ::= | s1 | s2 ::= if then else | if then ::= e1 | e2

IT 327 02/07/20 26 Other Grammar Forms BNF variations EBNF variations Syntax diagrams 02/07/20 IT 327 27 EBNF Variations Additional syntax to simplify some grammar chores: {x} to mean zero or more repetitions of x [x] to mean x is optional (i.e. x | )

() for grouping | anywhere to mean a choice among alternatives Quotes around tokens, if necessary, to distinguish from meta-symbols 02/07/20 IT 327 28 EBNF Examples Anything that extends BNF this way is called an Extended BNF: EBNF There are many variations ::= if then [else ] ::= { ;} ::= { ( | ) ;} 02/07/20

IT 327 29 Syntax Diagrams Syntax diagrams (railroad diagrams) ::= if then else if-stmt if 02/07/20 expr then IT 327 stmt

else stmt 30 Bypasses ::= if then [else ] if-stmt if 02/07/20 expr then IT 327 stmt

else stmt 31 Branching ::= + | * | ( ) |a|b|c exp exp + exp exp *

exp ( exp ) a b c 02/07/20 IT 327 32 Loops ::= {+ }

exp addend + 02/07/20 IT 327 33 Syntax Diagrams, Pro and Con Easier for human to read (follow) Difficult to perceive the phrase structures (syntax tree)? Harder for machine to read (for automatic parser-generators) 02/07/20 IT 327

34 Conclusion We use grammars to define programming language syntax, both lexical structure and phrase structure Connection between theory and practice Two grammars, two compiler passes Parser-generators can produce code for those two passes automatically from grammars (compiler tools) 02/07/20 IT 327 35

Recently Viewed Presentations

  • FORKLIFT TRAINING  Rewrote the training requirement for forklift

    FORKLIFT TRAINING Rewrote the training requirement for forklift

    The Counterbalance. Load Weight 9000lbs. Force downward 8000lbs. A forklift works on the principle of a cantilever. A load on a beam (the forks) supported by a fulcrum (the front wheels) is counterbalanced by a weight on the other end...
  • S F O D E N H Y

    S F O D E N H Y

    END RHYME - the rhyming words come at the end of the lines INTERNAL RHYME - rhyming words come within the same line NEAR RHYME (also called off rhyme, slant rhyme or approximate rhyme) the sounds are almost but not...
  • FAMILIAS NUMEROSAS Plan Superfamilias

    FAMILIAS NUMEROSAS Plan Superfamilias

    Con una cuota de bolsillo del 12,5%. Fuente: INE y HomeScan ACNielsen P.* - * Plan Superfamilias Plan Superfamilias Objetivos: Mejorar la imagen de Carrefour, apoyando a un target especialmente sensible a las iniciativas de ayuda económica Fidelizar a un...
  • Citations and bibliographies - University of Brighton

    Citations and bibliographies - University of Brighton

    Learning Resource Centre Information Skills tutorial Citations and bibliographies Before you begin… This presentation is intended to be a basic guide only Please check your School's policy on referencing - you should find this in your Student handbook Or consult...
  • This booklet is designed to help you build

    This booklet is designed to help you build

    The Woodbridge Arena was buzzing last night as this year's basketball championships reached their climax, The favourites made their mark early on and set the pace for the game as the Eagles struggled against the superior height of Johnson and...
  • PRESENTATION Attribute Based Access Control A New Access

    PRESENTATION Attribute Based Access Control A New Access

    PDP PEP Subject Resource Subject AA Resource AA Environment AA ABAC Policy Authority AA: Attribute Authority Service Provider Attribute & Policy Services Web Service SOAP Message Handler Policy Store Policy Decision Service Service Registry Identity Store SOAP Client SOAP Msg...
  • David Croft Educational Technology Masters Program  University of

    David Croft Educational Technology Masters Program University of

    * David Croft Educational Technology Masters Program University of Hawai'i at Manoa Department of Education, Hawai'i 3 class periods of automotive technology, 2 class periods of digital media, 1 class period of graphic communication Students are 14 to 18 years...
  • Biology 211 Anatomy & Physiology I

    Biology 211 Anatomy & Physiology I

    White Matter: Nervous tissue of the CNS consisting of myelinated axons & dendrites and their supporting glia Cortex: On the surface of the brain (only on cerebrum and cerebellum) Nucleus: Deeper, surrounded by white matter Coronal Section of Brain Cross...