下载文档原格式
编译原理期末复习题(包含上一份N多答案)(总28页)--本页仅作为文档封面，使用时请直接删除即可----内页可以根据需求调整合适字体及大小--编译原理复习题一、填空题：1、编译方式与解释方式的根本区别在于（是否生成目标代码）。
2、对编译程序而言，输入数据是（源程序），输出结果是（目标程序）。
3、如果编译程序生成的目标程序是机器代码程序，则源程序的执行分为两大阶段：（编译阶段）和（运行阶段）。
4、如果编译程序生成的目标程序是汇编语言程序，则源程序的执行分成三个阶段：（编译阶段）、（汇编阶段）和（运行阶段）。
5、自顶向下语法分析方法会遇到的主要问题有（回溯）和（（左递归带来的）无限循环）。
6、LL(k)分析法中，第一个L的含义是（从左到右进行分析），第二个L的含义是（每次进行最左推导），“k”的含义是（向输入串中查看K个输入符号）。
7、LL(1)分析法中，第一个L的含义是（从左到右进行分析），第二个L的含义是（每次进行最左推导），“1”的含义是（向输入串中查看1个输入符号）。
8、自顶向下语法分析方法的基本思想是：从（识别符号）出发，不断建立（直接推导），试图构造一个推导序列，最终由它推导出与输入符号相同的（符号串）。
9、自底向上语法分析方法的基本思想是：从待输入的符号串开始，利用文法的规则步步向上进行（直接归约），试图（归约）到文法的（识别符号|开始符号）。
10、LR(0)分析法的名字中，“L”的含义是（从左到右进行分析），“R”的含义是（采用最右推导的逆过程---最左归约），“0”的含义是（向貌似句柄的符号串后查看0个输入符号）。
11、LR(1)分析法的名字中，“L”的含义是（从左到右进行分析），“R”的含义是（采用最右推导的逆过程---最左归约），“1”的含义是（向貌似句柄的符号串后查看1个输入符号）。
12、SLR(1)分析法的名字中，“S”的含义是（简单的），“L”的含义是（从左到右进行分析），“R”的含义是（采用最右推导的逆过程---最左归约），“1”的含义是（向貌似句柄的符号串后查看1个输入符号）。
1.给出语言{a n b n a m b m | n,m≥0}的一个上下文无关文法。
(6分)解：G[S]：S—>ABA—>aAb |εB—>aBb |ε2.给出语言{1 n 0 m 1 m0 n | n,m≥0}的一个上下文无关文法。
解：G[S]：S—>1S0 | AA—>0A1 |ε3.P48 第6题（5）、（6）.画语法树6、已知文法G：<表达式>::=<项>｜<表达式>＋<项><项>::=<因子>｜<项>*<因子><因子>::=（<表达式>）｜i（５）i+(i+i) （６）i+i*i解：(5)语法树：（6）语法树：4.P48第13题直接短语等13、一个上下文无关文法生成句子abbaa的推导树如下：(3)求直接短语解：直接短语有：a ε bP102例题6.1及其分析.( 后加画语法树)例6.1 设文法G[S]为：(1)S—>aAcBe(2)A—>b(3)A—>Ab(4)B—>d对输入串abbcde#进行分析，检查该符号串是否是G[S]的句子。
步骤符号栈输入符号串动作（1）# abbcde# 移进（2）#a bbcde# 移进（3）#ab bcde# 归约（A—>b）（4）#aA bcde#移进（5）#aAb cde# 归约（A—>Ab）（6）#aA cde# 移进（7）#aAc de# 移进（8）#aAcd e# 归约（B—>d）（9）#aAcB e# 移进（10）#aAcBe # 归约（S—>aAcBe）（11）#S # 接受一、计算分析题（60%）1、正规式→ NFA→ DFA→最简DFAP72第1题（1）、（4）；第一题1、构造下列正规式相应的DFA.（1）1(0|1)*101解：先构造NFA0 1S AA A ABAB AC ABAC A ABZABZ AC AB除S，A外，重新命名其他状态，令AB为B、AC为C、ABZ为D，因为D含有Z（NFA的终态），所以0 1S AA A BB C BC A DD C B(4) b((ab)*|bb)*ab解：先构造NFA得到DFA如下所示：P72第4题（a）4、把下图确定化和最小化解：确定化：a b0 01 101 01 11 0、{1}，其中A为初态，A，B为终态，因此有：a bA B CB B CC A最小化：：初始分划得终态组{A,B}，非终态组{C}Π0：{A,B}，{C}，对终态组进行审查，判断A和B是等价的，故这是最后的划分。
1、给出下面语言的相应文法。
L1={a n b n c i|n≥1,i≥0}从n，i的不同取值来把L1分成两部分：前半部分是anbn：A→aAb|ab后半部分是ci：B→Bc|ε所以整个文法G1[S]可以写为：G1(S):S→AB ；A→aAb|ab ；B→cB|ε3、构造一个DFA，它接受 ={a，b}上所有包含ab的字符串。
（要求：先将正规式转化为NFA，再将NFA确定化，最小化）4、对下面的文法G:E →TE’ E’→+E|ε T →FT’ T’→T|εF →PF’ F’ →*F’|ε P →(E)|a|b|∧（1）证明这个文法是LL(1)的。
（2）构造它的预测分析表。
(1)FIRST(E)={(,a,b,^}FIRST(E')={+,ε}FIRST(T)={(,a,b,^}FIRST(T')={(,a,b,^,ε} FIRST(F)={(,a,b,^}FIRST(F')={*,ε}FIRST(P)={(,a,b,^}FOLLOW(E)={#,)}FOLLOW(E')={#,)}FOLLOW(T)={+,),#}FOLLOW(T')={+,),#}FOLLOW(F)={(,a,b,^,+,),#} FOLLOW(F')={(,a,b,^,+,),#}FOLLOW(P)={*,(,a,b,^,+,),#} (2)考虑下列产生式:'→+'→'→'→E E T T F F P E a b ||*|()|^||εεεFIRST(+E)∩FIRST(ε)={+}∩{ε}=φ FIRST(+E)∩FOLLOW(E')={+}∩{#,)}=φ FIRST(T)∩FIRST(ε)={(,a,b,^}∩{ε}=φ FIRST(T)∩FOLLOW(T')={(,a,b,^}∩{+,),#}=φ FIRST(*F')∩FIRST(ε)={*}∩{ε}=φFIRST(*F')∩FOLLOW(F')={*}∩{(,a,b,^,+,),#}=φ FIRST((E))∩FIRST(a) ∩FIRST(b) ∩FIRST(^)=φ 所以,该文法式LL(1)文法. (3)+ * ( ) a b ^ # EE TE →'E TE →' E TE →' E TE →'E' '→+E E'→E ε'→E εTT F T →' T F T →' T F T →' T F T →' T' '→T ε'→T T '→T ε '→T T '→T T '→T T '→T εFF P F →'F P F →' F P F →' F P F →'F' '→F ε '→'F F * '→F ε '→F ε '→F ε '→F ε '→F ε '→F εPP E →() P a → P b → P →^5、考虑文法: S →AS|b A →SA|a （1）列出这个文法的所有LR(0) 项目。
编译原理复习题有答案编译原理复习题及答案一、选择题1. 编译器的主要功能是什么？A. 代码格式化B. 代码优化C. 将源代码转换为机器码D. 错误检测和修复答案：C2. 词法分析阶段的主要任务是什么？A. 语法分析B. 语义分析C. 识别源程序中的词法单元D. 代码生成答案：C3. 下列哪个不是编译原理中的常见数据结构？A. 栈B. 队列C. 哈希表D. 链表答案：D4. 语法分析通常采用哪种方法？A. 递归下降分析B. 动态规划C. 贪心算法D. 深度优先搜索答案：A5. 代码优化的目的是什么？A. 增加程序长度B. 减少程序运行时间C. 提高程序的可读性D. 增加程序的复杂性答案：B二、简答题1. 简述编译过程的主要阶段。
答案：编译过程主要分为四个阶段：词法分析、语法分析、语义分析和代码生成。
词法分析负责将源代码分解成词法单元；语法分析构建语法树，检查源代码的语法结构；语义分析检查程序的语义正确性；代码生成将源代码转换成目标代码或机器码。
2. 什么是自底向上的语法分析方法？答案：自底向上的语法分析方法是一种从叶子节点开始，逐步向上构建语法树的方法。
它通常使用移进-归约分析技术，通过将输入符号与栈顶符号进行匹配，不断地将它们归约成非终结符，直到整个输入被归约为起始符号。
3. 请解释什么是中间代码，并说明其作用。
答案：中间代码是一种介于源代码和目标代码之间的代码形式，通常用于代码优化和目标代码生成。
它具有高级语言的可读性，同时又能表达程序的控制流和数据流信息。
中间代码使得编译器可以在不同的阶段对程序进行优化，提高程序的执行效率。
三、论述题1. 论述编译原理中的错误处理机制。
答案：编译原理中的错误处理机制主要包括错误检测、错误恢复和错误报告。
错误检测是指在编译过程中识别出源代码中的语法或语义错误；错误恢复是指在检测到错误后，编译器采取的措施以继续编译过程，避免因单个错误而中断整个编译；错误报告则是向程序员提供错误信息，帮助其定位和修复错误。
编译原理复习最终版第⼀章⼀.单项选择1.将编译程序分成若⼲“遍”，是为了（）A.提⾼程序的执⾏效率B.使程序的结构更为清晰C.利⽤有限的机器内存并提⾼机器的执⾏效率D.利⽤有限的机器内存但降低了机器的执⾏效率2.⼀个编译程序在编译时，⼤多数时间花在（）上A.出错处理B.词法分析C.⽬标代码⽣成D.表格管理及处理3. 下⾯代码不可能是⽬标代码的是（）A. 汇编指令代码B. 可重定位指令代码C. 中间代码D. 绝对指令代码4. 解释程序和翻译程序的根本区别A. 是否⽣成中间代码B. 是否有语义分析阶段C. 是否⽣成⽬标代码D. 是否有语法分析阶段5. 下⾯编译阶段既可以作为编译器的前端，也可以作为编译器的后端的是：（）A. 语法分析阶段B. 语义分析阶段C. 中间代码⽣成阶段D. 中间代码优化阶段⼆.多项选择1. ⼀个编译器可能有的阶段为（）A. 词法分析B. 语法分析C. 语义分析2. 编译器的各个阶段的⼯作都涉及到（）A. 表格处理B. 词法分析C. 语法分析D. 语义分析E. 出错处理3. ⼀般来说，编译器可分为前端和后端，下列编译阶段可被划分为编译的前端的有：（）A. 词法分析B. 语法分析C. 语义分析D. 中间代码⽣成E. 中间代码优化三.判断题1.⼀个编译器就是⼀个程序，该程序的输⼊是源程序，输出是与之等价的⽬标程序。
2.编译与解释程序的根本区别是：是否⽣成⽬标代码。
3.解释程序和编译程序的前端是相同的，其实现技术基本上也是相通的。
4.⼀般⽽⾔，中间代码是⼀种独⽴于具体硬件的记号系统。
四.综合题1.请画出编译程序的总体框图。
2.源程序的解释和和编译执⾏的主要区别是什么？第三章⼀.单项选择题1.词法分析器的输出是：（）A.单词在符号表中的位置B.单词的⾃⾝值C.单词的⾃⾝值和单词的种类码D.单词的种类码2.词法分析的依据是：（）A.语义规则B.构词规则C.语法规则D.等价变换规则3. 两个DFA等价是指：（）A. 这两个DFA的状态数相同B. 这两个DFA的状态数和有向弧条数都相等C. 这两个DFA的有向弧条数相等D. 这两个DFA接受的语⾔相同4. 词法分析器的输⼊是：（）A. Token序列B. 源程序C. ⽬标程序D. 符号表5.下列符号串不可以由符号集∑＝{a,b}上的正闭包运算产⽣的是：（）A. εB. aD.ab⼆.多项选择1. 令∑＝{a,b}，则∑上的符号串的全体可⽤下⾯的正规式表⽰。
编译原理复习题及答案一、选择题1．一个正规语言只能对应( B )A 一个正规文法B 一个最小有限状态自动机2．文法G[A] ：A→εA→aB B→Ab B→a是( A )A 正规文法B 二型文法3．下面说法正确的是( A ) A一个SLR（1）文法一定也是LALR （1）文法B一个LR （1）文法一定也是LALR （1）文法4．一个上下文无关文法消除了左递归，提取了左公共因子后是满足LL （1）文法的( A )A 必要条件B 充分必要条件5．下面说法正确的是( B )A 一个正规式只能对应一个确定的有限状态自动机B 一个正规语言可能对应多个正规文法6．算符优先分析与规范归约相比的优点是( A )A 归约速度快B 对文法限制少7．一个LR （1）文法合并同心集后若不是LALR （1）文法( B )A 则可能存在移进/归约冲突B 则可能存在归约/归约冲突C 则可能存在移进/归约冲突和归约/ 归约冲突8．下面说法正确的是( A )A Lex 是一个词法分析器的生成器B Yacc 是一个语法分析器9．下面说法正确的是( A )A一个正规文法也一定是二型文法B一个二型文法也一定能有一个等价的正规文法10．编译原理是对(C) 。
A 、机器语言的执行B、汇编语言的翻译C、高级语言的翻译D、高级语言程序的解释执行11．(A) 是一种典型的解释型语言。
A ．BASICB ．CC．FORTRAN D．PASCAL12．把汇编语言程序翻译成机器可执行的目标程序的工作是由(B) 完成的。
A. 编译器B. 汇编器C. 解释器D. 预处理器13．用高级语言编写的程序经编译后产生的程序叫(B) A ．源程序B ．目标程序C．连接程序 D ．解释程序14．(C) 不是编译程序的组成部分。
A. 词法分析程序B. 代码生成程序C.设备管理程序D. 语法分析程序15．通常一个编译程序中，不仅包含词法分析，语法分析，语义分析，中间代码生成，代码优目标代码生成等六个部分，还应包括(C)A ．模拟执行器B ．解释器C．表格处理和出错处理D ．符号执行器16．编译程序绝大多数时间花在(D) A ．出错处理B．词法分析C．目标代码生成D．表格管理17．源程序是句子的集A. 线性表(B) 可以较好地反映句子的结构。
总复习■第1章1、编译程序是一种翻译程序，它将高级语言所写的源程序翻译成等价的机器语言或者汇编语言的目标程序。
2、编译程序是计算机系统中重要的系统软件！3、解释程序与编译程序的主要区别是解释程序在执行过程中不产生目标程序。
4、编译的各个阶段。
答：整个编译过程可以分为5个阶段：词法分析，语法分析，语义分析及中间代码生成，代码优化和目标代码生成。
5、编译程序的结构框图或步骤。
6、遍（趟）：是对源程序或源程序的中间结果从头到尾扫描一遍，并作有关加工处理，生成新的中间结果或目标程序的过程。
■第2章1、符号串的基本运算。
2、简单的说文法由产生式组成；产生式中的符号分为两类：终结符号和非终结符号。
3、推导（最左、最右）、句型、句子、短语、句柄4、乔姆斯基层次中：L3 ⊂ L2 ⊂ L1 ⊂ L0■第2章例题已知文法G[E]：E→T|E+T|E-TT→F|T*F|T/FF→(E)|i（1）该文法的开始符号是什么？（2）请给出该文法的终结符号集合VT和非终结符号集合VN。
（3）找出句型T+T*F+i的所有短语、直接（简单）短语、句柄。
■第3章1、词法分析程序的输出是单词符号序列。
2、DFA的三种表示形式——状态转移图、状态转换表和五元组表示（Q, ∑, f, S, Z ）；3、正规式向DFA的转换：（1）正规式——NFA;（转换原则见下页）（2）NFA——DFA；（3）DFA的最小化。
4、DFA向正规式的转换。
正则式向NFA转换的原则：例：构造与正则表达式R=ba(a|b)*等价的状态最少的DFA，并写出该DFA的五元组形式或状态转换表。
■第4章1、语法分析方法的各种分类；2、LL(1)分析方法。
提示：在此算法中注意First集和Follow集的求法。
并且一定要注意分析过程中步骤要完整。
（分析步骤见下页总结）例：文法：S◊a|^|(T) T◊T,S|S试判断该文法是否是LL(1)文法。
习题4：P100 4.3 4.7 4.9■LL(1)分析方法相关知识总结1、消除文法中的左递归或提取左因子；（1）简单直接左递归的消除A →βA’A →Aα| β→A’ →αA’| ε（2）将文法G：A→αβ|αγ提取左因子。
1》编译程序的框架图与功能块：（1）画出编译程序的总体结构，并简述各部分的主要功能：七个部分（2）编译程序的结构分为几个阶段，各阶段的任务是什么？答编译程序总框架（1）词法分析器，又称扫描器，输入源程序，进行词法分析，输出单词符号。
（2）语法分析器，简称分析器，对单词符号串进行语法分析（根据语法规则进行推导或规约），识别出各类语法单位，最终判断输入串是否构成语法上正确的“程序”。
（3）语义分析与中间代码产生器，按照语义规则对语法分析器归约出（或推导出）的语法单位进行语义分析并把它们翻译成一定形式的中间代码。
（4）优化器，对中间代码进行优化处理。
（5）目标代码生成器，把中间代码翻译成目标程序。
（6）表格管理，登记源程序的各类信息，编译各阶段的进展状况。
（7）出错管理，把错误信息报告给用户。
编译程序的结构分为五个阶段：（1）词法分析.任务是：输入源程序，对构成源程序的字符串进行扫描和分解，识别出一个个的单词（亦称单词符号或简称符号），如基本字，标识符，常熟，算符和界符。
（2）。
语法分析，任务是：在词法分析的基础上，根据语言的语法规则，把单词符号串分解成各类语法单位（语法范畴）。
（3）语义分析与中间代码产生。
任务：对语法分析所识别出的各类语法范畴，分析其含义，并进行初步翻译（产生中间代码）。
（4）优化。
任务在于对前段产生的中间代码进行加工变换，以期在最后阶段能产生出更为高效（省时间和空间）的目标代码。
（5）目标代码生成。
任务是：把中间代码（或优化出理之后）变换成特定机械上的低级语言代码。
2》．重要概念：a. 编译程序：是指能够把源语言程序转换成逻辑上等价的目标语言程序的一个程序。
b. 单词符号：是语言的基本组成成分，是人们理解和编写程序的基本要素，是语言中具有独立意义的最基本结构，它一般包括：基本字、标识符、常数、运算符和界符等c. 中间代码：是一种含义明确，便于处理的记号系统，它通常独立于具体的硬件。
d. 遍：就是对源程序或源程序的中间结果从头到尾扫描一次，并作有关的加工处理，生成新的中间结果或目标程序。
e. 上下文无关文法（CFG）：它所定义的语法范畴（或语法单位）完全独立于这种范畴可能出现的环境之外，不宜描述自然语言。
自然语言中，句子和词等往往与上下文紧密相关f. LL（K）分析法：第一个L表示从左到右扫描输入串，第二个L表示最左推导，K表示分析时每一步需要向前查看K个符号。
g. LR分析法：L表示从左到右扫描输入串,R表示构造一个最右推导的逆过程。
h. 算符优先法：就是定义算符之间的某种优先关系，借助于这种关系寻找“可归约串”和进行归约。
i. 属性文法：是在上下文无关文法的基础上，为每个文法符号（终结符或非终结符）配备若干相关的“值“（称为属性），对于文法的每个产生式都配备了一组属性的计算规则（称为语义规则）。
3》.有哪些存储分配策略，并叙述何时用何种存储分配策略？答：有静态与动态存储分配策略。
动态的存储分配策略包括栈式动态分配策略与堆式动态分配策略。
静态分配策略在编译时对所有数据对象分配固定的存储单元，且在运行时始终保持不变。
栈式动态分配策略在运行时把存储器作为一个栈进行管理，运行时，每当调用一个过程，它所需要的存储空间就动态地分配于栈顶，一旦退出，她所占空间就予以释放。
堆式动态分配策略在运行时把存储器组织成堆结构，以便用户关于存储空间的申请与归还（回收），凡申请者从堆中分给一块，凡释放者退回给堆。
4》.编译过程中可进行的优化如何分类？最常用的代码优化技术有哪些？答：根据优化涉及范围与程序范围可以分为：局部优化，循环优化和全局优化。
最常用的代码优化技术有：删除公共子表达式，复写传播，删除无用代码，代码外提，强度削弱和删除归纳变量。
5》.一个编译程序的代码生成要着重考虑哪些问题？答：代码生成器的设计要着重考虑目标代码的质量问题，而衡量目标代码的质量主要从占用空间和执行效率两个方面综合考虑。
【代码生成要着重考虑两个问题：1）.如何使生成的目标代码较短 2.）如何充分利用计算机的寄存器。
（减少目标代码中访问存储单元的次数。
）这两个问题都直接影响目标代码的执行速度】6》．语言和文法的转换的例题(1). 文法G2：S→bA，A→aA∣a解：推导过程S⇒bA⇒baS⇒bA⇒baA⇒baa…S⇒bA⇒baA⇒…⇒ba…a归纳得出：L(G2)={ba^n︱n≥1}(2).文法G3：S→AB，A→aA∣a，B→bB∣b解：推导过程S⇒AB⇒abS⇒AB⇒aAB⇒aAb⇒aab⇒a^2bS⇒AB⇒abB⇒abb⇒ab^2…归纳得出L(G3)={a^mb^n︱m,n≥1}(3).若已知文法G6(A)： A → c|Ab 请给出G6(A)的语言?解答::L(G6)={c，cb，cbb，⋯} 以c开头，后继若干个b(4).若已知文法G8(S)：S→aSBE S→aBEEB→BE aB→ab bB→bb bE→be eE→ee请给出G8(S)的语言?解答: S→a S BES→aaB EB E (S→aBE)S→a aB BEE (EB→BE)S→aa bB EE (aB→ab)S→aab bE E (bB→bb)S→aabb eE(bE→be)S→aabbee (eE→ee)L(G8)={ a^nb^ne^n | n≥1}, 上下文有关文法(5)给出生成下述语言的上下文无关文法：（1）{ a^nb^na^mb^m| n，m>=0}（2）{ 1^n0^m1^m0^n| n，m>=0}▪G1(S)➢S→AA➢A→aAb|ε▪G2(S)➢S→1S0|A➢A→0A1|ε7》.有限自动机（1）DFA举例DFA M = ({0,1,2,3},{a,b},f,0,{3})f定义如下：f(0,a)=1 f(0,b)=2 f(1,a)=3 f(1,b)=2 f(2,a)=1 f(2,b)=3 f(3,a)=3 f(3,b)=3（2）.证明t=baab被下图的DFA所接受对于∑*中的任何字α，若存在一条从初态到某一终态的通路，且这条通路上所有弧的标bSUVQabba,ba a记符连接成的字等于α，则称α为DFA M所识别（或接受）证法一：∵a,b∈∑∴baab∈∑*f(S,baab) = f(f(S,b),aab) = f(V,aab) = f(f(V,a),ab) = f(U,ab) = f(f(U,a),b) = f(Q,b) =Q。
Q属于终态,故得证证法二：根据上述状态转换图，可以构造确定有限自动机DFA M＝〈{S,U,V,Q}，{a,b}，FM，S，{Q}〉其中，FM 是DFA M的状态转换函数，定义如下：FM （S,a）＝U FM （S,b）＝VFM （U,a）＝Q FM （U,b）＝VFM （V,a）＝U FM （V,b）＝QFM （Q,a）＝Q FM （Q,b）＝Q∵a,b∈∑∴baab∈∑*由题意可知：对于t＝baab，DFA M存在一条经过S、V、U、Q和Q的通路，使得该通路上所有弧的标记符连接成的字等于t因此，t 被DFA M所接受（2）：下图是一个NFA的状态转换图，请将其转化为一个DFA。
●解：采用NFA确定化算法（或子集法）。
状态集合I的ε-闭包表示为ε-closure(I)。
状态集I中任何状态S经任意条ε弧而能到达的状态集S∈ε-closure(I)。
状态集合I的a弧转换表示为move(I,a)，定义为状态集合J，其中：J是所有那些可从I 中的某一状态经过一条a弧而到达的状态的全体。
Ia = move(I,a) = ε-closure(J)。
因此得出上表。
根据上述NFA的状态转换图及其确定化过程，可以构造与它等价的DFA M。
DFA M ＝〈{S,A,B,C,D,E,F}，{a,b}，FM ，S ，{C,D,E,F}〉 这个DFA M 的状态转换图见下图所示。
其中 S={i,1,2} A={1,2,3} B={1,2,4} C={1,2,3,5,6,f} D={1,2,4,5,6,f} E={1,2,4,6,f} F={1,2,3,6,f}FM 是DFA M 的状态转换函数，定义如下： FM （S,a ）＝A FM （S,b ）＝B FM （A,a ）＝C FM （A,b ）＝B FM （B,a ）＝A FM （B,b ）＝D FM （C,a ）＝C FM （C,b ）＝E FM （D,a ）＝F FM （D,b ）＝D FM （E,a ）＝F FM （E,b ）＝D FM （F,a ）＝C FM （F,b ）＝E 8》．语法分析1．文法G[V]： V →N | N[E] E →V | V+E N →i是否为LL(1)文法？若不是，如何改造成LL(1)文法？ 解：LL(1)文法的基本条件是不含左递归和回溯（公共左因子），而G[V]中含有回溯，所以先消除回溯得到文法G ’[V]： G ’[V]： V →NV ’ V ’→ε|[E]V ’ E →VE ’ E ’→ε|+EE ’ N →i 由LL(1)文法的充要条件可证 G ’[V]是LL(1)文法 2.文法G[s]: S →BA A →BS|d B →aA|bS|c证明文法G 是LL(1)文法 ，构造LL(1)分析表，写出句子adccd 的分析过程解：一个LL(1)文法的充要条件是对每一个非终结符A 的任何两个不同产生式A →α|β，有下面的条件成立：FIRST(α)∩FIRST(β)=Φ， 若β* ε, 则有FIRST(α)∩FOLLOW(A)=Φ对于文法G[s]: S →BA A →BS|d B →aA|bS|cFIRST 集FIRST(B)={a, b, c}; FIRST(A)={a, b, c, d};FIRST(S)={a, b, c}。
FOLLOW 集 FOLLOW(S)={#}对S →BA 有 FIRST(A)\{ε}加入FOLLOW(B)，即FOLLOW(B)={a, b, c, d } 对A →BS 有FIRST(S)\{ε}加入FOLLOW(B)，即FOLLOW(B)={a, b, c, d } 对B →aA 有FOLLOW(B)加入FOLLOW(A)，即FOLLOW(A)={a, b, c, d } 对B →bS 有FOLLOW(B)加入FOLLOW(S)，即FOLLOW(S)={#, a, b, c, d } 由A →BS|d 得FIRST(BS) ∩FIRST(d) = { a, b, c } ∩{d} = Φ由B →aA|bS|c 得FIRST(aA)∩FIRST(bS)∩FIRST(c)={a}∩{b}∩{c}= Φ由于文法G[s]不存在形如 β→ε的产生式，故无需求解形如FIRST(α)∩FOLLOW(A)的值也即，文法G[S]是一个LL(1)文法 由G[s]：S →BA A →BS|d B →aA|bS|c 的 FIRST(B)={a, b, c}; FOLLOW(B)={a, b, c, d };bFIRST(A)={a, b, c, d}; FOLLOW(A)={a, b, c, d };FIRST(S)={a, b, c}。
