期末习题
问答
- 简述 L-属性文法的定义;
- 简述 S-属性文法的定义;
- 简述句型的定义;
- 简述文法 所定义的语言的含义;
- 简述素短语的定义。
文法
化简文法
解答
- 没有推导式可以推导出 ,因此删除包含 的产生式规则
- 会陷入无限递归,没有终止条件,将所有含有 的式子都删去
试写出下列满足要求或产生下列语言的文法
解答
第一题
第二题(已修改)
试给出语言 , 且 不含两个相邻的 的 LL(1) 文法
解答(已修改)
First 集 | Follow 集 | |
---|---|---|
S | {0, 1, } | {#} |
A | {0, } | {#} |
预测分析表 | 0 | 1 | # |
---|---|---|---|
S | |||
A |
没有冲突,是 LL(1) 文法
终态 ,有限自动机 中
0 | 1 | |
---|---|---|
{S, Y} | {A, Y} | |
{A, Y} | {S, Y} |
DFA
设计一个 DFA ,识别出所有的由 0、1 所成的串,要求:每一个 1 后边必须跟至少一个 0 。如: 0 是合法的。 010 也是合法的。但 01 是不合法的。
解答(已修改)
给出相应文法
终态 ,有限自动机 ,其中
0 | 1 | |
---|---|---|
{Z, Y} | {A} | |
{Z, Y} | {Z, Y} | {A} |
{A} | {Z, Y} |
将下面的有限自动机确定并最小化
解答
a | b | |
---|---|---|
{0, 1} | {1} | |
{0, 1} | {0, 1} | {0, 1} |
{1} | {0} |
上图已经是确定化的最小有限自动机
LL(1)
有文法
试给出 LL(1) 分析表,说明它是不是 LL(1) 文法
解答
First 集 | Follow 集 | |
---|---|---|
S | {a, b, ε} | {a, b, #} |
LL(1) 分析表 | a | b | # |
---|---|---|---|
S | | |
不是 LL(1) 文法
有文法
构造 LL(1) 分析表,写出句子 baa#
的分析过程
解答(已修改)
First 集 | Follow 集 | |
---|---|---|
Z | {b, a, ε} | {#} |
A | {a, ε} | {#} |
B | {b, ε} | {#, a} |
LL(1) 分析表 | a | b | # |
---|---|---|---|
Z | |||
A | |||
B |
步骤 | 栈 | 输入 | 输出 |
---|---|---|---|
1 | # Z | baa# | |
2 | # A B | baa# | |
3 | # A B b | baa# | |
4 | # A B | aa# | |
5 | # A | aa# | |
6 | # A a | aa# | |
7 | # A | a# | |
8 | # A a | a# | |
9 | # A | # | |
10 | # | # |
有文法
证明该文法是二义性文法
解答
对于表达式 有不同的语法树
graph TD
e1((E1)) --- e2((E2))
e1 --- e3((E3))
e2 --- e4((E4))
e2 --- e5((E5))
e3 --- k1["("]
e3 --- k2[")"]
e4 --- k3["("]
e4 --- k4[")"]
e5 --- k5["("]
e5 --- k6[")"]
ea((E1)) --- eb((E2))
ea --- ec((E3))
eb --- ka["("]
eb --- kb[")"]
ec --- ed((E4))
ec --- ee((E5))
ed --- kc["("]
ed --- kd[")"]
ee --- ke["("]
ee --- kf[")"]
%%{init: {'theme':'dark'}}%%
graph TD
e1((E1)) --- e2((E2))
e1 --- e3((E3))
e2 --- e4((E4))
e2 --- e5((E5))
e3 --- k1["("]
e3 --- k2[")"]
e4 --- k3["("]
e4 --- k4[")"]
e5 --- k5["("]
e5 --- k6[")"]
ea((E1)) --- eb((E2))
ea --- ec((E3))
eb --- ka["("]
eb --- kb[")"]
ec --- ed((E4))
ec --- ee((E5))
ed --- kc["("]
ed --- kd[")"]
ee --- ke["("]
ee --- kf[")"]
因此该文法是二义性文法
SLR(1)
有文法
给出文法的 SLR(1) 分析表,说明它是不是 SLR(1) 文法
解答(已修改)
状态 | ACTION | GOTO | ||
---|---|---|---|---|
^^ | a | + | # | S |
0 | s3 | 1 | ||
1 | s2 | acc | ||
2 | s3/ | r4 | r4 | 3 |
3 | r2/s2 | r2 | ||
4 | r3 | r3 |
其中有单元格出现冲突,不是 SLR(1) 文法
有文法
给出文法的 SLR(1) 分析表,说明它是不是 SLR(1) 文法
解答
状态 | ACTION | GOTO | ||
---|---|---|---|---|
^^ | a | b | # | S |
0 | s2/ | s4/ | r4 | 1 |
1 | acc | |||
2 | s2/ | s3/ | r4 | 3 |
3 | r2 | |||
4 | s2/ | s3/ | r4 | 5 |
5 | r3 |
是 SLR(1) 文法
算符优先文法
有文法
给出算符优先关系表,说明该文法是不是算符优先文法。给出算符优先函数。
解答
FirstVT(X) | LastVT(X) | |
---|---|---|
S | , i | ) |
L | i , | i ) |
- 第一条产生式规则
- 由 可知
(
)
- 由 可知
,
(
- 由 可知
(
,即(
,
和(
i
;同时)
,即)
)
- 由 可知
,
,即i
,
和)
,
- 第二条产生式规则
- 似乎没有什么推得出来的了
( | ) | , | i | |
---|---|---|---|---|
( | ||||
) | ||||
, | ||||
i |
由 [[undergraduate/compilers/s05_downtop#3 Martin 算法]] ,画图,可以得到下面的结果
LR(1)
有文法
给出项目集 和 接受 推导出的
解答
语义 语法
有数组定义
int a[5][10];
设数组按行存放,每个 int 占 4 字节,现有语句
while (i < 10){ if (i < 5) { i = a[i + 1][i * 2]; } else { i = i + 1; }}
写出该语句翻译成的目标代码(三地址代码或四地址代码)。若目标代码是四元式序列,则请从 100 号单元开始。
解答
Lwb: if (i < 10) goto Lwy goto LwnLwy: if (i < 5) goto Liy goto LinLiy: T1 := i + 1 T2 := 10 * T1 T3 := i * 2 T4 := T2 + T3 T5 := T4 * 4 T6 := a[T5] i := T6 goto LinextLin: T7 := i + 1 i := T7Linext: goto LwbLwn:
设有数组定义
int a[5][5];
设数组按行存放,每个 int 占 4 字节,现有语句
if (!a){ while (i < 10 && j > 0) { b = a[i + 1][j * 2]; }}b = b * 2;
写出该语句翻译成的目标代码(三地址代码或四地址代码)。若目标代码是四元式序列,则请从 100 号单元开始。
解答
if (a == 0) goto Liy goto LinLiy:Lwb: if (i < 10) goto L2 goto LwnextL2: if (j > 0) goto Lwy goto LwnextLwy: T1 := i + 1 T2 := 5 * T1 T3 := j * 2 T4 := T2 + T3 T5 := T4 * 4 T6 := a[T5] b := T6 goto LwbLwnext:Lin: Tk := b * 2 b := Tk
翻译
设有文法
给文法配上语义规则,计算并打印出括号嵌套的最大深度。
不知道对不对
属性文法
写出 for 循环和 do…while 循环的属性文法
for 循环
M.label = newLabelN.label = newLabelW.label = newLabelS.code = E1.code + gen(`${i} = ${E1.place}`) + gen(`${M.label}:`) + E2.code + gen(`if ${i} < ${E2.place} goto ${W.label}`) + gen(`goto ${S.next}`) + gen(`${N.label}:`) + gen(`${i} = ${i} + 1`) + gen(`goto ${M.label}`) + gen(`${W.label}:`) + S1.code + gen(`goto ${N.label}`) + gen(`${S.next}:`)
E1.code i := E1.placeM.label: E2.code if (i < E2.place) goto W.label goto S.nextN.label: i := i + 1 goto M.labelW.label: S1.code goto N.labelS.next:
do-while 循环
M.label = newLabelN.label = newLabel
N 标签用于
continue
语句的跳转
M.label: S1.codeN.label: if (E.place) goto M.label goto W.labelW.label:
运行时状态
设 C 语言函数的活动记录结构如下,运行栈自底向上增长
6 | 其他 |
---|---|
5 | 临时变量 |
4 | 局部变量 |
3 | 老 SP |
2 | 返回地址 |
1 | 形式参数 |
现有 C 程序如下
int f(int n, int m) { int k; if (n + m <= 0) k = 0; else k = n * m + f(n - 1, m - 2); return k;}void main() { int p; p = f(5, 4); // 其他语句} // 1
- 设采用标识符栈来登记标识符的作用域及其他的信息。而且该标识符表的内容需要留到以后阶段使用。当编译到 1 处时,画出标识符栈中的内容。
- 运行时当第二次(递归)进入
f
后,即main() -> f(5, 4) -> f(4, 2)
时,给出整个运行栈的内容。
解答
地址 | 内容 | 从属范围 |
---|---|---|
88 | k | f(4, 2) |
89 | 老 BP = 94 | f(4, 2) |
90 | 返回地址 | f(4, 2) |
91 | 4 | f(4, 2) |
92 | 2 | f(4, 2) |
93 | k | f(5, 4) |
94 | 老 BP = 99 | f(5, 4) |
95 | 返回地址 | f(5, 4) |
96 | 5 | f(5, 4) |
97 | 4 | f(5, 4) |
98 | p | main |
99 | 老 BP | main |
100 | 返回地址 | main |