编译原理知识点总结

所需积分/C币:50 2018-10-23 16:08:58 547KB PDF
134
收藏 收藏
举报

最全的编译原理知识点总结,逐条罗列出编译原理必考知识点。
不容易掌握 实现扩充语言编译程序的方式有 直接法:直接接受扩充式语言,并按语言的语义规则处理 间接法:接受串行源程序或带并行指示标志的串行源程序,并行编译程序对源程序进 行并行性检查,将检测到的并行成分转换成并行语句。或者立即进行并行编译处理。 并行粒度是对并行执行仟务或者事务大小的度量。分为作业级用户级程序级指令级语 句级。作业级粒度最大,指令级粒度最小。并行编译程序应该选择适当的并行粒度 加速比可认为是应用程序在单处理机上串行执行时间和个处理器并行执行的时 间之比,即 分析比较并行编译程序所牛成的目标程序的执行速度是可用此 指标。 并行硬件上实现神经模型和连接机制模型途径: 用大量的专门的神经元器件连接成特定的模型。用通用并行计算机支持各种连接模型。 第二章 字母表:字母表是元素的非空有穷集合。字母表中的元素称为符号。 符号串:符号的有穷序列成为符号串。什么符号也不包含的符号称为空符号串。符号串 中符号的个数称为符号的长度。 符号串相等若是集合上的两个符号串。且符号串的每个元素和元素的位置均相等时 符号串相等。 符号串的正闭包 为集合上所有符号串的集合 符号串的自反闭包:自反闭包不包含本身 文法:文法是对语言结构的定义与描述。即从形式上用于描述和规定语言结构的称为“文 法”(或称为“语法”)。对于妇女发要研究它的句型、句子和语言。 语法规则:我们通过建立组规则,来描述句了的语法结构。规定用“”表示“由… 组成”或“定义为… 产生式的定义;设 分别是非空有限的非终结符号集和终结符号集, ∩Φ。一个产生式是一个有序偶对(αβ)其中α∈β∈,通常表示 为a→β或aβ。称a为产生式的左部,称β为产生式的右部。产生式又称为重写规 则,它意味着能将个符号串用另个符号串替换。 文法的定义:文法( 非终结符号集。 终结符号集。 产生式或规则的集合。:开始符号(识别符号)∈ 文法和语言分类 将文法分为四类:型、型、型、型。这儿类文法的差别 在于对产生式施加不同的限制。 型文法 其中a∈∪+,β∈ 型文法称为短语结构文法。规则的左部和石部都可 以是符号串,一个短语可以产生另一个短语。 型语言: 这种话言可以用图灵机 接受。 型文法 8Y 其中Yy 称为上下文有关文法或上下文敏感文法。也即只有在 yY这样的上下文中才能把改写为δ 型语言: 这种语言可以由一种线性界狠自动机接受 型文法 其中∈, 6∈ 称为上下文无关文法。也即把改写为δ时,不必考虑上下文 注意:型文法与表小相等价。 型语言: 这种语言可以由下推自动机接受 型文法 (右线性) 其中 ∈ 型文法称为正则文法。它是对型文法进行进一步限制。 型语言 又称正则语言、正则集合这种语言可以由有穷自动机接受 根据上述分析 型文法可以产生 但型文法只能产牛,不能产生 从型文法到型文法,各文法描述语言的能力依次减弱 直接推导 设文法 aβ Y6∈U则称符号串yβ6为符号串 Ya6应用产生式aβ所得到的直接推导,记为yaδyβδ 特别有,当Y=8=ε时,有αβ即每个产生式得右部都是它左部的直接推导。 最左直接推导 在》直接推导中,若属于,属于,即是符号串最左非终结符,即 最左直接推导,若每一步都是最左直接推导,称为最左推导。 最右直接推导 在》直接推导中,若属于,属于,即是符号串最右非终结符,即最 右直接推导,若每一步都是最右直接推导(规范直接推导),称为最右推导(规范推导)。 句型:是文法的识别符号,若 ,则称为文法的句型。也是。 句子:是文法的识别符号,若,属于,则为文法的句子 语言:是文法的识别符号语言 属于,即文法的语言是文 法所有句子构成的集合。 语法树:句子结构的图示表示法,它是一种有向图,由结点和有向边组成。 ():树中每个结点都有一个标记,该标记是并上并上空中的一个符号 ():树的根节结标记是文法的标志符号 ():若书的个节点至少有个叶了结点,则该结点的标记点是个非终结 二义性:若对于一个文法的某一句子存在两棵不同的话法树,则该文法是二义性文法, 否则是无二义性文法。(包含二义性的句子) 无用非终结符号:如果文法的某个非终结符不出现的任何一个句型中,并且不能从它推 导出非终结号串,则称该非终结符称为无用非终结符号 不可达文法符号:如果一个非终结符不出现在如女发的任何一条产生式的右部,则称 该非终结符为不可达文法符号。 自上而下分析方法:从文法的识别符号出发,看是否能推导出待检查的符号申,如果能 推导出这个符号串,则表明此符号串是该文法的个句型或句了,否则便不是。或者说, 以文法的识别符号作为根节点,看其是否能构造一个语法树,而且此语法树所有叶子节 点从左到右所构成的符号串恰好是待检査的符号串。如果能生成这样的语法树,则表明 待检查的符号串是该文法的一个句型或句子,否则便不是。 带回溯的自上而下分析方法:又称为不确定的自上而下分析方法。这种方法显然花费时 间多,效率低 确定的自上而下分析方法:是指在分析的过程中,选择某个非终结符的产生式,是根据 待检查符号串的当前符号以及各产生式右部首符号而进行的,因此是确定的 自下而上分析方法:基本思想:从待检查的符号串山发,看最终是否能归约(推导的逆 过程)到文法的识别符号。如果能归约到文法的识别符号,则表明此待检查的符号串是 该文法的一个句型或句子,否则便不是。从待检查符号串出发,在其中寻找一个称为句 枘的子串,此句枘妇果与文法中的某一产生式右部相匹配,那么就用此产生式左部( 个非终结符)去膂换待检査符号串中的句炳,替换之后得一新符号串,然后对这新符号 串作同样处理。这便是个归约的过程 文法分类:为型、型、型、型文法。程序改计语言的语法规则属于型文法(正 规文法)。程序设计语言的语法和语义部分,一般属于型文法(上下文有关文法),但实 际上都是采用二型文法(上下文无关文法)。 语法分析:语法分析方法有两类,一类是自上而下分析法,另一类是自下而上分析法。 为了语汯分析,需讲文法的产生式存储在计算机,可以为文法建立一个产生表,为了方便 还可建立一个目录表 第三章 有穷自动机分为确定有穷自动机和非桷定有穷自动机 个确定的有穷自动机是一个五元组 其中,是非空有穷 状态集,∑是有穷输入字母表,是一个映射∑丶,c∈Q是开始状态,F包含于Q 是非空终止状态集。 个状态转换图实际上是一个有穷自动机。 个不有穷自动机是个五元组 其中,是非空有分状 态集,∑是有穷输入字母表,映射为∑→的子集所成的集合即是一个多值映射, 0∈Q是开始状态,F包含于Q是终止状态集。 非确定有穷自动机与确定有穷自动机的主要区别有二:一是有一个廾始状态集 而只有一个开始状态;二是的映射是∑→的子集所成的集合,是一个多 值映射,而的映射∑→,是个单值呋射 如果自动机的弧上允许标记E,则称此自动机为ε自动机,记为 或E ε自动机的状态转换图中会出现由若干条E弧组成的空移环路或空移。 确定化方法 子集法 设 ∑ 是个非确定的有穷自动机,那么可以通过了集法构造个和 它等价的确定有穷自动机DFAA'=(∑,Q,t,q,F”)。构造方法如下 (1)输入字母表∑不变 (2)把 的每一个状态子集都作为DFAA的一个状态 (3)DFAA'的映射定义t({r1,r2,,m},a)=q-t(rl,a)UU..U (4)DHAA'的开始状态={sl,s2,,sk},其中,∈Q(i=1,2,k) (5)DFAA的终态集为包含原终止状态的子集组成 造表法 造衣法中DFAA的输入字母衣∑、开始状态和终态集F的确定都与子集法的构造方 法 状态集Q与映射函数t'则是随着造表的过程而动态生成。 首先求出开始状态在接受各输入字母后状态变迁的结果,将其填入表中。然后把得到 的结果作为新的状态,再求其接受各输入字母后状态变迁的结果,填入表中,如此过程 不断重复,直到最后无新结果(状态)出现为止,此时造表结束。 造表法:在子集法中,如果NFA的状态个数n比较大,那么,确定化后的DFA 的状态个数2-1将更人,其中不少状态时不可达状态 包含,状态子集的ε-闭包,记为ε- closuer(I),定义如下: ①若q∈I,则q∈E- closuer(I) ②若qCE- closuer(I),q是由q出发经多条E弧所到达的状态,则q∈ E- closuer(I)。显然ε- closuer(I包含Q。 包含,∈∑,眺射qt(q,a=q,q∈I)=包含QI=E- closuer(J) 不可达状态动机中,从开始状态出发没有任何·条路径能达到的状态称为不可达状态。 的化简 对于任一个 存在一个唯一的状态最少的等价的 个有穷自动机是化简的兮它没有多余状态并且它的状态中没有两个是相等价的。 个有穷自动机可以通过消除多余状态和合并等价状态而转换成一个最小的与之等价的 有穷自动机 分割法”:把一个不含多余状态的状态分割成一些不相关的子集,使得任何不同 的两个子集状态都是可区别的,而同一个子集中的任何状态都是等价的 有穷自动机的多余状态:从该自动机的开始状态出发任何输入串也不能到达那个状态 等价状态状态和的等价条件是 致性条件:状态和必须同时为可接受状态或不接受状态 蔓廷性条件:对于所有输入符号状态和必须转换到等价的状态里 正则文法→有穷自动机 ①令止规文法的终结符号集作为有穷自动机的字母衣 ②文法的每一个非终结符都作为自动机的一个状态,特别是文法的开始符号作 为自动机的开始状态。 ③在自动机中增加一个新状态作为自动机的终止状态。 ④对于文法的形如→的产生式,在自动机中构造形如 的映射 ⑤对于文法的形如→的产生式,在自动机中构造形如 的映射。 有穷自动机→正则文法 ①自动机每一个状态的标记,均作为正规文法的非终结符,其中,自动机开始状态的标 记作为正规文法的廾始符号。自动机的输入字母表中的所有符号,作为正规文法的终结 ②对于自动机的映射(),构造文法的条产生式→ ③对于自动机的终止状态,在正规文法中增加一条产生式→→E 正规表达式的定义: 有字母表∑定义在∑上的正规表达式和正规集合递归定义如下 e和φ都是∑卜的正规表达式它们所表示的正规集合分别为ε和φ 任何∈∑是∑上的正规表达式它所表示的正规集合为 假定和都是∑上的正则表达式它们所表示的正则集合分别记为和 那么 和也都是∑上的正则表达式它们所表示的正则集合分别为 和 仟何∑上的正规表达式和正规集合均、和产生。 正则表达式中的运算符:或(选择)·连接 重复()括号 运算符的优先级:先闭包)后·连接最后或·在正则表达式中可以省略 正则表达式的性质 设 和均是某字母表上的正则表达式则有 单位正则表达式5 交换律 结合律 分配律 此外 正规文法→正规表达式 在转换之前,先将正规文法拓广,其产牛式可以是 或 其中、∈ ∈ 转换规则为: (1)产生式→a β ∈a、β∈,转换为正规表达式aβ (2)产生式→β,转换为aβ (3)产4式→>β,转换为aβ 正规表达式→正规文法 算法 对任何正规式选择一个非终结符作为识别符号 并产生产生式 若是正规式对形为 的产牛式重写为 其中为新的非终结符 同样对于 第四章 词法分析程序:编译程序中完成词法分析仟务的稈序段 扫描器:此法分析程序负责对源程序进行扌描,从中识别岀一个个的单词符号,因此, 词法分析程序乂称为扫描器 预处理:预处理包扦删除无用的空格、跳烙、冋车和换行等编辑性字符,以及注解部分 状态转换图:状态转换图是个有向图,仪包含有限个结点,每个结点表示个状态, 其中有一个初始结点,至少有一个终态结点,节点间弧的标记可以是输入字符或字符类 机内符:标识符的机内表示又称机内符,它包括标识符的全部信息 词法分析器与单词符号 词法分析器:编泽稈序中完成词法分析仟务的稈序段,称为词法分析器。词法分析器负 责对源程序进行扫描,从中识别出个个的单词符号,因此,词法分析器又称为扫描器 单词符号是程序设计语言的基本语法单位和最小语义单位。 单词的种类 关键字 标识符:表示变量名、过程名等 常数:无符号数、布尔常数、字符串常数等 运算符:、一、 等 分界符:逗号、分号、括号等 词法分析程序的输出形式单词的内部形式 单词类别单词自身值 几种常用的单词内部形式 按单词种类分类 、关键字、运算符和分界符釆用一符一类 标识符和常数的单词值又为指示字(指针值) 预处理包括删除无用的空袼、眺格、回车和换行等编辑性宇符以及注解部分。 文法: 识符字母标识符字母标识符数字 无符号整数数字无符号整数数字 单字符分界符 双单字符分界符冒号 冒号 标识符的处理 标识符的类型在机内可用向量形式衣示。 标识符赋予语义后,可以用来标识变量、数组、函数、过程等。 符号表用来存放在程序中出现的各种标识符及其语义特征。 定义性标识符、使用性标识符 第五章 语法分析阶段的主要任务是对词法分析的输岀结果一单词序列进行分析,识别合法的语 法单位。语法分析分为自上而下和自下而上两类方法 自上而下分析法的基本思想是从文法的识别符号出发,试图推导出输入符号串;或试图 为输入串从上而下构造·颗语法树。 自上而下语法分析面临的问题:左递归:造成死循环回溯现象:降低分析效率 文法的左递归性是指文法具有以卜形式的直接左递归: 或间接左递归: 用护展的表示法消除左递归 对巴科斯范式进行扩展,增加以下元符号 ①花括号 :表示符号串出现零次或多次。 :表示符号串能重复出现的最大次数,表示符号串能重复出现的最小次数。 ②方括号:用来表示可选项。 或E,表示符号串可出现一次或不出现。 ③圆括号:利用圆括号可提出个非终结符的多个产生式右部的公共因了 直接改写法 设户生式∷= 直接左递归形式 可将其改写为一个等价的非直接左递归形式 .E =YU U?∷=xU'|E 文法是种自上而下的语法分析方法。它是从文法的识别符号出发,生成句了的最 左推导。它从左到右扫描源程序,每次向前查看 个字符,便能确定当前应该选择的 产生式。如果每次只问前查看一个字符,则称为文法 集合 与 的构造 (1)设∈∪ 的构造 ①若∈,则 ②若∈,其产生式为 ∈则 若它有产生式为→E,则E∈ ③如果它有产生式 E∈ 如果它有产生式 其中 都是非终结符,且 则 E 如果 E,则E∈ (2)设α∈ a=XIX2.Xn, a的构造 ①若α=E,显然 ②若α≠E,则 E∈ ③若X1X2.XiE,则 若X1X2.XnE,则s∈ (3)设∈ 的构造 ①若是文法的识别符号,则 ②若有产牛式,贝 ③若有产生式→,或→ 则 (4)集合 →α的构造 ①当α不可空时 ②②当Q可空时 →0 分析器需要用到一个分析表和一个符号栈。 分析表是进行分析的重要依据。分析表是一个矩阵,它的元素 可以 存放一条非终结符的产生式,表明当符号栈的栈顶元素非终结符遇到当前输入字符 终结符时,说应选择的产生式:元素 也可存放一个出错标志,说明符号栈的栈 顶元素非终结符不应遇到当前输入字符终结符。 构造分析表的算法 ①对文法的每一条产生式a,若Ca)则 ②若E∈ 则 其中,∈ ③分析表的其它元素均为出错标志,通常用空白表示 递归下降分析方法是种确定的自上而下分析方法。它的基本思想是给文法的每个非 终结符均设计一个相应的子程序。山于文法的产生式往往是递归的,因而这些子程序往往 也是递归的。所以,这种分析方法又称为递归子程序法 第六章 自下而上分析法是从输入符号串出发,试图归约到文法的识别符号,或从下往上地为输 入串构造棵语法树。本章具体介绍自下而上分析法中的简单优先分析法和算符优先分析 法自下而上分析法是一种“移进一归约”法。它用到一个符号栈,待检查符号串的符号逐 个被“移进S栈,当栈顶符号串与某个产生式右部相匹配时,这个符号串被替换成(“归 约”为)该产生式左部非终结符 移进就是将一个终结符推进栈 归约就是将个或多个符号从栈中弹出,根据产生式将一个非终结符压入栈 对这个“可进行归约的符号串”,在不同的自下而上分析方法中有着不同的称呼,在简单 优先分析方法中称之为“句柄”,而在算符优先分析方法中称之为“素短语”。 短语和句柄 设是文法的识别符号,若 则称子串α是句型a相对于非终结符的短语。其中,∈;∈U 如果a是的一个直接推导,即a则称子串a是句型a相对于非终结符直接 短语或简单短语 个句型的最左直接短话,称为该句型的句柄。 个句型,有一棵相应的语法树(无二义性)。该语法树的一棵子树的叶子结点(从左到 右)组成的符号串便是这个句型关于子树根结点的一个短语。语法树的一株简单子树(只 有单层的子树)的叶子结点组成的符号串则是这个句型关于简单子树根结点的一个直接短 语。语法树中最左边的简单子树叶子结点组成的符号串就是这个句型的句柄。 移进一归约方法 个移进一归约分析器设置一个符号栈和一个输入缓冲区。输入符号串为α,分析开始 时,栈和输入缓冲区的格局为 符号栈 输入符号串 a# 对a进行分析时,将a的符号从左到右逐个移进符号栈,一旦栈顶符号串与某一个产生 式右部相匹配成为一个可归约符号串时,则将此符号串归约为一个非终结符,这个非终 结符是该产生式的左部符号。α的符号继续逐个移进符号串,重复这个过程.如果最终出 现如下格局: 符号栈 输入符号串 说明符号串α是文法的一个句子。否则,则表示α存在语法错误。 有关文法的一些关系关系 在集合∑到∑上的一个元关系,是笛卡儿乘积∑×∑×..×∑的一个子集。 或者说,一个元关系可定义为一个有序的元组集合即:设∈∑∈∑2,… ∈∑,则x1,x2,,n满足关系,当且仪当有序元组(x1,x2,,xn)∈ 般,不妨令∑一∑一∑,二元关系定义如下 集合上的二元关系,是∑的一个子集。或者说,与 ∈∑满足二元关系, 当且仅当有序偶对 。与满足关系,记为 关系具有以下基本性质 (1)自反性设是定义在集合∑上的个关系,如果对于任何∈∑,都有,则称关系 是自反的。如数学中的关系“≤”是自反的,但关系<不是自反的。 (2)对称性如果对任何,∈∑,,都有,则称关系是对称的。如数学中的关 系“”是对称的。 (3传递性对任何,∈∑,如果能由与推得,则称关系是传递的。如数 学中的关系<”是传递的。 和文法相关的一些关系: ()关系和 设,∈∑,与是上的两个关系,与的关系和记为 且仅当或。关系“<”与关系“”的关系和为 (2)关系积 关系与的关系积记为 当且仅当存在一个,使得 且 关系…<”与关系“<的关系积为,如 ,因为在与之间的任意一个数都满足 这种关系,如存在一个数,使得 且 (3传递闭包 关系的传递闭包记为,设,∈∑, 当且仅当存在一个,使得 其中 R (4)自反传递闭包 关系的自反传递闭包记为 其中,为恒等关系。设,∈∑ 当且仅 定理关系的转置关系记为,则 ()即转置关系()的关系矩阵 等于关系矩阵的转置矩阵

...展开详情
试读 22P 编译原理知识点总结
立即下载
限时抽奖 低至0.43元/次
身份认证后 购VIP低至7折
一个资源只可评论一次,评论内容不能少于5个字
您会向同学/朋友/同事推荐我们的CSDN下载吗?
谢谢参与!您的真实评价是我们改进的动力~
  • 签到新秀

  • 分享精英

关注 私信
上传资源赚钱or赚积分
最新推荐
编译原理知识点总结 50积分/C币 立即下载
1/22
编译原理知识点总结第1页
编译原理知识点总结第2页
编译原理知识点总结第3页
编译原理知识点总结第4页
编译原理知识点总结第5页

试读结束, 可继续读2页

50积分/C币 立即下载