文档库

最新最全的文档下载
当前位置:文档库 > 4-6章测试题

4-6章测试题

1、语法分析最常用的两类方法是自顶向下和自底向上分析法。

2、.语法分析的任务是识别给定的终极符串是否为给定文法的句子。

3.递归下降法不允许任一非终极符是直接左递归。

4.自顶向下的语法分析方法的关键是选择候选式的问题。

5.自顶向下的语法分析方法的基本思想是:从文法的开始符号开始,根据给定的输入串并按照文法的产生式一步一步的向下进行直接推导,试图推导出文法的句子,使之与给定的输入串匹配。

6.自底向上的语法分析方法的基本思想是:从给定的终极符串开始,根据文法的规则一步一步的向上进行直接归约,试图归约到文法的开始符号。

7.在LR(0)分析法的名称中,L的含义是从左到右扫描输入符号,R的含义是构造一个最右推导的逆过程,0 的含义是超前读入0个符号,以便确定归约用到的产生式

8.综合属性是用于自下而上传递信息。

9.继承属性是用于自上而下传递信息。

10.终结符只有综合属性,它们由词法分析器提供。

11、什么是属性文法?_在上下文无关文法基础上,赋予每个文法符号以一定属性,并规定文法的每个产生式对相关属性的运算规则,这些附加了一组属性和运算规则的文法称为属性文法______________

二、选择题

1.在语法分析处理中,FIRST集合、FOLLOW集合均是 B 。

A. 非终结符集

B.终结符集

C. 字母表

D. 状态集

2.编译程序中语法分析器接收以 A 为单位的输入。

A. 单词

B. 表达式

C. 产生式

D. 句子

3.在自底向上的语法分析方法中,分析的关键是 A 。

A. 寻找句柄

B. 寻找句型

C. 消除递归

D. 选择候选式

4. 在LR分析法中,分析栈中存放的状态是识别规范句型 C 的DFA状态。

A.句柄

B. 前缀

C. 活前缀

D. LR(0)项目

5、采用自上而下分析,必须(B)。

A、消除回溯

B、消除左递归

C、消除右递归

D、提取公共左因子

6、有一语法制导翻译如下所示:

T→aDa {print “1”}

D→(A {print “2”}

D→d {print “3”}

A→Dd {print “4”}

若输入字符序列为a(((dd)d)d)a,且采用自上而下的分析方法,则输出序列为(B)。

A、32224441

B、34242421

C、12424243

D、34442212

三、判断

1.每个文法都能改写为LL(1)文法。(F)

2.递归下降法允许任一非终极符是直接左递归的。(T)

3.算符优先关系表不一定存在对应的优先函数。(F)

4.自底而上语法分析方法的主要问题是候选式的选择。(F)

5.LR法是自顶向下语法分析方法。(F)

6.简单优先文法允许任意两个产生式具有相同右部。(F)

7.若一个句型中出现了某产生式的右部,则此右部一定是该句型的句柄。(F)

8.一个句型的句柄一定是文法某产生式的右部。(T)

四、名词解释

1、LL(1)文法

?LL(1)的含义:

–第一个L:从左至右扫描输入串;

–第二个L:最左推导;

–1:分析时每一步只需向前查看一个符号

2、LR(0) 分析器

3、算符优先文法

4、翻译方案

5、可归前缀

LR分析过程中每次采取归约动作前符号栈中的内容,即规范句型的可归前缀

五、计算题

1.有文法G[s]:

S→BA A→BS|d B→aA|bS|c

–(1)证明文法G是LL(1)文法。

–(2)构造LL(1)分析表。

–(3)写出句子abccd的分析过程

–其FIRST集如下:

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)文法。

–(2) 由G[s]:S→BA A→BS|d B→aA|bS|c的

FIRST(B)={a, b, c}; FOLLOW(B)={a, b, c, d };

FIRST(A)={a, b, c, d}; FOLLOW(A)={a, b, c, d };

FIRST(S)={a, b, c}。 FOLLOW(S)={#, a, b, c, d }可构造LL(1)预测分析表如下:

4-6章测试题

4-6章测试题

2、给定文法G[Z]:

1.Z→C S

2.C→if E then

3.S→A=E

其中:Z、C、S、A、E∈V N ;

if、then、=、∨、i∈V T

4.E→E∨A

5.E→A

6.A→i

a)构造此文法的LR(0)项目集规范族,并给出识别活前缀的DFA。

b)构造其SLR(1)分析表。

3、考虑下列文法

S->a| ^|(T)

T->T’S|S

(1)给出文法的FIRSTVT 和LASTVT (2)计算文法的优先关系

(3)计算优先函数

FIRSTVT(S)={a,^,(}

FIRSTVT(T)={,,a,^,(}

LASTVT(S)= {a,^,)}

LASTVT(S)= {,,a,^,)}

4-6章测试题

4-6章测试题

4-6章测试题

4-6章测试题

4、给定文法及相应的翻译方案:) E→E+T {print(“5”)}

E→T {print(“4”)}

T→T*F {print(“3”)}

T→F {print(“2”)}

F→( E ) {print(“1”)}

F→i {print(“0”)}

对于句型T+(T*(F+T)*i),处理完该句型后输出是什么?