编译原理作业
P7：1.1；1.2自编2.1；2.2自编2.3；2.4自编2.5自编3.1
自编3.2自编3.3；3.4P100.4.1；4.2自编4.3；4.4自编5.1
自编5.2自编7.1；7.2 自编8.1
P7：1.1
P7；1.2
自编2.1
文法G[S]：S→xSx│y所识别的语言是。

a. xyx
b. (xyx)*
c. x n yx n(n≥0)
d. x*yx*
【解答】
自编2.2
令文法G[N]为
G[N]: N→D∣ND
D→0∣1∣2∣3∣4∣5∣6∣7∣8∣9
(1) G[N]的语言L(G)是什么?
(2) 给出句子0127、34和568的最左推导和最右推导。

【解答】
自编2.3
对于文法G[S]: S→(L)∣aS∣a
L→L, S∣S
(1) 画出句型(S,(a))的语法树；
(2) 写出上述句型的所有短语、直接短语、句柄。

【解答】
自编2.4
已知文法G[S]为S→SaS∣ε，试证明文法G[S]为二义文法。

【解答】
自编2.5
按指定类型，给出语言的文法。

(1) L={a i b j│j>i≥1}的上下文无关文法；
(2) 字母表∑={a,b}上的同时只有奇数个a和奇数个b的所有串的集合的正规文法；
自编3.1
什么是扫描器？扫描器的功能是什么？
自编3.2
结合自动机证明：正规式(ab)*a与正规式a(ba)*是否等价？给出分析过程。

自编3.3
已知自动机DFA如图3-4所示
图3-4 DFA
写出其对应的语言，分别用正规文法和自然语言描述。

【解答】
自编3.4
设有L(G)={a2n+1b2m a2p+1| n≥0,p≥0,m≥1}。

(1) 给出描述该语言的正规表达式；
(2) 构造识别该语言的确定有限自动机(可直接用状态图形式给出)。

【解答】
P100：4.1
P100；4.2
自编4.3
在算符优先分析法中，为什么要在找到最左素短语的尾时才返回来确定其对应的头，能否按扫描顺序先找到头后再找到对应的尾，为什么？
【解答】
自编4.4
设有文法G[S]: S→a|b|(A)
A→SdA|S
(1) 构造算符优先关系表；
(2) 给出句型(SdSdS)的短语、简单短语、句柄、素短语和最左素短语；
【解答】
自编5.1
(1) 四元式之间的联系是通过实现的。

a. 指示器
b. 临时变量
c. 符号表
d. 程序变量
(2) 间接三元式表示法的优点为。

a. 采用间接码表，便于优化处理
b. 节省存储空间，不便于表的修改
c. 便于优化处理，节省存储空间
d. 节省存储空间，不便于优化处理
(3) 表达式(┐A∨B)∧(C∨D)的逆波兰表示为。

a. ┐AB∨∧CD∨
b. A┐B∨CD∨∧
c. AB∨┐CD∨∧
d. A┐B∨∧CD∨
【解答】
自编5.2
(4) 有一语法制导翻译如下所示：
S→bAb {print″1″}
A→(B {print″2″}
A→a {print″3″}
B→Aa) {print″4″}
若输入序列为b(((aa)a)a)b，且采用自下而上的分析方法，则输出序列为。

【解答】
自编7.1
将下面程序划分为基本块并作出其程序流图。

read(A,B)
F=1
C=A*A
D=B*B
if C<D goto L1
E=A*A
F=F+1
E=E+F
write(E)
halt
L1: E=B*B
F=F+2
E=E+F
write(E)
if E >100 goto L2
halt
L2: F=F-1
goto L1
【解答】
自编7.2
试画出如下中间代码序列的程序流图，并求出：
(1) 各结点的必经结点集合D(n)；
(2) 流图中的回边与循环。

J=0
L1：I=0
if I< 8 goto L3
L2：A=B+C
B=D*C
L3：if B =0 goto L4
write B
goto L5
L4：I= I+1
if I<8 goto L2
L5：J= J+1
if J<=3 goto L1
halt
【解答】
自编8.1
何谓嵌套过程语言运行时的DISPLAY表？它的作用是什么？【解答】。