发布时间 : 星期二 文章哈工大编译原理习题及答案更新完毕开始阅读
D→aBDD→ε
4.8对于如下的文法G［S］： S→SbS→Ab S→bA→Aa A→a
(1) 构造一个与G等价的LL(1)文法G′； (2) 对于G′，构造相应的LL(1)分析表。 49设已给文法 S→SaBS→bB A→SA→a B→Ac
(1) 求出各个FIRST集和FOLLOW集； (2) 将它改写为LL(1)文法。 410将下面的文法改写为LL(1)文法。
(1) 〈布尔表达式〉→〈布尔表达式〉∨〈布尔因子〉 〈布尔表达式〉→〈布尔因子〉
〈布尔因子〉→〈布尔因子〉∧〈布尔二次量〉 〈布尔因子〉→〈布尔二次量〉 〈布尔二次量〉→〈布尔初等量〉 〈布尔二次量〉→〈布尔初等量〉 〈布尔初等量〉→(〈布尔表达式〉) 〈布尔初等量〉→true | false (2) 习题26中所给的文法。
411设G［S］为LL(1)文法，A为G的非终结符号，A+ε，且由A至少可推出一个非ε的终结符号串，试证明： G中不会含有形如 B→αAAβ
的产生式，其中α，β∈(VT∪VN)*。
412试找出下列文法的全部简单优先关系，并指出它们是否为简单优先文法： (1) S→(AS)S→b A→(SaA)A→a (2) S→(R)S→∧ S→aR→T T→S,TT→S (3) S→(SRS→a R→,SRR→) (4) S→#Z#Z→E Z→E+TZ→T Z→iT→(Z) T→i
413对于文法G［S］： S→A/A→Aa A→ASA→/
(1) 构造G［S］的简单优先矩阵；
(2) 找出其中的多重定义元素，以验证G［S］不是简单优先文法。
414试用某种高级语言编写一个求出给定文法的全部简单优先关系的程序，此程序以某种适当形式表示的文法为输入。
415试证明如下的句柄定理，即证明简单优先文法的任何句型X1X2…Xn的句柄是满足如下关系： Xi-1＜·Xi
Xi=·Xi+1=·…=·Xi+k Xi+k＞·Xi+k+1
的最左子串XiXi+1…Xi+k。
416对于如下的文法G［〈变量说明〉］： 〈变量说明〉→VAR〈变量表〉：〈类型〉； 〈变量表〉→〈变量表〉，〈变量〉|〈变量〉 〈变量〉→i
〈类型〉→real|integer|boolean|char (1) 将G改造为等价的简单优先文法G′； (2) 求出G′的全部简单优先关系。
417试证明，任何算符文法不会有两个非终结符号相邻的句型。
418试证明，若G不是算符文法，则G至少有一个句型包含相邻的非终结符号。
419试构造这样的产生“简单算术表达式”的文法。此种表达式可含有+、-、*、/、↑等运算符，且以简单变量 (用变量标识符表示)作为运算对象，而上述运算符的优先顺序从高到低排列如下： +,- *,/ ↑
其中，排列在同一行的运算符有相同的优先级，同级的运算符服从右结合规则。 420对于算符文法G［S］： S→EE→E-T E→TT→T*F T→FF→-P F→PP→(E) P→i
(1) 构造G的算符优先矩阵；
(2) 指出G不是算符优先文法，即指出具有多重定义的优先矩阵元素； (3) 将G改写为算符优先文法。
421设G是一算符文法。试证明，在G的句型中，不含紧跟于非终结符号之后或直接居于非终结符号之前的短语，即证明如下两论断成立： (1) 若
α=…Ua…a∈VT, U∈VN
是G的一个句型，则α中任何含有a的短语也必包含U； (2) 若
α=…aU…a∈VT, U∈VN
是G的一个句型，则α中任何含有a的短语也必包含U。 422设G是算符文法，a,b∈VT,U∈VN，试证明：
(1) 若α=…aU…为G的句型，且U+b…，则有a○＜ b； (2) 若α=…Ub…为G的句型，且U+…a，则有a○＞ b。
423设G为算符文法，α=…aUb…或α=…ab…是G的一个句型 (a,b∈VT,U∈VN)，则算符优先关系a○＜ b，a○= b或a○＞ b至少有一个成立。
424设G为算符文法，α是G中至少含有一个终结符号的句型，试证明，在符号串#α#中，必含有一个形如aβc的子串，使如下的关系成立： a○＜ b1○= b2○= … bn○＞ cn≥1
其中，a,c∈VT∪{#}，而bi为β中的终结符号。
425设G为算符优先文法，α=…aUb…或α=…ab…是G的一个句型 (a,b∈VT,U∈VN)，试证明，关系a○＜ b,a○= b或a○＞ b之中，必有且仅有一个成立。
426设G为算符优先文法,α=…aUb…或α=…ab…是G的一个句型 (a,b∈VT,U∈VN)，试证明： (1) 若a○＜ b，则α中必有一个含有b但不包含a的短语； (2) 若a○= b，则α中每个含有a的短语也必包含b，反之亦然； (3) 若a○＞ b，则α中必有一个含有a但不包含b的短语。
427设G为算符优先文法，u是G的某一句型的短语，再设u中含有终结符号b1,b2,…,bn (n≥1)，且满足bi○= bi+1 (1≤i≤n-1)，试证明，u是该句型的一个素短语。
428设G为算符优先文法，α=…a0uan+1…是G的一个句型，其中a0,an+1∈VT，且u中含有终结符号a1,a2,…,an (n≥1)，且满足： a0○＜ a1
ai○= ai+1(1≤i≤n-1) an○＞ an+1
试证明，u是α的一个素短语。
429设G为算符优先文法，α是G的一个句型，再设a0uan+1是符号串#α#的子串，且u中含有终结符号a1,a2,…,an (n≥1)，试证明，若下列关系： a0○＜ a1
ai○= ai+1(1＜i≤n-1) an○＞ an+1
成立，则u是α的一个素短语。
430试证明： 算符优先文法的每一句型或是一个单个非终结符号，或含有一个素短语。 431设已给文法G［E］： E→E+TE→T T→T*FT→F F→P↑FF→P P→(E)P→i
(1) 构造此文法的算符优先矩阵；
(2) 用Floyd方式将所得的优先矩阵线性化。 432用Floyd方法对下面的优先矩阵构造优先函数。
[]Z[]b[]M[]L[]a[]([])Zb[4]=·[6]＜·[]＜·M[3]=·[6]=·L[3]＞·[6]＞·a[3]＞·[6]＞·[8]=·([4]＜·[]=·[]＜·[]＞·)[3]＞·[6]＞· 433对于算符文法： S→A［ ］A→［ A→aAA→B］
B→a
(1) 构造相应的优先矩阵； (2) 用Bell方法求出优先函数； (3) 检验此优先矩阵能否线性化。
434试用某种高级语言编写一个按简单优先分析方法进行语法分析的程序，此分析程序以给定的文法及相应的优先函数作为输入，并输入要分析的终结符号串；作为它的输出，则是这些非终结符号串是否为文法句子的信息。
435对于下列的文法，试分别构造它们的LR(0)项目集规范族及识别全部活前缀的DFA。 (1)S→aSbS→aSc S→ab
(2) S→cAS→ccB A→cAA→a B→ccBB→b
(3) S→aSSbS→aSSS S→c (4)S→AA→Ab A→a
436对于习题435中的各文法，判别哪些是LR(0)文法，并对它们构造相应的LR(0)分析表。 437判断下面的文法是哪一类LR文法，并构造LR分析表。 S→(SRS→a R→,SRR→)
438下列文法是否为SLR(1)文法?若是，构造相应的SLR(1)分析表，若不是，则阐明其理由。 (1) S→SabS→bR R→SR→a (2)S→aSABS→BA A→aAA→B B→b
(3)S→aSbS→bSa S→ab (4)S→aAS→bB A→cAdA→ε B→cBddB→ε
(5) 〈程序〉→〈分程序〉 〈程序〉→〈复合语句〉
〈分程序〉→〈分程序首部〉；〈复合尾部〉 〈分程序首部〉→begin D
〈分程序首部〉→〈分程序首部〉；D 〈复合尾部〉→Send
〈复合尾部〉→S；〈复合尾部〉 〈复合语句〉→begin〈复合尾部〉
(6) 〈程序〉→begin 〈说明表〉〈语句表〉end 〈说明表〉→〈说明表〉d；