编译原理第六章

第六章 属性文法和语法制导翻译要紧内容:[1] 法制导翻译的大体思想； [2] 属性文法的大体概念； [3] 基于属性文法的处置方式；[4] 在自上而下分析和自下而上分析中的属性计算。

大体要求:[1] 明白得语法制导翻译和属性文法的大体思想和方式， [2] 把握属性的计算方式。

教学要点：本章中，咱们将第一介绍属性文法的大体概念，然后介绍基于属性文法的处置方式，讨论如安在自上而下分析和自下而上分析中实现属性的计算。

讲义摘要：6.1 属性文法一、语义分析的任务一、静态语义分析或静态审查。

例如，类型检查、操纵流检查（操纵流语句必需使操纵转移到合法的地址 ）、维数检查、越界检查、名字的作用域分析 等。

二、动态语义处置。

若是静态语义正确，语义处置那么要执行真正的翻译。

例如，变量的存储分派；表达式的求值；语句的翻译（中间代码的生成）。

3、总目标：生成等价的中间代码二、属性文法 一、属性所谓属性，其涉及的概念比较普遍，经常使用以描述事物或人的特点、性质，品质等等。

比如，谈到一个 物体，能够用“颜色”描述它，谈起某人，能够利用“有幽默感“来形容他。

对编译程序利用的语法树的结点，能够用"类型"、"值"或"存储位置"来描述它。

二、属性文法（也称属性翻译文法）属性文法是Knuth 在1968年第一提出的。

它是在上下文无关文法的基础上，为每一个文法符号（终结符或非终结符）配备假设干相关的“值”（称为属性）。

这些属性代表与文法符号相关信息，例如它的类型、值、代码序列、符号表内容等等。

属性与变量一样，能够进行计算和传递。

属性加工的进程即是语义处置的进程。

关于文法的每一个产生式都配备了一组属性的计算规那么，称为语义规那么。

语义规那么所描述的工作能够包括属性计算、静态语义检查、符号表操作、代码生成等等。

3、属性文法的形式化概念形式上讲，一个属性文法是一个三元组:A=(G,V,F),其中 G:是一个上下文无关文法。

第六章属性文法和语法制导翻译本章要点1. 属性文法，基于属性文法的处理方法；2. S-属性文法的自下而上计算;3. L-属性文法的自顶向下翻译；4. 自下而上计算继承属性；本章目标掌握和理解属性方法、基于属性文法的处理方法、S-属性文法和自下而上计算、L-属性文法和自顶向下翻译、自下而上计算继承属性等内容。

本章重点1．语法制导翻译基本思想。

2．语义规则的两种描述方法：语法制导的定义和翻译方案。

语法制导的定义没有指明语义规则的计算次序，而翻译方案显式给出语义规则（或叫语义动作）的计算次序和位置。

3．基于属性文法的处理方法，综合属性定义（S属性定义）和L属性定义。

4．设计简单问题的语法制导定义和翻译方案，这是本章的重点和难点。

这种设计可看成是一种程序设计，是一种事件驱动形式的程序设计，因此它比一般的编程要难得多。

这里的事件是句子中各种语法结构的识别。

5．语义规则的三种计算方法：分析树方法、基于规则的方法和忽略规则的方法。

6．S属性的自下而上计算（边语法分析边属性计算，忽略规则的方法）。

7．L属性的自上而下计算（边语法分析边属性计算，忽略规则的方法）。

8．递归计算（先语法分析后属性计算，基于规则的方法）。

本章难点1. 设计简单问题的语法制导定义和翻译方案；作业题一、单项选择题：1. 文法开始符号的所有________作为属性计算前的初始值。

a. 综合属性b. 继承属性c. 继承属性和综合属性d. 都不是2. 对应于产生式A→XY继承属性Y.y的属性计算，可能正确的语义规则是________。

a. A.a:=f(X.x，Y.y)；b. )Y.y:=f(A.a，Y.y)；c. Y.y:=f(X.x)；d. A.a:=f(Y.y)；3. 描述文法符号语义的属性有两种，一种称为__ __，另一种称为__ ___。

a. L-属性b. R-属性c. 综合属性d. 继承属性4. 出现在产生式________和出现在产生式________不由所给的产生式的属性计算规则进行计算，而是由其他产生式的属性规则计算或者由属性计算器的参数提供。

编译原理第六章算符优先分析法第六章算符优先分析法课前索引【课前思考】◇什么是⾃下⽽上语法分析的策略？◇什么是移进-归约分析？◇移进-归约过程和⾃顶向下最右推导有何关系？◇⾃下⽽上语法分析成功的标志是什么？◇什么是可归约串？◇移进-归约过程的关键问题是什么？◇如何确定可归约串？◇如何决定什么时候移进，什么时候归约？◇什么是算符⽂法？什么是算符优先⽂法？◇算符优先分析是如何识别可归约串的？◇算符优先分析法的优缺点和局限性有哪些？【学习⽬标】算符优先分析法是⾃下⽽上（⾃底向上）语法分析的⼀种，尤其适应于表达式的语法分析，由于它的算法简单直观易于理解，因此，也是学习其它⾃下⽽上语法分析的基础。

通过本章学习学员应掌握：◇对给定的⽂法能够判断该⽂法是否是算符⽂法◇对给定的算符⽂法能够判断该⽂法是否是算符优先⽂法◇对给定的算符⽂法能构造算符优先关系表，并能利⽤算符优先关系表判断该⽂法是否是算符优先⽂法。

◇能应⽤算符优先分析算法对给定的输⼊串进⾏移进-归约分析，在分析的每⼀步能确定当前应移进还是归约，并能判断所给的输⼊串是否是该⽂法的句⼦。

◇了解算符优先分析法的优缺点和实际应⽤中的局限性。

【学习指南】算符优先分析法是⾃下⽽上语法分析的⼀种，它的算法简单、直观、易于理解，所以通常作为学习其它⾃下⽽上语法分析的基础。

为学好本章内容，学员应复习有关语法分析的知识，如：什么是语⾔、⽂法、句⼦、句型、短语、简单短语、句柄、最右推导、规范归约基本概念。

【难重点】◇通过本章学习后，学员应该能知道算符⽂法的形式。

◇对⼀个给定的算符⽂法能构造算符优先关系分析表，并能判别所给⽂法是否为算符优先⽂法。

◇分清规范句型的句柄和最左素短语的区别，进⽽分清算符优先归约和规范归约的区别。

◇算符优先分析的可归约串是句型的最左素短语，在分析过程中如何寻找可归约串是算符优先分析的关键问题。

对⼀个给定的输⼊串能应⽤算符优先关系分析表给出分析（归约）步骤，并最终判断所给输⼊串是否为该⽂法的句⼦。

编译原理武汉大学计算机学院编译原理课程组自上而下语法分析·基本思想·存在的问题·解决方法·LL(1)方法·递归子程序法消除左递归FIRST集、FOLLOW集·LL(1)文法递归子程序的构造LL(1)分析表的构造6.1 自下而上语法分析1．自下而上语法分析的基本思想从输入的符号串开始，利用文法的产生式步步向上归约，试图归约到文法的识别符号。

如果从语法树的角度看，自下而上分析的过程是以输入符号串作为末端结点符号串，向着根结点的方向往上构造语法树，使识别符号正好是该语法树的根结点。

相应于高级语言的编译过程，自下而上语法分析就是从该高级语言文法的源程序或与其等价的单词串出发，试图归约得到该文法的开始符号——<程序>。

6.1 自下而上语法分析3.自下而上语法分析遇到的基本问题例如，对文法G[S]：S→aAcBeA→bA→AbB→d分析符号串abbcde。

1．短语、直接短语与句柄6.2 短语和句柄则称句型xuy 中的子串u 为句型xuy (相对于非终结符号U )的短语。

设有文法G[Z]，w=xuy 是它的一个句型，如果有Z *⇒xUy +⇒且U u U ⇒u则称u为句型xuy的直接（简单）短语。

特别地，如果前述条件中U +⇒u为句型的最左直接（简单）短语称为句柄。

6.2 短语和句柄例：设有文法G[S]：S→ABA→Aa|bBB→a|Sb请给出句型baabaab的所有短语、直接短语和句柄。

6.2 短语和句柄2．短语、简单（直接）短语、句柄与语法树的关系语法树子树的末端结点符号串即是语法树所描述句型（相对于子树的根）的短语；简单子树（只有父子两代）的末端结点符号串即是直接短语。

最左简单子树的末端结点符号串即是句柄。

6.2 短语和句柄例：设有文法G[S]：S→ABA→Aa|bBB→a|Sb请给出句型baabaab的所有短语、直接短语和句柄。

第 6 章自学内容第 6 章作业P100 6.8求下列句型的所有短语、简单（直接）短语和句柄。

第6章自下而上语法分析
第6章
Bottom-up Parsing
学习目标
6.1 自下而上语法分析 6.1 自下而上语法分析
6.1 自下而上语法分析 6.1 自下而上语法分析6.1 自下而上语法分析 6.1 自下而上语法分析6.1 自下而上语法分析
6.2 短语和句柄 6.2 短语和句柄6.2 短语和句柄
6.3 简单优先分析法
6.3 简单优先分析法
6.3 简单优先分析法 6.3 简单优先分析法6.3 简单优先分析法
6.4 算符优先分析法 6.4 算符优先分析法6.4 算符优先分析法 6.4 算符优先分析法6.4 算符优先分析法 6.4 算符优先分析法
6.4 算符优先分析法 6.4 算符优先分析法6.4 算符优先分析法 6.4 算符优先分析法
6.4 算符优先分析法
两种优先分析方法
6.5 优先函数 6.5 优先函数
6.5 优先函数6.5 优先函数
6.5 优先函数
6.5 优先函数
第6章小结参考文献。