编译原理5.2.1-12-3-算符优先文法

《编译原理5.2.1-12-3-算符优先文法》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第五章语法分析5.1自下而上分析基本问题5.2算符优先分析5.3LR分析5.4YACC根据某种优先关系确定“可归约串”.简单优先分析法*求出该文法所有符号之间的优先关系可归约串:句柄是一种规范归约算符优先分析法只规定算符(广义讲为终结符)之间的优先关系可归约串:最左素短语不是规范归约优先分析法1.算符间的优先关系表示ab表示a的优先性低于bab表示a的优先性等于bab表示a的优先性高于b2.直观算符优先分析法G:E→E+E

2、E－E

3、E*E

4、E/E

5、E↑E

6、(E)

7、i二义性文法不能构造确定的分析过程

8、例如：对输入串i1+i2*i3进行自下而上分析,可构造两棵不同的语法树算符优先概念的引入表达式运算的次序只与运算符有关,而与运算对象无关我们称这类文法具有算符特性-优先性,结合性广义讲：终结符为算符对表达式的文法按公认的计算顺序规定优先级和结合性①↑优先级最高。服从右结合②*,/优先级其次。服从左结合③+,-优先级最低。服从左结合④(,)括号的优先性大于括号外的运算符,小于括号内的运算符,内括号的优先性大于外括号。⑤#与它相邻的任何运算符的优先性都比它大。⑥i优先级最高算符优先关系表分析步骤详见

9、黑板G:E→E+E

10、E－E

11、E*E

12、E/E

13、E↑E

14、(E)

15、i利用算符优先关系对输入串i1+i2*i3进行移进-归约分析结论:对于二义性的表达式文法，我们可以直观地给出运算符之间的优先关系，使得输入串i1+i2*i3的归约过程可以唯一确定.对任意给定的一个文法,如何计算算符之间的优先关系?5.2.1算符优先文法及优先表构造1、算符文法2、算符优先关系的定义3、算符优先文法4、优先关系表的构造1、算符文法OG文法－OperatorGrammar任一产生式都不含形如以下形式的右部:•••QR•••产

16、生式的右部不含有两个相邻(相继/并列)的非终结符算符文法的两个限制上下文无关文法不含空产生式补充例：表达式文法G:E→E+E

17、E*E

18、(E)

19、i该文法是算符文法2、算符优先关系的定义1.ab,当且仅当G中含有形如P→•••ab•••或P→•••aQb•••的产生式2.ab,当且仅当G中含有形如P→•••aR•••的产生式，且Rb•••或RQb•••3.ab,当且仅当G中含有形如P→•••Rb•••的产生式，且R•••a或R•••aQ图示算符优先关系11.ab,当且仅当G中含有形如P→•••ab••

20、•或P→•••aQb•••的产生式P…aδb…图示算符优先关系22.ab,当且仅当G中含有形如P→•••aR•••的产生式，且Rb•••或RQb•••P…aR…Ab…δ…图示算符优先关系33.ab,当且仅当G中含有形如P→•••Rb•••的产生式，且R•••a或R•••aQP…Rb…Aa…δ…3、算符优先文法OPG文法－OperatorPrecedenceGrammar一个算符文法G中的任意两个终结符对(a,b)至多只满足下述三种关系之一:ab,ab,ab则称G是一个算符优先文法.补充例：表达式文

21、法G:E→E+E

22、E*E

23、(E)

24、i该文法不是算符优先文法