第8课 第3章_文法和语言_二义性&规则实践

《第8课 第3章_文法和语言_二义性&规则实践》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第3章文法和语言湖南师范大学《编译原理》授课教师：罗迅二义的简洁性2共10页有关二义性的几个结论二义性对程序设计来说是有害的，应当避免。有时，二义文法更加直观更加容易写出，例如上课当中的if语句。因此，我们需要将二义文法改造成无二义的，或者说消除其二义性。出于简洁的目的，程序中允许出现二义文法，但是附加某些规则，使其对应于无二义文法遗憾的有如下两条：不存在通用方法判断一个文法是否为二义；不存在通用方法消除二义性。3共10页消除二义性方法优先级联左结合或右结合最近嵌套匹配4共10页优先级联曾经出现过的

2、表达式文法：E→a

3、E+E

4、E*E

5、(E)，对于a*a+a，它有两棵树，上课已经谈过。此处，我们可以引入优先级来消除二义性。习惯性的，我们规定“*”的级别高于“+”。可以得到如下文法：E→E+E

6、TT→T*T

7、(E)

8、a那么，我们所得到的类似于哪一个？EEE+EE*aaaEEE*EE+aaa5共10页左结合上一页的文法E→E+E

9、TT→T*T

10、(E)

11、a仍然是二义的，形如“a+a+a”的串EEE+EE+aaaEEE+E+aaEa此处，如果规定”+”符合左结合，希望只有左边是合法的。TT为什么得不到右

12、树，请思考一下TTTT6共10页最近嵌套匹配考虑这样一个文法：S→SS

13、iS

14、iSe

15、ε它是if语句的一个抽象，我们可以看到类似iie、iei、iiee都是合法的，而ei，iee都是非法的。但是，iie是二义的（正如上一课所显示的例子一样）。这里解决的方法是规定：e（else）总是和最近的未配对的i（if）匹配。这样，右边的树是正确的。我们可以有如右的文法：SieSiSεSiSiSeεS→SS

16、iS

17、iMe

18、εM→ε

19、iMeM7共10页补充说明关于上一页的改进文法S→ε

20、SS

21、iS

22、iMeM→ε

23、i

24、MeM仍然是一个二义的，iie仍然是二义的。考虑一下如何消除？？？8共10页例子已知如上所示语言，构造一个无二义文法。解：该语言是形如a…ab…b的集合，且b的数目不少于a。易得到如下文法：S→ε

25、aSb

26、Sb，它是二义的，例如abb就有两棵树。下一步，是消除二义性。考虑到a总出于少数地位，我们用最近嵌套法：a必须与最近的未匹配的b匹配。有：9共10页课后作业消除二义性**尝试写出C语言表达式的结构规则10共10页