一个个单启这过程，称为词法分析。
4、 最左推导
在推导过程中，如果在推导的任何一步α=>β，其α，β是句型，都是对α中的最左非终结符进行替换，则这种推导为最左推导。
5、 合法的日期表示有如下三种形式，请给出描述日期的正规式。
年.月.日，如1992.08.12 日 月 年，如12 08 1992 月/日/年，如08/12/1992 解：
digit=[0-9]
year =(digit)(digit)(digit)(digit) month=0[1-9]|1[0-2]
day =0[1-9]|[1-2][0-9]|3[0-1] date1=year.month.day date2=day month year date3=month/day/year date =date1|date2|date3
6、 First集
设G=（Vt,Vn,S,P）是上下文无关文法 α是任意的文法符号串，FIRST(α)是从α推导出的串的开始符号的终结符集合
即First(α)={a|α=>aβ，a∈Vt, α ，β∈V} 若α=>ε，则规定ε∈first(α)。
7、 什么是文法？什么是语言？什么是上下文无关文法？ 8、 编译程序有哪些主要构成分？各自的主要功能是什么？ 9、 什么是NFA?什么是DFA?
有限自动机分为两类：确定的有限自动机(DFA)和非确定的有限自动机(NFA)。DFA是NFA的特殊情况。有限自动机是一种语言识别装置，能准确地识别正规集。
10、 简述DFA与NFA有何区别?
DFA与NFA的区别表现为两个方面：一是NFA可以若干个开始状态，而DFA仅只一个开始状态。另一方面，DFA的映象M是从K×∑到K，而NFA的映象M是从K×∑到K的子集，即映象M将产生一个状态集合(可能为空集)，而不是单个状态。
11、 给出下的NFA M的五元组表示，并将其确定化。
*
*
*
12、 给出识别正则表达式((a|bc)*d)+的NFA。
13、 如何求文法G的first集合？ 14、 如何求文法G的follow集合？ 15、 什么是LL(1)文法？ 16、 LL(1)分析法对文法有哪些要求？ 17、 请计算下面文法G(E)中各非终结符的FIRST 和FOLLOW 集合。请说明该文法为什么不是LL(1)文法。 G(E)：E→E * T | T T→T - F | F F→(E) | id Answer: FIRST(E)={(, id} FIRST(F)={(, id} FIRST(T)={(, id} FOLLOW(E)={$, *, )} FOLLOW(F)={$, *, ), -} FOLLOW(T)={$, *, ), -} 由于： E→E * T | T 有： FIRST(E)∩FIRST(E)≠φ 所以，该文法不是LL(1)文法。
18、 什么是文法的左递归？
答：一个文法含有下列形式的产生式之一时： 1) A→Aβ，A∈VN，β∈V*
2) A→Bβ，B→Aα，A、B∈VN，α、β∈V* 则称该文法是左递归的。 19、 已知文法G[S]： S → S；G│G G → G(T)│ H H → a │ (S) T → T+S │ S
找出句型：a(T+S)；H；(S)的短语、直接短语和句柄。 短语: a, T+S, a(T+S) , H , a(T+S);H , (S) 直接短语：a , T+S , H , (S) 句柄是: a 20、 下图所示的分析树用到了某个上下文无关文法的所有产生式。
(a) 给出该文法的所有非终结符号集合N 和终结符号集合T。 (b) 给出该文法的产生式集合。
Answer:
非终结符号集合N={S, A, B} 终结符号集合T={a, b, c, d}
该文法的产生式集合: S→aAcB|Bd A→AaB|c B→bScA|b|?
21、 什么是规范句型的活前缀？ 22、 常用的中间语言种类有哪几种？ 23、 什么是句子？什么是语言?
设G是一个给定的文法，S是文法的开始符号，如果S?*x(其中x∈VT*)，则称x是文法的一个句子。
设G[S]是给定文法，则由文法G所定义的语言L(G)可描述为： L(G)＝{x│S?*x，x∈VT*}。 24、 自顶向下的语法分析方法的基本思想是什么?
从开始符出发导出句型并一个符号一个符号地与给定终结符串进行匹配。如果全部匹配成功，则表示开始符号可推导出给定的终结符串。因此判定给定终结符号串是正确句子。
25、 自底向上的语法分析方法的基本思想是什么?
在采用自左向右扫描，自底向上分析的前提下，该类分析方法是从输入符号串入手，通过反复查找当前句型的句柄(最左直接短语)，并使用文法的产生式把句柄归约成相应的非终极符来一步步地进行分析的。最终把输入串归约成文法的开始符号，表明分析成功。
26、 语法制导翻译方法的基本思想是什么? 27、 试给出确定自动机的定义。 28、 试给出非确定自动机的定义。
一个非确定的有穷自动机(NFA)M是一个五元组：M=（K，Σ，f，S ，Z）。 其中:
1. K是一个有穷集，它的每个元素称为一个状态；
2. Σ是一个有穷字母表，它的每个元素称为一个输入符号，所以也称Σ为输入符号表； 3. f是状态转换函数，是在K×Σ*→K的子集的映射，即，f: K×Σ*→2K ；表明在某状态下对于某输入符号可能有多个后继状态；
4. S﹙K是一个非空初态集； 5. Z﹙K是一个终态集（可空）。 29、 写出表达式(a＋b*c)/(a＋b)－d的逆波兰表示。
Abc*+ab+/d-
30、 表达式a-(-b)*c的逆波兰表示(@为单目减)为？
ab@c*-
31、 目标代码有哪几种形式？ 目标代码一般有以下三种形式。
(1) 能够立即执行的机器语言代码，所有地址均已定位。
(2) 待装配的机器语言模块。当需要执行时，由连接装人程序把它们和某些运行程序连接起来，转换成能执行的机器语言代码。
(3) 汇编语言代码，尚需经过汇编程序汇编，转换成可执行的机器语言代码。
代码生成要着重考虑两个问题：一是如何使生成的目标代码较短；另一是如何充分利用计算机的寄存器，减少目标代码中访问存储单元的次数。这两个问题都直接影响目标代码的执行速度。
32、 已知文法G[E]为：
E→T|E+T|E-T T→F|T*F|T/F F→（E）|i
① 该文法的开始符号（识别符号）是什么？
②请给出该文法的终结符号集合VT和非终结符号集合VN。 ③ 找出句型T+T*F+i的所有短语、简单短语和句柄。 解：
① 该文法的开始符号（识别符号）是E。 ②该文法的终结符号集合VT={+、-、*、/、（、）、i}。 非终结符号集合VN={E、T、F}。
③句型T+T*F+I的短语为i、T*F、第一个T、T+T*F+i;
直接短语为i、T*F、第一个T;句柄为第一个T。 33、 为正规式(a|b)*a(a|b)构造一个等价的确定的有限自动机。
a a,b ? 0 a 1 b 34、 对下列错误信息，指出可能是编译的哪个阶段(记法分析、语法分析、语义分析、代码生成)
报告的。
(1) else没有匹配的if (2) 数组下标越界
(3) 使用的函数没有定义 (4) 在数中出现非数字字符
2 答：(1)语法分析 (2)语义分析 (3)语法分析 (4)词法分析 35、 处于/* 和 */之间的串构成注解，注解中间没有*/。画出接受这种注解的DFA的状态转换
图。
1 / 2 * others 3 * others 4 *
/ 5 标记为others的边是指字符集中未被别的边指定的任意其它字符。
分析：这个DFA的状态数及含义并不难确定，见下面的五个状态说明。
状态1：注释开始状态。
状态2：进入注释体前的中间状态。 状态3：表明目前正在注释体中的状态。 状态4：离开注释前的中间状态。 状态5：注释结束状态，即接受状态。
在这个DFA中，最容易忽略的是状态4到本身的’*’转换。这个边的含义是：在离开注释前的中间状态，若下一个字符是’*’，那么把刚才读过的’*’看成是注释中的一个字符，而把这下一个字符看成可能是结束注释的第一个字符。若没有这个边，那么象
/**** This is a comment ****/ 这样的注释就被拒绝。
另外，上面的状态转换图并不完整。例如，对于状态1，没有指明遇到其它字符怎么办。要把状态转换图画完整，还需引入一个死状态6，.进入这个状态就再也出不去了。因为它不是接受状态，因此进入这个状态的串肯定不被接受。完整的状态转换图见下图，其中all表示任意字符。在能够说清问题时，通常我们省略死状态和所有到它的边。
1 / others 2 * others 3 * others all 4 * / 5 others 6 all 36、 假定有一个猎人带着一只狼、一头山羊和一棵白菜到河的左岸，岸边只有一条小船，猎人
每次只能带一件到达对岸，但狼会吃羊，而羊会吃白菜。请用状态转换图做一个工具，描述猎人可能采取的摆渡方案，并从中找出可将上述三件东西安全带到对岸的方案。
先写出渡河的方法，串中对象顺序为人来回渡河时所运的货物的顺序： ①羊空菜羊狼空羊 ②羊空狼羊菜空羊