Lit / Sco09

Sco09: Michael L. Scott. Programming Language Pragmatics

  • Third Edition. Elsevier Morgan Kaufmann. Burlington 2009.

1. Introduction

Spectrum of languages

  • functional: z.B. LISP, ML, Haskell
  • dataflow: z.B. Id, Val
  • logic or constraint-based: Prolog, manchmal auch SQL oder XSLT
  • von Neumann Languages: Fortran, C, ..: Modifikation von Variabeln durch Assingments
    • scripting: csh, PHP, JavaScript ...
  • OO meist von Neumann, aber CLOS ist Erweiterung von LISP

typische CompilationsPhasen: Kommunikation über SymbolTable

  • CharacterStream
    • Scanner = lexical analysis
  • TokenStream
    • Parser = Syntax Analysis
  • Abstract Syntax Tree oder intermediate form
    • Machine independent code improvement (optional)
  • (modified) intermediate form
    • Target Code Generation
  • target language e.g. Assembler
    • Machine specific code improvement
  • (modified) target language

2- Programming Language Syntax

  • regular expression besteht aus
    1. a character
    2. the empty string ε (alternativ: λ)
    3. Concatenation (zwei benachbare regular expressions, alternativ: .)
    4. | choice von zwei regularExpressions (alternativ: +)
    5. * Kleene star: 0 - n Wiederholungen der vorangehenden regularExpression
    6. (Klammern um Mehrdeutigkeiten zu eliminieren)
  • CFG = ContextFreeGrammars = BNF = BackusNaurForm
    • Regular Expression, statt Kleene Star aber Recursion
    • productions: variable/nonTerminal → rightHandSide
    • mehrere Produktionen derselben Variablen: Choice
  • Derivation aus einem Input einen Parse Tree erstellen, mit ⇒ für derives, z.B. für a + 2: expr ⇒ expr op expr ⇒ id op expr ⇒ id + expr ⇒ id + int
  • CFL Context Free Language: Menge von Strings, die durch eine CFG erzeugt/erkannt werden
  • CFG kann verschieden formuliert werden, z.B. eindeutig, links- rechts-Assoziative, Operatoren Prio kann eingebaut werden oder nicht → möglichst sinnvolles für den Rest des Compilers suchen

2.2 Scanning

  • mit longest possible token rule
  • Syntax in Automaten umwandeln (mit Generator)
  • NFA = nonDeterministicFiniteAutomaton 1. Schritt und dann in
  • DFA = DeterministicFiniteAutomaton
  • lexx, yacc: RE → DFA
  • DFA minimieren
  • lookAhead, je nach Syntax mehr oder weniger
  • 2 Implementationen
    • nested case
    • table driven: currentState x inputChar → newState
  • pragma = significantComment = Hint für den Compilers, z.B. Optimierungen usw., aber auch SemantikVeränderungen möglich

2.3 Parsing

  • LL-Parser = LeftToRight, LeftMostDerivation
    • topdown parser
    • Parser muss nächste Produktion Voraussagen (PREDICT)
    • recursive descent parser, meist handGeschrieben: jedes nonTerminal wird Prozedur
      • Case Statement für jedes LookAheadToken, und in entsprechend Prozedur springen
      • 2 Möglichkeit: Token ist Anfang einer Subproduktion → FIRST
      • oder Anfang der FolgeProduktion → FOLLOW
      • diese Parser haben nur zwei Resultat ok und fail und kein backTracking. Mein Parser 3 Ausgänge ok, notFound, fail und backtracking
    • table driven top down parser, meist generiert. nur eine Prozedur aber zwei Tables
      • parseTab: notTerminal x terminal → {error, production}
      • prodTab: production → list of symbols
    • Left Recursion = A →+ A α recursiveDescentParser geht in RekursionsLoop
    • CommonPrefixes = mehrere Produktionen mit selben Anfang
    • LeftRecursion und CommonPrefixes können automatisch entfernt werden = LeftFactoring
  • LR = LeftToRight, RightMostDerivation
    • bottomUp parser
    • shift = jedes Terminal auf Stack legen , bis oberste Symbols die rechte Seite einer Produktion sind, dann
    • reduce = diese Symbole durch linke Seite ersetzen.
    • Besser Grammatik umschreiben, damit es effizienter wird (niedrigerer Shift Stack).
  • LL(n) oder LR(n); mit n tokens look ahead

3. Names, Scopes, Bindings

  • Binding: Assoziation z.B. zwischen Namen und beNanntem
  • BindingTime: von LanguageDesign, -Implementation über programWriting, Compile, Link, Load, oder Run-Time (mit selber wieder vielen Varianten)
    • deep binding: ReferencingEnvironmnet wird bei erstem Erstellen des Bindings gewählt
    • shallow binding: ReferencingEnvironmnet wird bei jeder Benutzung des Bindings gewählt
  • Object Lifetime und StorageManagement: static, stack, heap
  • Scope Rules: meist zur CompileZeit bestimmt
    • Nested Subroutines wie in Algol
      • Benutzung vor Deklaration erlaubt/verboten ⇔ globalen/äusseren Variabeln (die unsichtbar werden)
      • NestedBlock (begin ... end, statt nur Routinen)
  • Modules = Packages = Namespaces = Collections von Routinen, Variabeln, Typen usw.
    • innerhalb Modul gegenseitig sichtbar
    • von aussen nur sichtbar, falls exportiert
    • closed scope: äusseres innen nur sichtbar, falls importiert
    • modules as managers: klassische enthält ein Modul nur eine Instanz seiner Abstraktionen, sollen mehrere gebraucht werden, ist ein Manager nögig, der Instanzen erstellt/wieder freigibt + ZusatzParameter in jeder Prozudur, für angesprochene Instanz
    • Modules as Types: Für jedes Modul kann das Programm beliebig viele ModulObjekte deklarieren (enthält natürlich OO Konzepte) - aber das ist ja auch nicht immer nötig, z.B. um ein Projekt in subProjekte aufzuteilen (v.a. wenn Sprache Klassen unterstützt)
    • oft sind Module Basis für Separate Compilation. Dann haben sie häufig einen declaration/header und eine implementation/body part
  • dynamic scoping: current binding, ist das most recently während der Ausführung erzeugte, aber noch nicht zerstörte
  • the meaning of name within a scope
    • Alias: zwei Namen zeigen auf dasselbe Objekt, z.B. globale Variabele und Parameter, oder 2 Pointers: verbieten gewisse Optimierungen, bzw. Compiler muss sie erkennen oder ausschliessen können
    • Overloading: Name der auf mehrere Objekte zeigen kann, z.B. overloaded Operators in C (auswahl durch types), oder Enumeration Werte in verschiedenen Enumerationen (mit EnumerationsType qualifizieren). Nahe verwande Konzepte sind
      • Coercion: Compiler wandelt Type automatisch in anderen um (int -> doulbe für Parameter von Prozedur)
      • Polymorphism: arbeiten mit verschiedenen Types
        • subType/inheritance Polymorphism
        • parameteric polymorphism
          • excplicit parametric polymorphism = genericity (z.B. Templates in C++)subType/inheritance Polymorphism
          • implicit parametric polymorphism: Compiler leitet Typen ab, z.B. ML
  • Binding of referencing envionment
    • welcher Scope gibt für den Call einer Prozedur, die als Parameter übergeben wurde?
    • Subroutine Closure: explicite Darstellung des referencingEnvironment plus Subroutine zusammen
    • value usage:
      • first class: kann als Parameter weitergegeben, von einer Subroutine zurückgegeben, oder in Variable assinged werden
      • second class: nur als Parameter weitergeben
      • third class: keine der drei Möglichkeiten
    • first class subroutines (mit closure) können dangling pointers erzeugen: entweder nichts zerstören (also heap allocation und Garbage collector aufräumen lassen) oder zusätzlich Regeln!
  • Macro Expansion: reines Text replacement - war äusserst hilfreich in Assembler. Aber Rest des Compiler weiss nichts von MacroExpansion und alle weiteren Regeln wirken dann zufällig, z.B. PrecedenceRules

4. Semantic Analysis

AST mit Attributen annotieren oder dekorieren, entweder on the fly während der AST Generierung oder im Nachhinein in separaten Durchgängen (oder in kleinerrer Granularität, z.B. Prozedurweise)

5. Target machine Architecture

6. Controlflow

  • expression evaluation: smalltalk midFix notation
    • precedence and associativity
    • assignments, references ↔ values
  • structured and unsturcture flow
    • goto, multilevel return, nonLocal goto, errors and exceptions, Continuations (verallgemeinerung von nonLocal goto):
    • sequencing (entscheidend be sideffects)
    • selection: if elsif* else
    • short circuited conditions
    • case/switch
    • iteration: enumeration controlled loops, oder allgemeiner wie in Algol, true Iterator oder Iterator Objects
    • logically controlled loops
    • iterations ↔ recursion, tail recursion
      • applicative order evaluation: evaluate Argument vor call
      • normal order evalution: Arguments erst bei Bedarf im Call evaluieren, lazy evaluation
    • nondeterminacy: Wahl zwischen Controlpaths ist absichtlich unspezifiziert

7 Data Types

2 Haupt Zwecke

  • implicit Context (z.B. int oder float add)
  • Begrenzen möglich Operation (z.B. Verbot String und Zahl zu addieren)

3 ways to think about types

  • denotational (Type al Menge)
  • constructive (primitive und composite types)
  • abstraction based: interface mit gewissen Operationen

Type Checking

  • Type Equivalence: structural equivalece ↔ name equivalence
  • Type Conversins, Casts, (un)checked
  • universal reference Type
  • Type inference
  • reference model und recursive data structures

8. Subroutines and Control Abstractions

p. 383