编译原理

2024-06-29 08:05| 来源: 网络整理| 查看: 265

目录第二章：文法和语言基本知识基本概念：（1）根据语言能设计文法（2）最左、最右推导概念（3）求短语、直接短语和句柄（通过语法树查找）（4）文法二义性的判断（5）文法和语言的分类(概念) 第三章：词法分析与又穷自动机基本概念：（1）正规文法→正规式（2）非确定有穷自动机的自动化（3）通过正规式→确定有穷自动机第四章：语法分析4.1:语法分析程序的功能4.2:自上而下分析法基本概念（1）文法左递归的消除（2）LL(1)文法的判断（3）LL(1)文法的判断，判断后构造预测分析表（4）判断文法是不是算符优先文法（两个条件、规则只有一种）（5）会计算FIRSTVT和LASTVT两个集合（6）构建优先关系表第五章：语法翻译技术与中间代码生成（1）属性文法的概念（2）给一个式子，会用逆波兰式表达

第二章：文法和语言基本知识基本概念： 1：字母表：元素的非空有穷集合；例如：∑={a,b,c}2：符号：字母表中的元素3：符号串：符号的有穷序列；例如：a,b,ab,ba,cba,abc,… - 不包含任何符号的的符号串，称为空符号串，用ε表示 - εA = Aε = A4：形式语言：是字母表上按一定的规则组成的所有符号串集合，其中的每个符号串称为一个句子

符号串的运算

符号串的连接、集合的乘积、符号串的幂运算、集合的幂运算集合A正闭包A+与闭包A* - A*：含空串 - A+:不含空串

对形式语言的描述两种方法

枚举法：当语言为有穷集合时文法：文法描述了无穷集合的语言

文法

G =（ VN, VT, P, S） - VN：一组非终结符号的集合 - VT：一组终结符号的计集合 - P：文法规则的集合 - S：一个开始符号

推导

(1):已知文法-------->确定该文法所定义的语言 (2):推导用“ ⇒ ”表示 (3):文法能唯一确定语言

直接推导：1 （）推导：>1 （+）广义推导：>0 （*）句型和句子概念： - 句型包含句子 - 句子必须都是终结符

规约

最右推导（规范推导的逆过程）：最左规约(规范规约)

用“ ⇒(.)标记

递归规则和文法的递归性

递归规则： - 左递归：A→A… - 右递归：A→…A - 递归：A→…A…文法递归 - 左递归：A ⇒+ A… - 右递归：A ⇒+ …A - 递归：A ⇒+ …A…

注：有递归性→描述的语言时无穷的，无递归性→描述的语言是有穷的

短语、直接短语、句柄

短语： - 经过若干步推导出直接短语： - 直接推导出来（一步）句柄： - 一个句型的最左直接短语

语法树与文法的二义性

语法树：子树：有某一非末端节点连同所有分支组成的部分简单子树：只有单层分支的子树

二义性： 1.定义：若一个文法存在某个句子对应两棵不同的语法树，则称这个文法是二义的。 2.特点：为编译程序的执行带来不确定性。 3.判定：需找到例子二义性消除： …略：

文法和语言的分类:P25

0型文法(无限制文法) - 规则形式：α→β - 且a中至少含有一个非终结符1型文法(上下文有关文法) - 规则形式：αAβ→αvβ，其中A∈VN（理解：左右两边有相同的字符） - 左边长度小于等于右边2型文法(上下文无关文法) - 规则形式：A→β，其中A∈VN - 产生式左边都只有一个非终结符3型文法（正规文法） - 右线性规则形式：A→αβ或 A→α，A,B ∈VN，α∈VT* - 左线性规则形式：A→βα或 A→α，A,B ∈VN，α∈VT*

有关文法的实用限制和变换

略（1）根据语言能设计文法对于给定一个语言，描述该语言的方法不是唯一的例一：P13 在这里插入图片描述

例二：P15

（2）最左、最右推导概念最左推导对一个推导序列中的每一步直接推导α⇒β，都是对α中的最左非终结符进行替换最右推导(规范推导) 对一个推导序列中的每一步直接推导α⇒β，都是对α中的最右非终结符进行替换。（3）求短语、直接短语和句柄（通过语法树查找）例一：在这里插入图片描述

例二：

（4）文法二义性的判断判断一个文法具有二义性，必须找到例子（5）文法和语言的分类(概念) 着重2、3型文法是1型文法的同时也可以是2型文法第三章：词法分析与又穷自动机基本概念：

词法分析程序的功能

是对字符串表示的源程序从左到右进行扫描和分解，根据语言的词法规则识别出一个一个具有独立意义的单词符号（识别单词符号） - 语言的单词符号（关键字、标识符、常数、运算符、界符）

词法分析程序输出的单词符号形式 P35

二元式：（单词种别，单词自身的值）单词种别：表示单词的种类，常用整数编码

语言单词符号的两种定义方式 P36

目的：为构造出识别单词语言符号的词法分析程序，必须先搞清楚如何定义描述程序语言单词符号的结构正规文法或正规式定正规文法：同上（3型文法）正规式：包含3种符号，优先级（"|" < “.” < “*”) 正规式的性质：交换、结合、分配律

正规文法和正规式：

1：正规文法到正规式的转换(例题：P38)

将正规文法中的每个非终结符表示成关于它的一个正规方程式依照求解规则： - 若x = αx | β（或x = αx + β)，则解为 x = α * β； - 若x = xα | β（或x = xα + β)，则解为 x = βα*；

2：正规式到正规文法的转换:

略：见书上

正规式与有穷自动机：

有穷自动机是具有离散输入与输出系统的一种抽象数学模型

确定有穷自动机（DFA）: 1.定义：是一个五元组：M=(Q，Σ，f，S，Z)，其中： 1）Q：状态集合 2）Σ：输入字母表 3）f：单值映射 4）S：初态 5）Z ⊆ Q，终态集在这里插入图片描述

非确定有穷自动机（NFA）: 1.定义：是一个五元组：M=(Q，Σ，f，S，Z)，其中： 1）Q：状态集合 2）Σ：输入字母表 3）f：多值函数 4）S：非空初态集合 5）Z ⊆ Q，终态集注意：在NFA状态转换图中，边上的标记可以是ε 在这里插入图片描述

由正规表达式R构建NFA：在这里插入图片描述例题：

NFA确定化为DFA的方法：

见下面考试范围（1）正规文法→正规式见知识点（2）非确定有穷自动机的自动化

1：定义新初态，并求出

注意：新初态应是包含原初态的新集注意：必须是从原初态出发后，再经由任意条ε弧，所能到达的状态在这里插入图片描述

2：造表（状态矩阵表）

注意：a/b/c的值得求法注意：q1 、q2 、q3 …qn ：是新出现的集合（上列a或b的值）注意：有多个新出现的值时必须全部列出，作为新的初态，直到没有新出现的集合为止！在这里插入图片描述

a/b/c值得求法：新初态的子集经过a/b/c…弧所到达的状态，和该状态相连的ε弧的状态（如没有ε弧则忽略）在这里插入图片描述

3：造图（状态转换图）

把新出现的集合，设对应值，然后画图即可！例子：在这里插入图片描述

（3）通过正规式→确定有穷自动机步骤一：正规式先转化为非确定有穷自动机步骤二：非确定有穷自动机的确定化即可得到确定有穷自动机第四章：语法分析 4.1:语法分析程序的功能

语法分析器的功能：

语法分析是编译过程的核心部分。它的任务是在词法分析识别出单词符号串的基础上，分析并判定程序的语法结构是否符合语法规则。即分析由这些单词如何组成各种语法成分，比如“声明”、“函数”、“语句”、“表达式”等，并分析判断程序的语法结构是否复合语法规则。在这里插入图片描述

4.2:自上而下分析法

4.2.1：非确定的自上而下分析基本思想：

对任何输入串W试图用一切可能的办法，从文法的开始符号出发，自上而下的为它建立一棵语法树。或者说，为输入串寻找一个最左推导。如果试探成功，则W为相应文法的一个句子，否则W就不是文法的句子。本质上是一种穷举试探过程由于难免会出现问题，故分析过程中难免会回溯缺点：分析效率低、代价高故通常采用确定的自上而下分析法进行语法分析但确定的，对文法有限制，必须描述语言的文法是无左递归和无回溯

4.2.2：文法的左递归性的消除

方法一：引进一个新的非终结符，把含左递归的规则改写成右递归（看题理解） - 在这里插入图片描述