第一章语言与语言的翻译优秀课件.ppt

《第一章语言与语言的翻译优秀课件.ppt》由会员分享，可在线阅读，更多相关《第一章语言与语言的翻译优秀课件.ppt（10页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第一章语言与语言的翻译第一章语言与语言的翻译第一章语言与语言的翻译第一章语言与语言的翻译第1页，本讲稿共10页2第二章第二章词法的双重含义：词法规则词法规则词法分析词法分析F模式、记号与单词F形式化描述：正规式与正规集F记号的识别：有限自动机NFA：与正规式有对应关系，易于构造，状态数少；DFA：具有确定性，不易构造，状态数可能多；识别方法：模拟DFA、模拟NFA对于正规式r，构造自动机识别字符串x，有结论：自动机空间时间NFAO(|r|)O(|r|*|x|)DFAO(2|r|)O(|x|)第2页，本讲稿共10页3第二章第二章F从正规式到词法分析器1.正规式描述模式2.由正规式构造NFA3.N

2、FA的确定化（子集法：smove，-闭包）4.DFA的最小化（可区分概念）5.词法分析器：表驱动与直接编码第3页，本讲稿共10页4第三章第三章F程序设计语言与文法1.正规式与正规文法2.上下文无关文法CFG=(N,T,P,S)3.文法分类：0型、1型、2型和3型F有关推导的基本概念1.产生语言的基本方法推导：句子与句型、直接推导与推导、最左推导与左句型 2.分析树与语法树分析树记录推导过程并反映语言结构语法树仅反映语言结构而忽略推导过程，树中没有非终结符3.二义性与二义性的消除第4页，本讲稿共10页5第三章第三章F自上而下分析1.分析方法：用推导的方法从上到下构造分析树，谋求与输入序列的匹配，

3、是一种试探的方法；2.对文法的要求：为避免回朔与无穷递归，要求文法没有公共左因子和左递归；3.递归下降子程序：每个非终结符是一个子程序4.预测分析下推自动机工作模式：格局与格局的变换预测分析表：四个动作、分析表中的内容预测分析表的构造：FIRST集合与FOLLOW集合5.LL(1)文法及其判别方法第5页，本讲稿共10页6F自下而上分析1.分析方法：用归约的方法从叶子到根构造分析树，谋求对输入序列的匹配2.基本概念：短语、直接短语、句柄、规约、规范规约、剪句柄3.基本方法:用移进-归约方法实现剪句柄LR文法与LR分析：LR(0),SLR(1),LALR(1),LR(1)SLR(1)分析格局与格局

4、变换、改变格局的四个动作移进归约分析表：动作表与转移表SLR(1)分析器的构造识别活前缀的DFA：LR(0)项目、项目集、项目集族、子集法识别活前缀：有效项目、可移进项、可规约项、冲突SLR(1)文法：简单向前看一个终结符第6页，本讲稿共10页7第四章第四章重点是程序设计语言的静态语义分析，并且在语法分析的基础上生成中间代码，采用的基本方法是语法制导翻译。F语法制导翻译的基本概念语法与语义属性与语义规则语义规则的两种形式F中间代码为什么生成中间代码常用形式：树、后缀式、三地址码(三元式、四元式)F符号表的组织条目与信息存储(直接/间接)作用域信息保存(线性表、散列表)第7页，本讲稿共10页8第

5、四章第四章F声明语句的翻译定义与声明：类型定义与变量声明，过程定义与声明变量声明：填写符号表过程声明左值与右值值调用、引用调用、复写恢复、换名调用名字的作用域：静态作用域与最近嵌套原则嵌套定义的过程中信息的存储F可执行语句的翻译简单算术表达式和赋值句的翻译：类型转换数组元素的引用第8页，本讲稿共10页9*第五章第五章本章介绍程序运行时的空间组织，重点是讨论如何通过对过程的静态分析(包括符号表的使用)建立运行环境，以保证程序的正确执行。F过程的动态特性过程、活动、生存期、控制流；活动树、控制栈、活动记录；名字的绑定、环境与状态；F运行时的存储空间组织内存划分：可执行代码、静态数据区、栈、堆；活动记录的内容：参数与返回值、控制链、访问链、机器状态、本地数据、临时变量等。第9页，本讲稿共10页10*第五章第五章F不同的存储分配策略静态分配：绑定是静态的栈分配：基于控制栈自动管理内存堆分配：根据要求从堆数据区动态地分配和释放内存F栈分配策略调用序列与返回序列；控制链与访问链：控制链用于活动记录的正确切换，体现活动调用关系；访问链用于访问非本地数据，体现过程嵌套关系；访问链的实现：访问链、显示表；第10页，本讲稿共10页