Chapter 1

  • Domains: scientific (floating point), business (report, decimal), AI (symbolic), system programming (efficiency), scripting, special-purpose
  • evaluation criteria: readability (most importnat), writability, reliability, cost, portability, generality, well-definess
  • architecture: Von Neumann
    • data / instruction in memory
    • CU, ALU
  • category
    • impertive (variables, assigment, statements, iteration)
    • functional (function, function, and functions)
    • logic (rule-based)
    • object-oriented (encapsulation, inheritance, dynamic type binding)
  • Compilation
    • Programs are translated into machine language
  • Pure Interpretation
    • Programs are interpreted by another program known as an


  • Hybrid Implementation Systems
    • A compromise between compilers and pure interpreters

Chapter 3

  • syntax: structure of a language
  • semantic: meanings
  • lexeme: smallest syntactic unit
  • recognizer 是給一篇文章,要辨識是不是這個語言 / generator 是給文法,要你生一篇文章
  • grammar: _finite_ nonempty set of rules
  • sentential form: derivation 裡的每一句的都算是 (including non-terminals and terminals)
  • precedence 高的會在樹下面
  • EBNF 中 {} 是 0 or more times
  • Attribute Grammar
    • 每個 node X 都有一些 attributes A(X)
    • X → X_1 … X_n
    • synthesized attribute of X 是用 X_1 .. X_n 的 A() 組成的,也就是只跟 children 有關(因為他們的是你傳下去的)
    • inherited attribute of X_j 則是用 X, X_1 … X_{j-1} 組成的,也就是只跟 parent 還有 left sibling 有關
    • predicated function used to ensure syntax and static sementics rules are obeyed
    • intrinsic attribute 是 left nodes 的 synthesized attribute(照定義,會跑出樹)
  • operational semantics
  • axiomatic semantics: proving correctness
    • rule of inference
    • (I and B) S {I} ⇒ {I} while B do S end {Q} 重點是 I 要滿足 P ⇒ I / \{I and B\} S \{I} / (I and not B)) ⇒ Q / loop termination
  • denotational semantics: based on recursion function
    • 對每個 entity 定義一個 mathematical object 然後定義把每個 entity 對應到 mathematical object 的 function
    • 跟 operational semantics 的差別是,前者用 code algo. 來定義,後者走數學來定義


Chapter 5

  • names
    • length
    • case
    • keyword (context sensitive) / reserve words
  • variable
    • (name, addr, value, type, lifetime, scope)
  • binding, an association
    • static (before runtime and cannot change) / dynamic (at runtime or changeable)
    • lifetime 只要還在 memory 中就算,即使你摸不到也可以(在 scope 外)
    • stack-dynamic 是說那種在 stack 上長的變數,有這種才有辦法做 recursion
    • implicit heap-dynamic 是說像是 Perl/JavaScript string (or array) 那種
    • explicit heap-dynamic 執行中產生出來的變數 例如 new
  • strong typing 是說所有 type errors 都可以抓出來
    • 有 union or record 的就不是了
    • Java 跟 Ada 幾乎算是,但是像是 Java 把 int 跟 floating 做運算,因為 int 會被強迫轉 floating 所以不算
  • type compatibility
    • name type compatibility: type name 一樣才算
    • structure type compatibility: 兩個 type 有一樣個 structure 就算,比較寬,但是很難做
  • scope
    • static, often encourages global
    • dynamic, convenient but poor readability
  • referencing enviroment 是說你現在可以摸到的所有 variables
  • named constant 是說它的 value *只*有在它 bind 到 storage 的時候才會 bind,換句話說,之後就不能改
  • initialization 則是說 value 在 variable bind 到 storage 的時候,一起 bind 上去

Chapter 7

  • operators 的 precedence 跟 associativity
    • 影響到的是相鄰的 operator,也就是中間只差一個 operand
    • 解決 function side affects 的方法
      • 不准寫!可是這樣子太苦了(不能玩 two-way parameters)
      • 固定 evaluation 順序,但是一些 optimization 就不能做了,像是 common subexpression elimation (CSE)
  • coercion 是指 implicit type conversion,會減少 compiler detect type error 的機會
  • short-circuit 會被 expression 的 side effect 影響,比如說 (a>b) || (b++/3),因為有 short-circuit,你不能確定 b 到底有沒有 +1
  • (C, C++, Jave) (a>b) ? a : b = 0,反正左邊是拿 l-value,所以沒差

Chapter 8

  • 所有的 control statements 都可以只用 two-way selection 跟 pretest 的 loop 幹掉
  • dangling else
  • Dijkstra, 1975, Guarded Commands
    • 在 selection 的時候,你不應該假設每個條件的順序
    • 主要是希望曾在寫程式的時候,就可以去驗證
course/programminglanguage.txt · Last modified: 2014/04/20 09:44 by