《编译分析技术与工具》由会员分享，可在线阅读，更多相关《编译分析技术与工具（65页珍藏版）》请在金锄头文库上搜索。
1、编译中的分析技术和工具简介大纲 概念 文法 分析 递归下降分析 LL分析 LR分析 YACC Lex 选择 学习资料概念：编译的地位降龙十八掌太公兵法理论、形式化经 验 、 积 累操 作 系 统编 译 器概念：编译 编译 Compile 翻译【计】to translate instructions 编纂 collect and put togetherint main() int a, b;a = (int)printf(“%xn”,a);return 0; B8 01 FE FF 0E 4B C6 F8 FE C+ Compiler源代码编译器目标代码概念：编译基本过程#define MAX
2、 256 #define TEXT “Hello” int main() int a = MAXchar x = TEXT B8 01 FE FF 0E 4B C6 F8 FE 预处 理优化代码 生成分析Pre-ProcessParseOptimizeGenerateint main() int a = 256char x = “Hello” 有向无 环图 DAG抽象语 法树 AST中间代码 Intermediate Code源代码 Source目标代码 Target概念：解释 解释 Interpret Interpret：口译#!/bin/sh echo “Begin” cat file |
3、 less make sed Bash源代码解释器执行动作catmakesedless概念：解释基本过程执行分析ParseRun#!/bin/sh echo “Begin” cat file | less make sed 概念：分析 分析 Parse 序列化到结构化 词法分析、语法分析、语义分析FUNCTION fact(x)IF x = 0 THENRETURN 1ENDIFs = 1FOR i = 1 TO xs = s * iNEXT i END FUNCTIONPRINT fact(10) PRINT fact(8) 文法 文法 Grammar 文法的概念 文法和语言 文法的表示 C
4、homsky文法分类文法：文法的概念（1）标准句型：（定语）主语（状语）谓语（补语）（定语）宾语主语：名词/代词 谓语：动词 宾语：名词/代词 定语：形容词/代词 状语：副词 补语：助词名词：苹果、人、水、船 动词：揍、吃、喝、喜欢 代词：我、它、那个 形容词：红、坏、贱 副词：飞快的、狠狠的、很 助词：了、吧、吗我 吃 红 苹果 我 飞快的 吃 苹果 我 狠狠的 揍 了 那个 贱人我 吃 船 苹果 吃 了 我 我 很 喜欢 坏 苹果文法：文法的概念（2）标准句型：（定语）主语（状语）谓语（补语）（定语）宾语主语：名词/代词 谓语：动词 宾语：名词/代词 名词：苹果、人、水、船 动词：揍、吃、
5、喝、喜欢 代词：我、它、那个 我 吃 红 苹果 我 飞快的 吃 苹果 我 狠狠的 揍 了 那个 贱人开始符号终结符 Terminal非终结符 Non-Terminal产生式 Production句子推导、表达规约、分析文法：文法的概念（3）Program：Condition Statement CommentCondition：if Expression Statement：print Value Comment：# Text Expression：Expression = Expression Value：a | b | c | d Text：Hello | Good | Howif a =
6、 b print Hello if b = c print Good 开始符号终结符 Terminal非终结符 Non-Terminal产生式 Production句子推导、表达规约、分析文法：文法和语言 文法的形式化定义 文法：四元组 (S, VN , VT , P) 句子：文法的一个推导 语言 文法中所有句子的集合XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX文法：文法的表示 产生式：句子主语 谓语 宾语 A Aa A Bc B bb AB Acd
7、 BNF范式（Backus-Naur Form）句子:=主语 谓语 宾语:= a:= bcd 扩展BNF范式（EBNF范式）:= a | c * | ab+c |文法：文法的Chomsky分类(1) 不同特点的产生式、不同的表达能力 3型文法（正则文法） Regular Grammar 产生式简单 :=a :=a 表达能力很弱 a、aa、aaa、aaaa、 ac、abc、abbc、abbbc、abbbbc 没有“记忆”能力 等价于确定性有限自动机 （DFA） 多用于定义单词（token）文法：文法的Chomsky分类(2) 3型文法的语言表达能力示例叽叽叽叽叽叽叽叽叽叽叽叽吱吱吱吱吱吱叽叽吱吱
8、文法：文法的Chomsky分类(3) 3型文法的语言分析能力示例FUNCTION fact(x)IF x = 0 THENRETURN 1ENDIFs = 1FOR i = 1 TO xs = s * iNEXT i END FUNCTIONPRINT fact(10) PRINT fact(8) FUNCTIONfact(x)IFPROGRAM := TOKEN SP * TOKEN := ALPHA * ALPHA:= a|b|c|z ALPHA:=A|B|C|Z文法：文法的Chomsky分类(4) 2型文法（上下文无关文法） Context Free Grammar abbr. CFG
9、产生式左部只有一个非终结符（|=1） :=ad :=xyz 表达能力较强 IF a b THEN a = b ELSE b = a static int printk(const char *fmt, ); 有一定的“记忆”能力 多用于定义简单语法（syntax）文法：文法的Chomsky分类(5) 2型文法的语言表达能力示例妈妈，抱抱(我)我要(那个(娃娃)哇哇哇哇呜呜呜呜文法：文法的Chomsky分类(6) 2型文法的语言分析能力示例FUNCTION fact(x)IF x = 0 THENRETURN 1ENDIFs = 1FOR i = 1 TO xs = s * iNEXT i EN
10、D FUNCTIONPRINT fact(10) PRINT fact(8) PROGRAMxsRETURN1IFPROGRAM := FUNCTION FUNCTION := FUNC ST END ST := IF EXPRR END IF EXPR := EXPR = EXPR FUNCTIONTHEN赋值=0文法：文法的Chomsky分类(7) 1型文法（上下文相关文法） Context Sensitive Grammar abbr. CSG 产生式左部长度小于右部长度（| |） :=ad ac:=xyz m := xyzu 推导是“收敛”的 表达能力更强 能表达语境的概念 可定义复杂
11、语法和部分语义（semantics）文法：文法的Chomsky分类(8) 1型文法的语言表达能力示例今王与百姓百姓同乐，则王矣王欲行王政，则勿毁之矣梁惠王齐宣王成为老大王者文法：文法的Chomsky分类(9) 1型文法的语言分析能力示例int x;int main() int x;x = 4;func();return 0; void func() x = 4; 赋值ESP+x4赋值DS+x4文法：文法的Chomsky分类(10) 0型文法（短语文法） 产生式没有限制 a:=ad :=x m := x 表达能力最强 等价于图灵机文法：文法的Chomsky分类(11) 乔姆斯基文法分类总结文法类
12、类型用处处0型文法短语文法图灵机1型文法上下文相关文法部分语义、复杂语法2型文法上下文无关文法语法3型文法正则文法单词、简单匹配表 达 能 力限 制 规 则分析：概念(1) 分析 Parse 序列化到结构化 理解 按照指定的文法去理解给定的句子 语义(Semantics)检查 语法(Syntax)分析 词法(Lexical)分析分析：概念(2) 完全分析 树结构太复杂int x;int main() int x;x = 4;func();return 0; void func() x = 4; 赋值ESP+x4DS+xmainfunc()返回函数定义=范围调用=赋值4范围0变量定义x程序分析：
13、概念(3) 分工 语法分析：主导 词法分析：支撑 语义分析：指导、检查语法树词法词法词法语义检查分析：词法分析 词法分析 用正则文法去理解“字符序列”，提供“单词序列”int x;int main() int x;x = 4;func();return 0; void func() x = 4; intintmainmainx=x=分析：语法分析 语法分析 用2型文法去理解“单词序列”int x;int main() int x;x = 4;func();return 0; void func() x = 4; 赋值返回函数定义调用赋值变量定义程序分析：分析方法 词法分析 直接分析 构造确定有
14、限状态机分析 语法分析 递归下降分析法 LL分析法 LR分析法 算符优先分析法 递归下降分析：下降 下降 逐级下降分工 每一级均为函数调用1+2*3+4/5表达式因子+因子1*+因子/2345递归下降分析：递归 递归 语法为递归定义时，调用也递归调用 严格定义的递归接口1+2*(3+4*5)表达式因子1*+因子2表达式因子3+45*递归下降分析 递归下降分析 结构简单、自然 编码容易 语言不复杂时性能极佳 采用递归下降作为前端的著名的C编译器： LCC GCC（3.0）C Compiler OpenWatcom C Compiler LLVM/Clang LL分析法(1) LL：Left-Le
15、ft 从左向右读入单词 从左向右分析 递归下降分析法即为LL分析法的一种特例 LL(k)：提前扫描k个单词 LL(1)：提前查看1个单词，最常用的LL分析法1+2+3+411+1+233+3+366+6+410LL分析法(2) LL(1)分析法 自顶向下分析 程序直观 可用状态转换表实现 可用递归下降实现 易于手工实现LR分析法(1) LR：Left-Right by Donald Knuth, 1965 从左向右读入单词 从右向左分析 LR(k)：提前查看k个单词 LALR(1)：LR(1)加约束，最常用的LR分析法1+2+3+411+1+21+2+1+2+3+1+2+3+4101+2+71+9LR分析法(2) LALR(1)分析法 自底向
