第五章 习题
5-1 设有文法G[S]:
S→A/ A→aA∣AS∣/ (1) 找出部分符号序偶间的简单优先关系。 (2) 验证G[S]不是简单优先文法。
5-2 对于算符文法G[S]:
S→E E→E-T∣T T→T*F∣F F→-P∣P P→(E)∣i
(1) 找出部分终结符号序偶间的算符优先关系。 (2) 验证G[S]不是算符优先文法。
5-3 设有文法G′[E]:
E→E1 E1→E1+T1|T1 T1→T T→T*F|F F→(E)|i
其相应的简单优先矩阵如题图5-3所示,试给出对符号串(i+i)进行简单优先分析的过程。
E E1EE1T1TF+*()i T1 T F + * ( ) i = ·= >··> >··> = >···> > >···= < < < <·····= < <···= < < < < < <·······> > >···> > >···题图5-3 文法G′[E]的简单优先矩阵
5-4 设有文法G[E]:
E→E+T|T T→T*F|F F→(E)|i
其相应的算符优先矩阵如题图5-4所示。试给出对符号串(i+i)进行算符优先分析的过程。
( i * + ) # ( < ○ < ○< ○ < ○i < ○ < ○< ○ < ○* < ○> ○> ○< ○> ○< ○+ < ○> ○> ○> ○> ○< ○) = ○> ○> ○> ○> ○ # > ○> ○> ○> ○ 题图5-4 文法G[E]的算符优先矩阵
5-5 对于下列的文法,试分别构造识别其全部可归前缀的DFA和LR(0)分析表,并判断哪些是LR(0)文法。
(1) S→aSb∣aSc∣ab (2) S→aSSb∣aSSS∣c (3) S→A A→Ab∣a
5-6 下列文法是否是SLR(1)文法?若是,构造相应的SLR(1)分析表,若不是,则阐明其理由。
(1) S→Sab∣bR R→S∣a
(2) S→aSAB∣BA A→aA∣B B→b
(3) S→aA∣bB A→cAd∣ε B→cBdd∣ε
5-7 对如下的文法分别构造LR(0)及SLR(1)分析表,并比较两者的异同。 S→cAd∣b A→ASc∣a
5-8 对于文法G[S]:
S→A A→BA∣ε B→aB∣b
(1) 构造LR(1)分析表;
(2) 给出用LR(1)分析表对输入符号串abab的分析过程。
5-9 对于如下的文法,构造LR(1)项目集族,并判断它们是否为LR(1)文法。 (1) S→A A→AB∣ε B→aB∣b (2) S→aSa∣a
第5章 习题答案2
5-1 解:
(1) 由文法的产生式和如答案图5-1(a)所示的句型A//a/的语法树,可得G中的部分优先关系如答案图5-1(b)所示。
SA / A a A S= = =···AAAS/aA< < ·A A / ·A///> > >·/ / a a / ··(a) 句型A//a/的语法树(b) 部分符号序偶间的优先关系答案图5-1
(2) 由答案图5-1(b)可知,在符号A和/之间,即存在等于关系,又存在低于关系,故文法G[S]不是简单优先文法。
5-2 解:
(1) 由文法G[S]的产生式可直接看出:
( ○= )
此外,再考察句型-P--(E)和i*(T*F)的语法树 (见答案图5-2(a)及(b))。 由答案图5-2(a)可得:
- ○> - , - ○< - , - ○< ( 由答案图5-2(b)可得:
i ○> * , * ○< ( , ( ○< * , * ○> )
SEETF--P(E)iPTFTFPSET-*(FETT*F)(a)句型-P--(E)的语法树答案图5-2(b)句型i*(T*F)的语法树 (2) 由答案图5-2(a)可知,在终结符号-和-之间,存在两种算符优先关系: - ○> - , - ○< - 故文法G[S]不是算符优先文法。
5-3 解:对符号串(i+i)进行简单优先分析的过程如答案表5-3所示。 因为分析成功,所以符号串(i+i)是文法G′[E]的合法句子。
答案表5-3 符号串(i+i)的简单优先分析过程
当前 步骤 0 1 2 3 4 分析栈 # #( #(i #(F #(T 关系 符号 低于 低于 优于 优于 优于 ( i + + + 输入串 i+i)# +i)# i)# i)# i)# i F T F→i T→F T1→T 余留 句柄 产生式 所用