Compilation vs Interpretation



Compilation vs Interpretation

Compilation – Takes source program, and transforms it into a target program. The target program take “input” (user or otherwise) and turns it into output. Typically goes away during execution.

Interpretation – Takes both the source program and input, and generates output. Typically stays around during execution.

Compilation “Phases” – These aren’t really phases as they work together to get the job done sometimes.

Scanner – Lexical analysis. Characters are read in from the source file, tokens are outputted to “next” stage.

-Removes comments

-Caches strings, identifiers, numbers

-Evaluates numeric constants

-Associates tokens with line numbers

Parser – Syntactical analysis. Reads in tokens, and generates a parse tree dependent on the “grammar” of the language.

Next - Semantic analysis and intermediate code generation.

Beyond – you’re on you own for this stuff.

Grammar -

-It is impossible to describe the syntax of almost any programming language or natural language using grammar.

-Tokens are used to make manageable units of a program. Grammars are defined in terms of tokens. Regular expressions are used for tokens.

-DFA:Deterministic Finite-state Automata are recognizers for regular expressions.

-Grammar rules define valid sentences in a language

-4 Types of grammars:

Type 3 Regular grammar – accepted by finite state automata

Type 2 Context-free grammar - accepted by push-down automata

Type 1 Context-sensitive grammar – accepted by linear bounded automata.

Type 0 unrestricted – accepted by Turing machines

-Syntax and semantics of a language is described by a meta-language.

-Abstract syntax – all possible forms for each syntactic class. i.e. tells when a statement is well formed and valid.

-Concrete syntax – Phrase structure of a well-formed sentence in the grammar. i.e. tells what a statement means.

-CFGContext-Free Gramars can be described using BNF, EBNF, and syntax charts

-Language vs Grammar : A language is the set of all possible statements/sentences that can be formed using a grammar.

-A grammar is ambiguous if a string has more than one parse tree.

-Abstract syntax tree is a condensed form of a parse tree that is appropriate for later stages of compilation. Leaves out all but the necessary parts of the structure of a program.

Why PLC?

-Why study programming languages?

-Breadth: to assess new languages, you must know many others

-Depth: features and interactions of your favorite language. Helps identify pros and cons.

-Insight: Language shapes our thinking, determines what we think about and how we think

-Adaptability: new features are added to working languages, and organizations switch to different languages

Models: beyond the imperative execution model

-Knowing a language entails 3 basic concepts: syntax, semantics, and pragmatics.

-Who cares about PLs? Users, language designers, compiler writers, CEOs/CTOs/etc, PLC.

History of PLs

-Machine language(binary) -> Symbolic Assemblers -> Fortran

Fortran – Formula Translator – shifted focus to the problem not the machine.

Cobol – Business application

Algol 60 – Precursor to Pascal, C, Ada, C++, Java – admired but not adopted.

LISP – List processing language – Radical advance. Programs and data kept uniformly as lists. Losely typed

Simula 67 - Class notion for simulation purposes, objects, garbage collector, class exts. Originally Algol with classes.

Smalltalk – Alan Kay at Xerox in 1971 – Introduced the term OOP. Formalized the concept.

Pascal – Nikalus Wirth – simple structure, compilation, and to teach. User defined types. Was alternative to Algol 68’s complexity.

C – developed circa 1970s. C++ in mid 80s. Concise expressive syntax. Compilers could generate high quality code.

Imperative (Procedural) Languages – C, Fortran, Pascal, Ada…

-Most widely known and used PLs.

-Programs execute statement by statement.

-Closely models conventional sequential processors.

-Programmer deals with both logic (what to be done) and control flow(how do you want).

Functional Languages – Lisp(Scheme), Haskell, SML

-Programs are expressions to be evaluated.

-Aims to minimize side effects.

-Alternative evaluation mechanisms are possible – lazy or eager.

Object Oriented Languages – Smalltalk, Objective-C, C++, Java

-Identity, encapsulation of data and behavior.

-Inheritance and common interfaces.

-Objects with same interface are treated uniformly.

-Subclassing.

Logic Programming Languages – Prolog, CLP, Mozart

-Functional or constraint logic.

-Inherently polymorphic

-No variable clutter or control structures.

Other paradigms

Scripting - Perl, Tcl, Awk, PHP, Python

String processing – ICON, SNOBOL

Parallel/Distributed – Occam, Parallaxis, Emerald

Markup/Stylesheet – SGML, XML, DSSSL, XSL

Specification – Z

Special Purpose – APL, Matlab, Lego/Mindstorms

................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download