发布时间 : 星期四 文章哈工大编译原理习题及答案更新完毕开始阅读
〈说明表〉→ε
〈语句表〉→〈语句表〉；〈语句〉 〈语句表〉→〈语句〉 〈语句〉→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