语法树和推导过程

最左推导和最右推导，语法树，⼆义性⽂法※最左推导和最右推导
（每⼀步替换最左边的⾮终结符/每⼀步替换最右边的⾮终结符），最右推导称为规范推导。

最右推导对应于最左规约（规范规约）
例：
⽂法：
S--->AB
A--->a|t
B---->+CD
C--->a
D---->a
最右推导：
S--->AB---->A+CD--->A+Ca---->A+aa----->a+aa
最左推导：
S---->AB----->aB--->a+CD--->a+aD----->a+aa
※语法树：
例
⽂法：
相应的语法树：
（这是最右推导的语法树）
※⽂法的⼆义性：
给定⼀个⽂法G，如果L（G）中存在⼀个具有两棵或两棵以上分析树的句⼦，我们就称该⽂法为⼆义性的，G也叫⼆义性⽂法。

对于以下⽂法：
对于id+id*id的串，有两个分析树与之对应
造成⼆义性的原因是：⽂法中没有体现出结合率和优先级。

程序编译的四个步骤程序编译是将高级语言编写的程序翻译成机器语言的过程。

编译器是用来进行编译的工具，它可以将源代码转换为可执行的机器码，从而能够被计算机直接执行。

程序编译通常包括四个主要步骤：词法分析、语法分析、语义分析和代码生成。

1.词法分析词法分析是程序编译的第一步，也是一个很关键的步骤。

在词法分析中，编译器会将源代码分解为一个个的词法单元。

词法单元是程序的最小语法单位，可以是关键字、标识符、运算符、常量等等。

编译器会根据事先定义好的语法规则，将源代码中的字符序列解析成词法单元序列，并且给每个词法单元加上相应的标记，以便后面的步骤进行处理。

2.语法分析语法分析是程序编译的第二步。

在语法分析中，编译器会根据词法分析得到的词法单元序列，构建语法树或抽象语法树。

语法树是一个树状的数据结构，它表示程序的语法结构。

编译器会根据文法规则和词法单元的组合规则，对词法单元序列进行检查，并将其组织成语法树或抽象语法树。

语法树或抽象语法树是编译器进行后续处理的基础，它描述了程序的语法结构，方便后续步骤对程序进行分析和优化。

3.语义分析语义分析是程序编译的第三步。

在语义分析中，编译器会对语法树或抽象语法树进行分析，进行语义检查和语义推导。

语义是指程序中传达的意义和规则，它描述了程序如何运行和产生结果。

编译器会根据语义规则检查程序是否存在语义错误，并进行类型检查和类型推导。

如果程序存在语义错误，则编译器会输出错误信息，提示开发人员进行修正。

另外，编译器还会进行一些语义转换和优化，例如将高级语言中的循环结构转换为汇编语言中的跳转指令。

4.代码生成代码生成是程序编译的最后一步。

在代码生成中，编译器会根据语义分析得到的语法树或抽象语法树，生成目标代码或机器代码。

目标代码是特定平台上的中间代码表示，它与具体的机器相关性较低。

机器代码是目标机器上可以直接执行的二进制代码。

编译器会将目标代码或机器代码生成为对应的输出文件，例如可执行文件、动态链接库或静态链接库。

编译原理期末总结复习编译原理期末总结复习篇一：一、简答题1.什么是编译程序？答：编译程序是一种将高级语言程序(源程序)翻译成低级语言(目标程序)的程序。

将高级程序设计语言程序翻译成逻辑上等价的低级语言(汇编语言,机器语言)程序的翻译程序。

2.请写出文法的形式定义？答：一个文法G抽象地表示为四元组 G=（Vn,Vt,P,S）–其中Vn表示非终结符号– Vt表示终结符号，Vn∪Vt=Ｖ(字母表)，Vn∩Vt=φ– S是开始符号，–P是产生式，形如：α→β(α∈V+且至少含有一个非终结符号，β∈V*)3.语法分析阶段的功能是什么？答：在词法分析的基础上，根据语言的语法规则，将单词符号串分解成各类语法短语(例：程序、语句、表达式)。

确定整个输入串是否构成语法上正确的程序。

4.局部优化有哪些常用的技术？答：优化技术1—删除公共子表达式优化技术2—复写传播优化技术3—删除无用代码优化技术4—对程序进行代数恒等变换（降低运算强度）优化技术5—代码外提优化技术6—强度削弱优化技术7—删除归纳变量优化技术简介——对程序进行代数恒等变换（代数简化）优化技术简介——对程序进行代数恒等变换（合并已知量）5．编译过程分哪几个阶段？答：逻辑上分五个阶段：词法分析、语法分析、语义分析与中间代码生成、代码优化、目标代码生成。

每个阶段把源程序从一种表示变换成另一种表示。

6. 什么是文法？答：文法是描述语言的语法结构的形式规则。

是一种工具，它可用于严格定义句子的结构；用有穷的规则刻划无穷的集合；文法是被用来精确而无歧义地描述语言的句子的构成方式；文法描述语言的时候不考虑语言的含义。

7. 语义分析阶段的功能是什么？答：对语法分析所识别出的各类语法范畴分析其含义，进行初步的翻译(翻译成中间代码)；并对静态语义进行审查。

8.代码优化须遵循哪些原则？答：等价原则：不改变运行结果有效原则：优化后时间更短，占用空间更少合算原则：应用较低的代价取得较好的优化效果9.词法分析阶段的功能是什么？答：逐个读入源程序字符并按照构词规则切分成一系列单词任务：读入源程序，输出单词符号—滤掉空格，跳过注释、换行符—追踪换行标志，指出源程序出错的行列位置—宏展开，……10.什么是符号表？答：符号表在编译程序工作的过程中需要不断收集、记录和使用源程序中一些语法符号的类型和特征等相关信息。

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

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

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

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

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

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

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

是汉语的一个句子。

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

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

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

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

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

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