哈工大编译原理习题及答案

发布时间 : 星期二 文章哈工大编译原理习题及答案更新完毕开始阅读

〈说明表〉→ε

〈语句表〉→〈语句表〉;〈语句〉 〈语句表〉→〈语句〉 〈语句〉→S 〈语句〉→ε

439对如下的文法分别构造LR(0)及SLR(1)分析表,并比较两者的异同。 S→AAdS→cAd S→bA→ASc A→SbA→cd A→a

440对于文法 S→AA→BA A→εB→aB B→b

(1) 构造LR(1)分析表;

(2) 给出用LR(1)分析表对输入符号串abab的分析过程。

441对于如下的文法,构造LR(1)项目集族,并判断它们是否为LR(1)文法。 (1)S→AA→AB A→εB→aB B→b

(2) E→E+TE→T T→(E)T→a

442下列文法是否为LR(1)文法?若不是,能否将它们改写为等价的LR(1)文法。 (1) E→E+EE→E*E E→i

(2) S→aSaS→bSb S→aS→b

(3) S→V∶=ES→LS L→I:V→I

(4) 〈程序〉→begin〈说明表〉;〈语句表〉end 〈说明表〉→d;〈说明表〉 〈说明表〉→d

〈语句表〉→S;〈语句表〉 〈语句表〉→S

443试证明任何正规集均可由某一LR(1)文法产生。

444对于一个LR(0)文法G而言,如果我们采用SLR(1)分析表而不是采用LR(0)分析表进行语法分析,则对分析的有效性是否会带来一些好处?

445试证明,在LR分析表的GOTO子表中,所有形如GOTO(i,X)=ERROR的表元素都不会在分析过程中访问到。

446设已给文法G[S]: S→AaAbS→BbBa A→eB→ε

试证明G是LL(1)文法,但不是SLR(1)文法。 447设已给文法 (1) G1[S]: S→Aa|bAc|dc|bda A→d

(2) G2[S]: S→Aa|bAc|Bc|bBa A→d B→d

试证明: G1是LALR(1)文法但不是SLR(1)文法;G2是LR(1)文法但不是LALR(1)文法。 448试为如下的文法构造LALR(1)分析表。 E→E+T|T T→TF|F F→F*|a|b 上 机 实 习 题

(一) 对于如下的文法,试编写调试一个语法分析程序: 〈程序〉→PROGRAM〈标识符〉;〈分程序〉 〈分程序〉→〈变量说明〉BEGIN〈语句表〉END 〈变量说明〉→VAR〈变量说明表〉;

〈变量说明表〉→〈变量表〉:〈类型〉|〈变量表〉:〈类型〉;〈变量说明表〉 〈类型〉→INTEGER|REAL

〈变量表〉→〈变量〉|〈变量〉,〈变量表〉 〈语句表〉→〈语句〉|〈语句〉;〈语句表〉

〈语句〉→〈赋值语句〉|〈条件语句〉|〈WHILE语句〉|〈复合语句〉 〈赋值语句〉→〈变量〉∶=〈算术表达式〉

〈条件语句〉→IF〈关系表达式〉THEN〈语句〉ELSE〈语句〉 〈WHILE语句〉→WHILE〈关系表达式〉DO〈语句〉 〈复合语句〉→BEGIN〈语句表〉END

〈算术表达式〉→〈项〉|〈算术表达式〉+〈项〉|〈算术表达式〉-〈项〉 〈项〉→〈因式〉|〈项〉*〈因式〉|〈项〉/〈因式〉 〈因式〉→〈变量〉|〈常数〉|(〈算术表达式〉)

〈关系表达式〉→〈算术表达式〉〈关系符〉〈算术表达式〉 〈变量〉→〈标识符〉

〈标识符〉→〈标识符〉〈字母〉|〈标识符〉〈数字〉|〈字母〉 〈常数〉→〈整数〉|〈浮点数〉 〈整数〉→〈数字〉|〈数字〉〈整数〉 〈浮点数〉→·〈整数〉|〈整数〉·〈整数〉 〈关系符〉→<|<=|=|>|>=|<> 〈字母〉→A|B|C|…|X|Y|Z 〈数字〉→0|1|2|…|9 要求和提示:

(1) 可选择一种你感兴趣的语法分析方法 (算符优先、LL(1)、递归下降、SLR(1)等)作为编制语法分析

程序的依据;

(2) 对于所选定的分析方法,如有需要,应选择一种合适的数据结构,以构造所给文法的机内表示。 (二) 试编写一个程序,用来判定给定的文法是否为简单优先文法 (或算符优先文法)。 提示:

(1) 确定文法的机内表示方法;

(2) 分别编写计算布尔矩阵B>·,B=·及B<·的程序,为此,还需要编写一个计算布尔矩阵B的闭包B+的子程序,供计算上述各布尔矩阵时调用;

(3) 编制判定优先矩阵是否有多重定义元素的程序,用来判断所给文法是否为简单优先 (算符优先)文法;

(4) 要求输出各优先关系的布尔矩阵以及有关判定结果的信息。

(三) 试编写一个程序,用来计算给定文法的全部FIRST集及FOLLOW集,并判定所给文法是否为LL(1)文法。 要求:

(1) 以给定的文法作为输入 (为此,需确定文法的机内表示);

(2) 程序的输出是各FIRST及FOLLOW集,以及所给文法是否为LL(1)文法等信息。

第四章习题参考答案

?

1.解:

(1)S→(S)Z21|()Z21|[S]Z31|[]Z31 A→(S)Z22|()Z22|[S]Z32|[]Z32 B→(S)Z23|()Z23|[S]Z33|[]Z33 Z11→ε|AZ11|BZ21

Z12→AZ12|BZ22Z13→AZ13|BZ23 Z21→Z11Z22→ε|Z12 Z23→Z13Z31→Z21 Z32→Z22Z33→ε|Z23

(2)S→bZ11|aZ21A→bZ12|aZ22

Z11→ε| AZ21Z12→AZ22Z21→SZ21Z22→ε|SZ22 (3)S→(T)Z11 | aZ11 | Z11S→(T)Z12 | aZ12 | Z12 Z11→ε| Z21Z12→Z22Z21→,SZ21Z22→ε|,SZ22

? S

2.解:

AbB1,1.1(表示第1步,用产生式1.1推导,以下同) CAbbB2,2.1 edAbbB3,4.1 edCAbbB4,2.1 ededAbbbB5,4.1

edaAbbbB5,4.2 (不符合,改写第5步,用4.2) edBfbbB4,2.2 edCSdfbbB5,3.1 ededSdfbbB6,4.1 edaSdfbbB6,4.2 eddfbbB5,3.2 eddfbbCSd6,3.1 eddfbbedSd7,4.1 eddfbbaSd7,4.2 eddfbbd6,3.2 ?

3.解:以下Save表示save token_pointer value, Restore表示restore token_pointer value。

(1)文法没有左递归。 Function P:boolean; Begin Save; P:=true;

If next_token=”begin” then

联系合同范文客服:xxxxx#qq.com(#替换为@)