哈工大软件学院编译原理考试大纲重点

《哈工大软件学院编译原理考试大纲重点》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第二章高级语言及其文法（1）什么是推导？什么是归约？推导：用某条规则的右部替换该规则的左部归约：用某条规则的左部替换该规则的右部（2）什么是句型？什么是句子？句型:如果符号串α是从开始符号S推导出来的，即有S⇒*α，α∈(ＶT∪ＶN)*，则称α是G产生的一个句型句子:如果S⇒*α，且α∈ＶT*，则称α是G产生的一个句子（3）什么是0~3型文法？各由什么机器识别？Ｇ=(ＶT，ＶN，Ｐ，Ｓ)是一个文法,α→β∈P文法描述由什么机器识别0型G图灵机无限制文法/短语结构文法PSG1型

2、α

3、≤

4、β

5、(除Ｓ→ε)的G线性界限自动机上下文有关文法CSG2型α∈ＶN的Ｇ

6、不确定的下推自动机上下文无关文法CFG3型右线性文法：A→aB或A→a的G左线性文法：A→Ba或A→ａ的G有穷自动机正规文法L(G)为1型/上下文有关/敏感语言(CSL)L(G)为2型/上下文无关语言（CFL）Ｌ(G)为3型/正规集/正则集/正则语言（RL）第三章词法分析词法分析器的基本任务：识别单词（的种类）单词的机内表示(种别码，属性值)单词种类：关键字，标识符，常量，运算符算术，关系，界限（1）正规式、NFA和DFA之间的等价变换（2）各类单词的状态转换图第四章语法分析（1）什么是最左推导？什么是最右推导？最左推导：每次推导都施加在句型的最左边的语

7、法变量上。与最右归约对应最右推导：（规范句型）每次推导都施加在句型的最右边的语法变量上。（２）自顶向下分析的基本思想基本思想：?寻找输入符号串的最左推导?试图根据当前输入单词判断使用哪个产生式基本过程：从根开始，按与最左推导相对应的顺序，构造输入符号串(Token)的分析树（３）产生回溯的原因文法中每个非终结符A的产生式右部称为A的候选式，如果有多个候选式左端第一个符号相同，则语法分析程序无法根据当前输入符号选择产生式，只能试探（4）文法的改造：消除左递归、消除回溯直接左递归的消除方法A→Aα

8、β　＝　A→βA′　　A′→αA′｜ε消除间接左递归：为非终

9、结符编号，再采用代入法将间接左递，归变为直接左递归消除回溯：提取左因子（5）求FIRST(α)的算法，求FOLLOW(A)的算法FIRST(α)的算法:若X→Y…∈P，且Y∈ＶN则FIRST(X)=FIRST(X)∪FIRST(Y)；若X→Y1…Yn∈P，且Y1...Yi-1⇒*ε：FIRST(X)=FIRST(X)∪…∪FIRST(Yk)；FOLLOW(A)的算法:1)将#加入到FOLLOW(S)2)若A→αBβ，则FOLLOW(B)=FOLLOW(B)∪FIRST(β)3)如果A→αB或A→αBβ，且β⇒*ε，A≠B，则FOLLOW(B)=FOLLO

10、W(B)∪FOLLOW(A)Selct(i)的算法:（6）LL(1)文法的判定，LL(1)分析表的构造LL(1)文法:同一非终结符的各个产生式的可选集互不相交?不存在终结符a，使得同一非终结符A的两个候选式αi和αj都能导出以a为首的串?同一非终结符的各个候选式中最多只有一个可以推导出空串（7）LL(1)通用控制算法LL(1)通用控制算法repeatX=当前栈顶符号;a=当前输入符号；ifX∈ＶT∪{#}thenifX=athenifX≠#then{将X弹出,且前移输入指针}elseerrorelseifM[X,a]=Y1Y2…Ykthen{将X弹出;依

11、次将Yk…Y2Y1压入栈；输出产生式X→Y1Y2…Yk}elseerroruntilX=#（8）预测分析法实现步骤预测分析法实现步骤?1）构造文法?2）改造文法：消除二义性、消除左递归、提取左因子?3）求每个变量的FIRST集和变量的FOLLOW集，从而求得每个候选式的SELECT集?4）检查是不是LL(1)文法?5）构造预测分析表?6）实现预测分析器（9）递归下降法的基本思想递归下降法算法基本思想?为每个非终结符编制一个递归下降过程，过程名表示产生式左部的非终结符，过程体则是按该产生式右部符号串顺序编写的?每匹配一个终结符，则再读入下一个符号；?对于产

12、生式右部的每个非终结符，则调用相应的过程?当一个非终结符对应多个候选式时，过程体将按可选集来决定选用哪个候选式（10）LR分析器的工作过程LR分析器的工作过程??1.初始化:s0#a1a2…an#对应“句型”a1a2…an??2.一般情况下s0s1…sm#X1…Xmaiai+1…an#对应“句型”X1…Xmaiai+1…an①Ifaction[sm,ai]=sithen格局变为：s0s1…smi#X1…Xmaiai+1…an#②Ifaction[sm,ai]=ri表示用第i个产生式A→Xm-(k-1)…Xm进行归约then格局变为：s0s1…sm-k#X

13、1…Xm-kAaiai+1…an#查goto表，当goto[sm-k,A]=it