[第五章语法分析习题.ppt

第5章 习题解答: 第5章 习题解答 第5章 习题解答 第5章 习题解答： 第5章 习题解答： 谢谢收看！ * * G(S)：S - a | ∧ |(T) T - T,S | S 【习题:】 给定文法如下： Ⅲ. 递归子程序法； IV. LL(1)分析法； ※ 试分别用下述分析法，对给定的符号串进行语法分析： V. LR(0)( 或SLR（1）)分析法； 设 给定的符号串为： α= ((a,∧),a) VI .简单优先（或算符优先）分析法； Ⅱ. 找出这个句子的短语，简单短语，句柄； Ⅰ. 证明符号串是文法的一个合法的句子； Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. ∴ ((a,∧),a)是文法的一个句子。 S =(T)=(T,S)=(S,S)=((T),S) =((T,S),S) =((S,S),S)=((a,S),S) =((a,∧),S =((a,∧),a) Ⅰ. 证明符号串是文法的一个合法的句子； G(S)：S - a | ∧ |(T) T - T,S | S Ⅱ. 找出这个句子的短语，简单短语，句柄； S ( T ) T , S S ( T ) T , S S a ∧ a 短语：((a,∧),a)；(a,∧),a； (a,∧)；a,∧；a；∧； 简单短语： a；∧； 句柄：a Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. G(S)：S-a ① | ∧ ② |(T) ③ T-T,S ④ | S⑤ Ⅲ. 构造递归子程序法： ⒈ 证明 G(S)是 LL(1)文法： select(①)= first(a)={ a } ※ 求选择集合： select(②)= first(∧)={ ∧ } select(③)= first((T))={ ( } select(④)= first(T,S) ={ a ,( , ∧ } select(⑤)= first(S) = { a ,( , ∧ } ⑴ ⑵ ∵ 选择集合⑴不相交, ⑵相交， ∴ G（S）不是 LL(1) 文法！ 必须进行文法变换！ G’(S)：S-a ① | ∧ ② |(T) ③ T-S{,S}④ 变换后的文法G’(S) Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. S子程序 主程序 ⒉ 构造递归子程序(框图)： 入口 , NEXT(w) 出口 n y S T子程序 ( NEXT(w) y n # NEXT(w) 结束 n y S 开始 err0 入口 出口 a err2 NEXT(w) n n y T ) NEXT(w) y ∧ n y NEXT(w) G’(S)：S-a ① | ∧ ② |(T) ③ T-S{,S}④ S err1 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. select(⑥)= follow(T’)= { ) } IV. LL(1)分析法： ⒈ 证明 G’’(S)是 LL(1)文法： select(①)= first(a)={ a } ※ 求选择集合： select(②)= first(∧)={∧} select(③)= first((T))={ ( } select(④)= first(ST’) ={ a,∧,( } select(⑤)= first(,ST’)= { ,} ⑴ ⑵ ∵ 两组选择集合⑴, ⑵ 皆不相交， ∴ G’’（S）是 LL(1) 文法！ 即 LL(1)分析法可用！！ G(S)：S-a ①|∧ ②|(T)③ T-T,S ④ | S⑤ G’’(S)：S-a①|∧②|(T)③ T-ST’④ T’-,ST’⑤ |ε⑥ 变换后的文法G’’(S) Evaluat