引论 《编译原理和技术》 张昱 0551-63603804，yuzhang@中国科学技术大学 计算机科学与技术学院 主要内容
1 编程语言及设计
2 编译器及形式
3 编译器的阶段
4 示例：程序的表示
5 基础实验的考虑 张昱：《编译原理和技术(H)》课程简介
2 主要内容
1 编程语言及设计
2 编译器及形式
3 编译器的阶段
4 示例：程序的表示
5 基础实验的考虑 张昱：《编译原理和技术(H)》课程简介 编程语言 
什么是编程语言 Aprogramminglanguageisanotationforputationstopeopleandtomachines. 每种编程语言有自己的计算模型 过程型(Procedural):
C,C++,C#,Java声明型(Declarative):SQL,…逻辑型(Logic):Prolog,…函数式(Functional):Lisp/Scheme,Haskell,ML,…脚本型(Scripting):AWK,Perl,Python,PHP,Ruby,…
3 张昱：《编译原理和技术》引论
4 求最大公约数gcd 张昱：《编译原理和技术》引论 编程语言百花齐放 / 众多：GitHub--开源项目涉及337种编程语言(2017.9) /用1500种语言编写 语言自身在不断发展 C-C90,C99,C11； C++-1998,…,2011,2014,2017 最流行的语言(动态变化) Tiobe/tiobe-index/ 2017.8：1Java,2C,3C++,4C#,5Python,6VB.NET 2010年：1Java,2C,3PHP,4C++,5VB,6C#,7Python 1970年：1Fortran,2Lisp,3Cobol,4Algol60,5APL,6Snobol4
5 张昱：《编译原理和技术》引论
6 1 99BottlesofBeer 99bottlesofbeeronthewall,99bottlesofbeer.Takeonedownandpassitaround,98bottlesofbeeronthewall. 98bottlesofbeeronthewall,98bottlesofbeer.Takeonedownandpassitaround,97bottlesofbeeronthewall....2bottlesofbeeronthewall,2bottlesofbeer.Takeonedownandpassitaround,1bottleofbeeronthewall. 1bottleofbeeronthewall,1bottleofbeer.Takeonedownandpassitaround,nomorebottlesofbeeronthewall. Nomorebottlesofbeeronthewall,nomorebottlesofbeer.Gotothestoreandbuysomemore,99bottlesofbeeronthewall. [Traditional] 张昱：《编译原理和技术》引论
7 C:99BottlesofBeer #defineMAXBEER(99)voidchug(intbeers);main(){ registerbeers;for(beers=MAXBEER;beers;chug(beers--)) puts(""); puts("\nTimetobuymorebeer!
\n");exit
(0);}voidchug(registerbeers){charhowmany[8],*s;s=beers!
=1?
"s":"";printf("%dbottle%sofbeeronthewall,\n",beers,s);printf("%dbottle%sofbeeeeer...,\n",beers,s);printf("Takeonedown,passitaround,\n"); if(--beers)sprintf(howmany,"%d",beers);elsestrcpy(howmany,"Nomore"); s=beers!
=1?
"s":""; printf("%sbottle%sofbeeronthewall.\n",howmany,s); } [BillWein] 张昱：《编译原理和技术》引论
8 Java:99BottlesofBeer classbottles{ publicstaticvoidmain(Stringargs[]){Strings="s"; for(intbeers=99;beers>-1;){System.out.print(beers+"bottle"+s+"ofbeeronthewall,");System.out.println(beers+"bottle"+s+"ofbeer,"); if(beers==0){System.out.print("Gotothestore,buysomemore,");System.out.println("99bottlesofbeeronthewall.\n");System.exit
(0); }elseSystem.out.print("Takeonedown,passitaround,"); s=(--beers==1)?
"":"s"; System.out.println(beers+"bottle"+s+"ofbeeronthewall.\n"); } } } [SeanRussell] 张昱：《编译原理和技术》引论
9 AWK:99BottlesofBeer BEGIN{ for(i=99;i>=0;i--){ printubottle(i),"onthewall,",lbottle(i)"." printaction(i),lbottle(inext(i)),"onthewall.“ print } } functionubottle(n){ returnsprintf("%sbottle%sofbeer",n?
n:"Nomore",n-1?
"s":"") } functionlbottle(n){ returnsprintf("%sbottle%sofbeer",n?
n:"nomore",n-1?
"s":"") } functionaction(n){ returnsprintf("%s",n?
"Takeonedownandpassitaround,":\ "Gotothestoreandbuysomemore,") } functioninext(n){ returnn?
n-1:99 } [OsamuAoki,/~osamu] 张昱：《编译原理和技术》引论 10 程序语言的设计 为什么那么多语言？ 单个语言不能适用所有应用程序员对语言的好坏、如何编程有自己的观点和看法没有评价语言好坏的普遍接受的标准 语言进化之驱动力 应用的多样性提高软件开发生产力(productivity)改善软件的安全性、可靠性和可维护性支持并行(parallelism)与并发(concurrency)移动和分发，模块化，多范型 张昱：《编译原理和技术》引论 11 程序语言设计的计算思维 计算思维(ComputationalThinking) Computationalthinkingisafundamentalskillforeveryone,notjustputerscientists.Toreading,writing,andarithmetic,weshouldputationalthinkingtoeverychild’sanalyticalability.JustastheprintingpressfacilitatedthespreadofthethreeRs,whatisappropriatelyincestuousaboutthisvisionisputingputersfacilitatethespreadofteM.putationalthinking.ComputationalThinkingCACM,vol.49,no.3,pp.33-35,2006 语言设计中的计算思维 张昱：《编译原理和技术》引论 ProblemDomain MathematicalAbstraction MechanizableModelof Computation ProgrammingLanguage 12
2 主要内容
1 编程语言及设计
2 编译器及形式
3 编译器的阶段
4 示例：程序的表示
5 基础实验的考虑 张昱：《编译原理和技术》引论 编译器是什么 源程序 编译器
Compiler 输入 目标程序 输出 13 张昱：《编译原理和技术》引论 14 目标语言 另一种编程语言CISCs（复杂指令集）：x86、IA64、…RISCs（精简指令集）：MIPS、ARM、…多核/众核GPUs:CUDA、OpenCLFPGAs量子计算机TPU，NPU… 张昱：《编译原理和技术》引论 15 解释器 源程序 解释器 输出 输入 Interpreter 直接在输入上执行源程序 张昱：《编译原理和技术》引论 16 Java编译器 源程序 .java 翻译器 Translator (javac) 输入 中间表示 Intermediate
Representation.class Java虚拟机 VirtualMachine(java) 张昱：《编译原理和技术》引论 输出 17 编译器的其他形式 交叉编译器（piler） 在一个平台上生成另一个平台上的代码PCARM 增量编译器（piler） 以增量地编译源程序,只编译修改的部分,如Freeline 即时编译器（piler） 在运行时对IR中每个被调用的方法进行编译，得到目标机器的本地代码，如JavaVM中的即时编译器 预先编译器（piler） 在程序执行之前将IR翻译成本地码，如ART中的AOT 张昱：《编译原理和技术》引论 18
3 Java虚拟机 类加载器 Classloader Java字节码 .class 即时编译器 JITCompiler 输入 垃圾收集器 Garbagecollector 字节码解释器 BytecodeInterpreter 输出 机器代码 Machinecode 输出 输入 张昱：《编译原理和技术》引论 19 C编译器 C源程序 预处理器 Preprocessor(cpp) .i 连接器 Linker(ld) 目标文件 .o C编译器 Compiler ) 汇编汇编器 .s Assembler (as) 张昱：《编译原理和技术》引论 库代码 Libraryroutines 输入 机器代码 Machinecode 输出 20 主要内容
1 编程语言及设计
2 编译器及形式
3 编译器的阶段
4 示例：程序的表示
5 基础实验的考虑 张昱：《编译原理和技术》引论 编译器的阶段 source
program Frontend前端 Backend后端 targetprogram LexicalAnalyzer 词法分析器 SyntaxAnalyzer 语法分析器 SemanticAnalyzer 语义分析器 Interm. CodeGen. 中间代码生成器 CodeOptimizer代码优化器 CodeGen.代码生成器 Token Stream记号流 Syntax Tree语法树 Annotated SyntaxTree 带注解的语法树 Interm. Rep.中间表示 Interm. Rep.中间表示 SymbolTable符号表 21 张昱：《编译原理和技术》引论 22 编译器的阶段 主要内容 sourceprogram Frontend前端 Programinput LexicalAnalyzer 词法分析器 SyntaxAnalyzer 语法分析器 SemanticAnalyzer/Interm.CodeGen. 语义分析器/中间代码生成器 Tree-walkroutines树遍历程序 Token Stream记号流 Syntax Tree语法树 AbstractSyntaxTreeor otherInterm.Rep.抽象语法树或其他中间表示 SymbolTable符号表 Programoutput 张昱：《编译原理和技术》引论 23
1 编程语言及设计
2 编译器及形式
3 编译器的阶段
4 示例：程序的表示
5 基础实验的考虑 张昱：《编译原理和技术》引论 24
4 int
main(){inti=getint(),j=getint();AB } ParseTree分析树 张昱：《编译原理和技术》引论 25 SymbolTable符号表 AbstractSyntaxTree抽象语法树 张昱：《编译原理和技术》引论 27 Awhile(i!
=j){if(i>j)i=i–j;elsej=j–i;} Bputint(i); ParseTree分析树 张昱：《编译原理和技术》引论 26 intmain(){inti=getint(),j=getint(); Awhile(i!
=j){if(i>j)i=i–j;elseBj=j–i; C}Dputint(i);} 张昱：《编译原理和技术》引论 28 主要内容
1 编程语言及设计
2 编译器及形式
3 编译器的阶段
4 示例：程序的表示
5 基础实验的考虑 张昱：《编译原理和技术》引论 基础实验的考虑 源代码 词法分析器
Parser0Parser 记号流 是否合法?
高级中间表示(AST) 解释器 是否合法?
程序变换器优化器 语义检查器 低级中间代码生成器 (AST2LIR) 低级中间表示(如LLVMIR) LLVM编译器工具链 代码生成器 寄存器分配器 JIT 汇编码 (如x86,MIPS) 29 张昱：《编译原理和技术》引论 30
5 解析器的生成器 生成器 生成Lexer：Flex（forwindows）、Jflex生成Parser LALR:Bison（forwindows）、JavaCUPLL:JavaCC、ANTLR–LL(*)[PLDI2011] 文法对Parser的影响 LRParser的优势：速度快、表达能力强LLParser的优势：代码结构与文法对应， 易理解，容易增加错误处理和错误恢复 张昱：《编译原理和技术》引论 31 ANTLR ANTLR(ANotherToolforLanguageRecognition) [/] Prof.TerenceParr,since1989支持多种代码生成目标 Java、C++、C#、Python、Go、JavaScript、Swift 张昱：《编译原理和技术》引论32 基于 开展的实验 开源：源码阅读，消化、理解生成器基于的原理 各种语言实现：31种模式 20.计算表达式的类型
1.从文法到递归下降识别器
2.LL
(1)递归下降词法分析器
3.LL
(1)递归下降语法解析器 12.内嵌遍历器13.外部访问者14.文法访问者 21.自动类型提升22.静态类型检查23.动态类型检查
4.LL(k)递归下降语法解析器15.模式匹配者（子树）24.语法制导的解释器
5.回溯解析器
6.记忆解析器
7.谓词解析器
8.解析树（分析树）
9.同型抽象语法树10.规范化异型AST11.不规则的异型AST 16.单作用域符号表17.嵌套作用域符号表18.数据聚集的符号表19.类的符号表型 张昱：《编译原理和技术》引论 25.基于树的解释器 26.字节码汇编器27.栈式解释器28.寄存器解释器 29.语法制导的翻译器30.基于规则的翻译器31.模型驱动的转换33 我听到的会忘掉，我看到的能记住，我做过的才真正明白。
张昱：《编译原理和技术》引论 34
6