Programming Languages - Fundamentals - Cao Hoàng Trụ

1 Programming Languages Fundamentals Cao Hoaøng Truï Khoa Coâng Ngheä Thoâng Tin Ñaïi Hoïc Baùch Khoa TP. HCM 2 Contents • Evolution and classification • Formal syntax and semantics • Compilation and interpretation 3 Machine Language CPU I/O Memory 0101001001101011 1101111001001001 0001101010101010 4 Machine Language Operation Code Operands Instruction: 10110011010010010011010110110001 5 Assembly Language A := B + C if A = 0 then body MOV r0, B ; move B into register r0 ADD r0, C ; add MOV A, r0 ; store BNE L1 ; branch if result not equal 0 body L1: 6 Language Levels Natural Language Machine Language Low-Level High-Level 7 What Makes a Good Language? • Clarity, simplicity, unity of language concepts • Clarity of program syntax • Naturalness for the application • Support for abstraction • Ease of program verification 8 What Makes a Good Language? • Programming environment • Portability of programs • Cost of use  program execution  program translation  program creation, testing, use  program maintenance 9 Language Classification • Imperative  von Neumann Fortran, Pascal, Basic, C  object-oriented Smalltalk, Eiffel, C++, Java • Declarative  functional Lisp, ML, Haskell  dataflow Id, Val  logic Prolog, VisiCalc 10 Von Neumann Languages • Most familiar and successful • Imperative statements • Modification of variables Fortran, Pascal, Basic, C, 11 Object-Oriented Languages • Imperative statements • Message passing among objects Smalltalk, Eiffel, C++, Java 12 Functional Languages • Recursive definition of functions (lambda calculus) • Expressions of function composition Lisp, ML, Haskell 13 Logic Languages • Logical facts and rules (predicate logic) • Computation as theorem proving Prolog, VisiCalc 14 Dataflow Languages • Computation as token flow among nodes • Inherently parallel model Id, Val 15 Contents • Evolution and classification • Formal syntax and semantics • Compilation and interpretation 16 Formal Syntax and Semantics • Computer languages must be precise • Both their form (syntax) and meaning (semantics) must be specified without ambiguity • Both programmers and computers can tell what a program is supposed to do 17 Formal Syntax • Abstract syntax • Context-free grammars • Backus-Naur formalism (BNF) • Syntax diagrams • Derivations and parse trees 18 Abstract Syntax • Syntactic class • Syntactic form 19 Example: Expressions • Syntactic class: E expression I identifier C constant O operator • Syntactic form: E = I | C | E O E | (E) 20 Example: Expressions a * (2 + b) E O E 21 Example: Expressions a - b - c E O E 22 Abstract Syntax • Advantage: simple • Disadvantages: No terminal symbols defined Ambiguous 23 Context-Free Grammars • Start symbol • Non-terminals • Terminals • Productions A  a1 | a2 | | an (Noam Chomsky, 1959) 24 Example: Unsigned Integers 6 2 5 7 3 25 Example: Unsigned Integers • Start symbol • Non-terminals , • Terminals 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 • Productions  | 26 Backus-Naur Formalism ::= | (John Backus, 1960) 27 Example: Expressions 12 * 3 + 4 28 Example: Expressions • Start symbol • Non-terminals , , , , , • Terminals 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, +, -, *, / 29 Example: Expressions • Productions:  |  |  | ()  + | -  * | / 30 Syntax Diagrams term expression term_op term expression 31 Derivations   +  +  * + 4  * 3 + 4  12 * 3 + 4 32 Parse Trees + 12 3 4 * 33 Parse Trees + 12 3 4 * 34 Formal Semantics • Operational semantics • Denotational semantics • Axiomatic semantics 35 Operational Semantics • A virtual computer to execute a program. • A set of formally defined operations to specify how the internal state of the virtual computer may change. 36 Denotational Semantics • Each program construct is a function that maps an input to an output. • A program is a composition of functions. 37 Axiomatic Semantics • The effect of a statement is defined via its precondition and postcondition. • A set of axioms and rules to define the effect of program constructs. 38 Axiomatic Semantics {P} S {Q} precondition statement postcondition 39 Axiomatic Semantics {PxE} x := E {P} • Axiom: 40 Axiomatic Semantics {x  2} x := x + 1 {x  3} E = x + 1 P = x > 3 PxE = x + 1 > 3 = x > 2 41 Axiomatic Semantics if ({P} S1 {Q})  ({Q} S2 {R}) then {P} S1 ; S2 {R} • Rule: 42 Contents • Evolution and classification • Formal syntax and semantics • Compilation and interpretation 43 Compilation and Interpretation Compiler Source program Target program Target program Input Output Interpreter Source program Output Input 44 Compilation and Interpretation • Interpreter: better flexibility and diagnostics • Compiler: better performance 45 Phases of Compilation Scanner (lexical analysis) Parser (syntactic analysis) Semantic analysis Machine-independent code optimisation Target code generation Machine-specific code optimization Character stream Token stream Parse tree Intermediate code Optimised intermediate code Target code Optimised target code 46 Phases of Compilation Scanner (lexical analysis) Parser (syntactic analysis) c := a + b * 7 id1 := id2 + id3 * 7 47 Phases of Compilation Parser (syntactic analysis) id1 := id2 + id3 * 7 := id1 id2 id3 + * 7 48 Phases of Compilation Semantic analysis CNV (7, , t1) * (id3, t1, t2) + (id2, t2, t3) ASS (t3, , id1) := id1 id2 id3 + * 7 49 Phases of Compilation CNV (7, , t1) * (id3, t1, t2) + (id2, t2, t3) ASS (t3, , id1) Machine-independent code optimisation * (id3, 7.0, t1) + (id2, t1, id1) 50 Phases of Compilation MOV reg, id3 MUL reg, 7.0 ADD reg, id2 MOV id1, reg * (id3, 7.0, t1) + (id2, t1, id1) Target code generation 51 Exercises • Define a formal syntax for a simple language supporting only the assignment statement and arithmetic expressions. • Write the derivation and draw the parse tree of ‘c := (a + b) * 7’ using the defined syntax.