1.什么是遍？是否任何一种高级语言都能通过一遍扫描完成编译？P6
遍是对源程序或其等价的中间语言程序从头到尾扫视并完成规定任务的过程。一个编译过程可由一遍、两遍或多遍完成。
2.简述PL/0编译系统中词法分析阶段三个全程变量（即：SYM、ID.、NUM）的作用？P18
SYM:存放每个单词的类别，用内部编码表示。
ID:存放用户所定义的标识符的值，即标识符的机内表示。
NUM:存放用户定义的数
3.文法G[N]为：运动会入场词100字N—>D|ND D—>0|1|2|3|4|5|6|7|8|9 G[N]的语言是什么？P48 练习2 {Dn |n>0且n属于整数}
4.文法G[S]为：S—>Ac|aB A—>ab B—>bc 写出L（G[S]）的全部元素。P47 练习1 L(G[S])={a，b，c}
5.简述编译程序的两种方式？并说明它们的区别。P7 方式：编译程序、解释程序 区别：生不生成目标代码
6.文法G[Z]为：Z—>aZb Z—>ab 写出L（G[Z]）的全部元素。 { an bn |n>=1}
7．DFA指的是什么？它由五元组组成，其各元的含义是什么？
确定的有穷自动机；
M=(K,∑,f, S,Z)
K是一个有穷集，它的每个元素称为一个状态；
∑是一个有穷字母表，它的每个元素称为一个输入符号，所以也称∑为输入符号表；
F是转换函数，是K×∑→K上的映像
S∈K，是唯一的一个初态
Z K，是一个终极态，终态也称为接收状态或结束状态
8.词法分析的常用方法有哪两种：自顶向下；自底向上。
9.文法G如果对某句型存在至少两种不同的语法树，则该文法称为什么？如果某语言对应的任意一种文法都是二义性文法，则该语言称为什么？二义性文法 二义性语言
10.简单优先分析法属于何种归纳？而算符优先分析法属于何种归纳？LR（0）分析法属于何种归纳？
规范规约、非规范规约、规范规约
11.确定的自顶向下分析法通常有哪两种？ 递归子程序法；预测分析法。
12.词法处理程序的任务？仅对源程序进行线性扫描即可完成
13.编译程序按扫描源程序的“遍”数分为哪两种？一遍编译、多遍编译
14.了解P16页PL/O语言的编译程序结构图的含义？
15.语法分析最常用的两类方法是什么？自顶向下；自底向上。
16.高级程序设计语言的翻译方式主要有哪两种？两者的根本区别是什么？
方式：编译程序、解释程序 区别：生不生成目标代码
17. chomsky定义的四种形式语言的文法的定义，如考察1型文法也称为什么文法？上下文有关的
18.高级语言的单词通常分为哪五类？基本字、运算符、标识符、常数、界符
19. LL(1)中每个字母（即L,L,1）的含义是什么？自左向右扫描输入串、最左推导、向右看一个字符
20.简单优先分析法每次归纳当前的句型的句柄，而算符优先分析法每次归纳的是什么？最左素短语
21.编译程序的组成部分？词法分析、语法分析、语义分析、中间代码生成、代码优化、目标代码生成
22.编译程序是_____软件?语言翻译程序
23.终结符：是构成语言文法的单词，是语法成分的最小单位。
24.非终结符：是一个语法成分，它是由终结符和非终结符串或终结符串定义的。
25.文法描述的语言是该文法一切句子的集合。
26.最右推导常被称为规范推导，由规范推导所得的句型称为规范句型。
27.如果一个文法存在某个句子对应两棵不同的语法树，则说的这个文法是二义的，或者说，若一个文法中存在某个句子，它有两个不同的最左（最右）推导，则这个文法是二义的。
28.写出表达式：A+B*(C-D)+E/(C-D)↑N的逆波兰式和四元式。P117-119
逆波兰式:ABCD-*+ECD-N↑/+
四元式(-篮球基础与实战技巧，C，D，T1)
(*，B，T1，T2)
(+，A，T2，T3)
(-，C，D，T4)
(↑，T4，N，T5)
(/，E，T5，T6）
(+，T3，T6，T7)
29.写出表达式：-a+b*(-c+d)的逆波兰式和四元式。
逆波兰式:a@bc@d+*+
四元式(@，a，-，T1)
(@，c，-，T2)
(+，T2，d，T3)
(*，b，T3，T4)
(+，T1，T4，T5)
30. 写出表达式：a+b*(c+d/e)的逆波兰式和四元式。
逆波兰式:abcde/+*+
四元式(/，d，e，T1)
(+，c，T1-，T2)
(*，b，T2，T3)
(+，a，T3，T4)
二、分析题
1.令文法G[E]为： E—>E+T|T T—>T*F|F
F—>(E)|v|d
（1）分析说明v*v+d是它的的一个句型；
（2）指出这个句型的所有短语、直接短语和句柄。
(1)
(2)短语为：v，v，v*v，d，v*v+d
直接短语为：v，v，d
句柄为：最左边的v
2. 将正规式r=a(a|d)*转换为相应的正规文法。P54 例4.4
令S是文法的开始符号，首先形成S—>a(a|d )*，然后形成S—>aA和A—>a(a|d )*，再变换形成：
S—>aA A—>(a|d )B
A—>ε B—>(a|d )B
B—>ε
进而变换为全部符合正规文法产生式的形式：
S—>aA B—>aB
A—>aB B—>dB
A—>dB B—>ε
A—>ε
3将文法G[S]：S—>aA、S—>a、A—>aA、A—>dA、A—>a、A—>d 转换为相应的正规式。
首先有：S=aA|a A=(aA|dA)|(a|d)
再将A的正规式变换为A=(a|d)A|(a|d)，又变换为A=(a|d)* (a|d),再将A右端代入S的正规式得：S= a(a|d)*(a|d) |a,再利用正规式的代数变换可依次得到：S=a ((a|d)*(a|d) |ε)
S=a(a|d)*即a(a|d)*为所求。
4. 令文法G[S]为：S—>aAcBe H—>aMd|d A—>b|Ab B—> d
（1）分析说明aAbcde是它的的一个句型；
（2）指出这个句型的所有短语、直接短语和句柄。
所有短语：aAbcde,Ab,d 直接短语：Ab,d 句柄：Ab
5. 令文法G[S]为： S—>SS* S—>SS+ S—> a
（1）分析说明aa+a*是它的的一个句型；
（2）指出这个句型的所有短语、直接短语和句柄。
（3）该文法的语言是什么？
短语：a,a.aa+,a,aa+a* 直接短语：a,a,a 句柄：a
与文法对应语言为a关于+，*运算的逆波兰式
三、计算题
1. 构造正规式（a*|b*）* 相应的最小化DFA。
(1) NFA：
令：r1=a* r2=b*
则NFA(r1) NFA(r2)分别为：
令：r3=r1|r2 则NFA(r3)为：
NFA(r3*)
（3）最小化：
（2）确定化：
| a | b |
SABCDZ | ABCDZ | ABCDZ |
ABCDZ | ABCDZ | ABCDZ |
| | |
2.构造正规式（a|b）*相应的最小化DFA。P74
(1).NFA：
(3)最小化：
(2).确定化：
2.构造正规式1（0|1）*101相应的最小化DFA。P68
(1).令r=r1r2r3 r1=1 r2=(0|1)* r3=101 图分别如下：
r=r1r怎样腌辣椒2r3:
(2).确定化：令：AB为B、AC为C、ABY为D
| 0 | 1 |
X | | A |
A | A | AB |
AB | AC | AB |
AC | A | ABY |
ABY | AC | AB |
| | |
(3).最小化：
四、证明题
文法G[S]: S—>aH H—>aMd|d M—>Ab|ε A—>aM|e
证明：G是否为LL（1）文法。
(1)first(S)={a};first(H)={a,d}; first(M)={a,e, ε} ;first(A)={a,e}
(2)follow(S)={#}; follow(H)={#}; follow(M)={d}∪ follow(A)={b,d}; follow(A)={b};
(3)lect(S—>aH)={a}; lect(H—>aMd)={a}; lect(H—>d)={d}; lect(M—>Ab)={a,e}; lect(M—>ε)={b,d};
lect(A—>aM)={a}; lect(A—>e)={e};
(4)构造LL（1）预测分析表为
| a | d | b | e | # |
S | →aH | | | | |
H | →aMd | →d | | | |
M | →Ab | →求导法则公式ε | →ε | →Ab | |
A | →aM | | | →e | |
| | | | | |
(5)由预测分析表中无多重入口判定文法是LL（1）的
五、作图题
画出与下面的NFA等价的DFA的状态转换图。
1. 首先计算T0=ε-closure(i)={i,1,2} T0未被标记，它是子集族C中唯一成立。
2. 标记T0：令T0=ε-closure(move(T0,a))={1,2,3}∉C，将T0加入C，T0未被标记
T2=ε-closure(move(T0,b))={1,2,4}∉C，将T2加入C，T2未被标记
3. 标记T1：T3=ε-closure(move(T1,a))={1,2,3,5,6,f}∉C，将T3加入C，T3未被标记
ε-closure(move(T1,b)) =T2∈C，没有必要加入C
4. 标记T2：ε-closure(move(T2,a)) =T1∈C，没有必要加入C
T4=ε-closure(move(T2,b))={1,2,4,5,6,f}∉C，将T4加入C，T4未被标记
5. 标记T3：ε-closure(move(T3,a)) =T3∈C，没有必要加入C
T5=ε-closure(move(T3中医的特点,b))={1,2,4,6,f}∉C，将T5加入C，T5未被标记
