程序分析技术第三讲元程序设计.ppt

《程序分析技术第三讲元程序设计.ppt》由会员分享，可在线阅读，更多相关《程序分析技术第三讲元程序设计.ppt（12页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、程序分析技术程序分析技术第三讲：第三讲：元元 程程 序序 设设 计计一、基础知识一、基础知识词法分析词法分析1.1.基本概念基本概念2.2.描述工具描述工具1)1)正则表达式正则表达式2)2)自动机自动机3.3.实现词法分析器注意的问题实现词法分析器注意的问题2语法分析语法分析1.1.形式语言形式语言2.2.分析原来分析原来1)1)自顶向下的语法分析自顶向下的语法分析2)2)自底向上的语法分析自底向上的语法分析语法制导语法制导分析的过程生成中间表示分析的过程生成中间表示3二、元程序二、元程序元程序元程序概念概念处理处理程序程序的程序的程序元程序系统元程序系统的组成的组成：1.1.预处理：把源程

2、序变成一种中间表示预处理：把源程序变成一种中间表示（经过词法分析，语法分析）（经过词法分析，语法分析）2.2.元级操作：提供最基本的操作（根据元级操作：提供最基本的操作（根据需求，用户可选择如何操作）需求，用户可选择如何操作）3.3.后处理：有必要把中间表示转为源代后处理：有必要把中间表示转为源代码码4三、中间表示三、中间表示四元式四元式:(op,a,b,t):(op,a,b,t)例例 a*(b+c)+d a*(b+c)+d (+,b,c,t1)(+,b,c,t1)，(*,a,t1,t2)(*,a,t1,t2)，(+,t2,d,t3)(+,t2,d,t3)逆波兰式逆波兰式:后缀式后缀式 上例上

3、例 abc+*d+abc+*d+树树 上例上例5+*d da a+b bc c四、规则分类和对应的结构四、规则分类和对应的结构1.1.结构规则（构造规则）结构规则（构造规则）AA X1X2X1X2XnXn2.2.选择规则选择规则AA X1|X2|X1|X2|XnXn是结构规则的特例，因为每次只能用一个是结构规则的特例，因为每次只能用一个规则规则6AX1X2Xn3.3.表规则表规则 A A E|E,AE|E,A(也可左递归也可左递归)构造双向链表操作更方便构造双向链表操作更方便4.4.词汇规则词汇规则 A A lexlex7t1At2E1t3E2t4E3实例实例while x0 doif y0

4、then x:=x+1else y:=y+18whileifc0vyc0thenelse:=vxc1+vxvx五、元级操作五、元级操作1.1.低级元操作低级元操作1)1)类型识别操作类型识别操作给结点的类型给结点的类型判定结点是否为给定的类型判定结点是否为给定的类型空结点定位空结点定位2)2)成份选择操作成份选择操作选择某一结点（满足条件）选择某一结点（满足条件）表元素的选择表元素的选择93)3)构造操作构造操作按某一结构构造结点。按某一结构构造结点。4)4)关系操作关系操作给定两结点，判断它们的关系。给定两结点，判断它们的关系。给定结点和关系，判断是否存在结点。给定结点和关系，判断是否存在结

5、点。5)5)编辑操作编辑操作插入，删除，查找，修改插入，删除，查找，修改6)6)词汇强制词汇强制2.2.高级元级操作高级元级操作可根据特定的需要，构造许多特殊的高级操作。可根据特定的需要，构造许多特殊的高级操作。如：控制流图，函数调用关系图等如：控制流图，函数调用关系图等10六、系统的自动生成六、系统的自动生成利用语法制导的方法生成利用语法制导的方法生成系统由两部分组成系统由两部分组成生成中间表示部分生成中间表示部分元级操作部分（可事先设计好）元级操作部分（可事先设计好）11按照按照 A AX X1 1XXn n 归约时归约时状态为状态为XiXi的结点已经构造好文法，结点指针未填的结点已经构造好文法，结点指针未填规约后，规约后，XiXi结点指针添加，结点指针添加，A A结点指针均空结点指针均空XiXi退栈退栈A A进栈进栈12Xn.X1d Sem栈