编译原理期末复习原版

每种类型题目给出了所涉及到的基本知识，然后对每类题目中的第一道例题进行了做法进行了讲解，剩下的例题请给大家作为练习，答案也都给出，希望对大家复习有所帮助，最2)构成：语法分析的主要任务是对输入的单词符号进行语法分析（根据语则进行推导或其中VT：终结符集合(非空)VN：非终结符集合(非空)，且VTVN= G：S→ifexprthenSS→ifexprthenSelse ife1thenife2thens1else文法的形式（231）0，其中：(VTV*NN有一个非终结符；(VTV*NN2）1型(上下文有关文法，线性界限自动机)：产生式形式为: 其中：||||，仅S例外，但是S不得出现在任何产生式右部。N3）2（上下文无关文法，非确定下推自动机)：产生式形式为：PPVNN

V*4）3：ABA V 左线性文法：产生式形如：ABA其中： G1GNTN：PPV(VV*NTN1型文法：产生式形式为: 其中：||||，仅S例外，但是S不得出现在 正则文法：右线性文法：产生式形如：ABA其中：V 左线性文法：产生式形如：ABA其中：V 答：PDA，PDAMK:有穷状态 h0:H中的初始符 f:K（Σ{})H–>K Z:包含于K，是终结状态集合。MM=(S,f,S0F),其中：1）S:有穷状态集，2）：输入字母表(有穷)，s，asss 5）FS：终态集(可空)

直接短语：PαPα，则α称为直接短语。(15)向量：一般编译程序对数组说明的处理是把数组的有关信息汇集在一个叫做“向量”或“信息向量”的表格中，以便以后计算数组元素的地址时这些信息。每个数组有Old 考题：1）G[S]为：S→SdT|TT→T<G|GG→(S|a试给出句型(SdG)<a的推导过程及语法树，并找出(SdG)<a的短语，直接（简单）短语、句柄和最左素短语。答：（1）STT<G

（2）短语：G，SdG,(SdG),a, 直接短语：G，a句柄：G最左素短注:还有一份试卷将句型改为adT<(S)，与这个类似，大家自己做做，答案是 直接短语：a,(S)句柄：a 单单简单短语:简单短语:Ab, •句柄Aba⑶;B-※【例2.13】G(S):S->aAcBe;A给定符号串 【例212】图23为E FT/ 图 E+F-T/F*i的语法⑵⑶SAcBE+F-短语:E+F-句柄: ②列出句型的所有短语、简单短语。（还有一份试卷上是出句型F+T*F的所有短语、简单最右推导（2）短语;i,i+i,(i+i),(i+i)*i直接短语：i3（正规文法2掌握几个基本形式{an|n>0}S→aS|an>=0S→aS|ε(ε{anbn|n>0}S→aSb|语言的类型。（10分） |n≥0,m>0二型文法 L2={0na1nbmcm|n>0，m二型文法：S→AB分L1candbm|n≥0,m>0} L20na1nbmcm|n>0,m0} 44、按指定的类型给出下列语言的文法分 3、按指定的类型给出下列语言的文法分L1canbm|n≥0,m>0} L20na1nbm|n>0，m0}P36第11或者SA|A0A1|B1B0|XX---XABCBDEC--DDCEFCF-GGFC首先将集合分为{A,B,D,F,G},{C,E}。{A,B,D,G}都有a,b作为条件输出，F只有b输出，所以分为{A,B,D,G}和{F}同理{C,E}分为{C},{E}。{A,B,D}a={B,DG}a={F}所以{A,B,D,G}分为{A,B,D}和{G}。{A}b={C}{B,D}a={D}所以分为{A}{B,D}2：NFADFA(10ФФФФabSABAACBФECDEDФFEФФFDEYDFA的终态,3：01（10分00102 4003状态1：偶数个0偶数个 状态3：奇数个0奇数个 左递归和回溯（具体请参见简答题中的第（14）题提取公共左因子:AA→1|2|…|n|1|2||m(其中，每个不以开头)那么，可以把这些规则改写成A→A|1|2||A→1|2|…|P→P|，其中不以P开头。我们可以把P的规则等价地改写为如下的非直接左递归形 PP→P1|P2||Pm|1|其中，每个都不等于，每个都不以P开头那么，消除P的直接左递归性就是把这些规则改写成：P→1P|2P|…|nP P→1P|2P|…|mP|例：文法E→E＋T|TT→T*F|FF→(E)| E→+TE| T→FT T→*FT| F→(E|iS→[A A→ A’→SA’| B’→B|考题2：写出文法G[A]: C→Bg|h消除左递归后的文法。答：(1)经分析发现文法G[A]并无直接左递归；BC得：C→dAg|Aeg|fg|h又由于AA→BaA→CbB,CA得到：A→dAa|Aea|fa|dAgb|Aegb|fgb|hb|cA→Aea|Aegb|dAa|fa|dAgb|fgb|hb|c将A消除直接左递归A→dAaA’|faA’|dAgbA’|fgbA’|hbA’|c A’→eaA’|egbB→dA|Ae|f，C→dAg|Aeg|fg|h由于未在任何产生式的右部出现，所以是多’A’→eaA’|egb一个当前符号（括号中的1 则FIRST(i)∩FIRST( 对文法中的每个非终结符A，若它存在某个候选首符集包含，则FIRST( i=1,2,...,nGGLL(1LL(1)文法的三个充要条件，分为以下几步：1）LL(1)文法；*算Select集合，书上没有提到Select集合，计算Select集合实质就是计算First()，当然考试时不一定非要写成SelectFirst()来判断交LL(1)1。1.的分析过程。（15分 LL(1)LL(1)LL(1)文法的充要条件，有一个不满足就不是LL(1)文法。对于aabe根据文法SaDaSTeaaDTeaaTeaabMeMε，所以最后肯定推不出来，也就是LL(1)文法，否则题目就不好往下做，没有意义。Sa D TbeMbeH e②将文法分解为： Follow(D)={#b} Follow(H)={e∵First(Ste)∩Follow(D)=Ф∴该文法是LL(1)文法abe#SDTMHaabe01aabe23456782LL(1)LL(1)分析表，写出aaabd的分 （1） FirstFollowSa#H#M,AbSelect ∵Select(H→aMd)∩Select(H→d)=Select(M→Ab)Select(A→aM)∩Select(A→e)=adbeSHMA01aaabd23456789##上托栈顶符号放入将规则X→X1X2...Xn上托栈顶符号放入将规则X→X1X2...Xn是是是否 是否否否是'#','S'进栈，当前终结符送结出出1为更正后的答案。考题1：为文法G[E]：E→V| V→N| N→i构造递归下降识别程序（10分（1） E’ V V’→[E]| N→ IFSYM=‘+’ IFSYM=‘[’THEN ELSE

SYM=‘i’ELSEERROR; （1） E→+TE| T→*FT| F→(E)|

IFSYM=‘i’THENIFSYM=‘(’THENIFSYM=‘)’ELSEERRORELSELR(0)是考定的了，SLR(1),LR（1）LR(0)分析法个人感觉也 LR(0)A→AbA→•AbA→A•bA→Ab•都是该产识别进度的定位。项目A→Ab•Ab的一切条件，因此被称为归约项项目可以分为以下四类：P→α•aβ称为移进项目其中P→α•Xβ称为待约项目，其中X为非终结符，P→α•称为归约项目，S→S称为接收项目LR分析器的是一张分析表ACTION[s，a]：当状态s输入符号a时，应采取什么动作GOTO[s，X]sX#a1a2ai an# 程序状态符 分析 LR分析每一项ACTION[s，a]所规定的四种动作移进把(s，a)的下一状态s’和输入符号a推归约指用某产生式A 的长度为r，归约动作是，去除栈顶r个项，下一状态s’=GOTO[sm-r,A]和文法符号A推进接受宣布分析成功，停止分析器工作报(1)文法：假定文法G是一个以S为开始符号的文法，我们构造一个G，它包含了整个GGSS→SS是结符，非终结符都可以，GO(I，X)=CLOSURE(J).J是从I中项目出发后X后到达的后J={P→αX•β|P→α•Xβ∈I}CLOSUREGOCLOSURE({S→•S})GO DFALR(0)LR(0)构造方法如 ACTION[s，a]所规定的四种动作:(s，a)s’a推进栈，下一输入符号变成现行输入归约指用某产生式A→β进行归约.假若βr，归约动作是，去A]A推进栈.接受（acc）宣布分析成功，停止分析器工作（0）S→E（1）E→aA（2）E→bB（3）A→cA（4）A→d（5）B→cB（6）B→d句子进行分析后必定得到“acc（接受的意思LR(0)分析表出错。（1）I0=Closure({S→•E})={S→•E,E→•aA,E→•bB}I1=GO(I0,E)=Closure({S→E•})={S→E•}I2=GO(I0,a)=Closure({E→a•A})={E→a•A，A→•cA，A→•d}I3=GO(I0,b)=Closure({E→b•B})={E→b•B,B→•cB，B→•d}I0是必须要的I4=GO(I2,A)={E→aA•} I5=GO(I2,c)={A→c•A，A→•cA，A→•d}I6=GO(I2,d)={A→d•} I7=GO(I3,B)={E→bB•}I8=GO(I3,c)={B→c•B，B→•cB，B→•d} I9=GO(I3,d)={B→d•}I10=GO(I5,A)={A→cA•} I11=GO(I8,B){ i代表跳转到第i12345#6#7#8#9#（1）-a-(b*c/(c-d)+(- -A+B*C↑解：（1）a@bc*cd-/b@a*+-（2）如：A+B*(C-D)+E/(C-D)^N对应的四元式序列如下:四元式: (-,C,D,T1) (*,B,T1,T2) (+ (- (^ (6)(/,E (+,T3,T6注：T1,T2（jnz,a,-- p 表示if (jrop,x,y, p) 表示if xropy p（rop代表关系(j,-- ---, 表 例如：写出条件语句IFa>0THENx:=x+1ELSEx:=4*(x1)(1)(j>,a,0(2)(j,-,-,(6))(3)(+,x,1,T1)(4)(:=,T1,-,T2(5)(j,-,-(6)(-,x,1,(7)(*,4,T3,T4(8)(:=,T4,-,x)（5）和（9） 答案答案ifx>ythen}x:=z+写出上述代码的四元式或者三址码。（(6)(:=,T3,-(9)(:=,T4,-100:ifx>ygoto101:goto102:T1:=y-103:104:105::107:goto108:109:(1)高级语言程序中常用的参数传递方式有哪些？请根据这些传递方式写出程序的运staticintintp(intx,inty,int{cout<<"InP}

int{inta=2;intb=3;cout<<"Inmain"<<a<<endl;return0;}分析：函数paaapa1.a2；Pa=a+1a=3a=a+aa=6;传名时，直接将实参带入形参，原来程序被替换为:a=a+1;a=a+a；a=26.答：①C1)传值2）传地址3）

传值方式：InPInmain

传地址：InPInmain

传名:InPInmainProcedurep(x,y,z);end;{p}

p(a+b,a,a)printa2传地址传递时输出结果为：8 ， read read rea