CS 326 Programming Languages, Concepts and Implementation Instructor:

CS 326 Programming Languages, Concepts and Implementation Instructor:

CS 326 Programming Languages, Concepts and Implementation Instructor: Mircea Nicolescu Lecture 2 Compilation and Interpretation Compiler translates into target language (machine language), then goes away The target program is the locus of control at execution time Interpreter stays around at execution time Implements a virtual machine whose machine language is the high-level language

2/69 2 Compilation and Interpretation Interpretation Greater flexibility, better diagnostics Allow program features (data types or sizes) to depend on the input Lisp, Prolog: program can write new pieces of itself and execute them on the fly Java: compilation, then interpretation Compilation Better performance

Many decisions are made only once, at compile time, not at every run time Fortran, C 3/69 3 Programming Environments Set of tools:

Editors Pretty printers Style checkers Preprocessors Debuggers Linkers Module management Browsers (cross-references) Profilers Assemblers

Separate programs: Unix Integrated environment: Microsoft Visual C++, Visual Works for Smalltalk 4/69 4 Overview of Compilation Front end Back end 5/69 5

Lexical Analysis (Scanner) Compute greatest common divisor, in Pascal: program gcd (input, output); var i, j : integer; begin read (i, j); while i <> j do if i > j then i := i j else j := j i; writeln (i) end. The scanner extracts tokens (smallest meaningful units):

program gcd ( input , output ) ; var i , j : integer ; begin read

( i , j ) ; while ..... 6/69 6 Syntax Analysis (Parser) The parser uses a context-free grammar, as a description of the language syntax: program PROGRAM identifier ( identifier more_identifiers ) ; block .

block labels constants types variables subroutines BEGIN statement more_statements END more_identifiers , identifier more_identifiers more_identifiers .. Generates a parse tree, that reflects the structure of the program Shows how the sequence of tokens can be derived under the rules of the grammar 7/69 7 Syntax Analysis (Parser)

Parse tree: 8/69 8 Semantic Analysis Discovers meaning in a program Static semantic analysis (at compile time): Identifiers declared before use Subroutine calls provide correct number and type of arguments Dynamic semantics (cannot be checked at compile time, so generate code to check at run time): Pointers dereferenced only when refer to a valid object

Array subscript expressions lie within bounds Simplifies the parse tree syntax tree Maintains symbol table, attaches attributes 9/69 9 Semantic Analysis Syntax tree: 10/69 10 Back end Target code generation

Generate assembly or machine language Traverses the syntax tree to generate elementary operations: loads and stores, arithmetic operations, tests and branches Code improvement (optional) A.k.a optimization Transform program into a new version with same functionality, but more efficient (faster, uses less memory) 11/69 11 Compilation Review Lexical analysis (scanner)

Break program into primitive components, called tokens (identifiers, numbers, keywords, ...) Formal models: regular grammars and finite automata Syntactic analysis (parser) Create parse tree of the program Formal models: context free grammars and pushdown automata Symbol table Store information about declared objects (identifiers, procedure names, ...) 12/69 12

Compilation Review Semantic analysis Understand relationships between tokens in the program Code improvement (machine independent) Rewrite syntax tree to create a more efficient program Code generation Convert parsed program into executable form in target (machine) language Code improvement (machine dependent) Rewrite target code to create a more efficient program Will discuss scanning and parsing

13/69 13 Formal Translation Models Formal language: a set of strings of symbols drawn from a finite alphabet Examples: L1 = { black, white } L2 = { 1, 01, 001, 0001, ... } L3 = { ab, aabb, aaabbb, ... } L4 = English 14/69 14

Grammars Nonterminals: a finite set of symbols:

Terminals: a finite set of symbols: the, boy, girl, ran, ate, cake Start symbol: one of the nonterminals: 15/69 15 Grammars Rules (productions): A finite set of replacement rules:

ran | ate

the boy | girl | cake 16/69 16 Grammars Replacement operator (written =>): Replace a nonterminal by the right hand side of a rule Derivation: =>


=> the ... => the boy ate the cake First rule Second rule Fifth rule Can also derive: => ... => the cake ate the boy Syntax does not imply correct semantics 17/69 17

Grammars Concepts: Derivation: series of replacements to obtain string of terminals from start symbol Sentential form: any intermediate string of symbols during derivation Yield: the final sentential form, containing only terminals Language generated by grammar G: the set of all possible yields 18/69 18 Parse Trees Grammar:

B 0B | 1B | 0 | 1 Generate 010 Derivation: B => 0B => 01B => 010 Parse tree 19/69 19 Parse Trees But derivations may not be unique: Grammar: S SS | (S) | () Generate (())() Derivation1:

S => SS =>(S)S =>(())S =>(())() Derivation2: S => SS => S() =>(S)() =>(())() Parse tree Different derivations but get the same parse tree 20/69 20 Parse Trees Ambiguity Grammar: S -> SS | (S) | () Generate ()()() Unique derivation:

S => SS => SSS => ()SS => ()()S => ()()() Ambiguous grammar one string has multiple parse trees 21/69 21 Readings Chapter 2, up to 2.2.3 22/69 22

Recently Viewed Presentations

  • Theories Of Romantic Relationships

    Theories Of Romantic Relationships

    Social Exchange Theory is an 'economic theory' - it takes the view that social relationships are run in a similar way to a business - people are negotiating to get the best deal. SET. is based on the principles of...
  • video slide - Gavilan College

    video slide - Gavilan College

    Most chordates have bones along their nerve cord, making them vertebrates. Not all - some of our phylum are invertebrates! Sea squirts (subphylum urochordates) have a larval form that is built much like a tadpole, barring a lack of bone,...
  • God&#x27;s Outreach Ministry Int

    God's Outreach Ministry Int

    Deborah or Debra (Hebrew: דְּבוֹרָה,; "Bee") continued served as the fourth, and the only female Judge' & Prophetess at "the palm tree of Deborah" in southern Ephraim between Ramah and Bethel in pre-monarchic Ancient Israel in the Old Testament (Tanakh).She...
  • Modern Language Association (MLA) Format

    Modern Language Association (MLA) Format

    Modern Language Association(MLA) Format. Samples of Common Source Citations for Annotated Bibliographies and Works Cited ... The Facts On File Companion to . British Poetry, 19th Century. 2009. Bloom's. (URL address or DOI) MLA Format - Scholarly Journal from a...
  • Legal English and the Common Law - DidatticaWeb 2.0

    Legal English and the Common Law - DidatticaWeb 2.0

    Thoburn. case arose out of a dispute concerning EU obligations in the national legal system. "In my opinion a constitutional statute is one which. conditions the legal relationship between the citizen and the state, in some general or overarching manner,...
  • The Affluent Society - Amphitheater Public Schools

    The Affluent Society - Amphitheater Public Schools

    The Affluent Society. American Abundance. ... Jack Kerouac wrote . On the Road. Charles Bukowski was famous for his drunken, crude poetry. African American Entertainers. African Americans struggled to find acceptance. Rock n' Roll singers faced fewer obstacles.
  • Colorado Regulation 7 Upstreams LDAR Future Standards Certification

    Colorado Regulation 7 Upstreams LDAR Future Standards Certification

    For the oil & gas sector, Reg. 7 is now a hydrocarbon rule (i.e., it includes methane) Reg. 7 applies statewide, not just the ozone non-attainment area; and covers new and existing sources. Reg. 7 covers oil & gas exploration...
  • Summary of Seismic Network in Mozambique

    Summary of Seismic Network in Mozambique

    3. Seismic Activity in Mozambique. The zones with the greatest concentration of earthquakes are: African Rift extension to the south from Lake Niassa and heading south more or less parallel between meridians 33⁰-35⁰ E to the parallel 25⁰ S;