编译原理复习资料整理.doc

第一章1 编译原理的工作过程（结合p6 图 1.3）编译程序的主要功能是将源程序翻译成等价的目标程序，这个翻译过程（也称编译过程）十分复杂，所以它一般首先分析源程序，然后综合成目标程序。编译程序在分析阶段检查源程序的正确性后，再将其分解为若干基本成分。这其中的工作也包括建立一些表格，改造源程序为中间语言程序。2 编译方式和解释方式的比较（结合p2图 1.1和p3图1.2）编译方式中源程序的编译和目标程序的运行时分成两个阶段完成的。经编译所得的目标程序，计算机暂时还不能直接执行，必须由连接装配程序将目标程序和编译程序以及运行子程序连接成一个可执行程序，这个可执行程序才可直接被计算机执行。解释方式并不先产生目标程序然后再执行之，而是对源程序边翻译边执行。解释程序的主要优点是便于对源程序进行调试和修改，但其加工处理过程速度较慢。3 编译的特性.模块性 静态解释和动态解释 机器无关性 语言标准化 程序语言特征第二章1 文法的形式定义 G=（VN，VT，S，P）VN:非空有限的非终结符号集（变量表）VT:非空有限终结符号集（符号表）S:开始识别符号P:产生式的集合觉得抽象的话，请看21页例题2.12 文法的分类（看产生式 P） 0型文法（PSG ：Phrase Structure Grammar-无限制的文法）-，（VNVT）+，（VNVT）*，即产生式至少有一个非终结符即可。1 型文法（CSG: Context Sensitive Grammar-上下文有关文法）-，=1A2，=1B2，1，2（VNVT）*，AVN，B（VNVT）+，1|意思就是说当B的两边是1，2串,时才将B规约为1A2。2 型文法（CFG ：Context Free Grammar-上下文无关文法）A-，AVN，（VNVT）+，意思就是说把规约成A不需要管的两边是什么。3 型文法（RG: Regular Grammar-右线性文法和正规文法）右线性文法：A或者AB，其中A,BVN，VT*,正规文法：A或者AB，其中A,BVN，VT,即正规文法只能出现单个的终结符号，而右线性文法则可能出现若干个终结符号组成的串拓展 左线性文法：A或者AB，其中A,BVN，VT*,他们的关系如下：典型题型：构造文法生成下列语言（默认是CFG）anb2m-1|n，m1由于符号串中a，b中的个数没有直接关系，所以将句子分成两步分：an和b2m-1，分别构造，所以得文法：（答题时只写出下面的文法即可，下同）GS: SABAa|aABb|bbB anbn|n1GS: SaSb|ab能被5整除的整数的集合除符号位外可以分为首位不能为0，末尾只能是0或者5，中间是0到9的数三个部分文法为：GS:SA|-A|0 A1B|2B|3B|4B|5B|6B|7B|8B|9B B0B|1B|2B|3B|4B|5B|6B|7B|8B|9B|C C0|5解此类题目答案不唯一，只要能正确表达就行，不要想用一个文法就可以表示语言了，多举几个具体的例子找规律，做出题目后最好还要用具体的例子带进去检查。3 句型，句子和语言 短语和句柄的概念（短语和句柄 为第6章的内容）句型：任何能由开始符号推出的符号串。句子：只含有终结符的句型。语言：文法所有句子的集合。短语：设是文法GS中的一个句型，如果有S=*A且A=+，则称是句型相对于非终结符A的短语。直接短语：特别的如有A=，则称是句型相对于规则A的直接短语（简单短语）。句柄：一个句型的最左直接短语称为该句型的句柄。句柄就是“可归约串”。4 构造句型的语法树，书上P29页写得比较详细，还有具体的例子，再此不在赘述5 最左、最右推导和规范推导最左推导：在直接推导xUy=xuy直接推导中，xVT*，UVN，即U是符号串xUy中最左非终结符，则此直接推导为最左直接推导。若一个推导的每一步直接推导都最左直接推导，那么此推导为最左推导。最右推导=规范推导：在直接推导xUy=xuy直接推导中，yVT*，UVN，即U是符号串xUy中最右非终结符，则此直接推导为最右直接推导。若一个推导的每一步直接推导都最右直接推导，那么此推导为最右推导。典型考题 设文法G=（N，D,0,1,2,3,4,5,6,7，P，N）其中 P=NND|D,D0|1|2|3|4|5|6|7,写出3274的最左推导和最右推导最左推导如下：N=ND=NDD=NDDD=3DDD=32DD=327D=3274最右推导如下：N=ND=N4=ND4=N74=ND74=N274=D274=32746 二义性句子的二义性：一个文法，如果它的一个句子有两颗或以上的语法树文法的二义性：至少含有一个二义性的句子语言的二义性：存在二义性的文法描述它自上而下分析方法：从文法的开始符号出发，反复使用文法的产生式，寻找与输入符号串匹配的推导。 自下而上分析方法：从输入符号串开始，逐步进行归约，直至归约到文法的开始符号第三章有穷自动机（FSA：Finaite State Automaton）的形式定义有穷自动机分为确定的有穷自动机（DFSA： Deterministic Finate State Automaton）和非确定有穷的自动机（NDFSA: NonDeterministic Finate State Automaton）DFSA=(Q,t，q0，F)Q是非空有穷状态集，其中的没歌元素成为一个状态；是有穷输入字母表，它的每一个元素称为一个输入符号；t是一个单值映射QQ，也称状态转换函数，t（q，x）=q,意值：当现行状态为q面临的输入符号位x时，将转到下一个状态q,，q,称为q的一个后继状态；q0Q称为开始状态；F Q称为终止状态集，它至少由一个终止状态组成。NDFSA=(Q,t，q0，F)Q是非空有穷状态集，其中的没歌元素成为一个状态；是有穷输入字母表，它的每一个元素称为一个输入符号；t为映射QQ的一个子集，即t为一个多值映射；q0Q称为开始状态；F Q称为终止状态集，它至少由一个终止状态组成。它们之间的主要区别有NDFSA有一个开始状态集，而DFSA只有一个开始状态NDFSA的映射是QQ的一个子集，是一个多值映射，而DFSA的映射是QQ，是一个单值映射。NDFSA在没有扫描符号的情况下，也可以进行移动，成为空移。8 利用造表法将NDFSA确定化结合书上的例子3.6 P61页I 表示当前状态集，Ia表示当前状态面临a时可以到达的状态集或者空移到的状态集，如果这一行产生了新的状态集，则将其加入到下一行中，作为另一个新的状态集。表造好后，将I这列依次赋予新的状态号，如0,1，如果某个状态包含以前的终结状态，则这个状态就位新的终结状态。最后根据确定后的状态转换表，画出新的状态转换图即可。如 I=S,5,1,为初始状态集，55a，31a，15，5S，所以Ia=5,3,1，5,3，1没有在前面出现过，为新的状态。其他的状态同理可求。表建好后，将所有I这一列从新编号，依次为0,1，由于H为终态，所以包含H的状态集都未终态。Ia和Ib这两列中用I列中相应的编号表示即可。确定后就可以画状态转换图了。9 DFSA的化简：将相同的状态和为一个何为相同的状态，就是值如果两个状态面临所有的不同输入符时，得到的结果都一样。算法描述：P65页我的理解：首先将所有的状态分为终态组和非终态组两部分分别检测这两组中面临所有不同的输入符时是不是还在同一组，如果是就有可能是相同的状态，如果不是，则一定不是相同的状态，重复这个过程，直到不能再分为止结合62页 图3.12，首先将其分为两组，即终态组3,4,5,6和非终态组0,1,23,4,5,6a=（3,6,6,3）3,4,5,6 3,4,5,6b=（4,5,5,4）3,4,5,6，所以3,4,5,6应该属于同一个状态0,1,2a=（1,3,1），不在同一个组中，应该将其分开为1和0,20,2b=（2,5）也不在同一个组中，应该将其分开为0，2，化简后如书上图3.14 P6610 从正规文法到FSA的转换结合书上P69页 例题3.10 注意F是增设的终态 书上说的比较详细，在此不在赘述11从FSA到正规文法（考的概率较小）结合书上P70页 例题3.11 注意如果是终态 Z，要加上 Z；12 正规表达式到FSA规则：书上P73 图3.20 ，注意，对于构造的自动机，不要出现太多的空移13 从正规文法到正规表达式（考的概率小）转换规则P80页第四章1词法分析的主要任务是从左向右扫描每行源程序的符号，按照词法规则从构成源程序的字符串中识别出一个个具有独立意义的最小语法单位，并转换成统一的内部表示(token)，送给语法分析程序。第五章1 消除左递归对于直接左递归（形如 UUx）可根据如下所示消除：UUx1|Ux2|Ux3|Uxm|y1|y2|yn，则Uy1U|y2U|ynUUx1 U|x2 U|xm U|多于间接左递归，要采用会带的方式，使之变为直接左2 LL(1)分析表的构造首先要会构造FIRST,FOLLOW集合，构造规则在书上P116到P117,构造这两个集合，要理解这两个集合表示什么FIRST（U）表示U串中的第一个符号的集合，FOLLOW（U）表示跟在U串中的第一个符号的集合，SELECT集合表示当前读头为某个字符时应该选择哪个产生式。搞清楚它们的本质，那就好求了。 例题 设文法GE: E-TEE-+E| T-FTT -T| F- PFF- *F| P-(E)|a|b| FOLLOW集合有： （除了识别符号，主要看产生式的右部）FOLLOW(E)=),$; /出现E的有，和，由，知$FOLLOW(E)，由知 )FOLLOW(E)FOLLOW(E)=FOLLOW(E)=),$; /由知 FOLLOW(E) FOLLOW(E)FOLLOW(T)=（FIRST(E)- ）FOLLOW(E)=+,), $; /由知道（FIRST(E)- ） FOLLOW(T)，由知道E可为，所以FOLLOW(E) /FOLLOW(T)FOLLOW(T)=FOLLOW(T)= +,), $; /由知FOLLOW(T) FOLLOW(T)FOLLOW(F)=（FIRST(T)- ）FOLLOW(T)=(,a,b,+,), $;/由知（FIRST(T)- ） FOLLOW(F)，又由知道，T可为，所以FOLLOW(T) / FOLLOW(F)FOLLOW(F)=FOLLOW(F) =(,a,b,+,), $; /知 FOLLOW(F) FOLLOW(F)FOLLOW(P)= （FIRST(F)- ）FOLLOW(F)=*,(,a,b,+,), $;/由知（FIRST(F)- ） FOLLOW(P)，又知F可为，所以FOLLOW(F) /FOLLOW(P)各产生式的SELECT集合有： SELECT(E-TE)=FIRST(T)=(,a,b,; SELECT(E-+E)=+; SELECT(E-)=FOLLOW(E)=),$ SELECT(T-FT)=FIRST(F)=(,a,b,; SELECT(T-T)=FIRST(T)=(,a,b,; SELECT(T-)=FOLLOW(T)=+,),$; SELECT(F-PF)=FIRST(P)=(,a,b,; SELECT(F-*F)=*; SELECT(F-)=FOLLOW(F)=(,a,b,+,), $; SELECT(P-(E)=( SELECT(P-a)=a SELECT(P-b)=b SELECT(P-)= 分析表如下所示第六章1 简单优先分析方法FIRST与LAST的求法FIRST: AB，AVN，B（VNVT），（VNVT）*,也就是说B是A的产生式的第一个符号。FIRST+：从A推导出来的头符号的集合FIRST*:从A推导出来的头符号的集合（包含自身）LAST:AB，AVN，B（VNVT），（VNVT）*,也就是说B是A的产生式中的最后一个符号。LAST +：从A推导出来的尾符号集合。LAST *:从A推导出来的尾符号集合（包含自身）、 ，三个关系的求法的求法：ULR，L,R（VNVT）；，（VNVT）*，则L R，即产生式的右侧任意相邻的两个符号是相等的。的求法：ULP，P=+R，L,R（VNVT），P VN，（VNVT）*，则LR 也可利用公式的求法：UWP，W=+L ，P=*R；L,R（VNVT）；W，P VN；，（VNVT）*；则LR例题：见书上的152页 例6.11思路：找等于的时候找相邻的符号即可，找小于或者大于，应该找至少有一个终结符的文法片段，且到终结符截止，中间每一个过程都会有这样一个关系。拿上面的例子来说S-bMbM-（L|a L-Ma）等于：这个只要是相邻的符号，都是的（b，M），（M，b），（，L），（M，a），（a，）小于：两相邻的符号，靠右边的为非终结符，靠左边的将小于所有靠右边的产生的一个符号，直到终结符为止由知b会小于M产生的第一符号，即（b，（），（b，a）由知（会小于L产生的第一个符号，即（，M），M为非终结符，（继续小于M产生的第一个符号，即（，（），（，a）大于：两相邻的符号，右边的为非终结符，则右边产生的最后一个符号要小于左边的符号和左边产生的第一个符号，直到终结符为止。由知，M产生的最后一个符号大于b，