编译分析技术与工具课件.ppt

1、编译中的分析技术和工具简介大纲 概念 文法 分析 递归下降分析 LL分析 LR分析 YACC Lex 选择 学习资料概念：编译的地位降龙十八掌太公兵法理论、形式化理论、形式化经经验验、积积累累操操作作系系统统编编译译器器概念：编译 编译 Compile 翻译【计】to translate instructions 编纂 collect and put togetherint main()int a,b;a=(int)&b;printf(“%xn”,a);return 0;B8 01 FE FF 0E 4B C6 F8 FEC+Compiler源代码编译器目标代码概念：编译基本过程#define

2、 MAX 256#define TEXT“Hello”int main()int a=MAX char x=TEXTB8 01 FE FF 0E 4B C6 F8 FE预处理优化代码生成分析分析Pre-ProcessParseOptimizeGenerateint main()int a=256 char x=“Hello”有向无环图DAG抽象语法树AST中间代码IntermediateCode源代码Source目标代码Target概念：解释 解释 Interpret Interpret：口译#!/bin/shecho“Begin”cat file|lessmakesed Bash源代码解释器

3、执行动作catmakesedless概念：解释基本过程执行分析分析ParseRun#!/bin/shecho“Begin”cat file|lessmakesed 概念：分析 分析 Parse 序列化到结构化 词法分析、语法分析、语义分析FUNCTION fact(x)IF x=0 THEN RETURN 1 ENDIF s=1 FOR i=1 TO x s=s*i NEXT iEND FUNCTIONPRINT fact(10)PRINT fact(8)文法 文法 Grammar 文法的概念 文法和语言 文法的表示 Chomsky文法分类文法：文法的概念（1）标准句型标准句型：（定语）主语（

4、状语）谓语（补语）（定语）宾语主语主语：名词/代词谓语谓语：动词宾语宾语：名词/代词定语定语：形容词/代词状语状语：副词补语补语：助词名词名词：苹果、人、水、船动词动词：揍、吃、喝、喜欢代词代词：我、它、那个形容词形容词：红、坏、贱副词副词：飞快的、狠狠的、很助词助词：了、吧、吗我 吃 红 苹果我 飞快的 吃 苹果我 狠狠的 揍 了 那个 贱人我 吃 船苹果 吃 了 我我 很 喜欢 坏 苹果文法：文法的概念（2）标准句型标准句型：（定语定语）主语主语（状语状语）谓语谓语（补语补语）（定语定语）宾语宾语主语主语：名词名词/代词代词谓语谓语：动词动词宾语宾语：名词名词/代词代词名词名词：苹果、人、

5、水、船动词动词：揍、吃、喝、喜欢代词代词：我、它、那个我 吃 红 苹果我 飞快的 吃 苹果我 狠狠的 揍 了 那个 贱人开始开始符号符号终结符终结符Terminal非终结符非终结符Non-Terminal产生式产生式Production句子句子推导、推导、表达表达规约、分析规约、分析文法：文法的概念（3）Program：Condition Statement CommentCondition：if ExpressionStatement：print ValueComment：#TextExpression：Expression=ExpressionValue：a|b|c|dText：Hello

6、|Good|Howif a=b print Helloif b=c print Good 开始开始符号符号终结符终结符Terminal非终结符非终结符Non-Terminal产生式产生式Production句子句子推导、表达推导、表达规约、分析规约、分析文法：文法和语言 文法的形式化定义 文法：四元组 (S,VN,VT,P)句子：文法的一个推导 语言 文法中所有句子的集合XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX文法：文法的表示 产生式：句子主语

7、谓语 宾语A AaA BcB bbAB Acd 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 THEN RETURN 1 ENDIF s=1 FOR i=1 TO x s=s*i NEXT iEND FUNCTIONPRINT fact(10)PRINT fact(8)FUNCTIONfact(x)IFPROGRAM:=TOKEN SP*TOKEN:=ALPHA*ALPHA:=a|b|c|zALPHA:=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 THEN RETURN 1 ENDIF s=1 FOR i=1 TO x s=s*i NEXT iEND FUNCTIONPRINT fact(10)PRINT

10、fact(8)PROGRAMxsRETURN1IFPROGRAM:=FUNCTIONFUNCTION:=FUNC ST ENDST:=IF EXPRR END IFEXPR:=EXPR=EXPRFUNCTIONTHEN赋值=0文法：文法的Chomsky分类(7)1型文法（上下文相关文法）Context Sensitive Grammar abbr.CSG 产生式左部长度小于右部长度（|）:=ad ac:=xyz m:=xyzu 推导是“收敛”的 表达能力更强 能表达语境的概念 可定义复杂语法和部分语义（semantics）文法：文法的Chomsky分类(8)1型文法的语言表达能力示例今王王与百

11、姓百姓同乐，则王王矣王王欲行王王政，则勿毁之矣梁惠王齐宣王成为老大王者文法：文法的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)乔姆斯基文法分类总结文法类型文法类型用处用处0型文法短语文法图灵机1型文法上下文相关文法部分语义、复杂语法2型文法上下文无关文法语法3型文法正则文法单词、简单

12、匹配表达能力限制规则分析：概念(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程序分析：概念(3)分工 语法分析：主导 词法分析：支撑 语义分析：指导、检查语法树语法树词法词法词法词法词法词法语义检查语义检查分析：词法分析 词法分析 用正则文法

13、去理解“字符序列”，提供“单词序列”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;赋值返回函数定义调用赋值变量定义程序分析：分析方法 词法分析 直接分析 构造确定有限状态机分析 语法分析 递归下降分析法 LL分析法 LR分析法 算符优先分析法 递归下降分析：下降 下降 逐级下降分工 每一级均为函数调用1+2*3+4/5表达式因

14、子+因子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-Left 从左向右读入单词 从左向右分析 递归下降分析法即为LL分析法的一种特例 LL(k)：提前扫描k个单词 LL(1)：提前查看1个单词，最常用的LL分析法1+2+3+

15、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)分析法 自底向上的分析 用二维状态转换表实现 转换表构造过程复杂，难以手工实现 自己维护较大的栈（“记忆”的多）可表达的语法范围比LL分析法

16、广 LL和LR的兼容问题int foo()x=4;return 1;int bar()x=8;return 1;if(foo()&bar()printf(“x=%dn”,x);YACC：概念(1)背景 写一个编译器前端很困难 大量编译器前端的工作重复 形式语言理论成熟 MULTICS项目 LALR分析法“很好很强大”手工构造状态转换表很困难 构造状态转换表的方法较机械YACCYACC：概念(2)Yet Another Compilers Compiler by Stephen C.Johnson,1975,Bell Lab 神一般的工作人编译器程序苦力YACC神?YACC：概念(3)YACC

17、输入一个CFG文法 输出一个LALR分析器（C语言实现）与主程序结合，成为一个编译器/解释器 AT&T Yacc,Berkeley Yacc,GNU Bisongrammar.yYACCy.tab.cCCmain.c编译器/解释器源程序YACC：实践(1)实践任务：简单的四则混合运算计算器calc 例如：1+(2+3)*6/5-4*6 从文件中读入源程序 源程序为一个混合运算式 程序以#结尾 运算数为个位数 运算符为+、-、*、/和括号(、)分析完后执行运算，打印出结果9-8*7/(1+2+1)+4*(2+5)#calcsource.calc23YACC：实践(2)分析文法，归纳语法 1+2*

18、(3+4*5)+6 括号里和整个表达式是同构关系 乘除运算优先级较高 加减运算优先级最低 最直接的文法 表达式表达式:=因子因子+-因子因子+-因子因子+-（一个或多个）因子因子:=因数因数*/因数因数*/因数因数*/（一个或多个）因数因数:=数字数字 因数因数:=(表达式表达式)YACC：实践(3)化简为2型文法（CFG）BNF/EBNF表示的产生式（尽量用右递归）程序程序:表达式表达式#表达式表达式:=表达式表达式+因子因子 表达式表达式:=表达式表达式-因子因子 表达式表达式:=因子因子 因子因子:=因子因子*因数因数 因子因子:=因子因子/因数因数 因子因子:=因数因数 因数因数:=数

19、字数字 因数因数:=(表达式表达式)数字数字:0 数字数字:9YACC：实践(4)设计动作 每分析完一条产生式则立即运算 例如分析7*2：数字数字:=7，将“数字”的值设为7 因数因数:=数字数字，将“因数”的值设为“数字”值，即7 因子因子:=因数因数，将“因子”的值设为“因数”值，即7 数字数字:=2，将“数字”的值设为2 因数因数:=数字数字，将“因数”的值设为“数字”值，即2 因子因子:=因子因子*因数因数，将“因子”的值设为7*2即14 程序程序:=表达式表达式#，将表达式的值XXXX打印出来YACC：实践(5)写yacc源文件 yacc源文件格式 规则：类似EBNF格式 动作：C语

20、言的程序段 用YACC生成y.tab.c%C语言的定义、声明%/*YACC定义*/%/*规则定义*/规则1 动作1;规则2 动作2;%其他C代码YACCy.tab.cYACC：实践(6)写主控程序 主控程序和y.tab.c的主要接口 yylex：分析器调用yylex读入字符（单词）序列 yyerror：当分析错误时，分析器调用该函数 yyparse：开始分析函数，由主控程序调用int main()int yylex()void yyerror()XXXXYYYYyyparse()ZZZZy.tab.c主控程序YACC：实践(7)联编 编译连接 cc-c y.tab.c cc-c main.c

21、cc-o calc main.o y.tab.o 测试 创建一个文件test.ca 内容：9-8*7/(1+2+1)+4*(2+5)#运行：./calc test.ca 结果：Result=23 修改内容：9-8*7/(1+2#运行：./calc test.ca 结果：ERROR:Syntax errorYACC：实践(8)问题 仅能识别1位数的数字（value:1|2|99|10000?）不能识别符号（value:A|B|Z|AB|ABC|?）加入这些功能使得状态转换表规模很大（N2）怎么办？将数字、符号的识别功能“外包”给某个程序 保持较小的状态转换表规模 N2+M2 (N+M)2LEXL

22、EX：概念(1)LEX Lexical Parser Generator，词法分析器生成器 目标：配合YACC by Eric Schmidt and Michael Lesk,1975,Bell Lab AT&T Lex,GNU Flex LEX：概念(2)LEX 输入一个3型（正则）文法 输出一个单词分析器 与YACC结合，为YACC提供yylex()等接口grammar.yYACCy.tab.cCCmain.c编译器/解释器源程序lexical.lLEXlex.yy.cy.tab.hLEX：实践(1)实践任务1：简单的单词分析器，配合YACC 数字：1、10、124 常量：LONG、CH

23、AR 从文件中读入源程序，分析数字和符号 提供yylex()，每调用一次得到一个单词类型 源程序为较复杂的混合运算式120*LONG+32*(CHAR+2*LONG)#120*+32*+2*#)LONGCHAR(LONGLEX：实践(2)实践任务2：YACC和LEX实现更强大的计算器 使YACC分析时能支持多位的整数 使YACC能支持预定义的常量 LONG=4 CHAR=1LEX：实践(3)分析和归纳文法 12345重复且相连的数字 ABCDE重复且相连的字母+、-、*、/、(、)、#：单个字符的运算符“空格”：（连续的）空白 最直接的文法 整数整数:=数字数字 数字数字 数字数字（一个或多个

24、）常量常量:=字母字母 字母字母 字母字母（一个或多个）数字数字:=0或1或2或或9 字母字母:=A或B或C或或Z 加号加号:=+减号减号:=-LEX：实践(4)乘号乘号:=*除号除号:=/左括号左括号:=(右括号右括号:=)结束符号结束符号:=#空白空白:=（一个或多个）LEX：实践(5)化简为3型文法（正则文法）正则表达式 整数:=0-9+常量:=A-Z+空白:=+加号:=+减号:=-乘号:=*除号:=/左括号:=(右括号:=)结束符号:=#LEX：实践(6)设计动作 yylex()的返回值，不再是数值，而是枚举 NUMBER、CONSTANT、OP_ADD、OP_SUB、OP_MUL、O

25、P_DIV、OP_LPA、OP_RPA、END 这些枚举在yacc中被看做单词（token）对于空白，忽略。即yylex()返回的一定是非空白 当前获取的单词的内容，通过yytext取得。设计接口 yywrap()：返回1，分析完源程序就“撤”yyin：Lex的输入文件。提供FILE*，它自己读。LEX：实践(7)写lex源文件 lex源文件格式 规则：正则表达式 a-z：a|b|c|z aceg：a|c|e|g a，a+，a*，a?.动作：C语言的程序段 用Lex生成lex.yy.c%C语言的定义、声明%/*单词定义*/定义1 动作1;定义2 动作2;%其他C代码Lexlex.yy.cLEX

26、：实践(8)改写yacc源文件 从yylex()读到的是单词类型 从yytext读单词内容 用yacc-d生成y.tab.h，定义单词类型%C语言的定义、声明%/*YACC定义*/%/*规则定义*/规则1 动作1;规则2 动作2;%其他C代码YACCy.tab.cy.tab.h 改写主控程序 主控程序和y.tab.c的新增接口 get_constant：解析yytext的常量字符串为数值 get_number：解析yytext的整数字符串为数值int yylex()char*yytextLEX：实践(9)int main()int get_constant()int get_number()v

27、oid yyerror()int yywrap()XXXXYYYYint yyparse()ZZZZy.tab.clex.yy.cmain.cLEX：实践(10)联编 编译连接 cc-c y.tab.c cc-c lex.yy.c cc-c main.c cc-o calc main.o y.tab.o lex.yy.o 测试 创建一个文件test.ca 内容：LONG-CHAR*120/(CHAR+LONG+1)+30*(2+CHAR)#运行：./calc test.ca 结果：Result=74 内容：LONG-UNKNOWN#结果：ERROR:Syntax error选择：比较 手工 v

28、s 自动 语法的文法类型 自动：2、3型文法，LL(1)、LALR(1)、GLR分析器 手工：无绝对限制，LL(k)、LR(k)分析器 语法复杂度 自动：无绝对限制，对复杂度不敏感 手工：越复杂越困难（C+）语法扩展方向 编程设计水平 性能要求 自动：语法复杂时优势渐显，优化有限 手工：语法简单时性能佳，优化潜力大选择：参考 手工分析器 GCC词法、语法分析器 LLVM/Clang词法、语法分析器 LCC词法、语法分析器 OpenWatcom CC词法、语法分析器 其他语言分析/解释器（Python、Perl）自动分析器 Java词法、语法分析器（ANTLR）自定义格式的语言、配置文件解析 实验性语言分析器学习资料 理论教材程序设计语言编译原理，陈火旺 编译原理，吕映芝 编译原理及编译程序构造，金茂忠，高仲仪 Crafting A Compiler With C，Charles N.Fischer 形式语言与自动机 实践教材可变目标编译器：设计与实现，Chris W.Fraser Lex与Yacc，John R.Levine,Tony Mason 完 Thanks!