编译原理复习要点

1、考试安排：7月13日（20周周三），15：00-17:00,20208填空10X1分、选择10X2分、简答4X5分、大题5X10分考试大题：循环优化 LL(1).定义之类的 算符优先算法 自下而上分析法（20分，选择、填空、大题）第一章 引论一编译程序(compiler):把某一种高级语言程序等价地转换成另一种低级语言程序(如汇编语言或机器语言程序)的程序二编译程序的工作的五个阶段:词法分析、语法分析、中间代码产生、优化、目标代码产生1. 词法分析Pascal语言任务: 输入源程序，对构成源程序的字符串进行扫描和分解，识别出一个个单词符号。依循的原则：构词规则描述工具：有限自动机FOR I :

2、= 1 TO 100 DO保留字 标识符 等符 整常数 保留字 整常数 保留字2. 语法分析任务:在词法分析的基础上，根据语言的语法规则把单词符号串分解成各类语法单位。依循的原则：语法规则述工具：上下文无关文法3. 语义分析与中间代码产生任务:对各类不同语法范畴按语言的语义进行初步翻译。（变量是否定义、类型是否正确等）依循的原则：语义规则中间代码:三元式，四元式，逆波兰记号，树形结构等。是一种独立于具体硬件的记号系统。例：将Z:=X + 0.618 * Y 翻译成四元式为(1) * 0.618 Y T1(2) + X T1 T2(3) := T2 _ Z4. 优化任务：对于前阶段产生的中间代码

3、进行加工变换，以期在最后阶段产生更高效的目标代码。依循的原则：程序的等价变换规则FOR K:=1 TO 100 DO BEGIN M := I + 10 * K; N := J + 10 * K; END4. 目标代码产生任务: 把中间代码变换成特定机器上的目标代码。依赖于硬件系统结构和机器指令的含义目标代码三种形式:a) 绝对指令代码: 可直接运行 b) 可重新定位指令代码: 需要连接装配c) 汇编指令代码: 需要进行汇编三. 编译程序结构u 编译程序总框 (简答题5分)第二章 高级语言及其语法描述语法词法规则：单词符号的形成规则。a) 单词符号是语言中具有独立意义的最基本结构。一般包括：常

4、数、标识符、基本字、算符、界符等。b) 描述工具：正规式和有限自动机语法规则：语法单位的形成规则。a) 语法单位通常包括：表达式、语句、分程序、过程、函数、程序等;c) 描述工具：上下文无关文法语义语义：一组规则，用它可以定义一个程序的意义。描述方法：a) 自然语言描述：隐藏错误、二义性和不完整性b) 形式描述：F 无二义性F 完整性多数语言中，算符的优先顺序如下：u 乘幂（*或）优先级由高自低u 一元负（-）u 乘、除u 加、减不同的语言对算符优先级的规定有差异，甚至差异很大！u 关系符（<,=,>,<=,>=,<>）u 非（¬，not）u 与(

5、，&，and )u 或(,|,or,)u 隐含( 或imp)u 等值（ 或epui，或 ）2.3 程序语言的语法描述1. 几个概念:a) 考虑一个有穷 字母表 字符集b) 其中每一个元素称为一个字符c) 上的字(也叫字符串) 是指由中的字符所构成的一个有穷序列d) 不包含任何字符的序列称为空字，记为e) 用*表示上的所有字的全体,包含空字例如: 设 =a， b，则 *=,a,b,aa,ab,ba,bb,aaa,.f) *的子集U和V的连接（积）定义为UV ab | aÎU & bÎV 例如: 设：U a, aa ,V b, bb 那么：UV= ab, abb

6、, aab, aabb g) V自身的 n次积记为Vn=VVVh) 规定V0=e，令V*=V0V1V2V3 称V*是V的闭包;记 VVV* ，称V+是V的正规闭包。例如: 设：U a, aa 那么：U* = e , a, aa, aaa, aaaa, U = a, aa, aaa, aaaa, i) 0型(短语文法，图灵机)： 产生式形如： a ® b 其中：aÎ (VT È VN)*且至少含有一个非终结符；bÎ (VT È VN)* 任何0型语言都是递归可枚举的。j) 1型(上下文有关文法，线性界限自动机)： 产生式形如： a ®

7、b 其中：|a| £ |b|，仅 S®e 例外。意味着对非终结符进行替换时务必考虑上下文，并且，一般不允许替换成空串e 。k) 2型(上下文无关文法，非确定下推自动机)： 产生式形如： A ® b 其中：AÎ VN；bÎ (VT È VN)*。非终结符的替换可以不必考虑上下文。l) 3型(正规文法，有限自动机)：右线性文法 产生式形如： A ® aB 或 A ® a 其中： aÎ VT*；A，BÎVN左线性文法 产生式形如： A ® Ba 或 A ® a 其中： aÎ

8、; VT*；A，BÎVN正规文法的能力要比上下文无关文法弱得多。四种类型描述能力比较 m) 上下文无关文法的定义： 一个上下文无关文法G是一个四元式 G=(VT，VN，S，P)，其中VT：终结符集合(非空)VN：非终结符集合(非空)，且VT Ç VN=ÆS：文法的开始符号，SÎVNP：产生式集合(有限)，每个产生式形式为P®a， PÎVN， a Î (VT È VN)*开始符S至少必须在某个产生式的左部出现一次。例：文法G1(A)： A ® c|AbG1(A)的语言?解：L(G1)=c，cb，cbb，&#

9、188;，以c开头，后继若干个bn) 定义：如果一个文法存在某个句子对应两颗不同的语法树，则说这个文法是二义的。G(E)： E ® i|E+E|E*E|(E) 是二义文法。o) 语言的二义性：一个语言是二义性的，如果对它不存在无二义性的文法。可能存在G和G，一个为二义的，一个为无二义的。但L(G)=L(G) 2. 状态转换图 a) 概念：状态转换图是一张有限方向图。b) 结点代表状态，用圆圈表示。c) 状态之间用箭弧连结，箭弧上的标记(字符)代表射出结状态下可能出现的输入字符或字符类。d) 一张转换图只包含有限个状态，其中有一个为初态，至少要有一个终态3. 正规运算符优先顺序在不致混

10、淆时，括号可以省去，但规定算符的优先顺序为：*（闭包） .（连接） |（或）4. 3型文法-正规式 G的任何产生式为 A ® aB 或 A ® a 其中： aÎ VT*；A，BÎVN 3型文法等价于正规式，所以也称正规文法。3.3.2 确定有限自动机(DFA)对状态图进行形式化，则可以下定义：自动机M是一个五元式M=(S, S, f, S0, F),其中：a) S: 有穷状态集，b) S：输入字母表(有穷)，c) f: 状态转换函数，为S´S®S的单值部分映射，f(s，a)=s表示：当现行状态为s，输入字符为a时，将状态转换到下一状态

11、s。我们把s称为s的一个后继状态。d) S0ÎS是唯一的一个初态； e) FÍS ：终态集(可空)。例如：DFA M=(0，1，2，3，a，b，f，0，3)， 其中：f定义如下：f(0，a)=1f(0，b)=2f(1，a)=3 f(1，b)=2f(2，a)=1f(2，b)=3f(3，a)=3 f(3，b)=33.3.3 非确定有限自动机(NFA)定义：一个非确定有限自动机(NFA) M是一个五元式M=(S, S, f, S0, F)，其中：1 S: 有穷状态集；2 S ：输入字母表(有穷)；3 f: 状态转换函数，为S´S*®2S的部分映射(非单值)；4

12、 S0ÍS是非空的初态集；5 F ÍS ：终态集(可空)。从状态图中看NFA 和DFA的区别： 1 弧上的标记可以是S*中的一个字，而不一定是单个字符； 2 同一个字可能出现在同状态射出的多条弧上。DFA是NFA的特例。定义：对于任何两个有限自动机M和M，如果L(M)=L(M)，则称M与M等价。自动机理论中一个重要的结论：判定两个自动机等价性的算法是存在的。对于每个NFA M存在一个DFA M，使得 L(M)=L(M)。亦即DFA与NFA描述能力相同。把上述NFA确定化采用子集法.设I是M的状态集的一个子集，定义I的e-闭包e-closure(I)为: i) 若sÎ

13、;I，则sÎe-closure(I)； ii) 若sÎI，则从s出发经过任意条e弧而能到达的任何状态s都属于e-closure(I) 即 e-closure(I)=IÈs|从某个sÎI出发经过任意条e弧能到达s例：设a是S中的一个字符，定义 Ia= e-closure(J)其中，J为I中的某个状态出发经过一条a弧而到达的状态集合。3.3.4 正规文法与有限自动机的等价性定理： 1.对每一个右线性正规文法G或左线性正规文法G，都存在一个有限自动机(FA) M，使得L(M)L(G)。2.对每一个FA M，都存在一个右线性正规文法GR和左线性正规文法GL，使得

14、L(M)L(GR)L(GL)。3.3.5 正规式与有限自动机的等价性定理： 1. 对任何FA M，都存在一个正规式r，使得L(r)=L(M)。 2. 对任何正规式r，都存在一个FA M，使得L(M)=L(r)。2 对转换图概念拓广，令每条弧可用一个正规式作标记。(对一类输入符号)3.3.6 确定有限自动机的化简u 对DFA M的化简:寻找一个状态数比M少的DFA M，使得L(M)=L(M)u 假设s和t为M的两个状态，称s和t等价:如果从状态s出发能读出某个字a而停止于终态，那么同样，从t出发也能读出a而停止于终态；反之亦然。u 两个状态不等价，则称它们是可区别的。u 对一个DFA M最少化的

15、基本思想: 把M的状态集划分为一些不相交的子集，使得任何两个不同子集的状态是可区别的，而同一子集的任何两个状态是等价的。最后，让每个子集选出一个代表，同时消去其他状态。I(1)=0, 1, 2 I(2)=3, 4, 5, 6 Ia(1) =1, 3 I(11) =0, 2 I(12) =1 I(2)=3, 4, 5, 6 I(11) =0, 2Ia(11) =1 Ib(11) =2, 5 I(111) =0 I(112) =2 I(12) =1 I(2)=3, 4, 5, 6 Ia(2) =3, 6 Ia(2) =4, 5 第四章 语法分析自上而下分析u 语法分析的方法：u 自下而上分析法(B

16、ottom-up)u 自上而下分析法(Top-down)u 基本思想：它从文法的开始符号出发，反复使用各种产生式，寻找"匹配"的推导。u 递归下降分析法：对每一语法变量(非终结符)构造一个相应的子程序，每个子程序识别一定的语法单位，通过子程序间的信息反馈和联合作用实现对输入串的识别。u 预测分析程序F 优点：直观、简单和宜于手工实现。4.3 LL(1)分析法u 构造不带回溯的自上而下分析算法u 要消除文法的左递归性u 克服回溯4.3.1 左递归的消除u 直接消除见诸于产生式中的左递归：假定关于非终结符P的规则为PPa | b 其中b不以P开头。 我们可以把P的规则等价地改写

17、为如下的非直接左递归形式：PbP¢左递归变右递归P¢aP¢|eu 一般而言，假定P关于的全部产生式是 PPa1 | Pa2 | | Pam | b1 | b2|bn其中，每个a都不等于e，每个b都不以P开头 那么，消除P的直接左递归性就是把这些规则改写成： Pb1P¢ | b2P¢ | | bnP¢ P¢a1P¢ | a2P¢ | | amP¢ | eu 提取公共左因子: 假定关于A的规则是 Adb 1 | db 2 | | db n | g 1 | g 2 | | gm (其中，每个g 不以d

18、开头) 那么，可以把这些规则改写成AdA¢ | g 1 | g 2 | | g mA¢b 1 | b 2 | | b nu 经过反复提取左因子，就能够把每个非终结符(包括新引进者)的所有候选首符集变成为两两不相交。4.3.3 LL(1)分析条件u 假定S是文法G的开始符号，对于G的任何非终结符A，我们定义特别是，若，则规定ÎFOLLOW(A)n 构造不带回溯的自上而下分析的文法条件1. 文法不含左递归，2. 对于文法中每一个非终结符A的各个产生式的候选首符集两两不相交。即，若 Aa 1|a 2|a n 则 FIRST(a i)FIRST(a j)f (i¹

19、;j) i=1,2,.,n3. 对文法中的每个非终结符A，若它存在某个候选首符集包含e，则FIRST(A)FOLLOW(A)=f如果一个文法G满足以上条件，则称该文法G为LL(1)文法。第五章 语法分析自下而上分析语法分析的方法：自下而上分析法(Bottom-up)u 基本思想：从输入串开始，逐步进行“归约”，直到文法的开始符号。即从树末端开始，构造语法树。所谓归约，是指根据文法的产生式规则，把产生式的右部替换成左部符号。u 算符优先分析法：按照算符的优先关系和结合性质进行语法分析。适合分析表达式。u LR分析法：规范归约5.1.2 规范归约1.定义：令G是一个文法，S是文法的开始符号，假定a

20、bd是文法G的一个句型，如果有 且 ，则称b是句型abd相对于非终结符A的短语。特别是，如果有AÞb,则称b是句型abd相对于规则A® b的直接短语。一个句型的最左直接短语称为该句型的句柄。2.归约采用“移进归约”思想进行自下而上分析。基本思想：用一个寄存符号的先进后出栈，把输入符号一个一个地移进到栈里，当栈顶形成某个产生式的候选式时，即把栈顶的这一部分替换成(归约为)该产生式的左部符号。5.2 算符优先分析u 四则运算的优先规则： 先乘除后加减，同级从左到右u 考虑二义文法文法G(E)：G(E)： E ® i| E+E|E-E|E*E|E/E|(E)u 它的句子

21、有几种不同的规范规约。u 归约即计算表达式的值。归约顺序不同，则计算的顺序也不同，结果也不一样。u 如果规定算符的优先次序，并按这种规定进行归约，则归约过程是唯一的。u 起决定作用的是相邻的两个算符之间的优先关系。u 所谓算符优先分析法就是定义算符之间的某种优先关系，借助于这种关系寻找“可归约串”和进行归约。5.2.1 算符优先文法及优先表构造u 一个文法，如果它的任一产生式的右部都不含两个相继(并列)的非终结符，即不含如下形式的产生式右部：QR 则我们称该文法为算符文法。u 约定：u a、b代表任意终结符；u P、Q、R代表任意非终结符；u 代表由终结符和非终结符组成的任意序列，包括空字。u

22、 假定G是一个不含e-产生式的算符文法。对于任何一对终结符a、b，我们说：1. a=b当且仅当文法G中含有形如Pab或PaQb的产生式；2. a<b当且仅当G中含有形如PaR的产生式， 而Rb或RQb；3. a>b 当且仅当G中含有形如PRb的产生式，而 Ra或RaQ。n 如果一个算符文法G中的任何终结符对(a，b)至多只满足下述三关系之一：a=b，a<b， a>b。 则称G是一个算符优先文法。u 从算符优先文法G构造优先关系表的算法。u 通过检查G的每个产生式的每个候选式，可找出所有满足a=b的终结符对。u 确定满足关系<和>的所有终结符对：u 首先需要对

23、G的每个非终结符P构造两个集合FIRSTVT(P)和LASTVT(P)：a<b当且仅当G中含有形如PaR的产生式， 而Rb或RQb；a>b 当且仅当G中含有形如PRb的产生式，而 Ra或RaQ。q 有了这两个集合之后，就可以通过检查每个产生式的候选式确定满足关系<和>的所有终结符对。Ø 假定有个产生式的一个候选形为aP 那么，对任何bÎFIRSTVT(P)，有 a<b。Ø 假定有个产生式的一个候选形为Pb 那么，对任何aÎLASTVT(P)，有 a>b。u 按其定义，可用下面两条规则来构造集合FIRSTVT(P)：1.

24、 若有产生式Pa或PQa，则aÎFIRSTVT(P)；2. 若aÎFIRSTVT(Q)，且有产生式PQ，则aÎFIRSTVT(P)。练习：P133-2 计算它的FIRSTVT和LASTVT； 计算G的优先关系 。并确定G是否是一个算符优先文法？u LR分析方法：把"历史"及"展望"综合抽象成状态；由栈顶的状态和现行的输入符号唯一确定每一步工作u LR分析器的核心是一张分析表：u ACTIONs，a：当状态s面临输入符号a时，应采取什么动作.u GOTOs，X：状态s面对文法符号X时，下一状态是什么u 文法G的每个产生式的右部

25、添加一个圆点称为G的LR(0)项目例：如:A®XYZ有四个项目：A®.XYZ A®X.YZ A®XY.Z A®XYZ. F A®a . 称为"归约项目"F 归约项目 S®a . 称为"接受项目"F A®a .ab (aÎVT) 称为"移进项目"F A®a .Bb (BÎVN) 称为"待约项目".例：文法G(S¢) S¢E EaA|bB AcA|d BcB|d 该文法的项目有：1.S

26、62;·E 2.S¢E· 3.E·aA 4.Ea·A 5.EaA· 6.A·cA 7.Ac·A 8.AcA· 9.A·d 10.Ad· 11.E·bB 12.Eb·B 13.EbB· 14.B·cB 15.Bc·B 16.BcB· 17.B·d 18.Bd·u 构造识别文法所有活前缀的NFA方法 1. 若状态i为X®X1 Xi-1.Xi Xn ，状态j为X®X1 Xi-1Xi .Xi+1

27、 Xn ，则从状态i画一条标志为Xi的有向边到状态j； 2. 若状态i为X®a .Ab ，A为非终结符，则从状态i画一条e边到所有状态A®.g。u 把识别文法所有活前缀的NFA确定化。u 构成识别一个文法活前缀的DFA的项目集(状态)的全体称为文法的LR(0)项目集规范族。LR(0)分析表的构造u 假若一个文法G的拓广文法G¢的活前缀识别自动机中的每个状态(项目集)不存在下述情况： 1) 既含移进项目又含归约项目， 2) 含有多个归约项目 则称G是一个LR(0)文法。u 分析表的ACTION和GOTO子表构造方法：1. 若项目Aa·ab属于Ik且GO(I

28、k, a)Ij，a为终结符，则置ACTIONk,a 为“sj”。2. 若项目Aa·属于Ik，那么，对任何终结符a(或结束符#)，置ACTIONk,a为 “rj”(假定产生式Aa是文法G¢的第j个产生式)。3. 若项目S¢S·属于Ik，则置ACTIONk,#为 “acc”。4. 若GO(Ik,A)Ij，A为非终结符，则置GOTOk,A=j。5. 分析表中凡不能用规则1至4填入信息的空白格均置上“报错标志”。u 按上述方法构造出的ACTION与GOTO表如果不含多重入口，则称该文法为SLR(1)文法。u 使用SLR表的分析器叫做一个SLR分析器。u 每个SL

29、R(1)文法都是无二义的。但也存在许多无二义文法不是SLR(1)的.I1、I2和I9都含有“移进归约”冲突。FOLLOW(E)#, ), +，5.3.4 规范LR分析表的构造u 我们需要重新定义项目，使得每个项目都附带有k个终结符。每个项目的一般形式是Aa·b, a1a2ak ，这样的一个项目称为一个LR(k)项目。项目中的 a1a2ak 称为它的向前搜索符串(或展望串)。u 向前搜索符串仅对归约项目Aa·，a1a2ak有意义。对于任何移进或待约项目Aa·b, a1a2ak, b¹e，搜索符串 a1a2ak 没有作用。按上述算法构造的分析表，若不存在多重

30、定义的入口(即，动作冲突)的情形，则称它是文法G的一张规范的LR(1)分析表。使用这种分析表的分析器叫做一个规范的LR分析器。具有规范的LR(1)分析表的文法称为一个LR(1)文法。LR(1)状态比SLR多，LR(0)ÌSLR Ì LR(1) Ì无二义文法。第六章 属性文法和语法制导翻译6.1 属性文法u 属性文法（也称属性翻译文法）u 在上下文无关文法的基础上，为每个文法符号（终结符或非终结符）配备若干相关的“值”（称为属性）。u 属性代表与文法符号相关信息，如类型、值、代码序列、符号表内容等u 属性可以进行计算和传递u 语义规则：对于文法的每个产生式都配备了一

31、组属性的计算规则u 属性u 综合属性：“自下而上”传递信息u 继承属性：“自上而下”传递信息u 综合属性u 在语法树中，一个结点的综合属性的值由其子结点的属性值确定。u 使用自底向上的方法在每一个结点处使用语义规则计算综合属性的值u 仅仅使用综合属性的属性文法称S属性文法u 继承属性u 在语法树中，一个结点的继承属性由此结点的父结点和/或兄弟结点的某些属性确定u 用继承属性来表示程序设计语言结构中的上下文依赖关系很方便6.2.3 一遍扫描的处理方法u 一遍扫描的处理方法是在语法分析的同时计算属性值 u 所采用的语法分析方法u 属性的计算次序u L属性文法适合于一遍扫描的自上而下分析u S属性文

32、法适合于一遍扫描的自下而上分析 6.4 L-属性文法和自顶向下翻译u 通过深度优先的方法对语法树进行遍历，计算属性文法的所有属性值u LL(1)：自上而下分析方法，深度优先建立语法树第七章 语义分析和中间代码产生u 静态语义检查u 类型检查u 控制流检查u 一致性检查 u 相关名字检查u 名字的作用域分析 7.1 中间语言u 常用的中间语言：u 后缀式，逆波兰表示u 图表示： DAG、抽象语法树u 三地址代码u 三元式u 四元式u 间接三元式u 逆波兰表示法不用括号。只要知道每个算符的目数，对于后缀式，不论从哪一端进行扫描，都能对它进行唯一分解。u 后缀式的计算u 用一个栈实现。u 一般的计算过程是：自左至右扫描后缀式，每碰到运算量就把它推进栈。每碰到k目运算符就把它作用于栈顶的k个项，并用运算结果代替这k个项。7.4 布尔表达式的翻译u 布尔表达式的两个基本作用:u 用于逻辑演算,计算逻辑值;u 用于控制语句的条件式.u 产生布尔表达式的文法: EE or E | E andE | Ø E | (E) | i rop i | i第十章 优化u 优化