编程语言、编译器、解释器、虚拟机等底层笔记

Compiler.md

####<<编译原理>>笔记

#####第一章 编译原理简介

• 阶段
  • 前端：词法分析、语法分析、中间代码生成
  • 后端：代码优化、目标机器代码生成
• 使用
  • 编译器
  • 文本转换
  • 智能提示
  • 重构
  • 类型推导

#####第二章 简单的一遍翻译

• 上下文无关文法
  • 符号集、终结点符号、非终结点符号、初始符号、产生式
  • 文法的歧义(有多于一种语法分析树）
  • 操作符、操作数；前缀、中缀、后缀；优先级、左结合、右结合；
  • 左递归、右递归、左递归树、右递归数
  • 左递归消除技术
• 抽象语法树
• 具体语法树（分析树）
• 递归下降算法Lex
  • 双缓存LookUp

递归可枚举语言，上下文相关语言，上下文无关语言，正规语言

#####第三章 词法分析

• lex and parser
  • token and identity
  • linearly sequence -> tree
• 正规表达式
  • 并（concatenation）
  • 或（alternation）
  • 克林闭包（Kleene star）
  • 正规表达式转NFA
    • Thompson构造法
    • 将正规表达式分解为最基本的子表达式，分别构造其NFA，然后组合
      • e: -[s]->(i)-[e]->(f)
      • a: -[s]->(i)-[a]->(f)
      • s|t: -[s]->(i) (-[e]->(()N(s)())-[e]|-[e]->(()N(t)())-[e]) ->(f)
      • st: -[s]->(i)N(s)()N(t)(f)
      • s*: -[s]->(i)-[e]->(()N(s)())-[e]->(f)&(i)-[e]->(f)&()-[e]->()
• 最小化（压缩）状态转表
• NFA
  • e-clousure(s)、e-clousure(T)、move(T,a)
  • 子集构造法->DFA

   function NFA2DFA(inputs,s0,Dstates,Dtrans)
   	A=e-closure({s0})
   	Dstates.Add(A,false)
   	while T in Dstates.PopUnlableSet() do
   		for c in inputs do
   			U = e-closure(move(T,c))
   			if not Dstates.Contain(U) then
   				Dstates.Add(U,false)
   			end
   			Dtrans[T,c]=U
   		end
   	end
   end
   function e-closure(states,T)
   	closure=T
   	stack=T
   	while not stack.IsEmpty() do
   		t = stack.top();
   		stack.pop();
   		for u in states do
   			if edege(t,u)==e then
   				if not closure.Contain(u) then
   					closure.add(u)
   					stack.push(u)
   				end
   			end
   		end
   	end
   end
  

  • 双堆栈模型

   function (S,F,a,s0,nextchar,e-closure,move)
   	S=e-closure({s0})
   	a=nextchar()
   	while not a=eof do
   		S=e-closure(move(S,a)
   		a=nextchar()
   	end
   	if not S.Intersect(F).IsEmpty() then return "yes" end
   	return "no"
   end
  

  • 基于NFA 模式匹配
• DFA
  • 状态集
  • 初始状态
  • 接受状态
  • 基于DFA 模式匹配
    • NFA的重要状态：有标记为非e的出边的状态
    • 两个子集是等同的iff它们的重要状态相同并且同时包含或者不包含NFA的接受状态
    • 将NFA的重要状态与正规表达式的符号相关联，只有字母表上一个符号出现在正规表达式中，Thompson构造法才创建一个重要状态。
    • NFA有且只有一个接受状态，但该状态不是重要的，因为没有出边，通过在正规表达式r右边链接一个结束符#， 使得接受状态成为重要状态。非重要的NFA状态用大写字母表示。
    • 用语法树扩展正规表达式，叶子节点是符号表中的符号或者e标记，内节点表示操作符，分别有cat-节点，or-或者star-节点。 对每个非e的叶子节点分配唯一的整数位置。
    • 正规表达式节点位置函数：nullable(n),firstpos(n),lastpos(n),followpos(n)

     function nullable(node)
     	if node.IsLeaf() and node.IsE() then 
     		return true 
     	end
     	if node.IsLeaf() and (not node.IsE()) then
     		return false
     	end
     	if node.IsOrNode() then
     		c1=node.Left()
     		c2=node.Right()
     		return nullable(c1) or nullable(c2)
     	end
     	if node.IsCatNode() then
     		c1=node.Left()
     		c2=node.Right()
     		return nullable(c1) and nullable(c2)
     	end
     	if node.IsStarNode() then
     		return true
     	end
     end
    

     function firstpos(node)
     	if node.IsLeaf() and node.IsE() then 
     		return {}
     	end
     	if node.IsLeaf() and (not node.IsE()) then
     		i=node.pos()
     		return {i}
     	end
     	if node.IsOrNode() then
     		c1=node.Left()
     		c2=node.Right()
     		return firstpos(c1).Union(firstpos(c2))
     	end
     	if node.IsCatNode() then
     		c1=node.Left()
     		c2=node.Right()
     		if nullable(c1) then
     			return firstpos(c1).Union(firstpos(c2))
     		else
     			return firstpos(c1)
     		end
     	end
     	if node.IsStarNode() then
     		return true
     	end
     end
    

    lastpos的计算和firstpos类似，只需调换c1和c2，则计算followpos的股则如下： 1. 如果n是cat节点，具有左子节点c1和右子节点c2，并且i是lastpos(c1)中的一个位置， 则firstpos(c2)的所有位置在follow(i)中。 2. 如果n是star节点，并且i是lastpos中的一个位置，则所有firstpost(n)中的位置都在followpos(i)中。
    • 从正规表达式构造DFA

     function (r,inputs)
     	r=root(concat('(',r,')#'))
     	Dstates={firstpos(r))
     	while Dstates.HasUnLabel() do
     		T=Dstates.GetNextUnLable()
     		for a in inputs do
     			for p in T do
     				U=followpos(p)
     				a=getnode(p).Symbol()
     				if not U.IsEmpty() and (not Dstates.Contain(U)) then
     					Dstates.Add(U,unlable=true)
     				end
     				Dtran[T,a]=U
     			end
     		end
     	end
     end
    

    • 最小化DFA的状态数

#####第四章 语法分析

• 典型语法分析算法
  • Cocke-Younger-Kasami算法和Earley算法，能分析任何文法，但生成编译器效率低
  • 自顶向下法
  • 自底向上法
• 语法错误处理
  • 错误类型
    • 词法错误：标识符、关键字、操作符拼写错误
    • 语法错误：括号不匹配、少了分号
    • 语义错误：操作符作用于不相容的操作数
    • 逻辑错误：死循环、无限递归
  • 错误恢复
    • 紧急错误恢复
    • 短语级错误恢复
    • 出错产生式
    • 全局纠正
• 上下文无关文法
  • 分析树和推导
  • 二义性
  • 正规表达式和上下文无关文法比较
    • 使用正规表达式的场景
      • 语言的词法规则通常比较简单，不必动用文法
      • 对于记号，正规表达式更简洁易于理解
      • 正规表达式易于自动构造词法分析器，文法构造词法分析器难
      • 把语法分为词法和非词法，利于编译器前端的模块化
    • 功能差别
      • 正规表达式通常描述标识符、常数、关键字
      • 文法在描述括号配对、begin-end配对、if-then-else等嵌套结构，正规表达式此时无力
  • 验证文法所产生的语言：归纳法
  • 消除二义性：改写
  • 消除左递归
    • 消除直接左递归：A->Aα1|...|Aαm|β1|...|βn => A->β1A'|...|βnA' + A'->α1A'|...αmA'|e
    • 消除隐式左递归

   function(A1,A2,...,An)
   	for i=1:n do
   		for j=1:i-1 do
   			Ai->Ajγ+Aj->δ1|δ2|...|δk => Ai->δ1γ1|δ2γ2|...|δkγk
   		end
   		Ai->Aiα1|...|Aiαm|β1|...|βn => Ai->β1Ai'|...|βnAi' + Ai'->α1Ai'|...αmAi'|e
   	end
   end
  

  • 提取左因子

   function(A1,A2,...,An)
   	for i=1:n do
   		Ai->αiβi1|...|αiβin|γ => Ai->αiAi'|γ+Ai'->βi1|...|βin
   	end
   end
  

  • 非上下文无关语言结构
    • 不可用上下文无关文法表示的例子：
      • L1={wcw|w \in (a|b)*} 标识符的声明先于引用
      • L2={a^nb^mc^nd^m|m>=1,n>=1} 过程声明的形参个数和过程引用的实参个数应该一致
      • L3={a^nb^nc^n|n>=0} 在键盘上敲打字母键，退格同样次数，敲打同样次数下划线：下划线标记的单词集合，正规表达式(abc)*则可以描述之
    • 可用上下文无关文法表示的例子：
      • L1'={wcw^R|w \in (a|b)*,w^R表示w的逆序}
      • L2'={a^nb^nc^md^m|m>=1,n>=1}
      • L3'={a^nb^n|n>=1} 这个例子不能用正规表达式表示
    • 两个性质
      • 有穷自动机不能计数，如上L3'不能用正规表达式
      • 上下文无关文法能计2项的数，不能计3项的数，如上L3和L3'的对比
• 预测语法分析

functions look(products,inputs)
	a=inputs.begin();
	<s,t>=products.states.begin()
	while a and <s,t> do
		if a is terminal then
			if match(s,t,a) then 
				a=inputs.next()
				<s,t>=products.states.next() 
			else
				return false
			end
		else
			store.a=a
			store.inputs=inputs
			subproducts = a.getproducts()
			for subproduct in subproducts do//递归下降
				if look(a.getproducts(),inputs.rest()) then
					<s,t>=products.states.next()
					a=inputs.next()
					break
				else//回朔
					a=store.a
					inputs=store.inputs
				end	
			end
		end
	end
	return products.states.finish()
end

• 非递归的预测语法分析（表格驱动），对比NFA双堆栈模型

function look(stack,table,inputs,outputs)
	--stack是文法符号序列，栈底是$,初始时stack含有文法的开始符号和下边的$
	--table是分析表M,value=M[A,a],A是非终结符，a是终结符或$
	--inputs是输入符号序列,末尾是$
	--outputs是输出的语法树
	ip=inputs.First()
	while true do
		X,a=stack.Top(),ip.Symbol()
		if X.IsTerminalOr$() then
			if X==a then
				stack.Pop(),ip=inputs.Next()
			else
				error()
			end
		else
			if not M[X,a]==error then --M[X,a]={X={Y1,Y2,...,Yk}}，表示X->Y1Y2...Yk
				stack.Pop()
				Y=M[x,a][X]
				outpus.Dump(X).Dump('->')
				for i=1,k do 
					stack.Push(Y[k-i])
					outpus.Dump(Y[i])
				end
			else
				error()
			end
		end
		if X==$ then break end
	end
end

<<程序设计语言基础>>笔记

---

#####第一章 引言

• λ记法和λ演算系统
  • λx:σ.M
    • α等价:λx:σ.M->λy:σ[y/x]M
    • β等价:(λx:σ.M)N->[N/x]M
    • 同余规则:(M1=M2,N1=N2)/M1N1=M2N2
    • Church-Roosser汇聚性、强正则化性质
• 类型与类型系统简述
  • 类型：一个类型是共享某种性质的值的集合，是一个Collection（集聚）
  • 值：类型的成员
  • 论域、阶（Order）、种类（Kind）：以类型为成员
  • 避免：所有类型的类型，以免罗素悖论
  • 编译器类型检查
    • 较早发现错误
    • 编译文档
    • 保证优化得以实施
    • 绝大多数编译时类型检查基于简单的一些算法，它们拒绝接受带有运行时类型错误的程序，但同时也拒绝了可能不包含运行时错误的某些程序。这是基本递归论的一个不可避免的后果：语言运行时的类型错误是程序的一种不可判定的性质。
  • 运行期类型检查
• 集合论基本知识
  • 集合论是数学的机器语言
    • 空集、相等；序偶、笛卡尔乘积
    • 罗素悖论
    • 朴素集合定义(x|P(x))，不会导致悖论的集合定义(x \in A|P(x))。
    • 幂集和幂集的幂集
    • 序偶，三元组，K元组
    • 良序（基）：集合A上的二元关系良序，其性质是不存在无限下降序列a0>a1>a2>...
      • <是A上的良序， iff A 的每个非空子集有最小元。
  • 关系
    • 自反、对称、传递；反对称、排中律；
    • 等价关系、偏序关系、全序关系；
  • 函数
    • 单射、满射、投影、双射；
    • 部分函数、全部函数；
    • 定义域、值域；
• 上下文无关文法
  • 参考<<编译原理>>笔记第二章
• 归纳法基本知识
  • 自然数归纳法，形式1：欲证明对每一个自然数n，P(n)为真，则只需先证明P(0)和对任意的自然数m，若P(m)为真，则P(m+1)亦然。
  • 自然数归纳法，形式2：欲证明P(n)对每一个自然数n为真，只要证明对任意自然数m，若P(i)对所有的i<m为真，则P(m)也必为真。
  • 结构归纳法，形式1：欲证明P(e)对于某文法产生的每个表达式e为真，只要证明P(e)对每个原子表达式成立，并且证明对任何带有直接子表达式e1,...,ek的复合表达式e，若P(ei)对于i=1,...,k成立，则P(e)也成立。
  • 结构归纳法，形式2：欲证明P(e)对由某种文法产生动每一个表达式e为真，只要证明对任何表达式e，若P(e'')对于每个e的子表达式e''成立，则P(e)成立。
  • 公理与推理规则通常写成模式，借以表达一个给定形式的所有公式或证明步骤。
    • 自反性公理: e=e，每个形如e=e的等式为公理。
    • 推理规则：(A1 ... An)/B,若有形如A1,...,An的公式的证明，则可组合它们得到对应公式B的证明。
    • 等式的传递的推理规则：(e1=e2,e2=e3)/(e1=e3)
  • 形式化而言，一个证明可定义为一个公式序列，其中每个公式或者证明是一个公理，不然则由前面的公式通过单一推理规则而得。由于每个推理规则通常有一系列前件和一个后件，很容易将证明看成一颗以公式标记的叶和内节点的形式的树。
    • 每个公理认为是可能的叶
    • 每条推理规(A1 ... An)/B作为可能的内部的分支节点，其子树比为A1,...,An的证明。
  • 证明上帝结构归纳法：欲证明P(π)对某一证明系统中的每个证明π为真，只要证明P对于该证明系统的每条公理成立，并且接着假定P对π1,...,πk等证明成立，则对任何以一条推理规则扩展π1,...,πk等证明之中的一个或多个而结束的任意证明，证明P(π)均成立。
  • 良序归纳法：设<是集合A上的良序二元关系，并且设P为A的某性质。若当P(A)对所有b<a成立时P(a)都成立，则P(a)对所有a \in A成立。

#####第二章 PCF语言

• PCF语法
  • 每个PCF表达式都有唯一类型
    • 自然数、布尔值:nat bool，值:true false
    • 序偶、参数：笛卡尔乘机σxτ、函数σ->τ（以σ为定义域，τ为值域），函数是右结合的。
  • 表达式文法
    • boolexp=true|false|if boolexp then boolexp else boolexp|Eq? natexp natexp
    • natexp=digital*|natexp+natexp|natexp x natexp|if boolexp then natexp else natexp
    • digital=0|1|2|3|4|5|6|7|8|9
    • σexp=if boolexp then σexp then σexp
  • 公理
    • 0+0=0,0+1=1,1+0=1,1+1=2,...
    • if true then M else N=M,if false then M else N=N
    • Eq? n n = true, Eq? m n = false (m,n not equal)
• 配对及其函数
  • 配对
    • 定义：若M具有类型σ，N具有类型τ，则<M,N> 具有类型 σxτ
    • 公理：
      • proj: Proj1<M,N>=M Proj2<M,N>=N
      • sp: <Proj1<M,N>,Proj2<M,N>>=<M,N> 满射配对
  • 函数:
    • 高阶函数:comp def= λf:nat->nat.λg:nat->nat.λx:nat.f(g(x))
    • 公理：
      • α：λx:σ.M=λy:σ.[y/x]M, y在M中不是自由的
      • β: (λx.σ.M)N=[N/x]M
        • [N/x]x=N
        • [N/x]a=a a是常量或a不等x
        • [N/x](PQ)=([N/x]P)([N/x]Q)
        • [N/x]λx:σ.M=λx:σ.M
        • [N/x]λy:σ.M=λy.σ.[N/x]M x不等y且y不属于FV(N)
        • [N/x]λy:σ.M=λz.σ.[N/x][z/y]M z,y不等x且z不属于FV(MN)
      • η：λx.σ.Mx=M x不属于FV(M)
  • 参数分离：
    • Curry=λf:(natxnat)->nat.λx:nat.λy:nat.f<x,y>
    • add=λp:natxnat.(Proj1p)+(Proj2p)

     Curry(add)=(λf:(natxnat)->nat.λx:nat.λy:nat.f<x,y>)add  
         =λx:nat.λy:nat.add<x,y>  
         =λx:nat.λy:nat.(Proj1<x,y>)+(Proj2<x,y>)  
         =λx:nat.λy:nat.x+y  
    

• 惯用形化
  • 定义：let x:σ=M in N def= (λx:σ.N)M
  • 例子+去惯用形+规约：

   let compose=λf:nat->nat.λg:nat->nat.λx:nat.f(g x) in
     let h=λx:nat.x+x in
       compose h h 3
  
   (λcompse:(nat->nat)->(nat->nat)->nat->nat.
     (λh:nat->nat.compose h h 3) λx:nat.x+x)
      λf:nat->nat.λg:nat->nat.λx:nat.f(g x)
  
   ->(λh:nat->nat.(λf.nat->nat.λg:nat->nat.λx:nat.f(g x)) h h 3) λx:nat.x+x
   ->(λf.nat->nat.λg:nat->nat.λx:nat.f(g x))(λx:nat.x+x)(λx:nat.x+x) 3
   ->(λg:nat->nat.λx:nat.(λy:nat.y+y)(g x))(λx:nat.x+x) 3
   ->(λx:nat.(λy:nat.y+y)((λz:nat.z+z) x) 3
   ->(λy:nat.y+y)((λz:nat.z+z) 3)
   ->(λy:nat.y+y)(3+3)
   ->(3+3)+(3+3)
   ->12
  

• 不动点

  • 引入

   letrec f:σ->σ=M in N
   let f:nat->nat=λy:nat.(if Eq? y 0 then 1 else y*f(y-1)) in f 5
   F def= λf:nat->nat.λy:nat.if Eq? y 0 then 1 else y*f(y-1)
   
   fixσ:(σ->σ)->(σ->σ)
   letrec f:σ->σ=M in N def= let f:σ->σ=(fixσ λf:σ.M) in N
  

  • 公理:

   fix: fixσ=λf:σ->σ.f(fixσ f)
   fixσ M = M(fixσ M)
  

   fact n = (fix F) n
         -->-> F(fix F)n
          = (λf:nat->nat.λy:nat.if Eq? y 0 then 1 else y*f(y-1)) (fix F) n
         -->-> if Eq? n 0 then 1 else n*(fix F)(n-1)
  

  • 联立递归：

   f = F f g
   g = G f g
   fixσxτ =λ<f,g>:<σ,τ>.<F f g,G f g>
  

• 公理语义

  • 基本公理
    • add Eq? cond proj sp α β η fix
  • 推理规则
    • 等价(对称、传递) (M=N)/(N=M) (M=N,N=P)=(M=P)
    • 同余(nat、bool) (M=N,P=Q)/(M+P=N+Q) (M=N,P=Q)/(Eq? M P=Eq? N Q) (M1=M2,N1=N2,P1=P2)/(if M1 then N1 else P1=if M2 then N2 else P2)
    • 序偶 (M=N)/(ProjiM=ProjiN) (M=N,P=Q)/(<M,P>=<N,Q>)
    • 函数 (M=N)/(λx:σ.M=λx:σ.N) (M=N,P=Q)/(MP=NQ)

参考资料

---

1. So yuo want to learn type theory
2. Logic, Languages, Compilation, and Verification
3. Constructive Logic
4. Programming in Martin-L¨of ’s Type Theory
5. Beginner's Guide to Linkers
6. The difference between top-down parsing and bottom-up parsing

<<编译原理>>
1-5章为第一阶，6-7章为第二阶，8-10章为第三阶，11章独立。
<<程序设计语言基础>>
1-2章为第一阶。

Parser是用来将完全展开的终结点序列转换成带非终结点的树形结构，形成语法树的过程。
语法的复杂性直接决定了文法的复杂性，从而决定了Parser的复杂性。如果设计的语法简洁，则不需要写复杂的Parser算法。如果此时还能保持优雅、组合能力、表达能力强，则是一门上品程序语言。永远记住复杂并不是好的标准。

最简单的Parser：How to parser command line parameters

从Parser的角度来说，Program就是一个人肉Parser的过程