编译原理-语法树

（一）语法分析概述语法分析是对高级语言的句子结构进行分析，在编译过程中处于核心地位，它的主要任务是在词法分析识别出正确单词符号串的基础上，根据语言定义的语法规则，从单词符号串中识别出各种语法成分，并进行语法检查和错误处理，生成相应的语法树。

生成语法树的方法有两种，一种是自上而下另一种是自下而上。

[1]自上而下的语法分析方法是对由单词种别构成的源程序，尝试用所有可能的途径，从语法树的根结点出发，从上至下为输入符号串建立一棵语法树。

也可以说成是为输入符号串构造一个最左推导。

整个分析过程就是一种试探的过程，通过不断使用不同产生式谋求匹配输入符号串的过程。

自上而下的语法分析方法分为确定的和不确定的两种。

只有LL（1）文法才能进行确定的自上而下语法分析，在这种分析方法中面临两个问题，回溯和死循环。

通过对文法的产生式进行改造来解决这两个问题，在回溯中改造的方法是提取公共左因子，比如:A→αβ1|αβ2，改造后为A→αA’，A’→β1|β2。

死循环的改造方法是消除左递归，比如:A→Aα|β改造后为A→βA’，A’→αA’|ε。

而不确定的有递归下降分析和预测分析，前者适合手工实现，后者适合自动生成。

递归下降分析是用子程序来实现的，为每个非终结符创造一个子程序，每个子程序里面都有一个函数体，这个函数体是根据非终结符的产生式而定义展开的，当分析过程中遇到终结符时就直接匹配，如果遇到非终结符就调用相应的非终结符对应的子程序。

预测分析方法需要借助一个状态栈和一个二维分析表来实现，两者必须联合控制才能更好的实现预测分析方法。

自下而上的语法分析方法和自上而下的语法分析方法是完全不同的两种方法，但是它们产生的结果是相同的，都是构造一棵语法树，只是构造的过程不同罢了。

语法树创建的过程是把分析符号串的各个符号作为叶子结点，按照文法定义的规则，把产生式左部的非终结符作为父结点，自下而上构造此树的过程。

它的基本思想是“移进—归约”。

编译原理之理解语法树、短语、直接短语和句柄短语书上的定义如下:书上写的⽐较抽象，我这⾥简单解释⼀下，有两个⽂法，分别是：S=*=>aAp (由于部分字符难以输⼊，在此⽤a,b,p代替)A=+=>b我们由此可以画出他的抽象语法树，如下:那么，abp为此句型的短语总结来说：⼀个句型的语法树中任⼀⼦树叶结点所组成的符号串都是该句型的短语，由这概念，那么我们⾃然可以想到，b也应该是该句型的⼀个短语。

直接短语书中的定义：书中的意思总结来说，指的是如果⼦树中不再包含其他的⼦树，即A只能推导出b，⽽b不能再推出其他的式⼦，则b为此句型的直接短语句柄先来看⼀下书中的定义:书中的意思就是：直接短语中的最左直接短语为该句型的句柄。

⼩练习1.已知⽂法：S->a|^|(T)T->T,S|S分析句型（T,(^,a))，求全部的短语、直接短语和句柄。

S -> (T) -> (T, S) -> (T, (T)) -> (T, (T, S)) -> (T, (S,S)) -> (T, (^, S)) ->（T, (^, a))此⽂法的抽象语法树为:由此可得S=(S, (T), b)为此⽂法的⼀个句型：短语: ^; a; ^, a; (^, a); T, (^, a); （T, (^, a));直接短语:^; a;句柄:^此时的最左直接短语是^所以句柄为^2.构造上下⽂⽆关⽂法，描述语⾔：（1）｛a n b n|n>=0｝ a, b个数相等，即可得 S -> aSb l ab | ε（2）｛a m b n|m>=n>=0｝ a个数⼤于b，即可得 S -> aS l A A -> aAb | ε（3）｛(ab)n|n>=0｝ A -> ab S -> (A)S | ε（4）｛a m b n|m,n>=1｝ S -> aSb|aS|Sb|ab（5）if语句 if => if <条件> then <语句A> | if <条件> then <语句B> else <语句B>3.如果if语句的⽅法：stmt -> if expr then stmt| if expr then stmt else stmt| other句⼦if E1 then if E2 then S1 else S2是否有两棵不同的语法树？说明了什么？ 有两颗语法树，分别如图说明原语法树是⼆义的。

编译原理名词解释2.二义性文法：如果一个文法存在某个句子对应两棵不同的语法树，则称这个文法是二义性文法。

3.DISPLAY表：过程的嵌套层次显示表，记录该过程的各外层过程的最新活动记录的起始地址。

由于过程嵌套允许内层过程引用外层过程定义的数据，因此，当一个过程运行时必须跟踪它的所有外层过程的最新活动记录起始地址，display表就是用于登记每个外层过程的最新活动记录起始地址。

9.语法制导翻译：在语法分析过程中，根据每个产生式所对应的语义子程序进行翻译的办法叫做语法制导翻译。

10.短语：令G是一个文法，S 划文法的开始符号，假定αβδ是文法G的一个句型，如果有SαAδ且Aβ，则称β是句型αβδ相对非终结符A的短语。

14.超前搜索：在词法分析过程中，有时为了确定词性，需超前扫描若干个字符。

15.句柄：一个句型的最左直接短语。

16.语法制导翻译：在语法分析过程中，根据每个产生式所对应的语义程序进行翻译的方法叫做语法制导翻译。

17.规范句型：由规范推导所得到的句型。

18.素短语：素短语是指这样一个短语，至少含有一个终结符，并且，除它自身外不再含任何更小的素短语。

19.语法：是组规则，用它可形成和产生一个合式的程序。

20.语义：定义程序的意义的一组规则。

21.优化：对程序进行各种等价变换，使得从变换后的程序出发，能产生更有效的目标代码。

三种级别：局部优化、循环优化、全局优化21．词法分析词法分析的主要任务是从左向右扫描每行源程序的符号，按照词法规则从构成源程序的字符串中识别出一个个具有独立意义的最小语法单位，并转换成统一的内部表示(token)，送给语法分析程序。

22．LL(1)文法若文法的任何两个产生式A →α | β都满足下面两个条件：（1）FIRST(α) ⋂FIRST(β) = φ；（2）若β⇒* ε，那么FIRST(α)⋂ FOLLOW( A ) = φ。

我们把满足这两个条件的文法叫做LL(1)文法，其中的第一个L代表从左向右扫描输入，第二个L表示产生最左推导，1代表在决定分析器的每步动作时向前看一个输入符号。

编译原理for结构的语法树
编译原理中，for结构是一种常见的语法结构，用于循环执行一些语句。

在语法树中，for结构通常由三个部分组成：循环变量的初始化语句、循环条件判断语句和循环体语句。

循环变量的初始化语句一般用于给循环变量赋初始值。

在语法树中，循环变量的初始化语句通常是一条简单的赋值语句，例如：i = 0。

循环条件判断语句用于判断循环要不要继续执行。

在语法树中，
循环条件判断语句通常是一条关系运算符语句或者逻辑运算符语句，
例如：i < n。

循环体语句用于执行循环中需要重复执行的操作。

在语法树中，
循环体语句可以是一条语句、多条语句的块结构或者一个函数调用语句，例如：print(i)。

在编译器中，编译器会根据语法树中的for结构生成一种特殊的
代码。

这种代码通常包含一个循环头和一个循环尾。

循环头中包括了
循环变量的初始化语句和循环条件判断语句，而循环尾中包括了循环
变量的更新语句和跳转语句。

在编译器中，编译器会根据循环体语句
生成一些中间语言代码，最终将这些代码和循环头和循环尾的代码合
并生成最终的代码。

在实际编程中，for结构是一种非常常用的语法结构。

它可以用于循环遍历数组、枚举类型以及一些需要反复执行的操作。

在编写for
结构代码的时候，需要注意一些细节问题，例如循环变量的初始化、循环条件的判断以及循环体语句的执行。

只有掌握了这些细节问题，才能编写出高效且正确的for结构代码。

编译原理——关于⽂法、推导、规约、句柄、语法树、⼆义性的理解短语：直观理解，该句型中的⼀个符号串，这个符号串能被前⾯句型中的某个⾮终结符推出，那么这个符号串是该句型的短语。

注意必须保证⾮终结符是前⾯句型的，说明要确定⼀个句型的短语，要找到句型对应的推导，规约或语法树才可以，对应的是这个句型⽣成的动态过程。

简单短语：略句柄：⼀个句型只能有⼀个句柄。

（前提默认⾮⼆义性⽂法）推导和规约过程理解推导过程：对每⼀个句型，该句型⼀定有⼀个推导过程（可能不唯⼀），推导过程⼀定对应⼀颗语法树（推导过程可能不唯⼀，当然语法树也可能不唯⼀）推导不唯⼀，规约不唯⼀，规范推导规范推导：最右推导，每次拆最右边的⾮终结符规约过程：规约直观理解就是，“剪⼦树（但留⼦树的根）【对应到表达式就是⽤短语替代那个⾮终结符】，每剪⼀次对应⼀次规约，直到剪到只剩树根”规范规约：最左规约，每次对最左简单短语进⾏的规约⼀个⽂法的句型，必能通过⼀次⼀次的规范推导获得。

同时也能通过⼀次⼀次的规范规约规约⾄开始符号，每次规约都对应⼀个句柄。

所以⽤规约简单短语的⽅法检查⽂法是可⾏的。

规范推导和规范规约互为逆过程：规范推导倒着看就是规范规约规范句型：由规范推导或规范规约得到的句型⼆义性⽂法——不可判定的⽂法所定义的某个句⼦存在两棵不同的语法树。

⽂法中存在某个句⼦，它有两个不同的规范（最右）推导。

⽂法中存在某个句⼦，它有两个不同的规范（最左）规约，即在规约中某些规范句型的句柄不唯⼀。

注意：1. 如果存在两种推导，那么不能说明⼀定是⼆义性⽂法，因为两种推导可能对应同⼀个语法树2. ⼆义性的例⼦句型E+E*i存在不同句柄题型：给⼀句型，找短语、简单短语、句柄1. 画语法树2. 对于某个句型的语法树，它的每⼀颗⼦树都能找出⼀个短语（可能重复），枚举所有的⼦树就能找全。

3.。

第二章文法和语言本章讲述目前广泛使用的上下文无关文法。

即用上下文无关文法作为程序设计语言语法的描述工具。

阐明语法的一个工具是文法。

本章将介绍文法和语言的概念。

本章重点：上下文无关文法及其句型分析中的有关问题。

第一节文法的直观概念当我们表述一种语言时，无非是说明这种语言的句子，如果语言只含有有穷多个句子，则只需列出句子的有穷集就行了，但对于有无穷句子的语言来讲，存在着如何给出它的有穷表示的问题。

以自然语言为例，人们无法列出全部句子，但是人们可以给出一些规则，用这些规则来说明（或者定义）句子的组成结构，比如：“我是大学生”。

是汉语的一个句子。

汉语句子可以是由主语后随谓语而成，构成谓语的是动词和直接宾语，我们采用EBNF来表示这种句子的构成规则：〈句子〉∷＝〈主语〉〈谓语〉〈主语〉∷＝〈代词〉|〈名词〉〈代词〉∷＝我|你|他〈名词〉∷＝王明|大学生|工人|英语〈谓语〉∷＝〈动词〉〈直接宾语〉〈动词〉∷＝是|学习〈直接宾语〉∷＝〈代词〉|〈名词〉“我是大学生”的构成符合上述规则，而“我大学生是”不符合上述规则，我们说它不是句子。

这些规则成为我们判别句子结构合法与否的依据。

一旦有了一组规则以后，我们可以按照如下方式用它们去推导或产生句子。

我们开始去找∷＝左端的带有〈句子〉的规则并把它表示成∷＝右端的符号串，这个动作表示成：〈句子〉⇒〈主语〉〈谓语〉，然后在得到的串〈主语〉〈谓语〉中，选取〈主语〉或〈谓语〉，再用相应的规则∷＝右端代替之。

比如，选取了〈主语〉,并采用规则〈主语〉∷＝〈代词〉，那么得到：〈主语〉〈谓语〉⇒〈代词〉〈谓语〉，重复做下去，我们得到句子：“我是大学生”的全部动作过程是：〈句子〉⇒〈主语〉〈谓语〉⇒〈代词〉〈谓语〉⇒我〈谓语〉⇒我〈动词〉〈直接宾语〉⇒我是〈直接宾语〉⇒我是〈名词〉⇒我是大学生符号⇒的含义是，使用一条规则，代替⇒左边的某个符号，产生⇒右端的符号串。

显然，按照上述办法，不仅生成“我是大学生”这样的句子，还可以生成“王明是大学生”，“王明学习英语”，“我学习英语”，“他学习英语”，“你是工人”，“你学习王明”等几十个句子。