当前位置：文档之家 › 编译原理西安交通大学ppt

编译原理西安交通大学ppt

  • 格式：pptx
  • 大小：1.92 MB
  • 文档页数：68

下载文档原格式

  / 68

合集下载

《编译原理》课件

《编译原理》课件
代码生成
编译器可以将高级语言编写的源代码转换成机器语言或低级语言，以便在特定的硬件平台上运行。编 译器还可以生成可执行文件或动态链接库等二进制文件。
编译器在人工智能领域的应用
机器学习编译器
机器学习编译器可以将机器学习模型转换成可执行代码，以便在嵌入式设备或边缘计算 设备上运行。这种编译器可以优化模型的计算性能和内存占用，提高模型的运行效率。
3
缺点
对于某些复杂文法，可能导致大量的无用推导和 状态爆炸。
自底向上的语法分析
分析步骤
从输入符号序列的最后一个符号开始，逐步向上构建语法树，直 到找到与文法中的某个产生式右部匹配的符号串。
优点
可以充分利用已知信息，避免不必要的推导和状态爆炸。
缺点
对于某些复杂文法，可能导致大量的无用归约和状态爆炸。
04
中间代码生成
中间代码生成的定义和任务
定义
中间代码生成是编译器的一个阶段，将源代码转换成中间代码的过程。
任务
将源代码转换成一种中间表示形式，以便进行后续的优化和目标代码生成。
三地址代码的生成
01
三地址代码是一种中间代码形 式，由一系列的三元式组成。
02
三元式的形式为(op, arg1, arg2)，表示执行一个操作(op) 并产生一个结果，操作数arg1 和arg2来自寄存器、常数或之 前的计算结果。
语义分析
检查AST是否有语义错误，如类型错 误、未定义的变量等。
中间代码生成
将AST转换为中间代码，通常是三地 址代码。
代码优化
对中间代码进行优化，提高执行效 率。
代码生成
将中间代码转换为机器语言代码， 能够在特定硬件上执行。
编译器的分类

编译原理第一章ppt

编译原理第一章ppt

知识结构
程序设计语言与编译

程序设计语言
– 高级语言
– 汇编语言
– 机器语言

在计算机上如何执行一个高级语言程序？
– 把高级语言程序翻译成机器语言程序 – 运行所得的机器语言程序求得计算结果
翻译程序：就是把一种语言(称作源语言)书写 的程序，在不改变语义的条件下，翻译成另一 种语言(称作目标语言)的等价的程序。 Source Program
语句id1:=id2+id3*10的语法树
赋值语句 标识符 id1 := 表达式
表达式
+
表达式
标识符 id2
表达式
*
表达式
标识符
整数
id3
10
id1:=id2+id3*10
:=
id1
id2
+
* id3 10
依循的规则：语法规则

例如：
(1) 任何标识符是表达式。
(2) 任何常数(整常数、实常数)是表达式。
(3) 若表达式1和表达式2都是表达式，
那么表达式1+表达式2以及表达式1 * 表 达式2都是表达式。
③ 语义分析Semantic Analyzer
任务∶— 完成静态语义审查和处理 — 上下文相关性审查 — 类型匹配审查 — 类型转换
依循的规则：语义规则
例，int arr[2],c;
c = arr1 * 10 ;

常数表与标号表
编译程序在计算机系统中的所在层
来自计算机百科全书的定义
软件：计算机系统中的程序及其文档 系统软件：居于计算机系统中最靠近硬件的一层， 其他软件一般都通过系统软件发挥作用。他和具体 的应用领域无关，如编译系统和操作系统等。 语言处理系统：把软件语言书写的各种程序处理成 可在计算机上执行的程序。 软件语言：用于书写软件的语言。它主要包括需求 定义语言，功能性语言，设计性语言，程序设计语 言以及文档语言。

编译原理-西安交通大学(冯博琴)2_词法分析_3.0

编译原理-西安交通大学(冯博琴)2_词法分析_3.0

对于如上的状态转换图，状态0的代码如下所示：
state 0： C := GETCHAR ; if LETTER(C) then goto state 1 else FAIL( )
0
字母或数字
字母 1
其他
*
2
算 ‘D只 分界CE数D术 ＝要 界中符LI它过IG、 ’碰 符M的，I返程IT逻 、TT到一字它R(E，回辑‘标般符)R返U是当真(E符；识为C是回布。且假)号’符：是数T尔仅值R，、后空过字函U当括‘的格程，E。号.分、，’ 、、
单词符号识别的简单方法：超前搜索。 关键字识别：
例如：在标准FORTRAN中 1、DO99K = 1,10 2、IF(5.EQ.M)I = 10 3、DO99K = 1.10 4、IF(5) = 55
其中的DO、 IF为关键字
其中的DO、 IF为标识符 的一部分
标识符的识别
多数语言的标识符是字母开头的“字母/数字”串， 而且在程序中标识符的出现后都跟着算符或界符。因此， 不难识别。
状态转换图的功能:用于识别一定的字符串。
初态：一张转换图的启动条件，至少有一个,用圆圈表示。
终态：一张转换图的结束条件，至少有一个，用双圈表示。
* ：表示多读进了一个字符。
例2-3：简单的状态转换图示例：
1
X2
初态
从0状态到1状态 可能出现字母
字母或数字
终态
0
字母 1
其他 2 * 0
（b）识别标识符的转换图
常数的识别
对于某些语言的常数的识别也需要使用超前搜索。
算符和界符的识别
对于诸如C++语言中的“+ +”、“- -”，这种复 合成的算符，需要超前搜索。

编译原理第一章PPT课件

编译原理第一章PPT课件

掌握编译原理有助于提高程序员对程序性能、代码质量和软件
03
工程实践的理解。
编译原理的应用领域
编译器设计
编译原理的核心应用领域之一 是编译器设计，包括源代码到
目标代码的转换、优化等。
解释器设计
解释器是另一种将源代码转换 为机器码的程序，编译原理同 样适用于解释器的设计。
程序分析
编译原理中的一些技术可以用 于程序分析，例如静态分析、 动态分析和程序切片等。
从高级语言的设计开始，逐步向下设计低级语言和机器语言。
数据结构和算法选择
选择合适的数据结构和算法，提高编译器的性能和可维护性。
代码优化
在生成目标代码之前，对中间代码进行优化，以提高目标代码的性能 和质量。
04 语言与语法
语言的定义与分类
总结词
语言的定义与分类是编译原理的重要基础，它涉及到语言的语法、语义和语用等方面。
语言的语义分析
总结词
语义分析是编译过程中的重要环节，它涉及 到对语言意义的解释和理解。
详细描述
语义分析是对源代码进行静态分析的过程， 目的是理解源代码的意义和功能。在语义分 析阶段，编译器会检查源代码中是否有语法 错误、类型错误、逻辑错误等，并对其进行 相应的处理。同时，语义分析还会进行符号 表管理、类型检查、控制流分析等工作，以
详细描述
中间代码生成是编译过程的第三步，其主要任务是将抽象语法树转化为中间代码。中间代码是一种抽象的、与具 体机器无关的代码形式，通常采用三地址码、四元式等表示方式。中间代码的主要目的是为了方便后续的优化和 目标代码生成。
代码优化
总结词
对中间代码进行优化，提高执行效率。
详细描述
代码优化是编译过程中非常重要的一步，其主要任务是对中间代码进行优化，以提高生成的目标代码 的执行效率。常见的优化技术包括常量折叠、无用代码删除、循环展开等。

西安交通大学编译原理课件

西安交通大学编译原理课件

E→E+a|a E⇒E+a ⇒E+a+a ⇒… L(G)={a,a+a,a+a+a,…}
5
上下文无关文法回顾
A→Aa|a A→aA|a
L(G)={an|n为整数，n≥1}
A→Aα|β A→αA|β
A→ε
β不以A开头 L(G)={βαn|n为整数，n≥0}
L(G)={ε,…}
A→Aa|ε A→aA|ε
10
Parse Trees and Abstract Syntax Trees
推导：从开始符号起构造特定句子的一个方法 推导：不能够唯一地表示所推到出的句子的结构
11
上下文无关文法回顾
exp→exp op exp|(exp) | number op →+|-|*
(number – number) * number
15
exp⇒exp op exp ⇒(exp) op exp ⇒(exp op exp) op exp ⇒(number op exp) op exp ⇒(number - exp) op exp ⇒(number - number) op exp ⇒(number - number) * exp ⇒(number - number) * number
typedef struct streenode
{ ExpKind kind;
OpKind op;
struct streenode *lchild, *rchild;
int val;
} StreeNode;
typedef StreeNode *SyntaxTree;
18
Yinliang Zhao （赵银亮）

编译原理精选版演示课件.ppt

编译原理精选版演示课件.ppt

预测分析表
3
表驱动的预测分析程序模型
khk
4
实现步骤：
（1） 判断文法是否为LL(1)文法。 如果文法中含有左递归，必须先消除 左递归
（2）构造预测分析表 ： Select(A ) （3）列出预测分析过程
khk
5
第6章：自底向上分析方法
自底向上分析方法，也称移进归约分析法
实现思想（是推导的逆过程）：
对输入符号串自左向右进行扫描，并将输入符逐个 移入一个后进先出栈中，边移入边分析，一旦栈顶 符号串形成某个句型的可归约串时，就用该产生式 的左部非终结符代替相应右部的文法符号串，称为 归约。重复这一过程，直到归约到栈中只剩下文法 的开始符号时，则分析成功。
关键问题
khk
6
移进—规约分析（Shift-reduce parsing)
＋
A a
可得 b <. a
由A→( B 且B＋ ( B… 可得 (<. (
＋
B aa…
可得 (<. a
＋
B Aa )
可得 (<. A
khk
18
A(B(Aa) …)
(3) 求> .关系:
A(B…B
＋
Aa
由S→bAb，且A…) 可得 ) > . b
A＋…B 可得 B > . b
khk
88
例1：文法
SaAcBe A b A Ab B d
输入串abbcde#分析
khk
9
归约分析过程（移进归约）：
步骤 1 2 3 4 5 6 7 8 9 10 1kh1k
符号栈 # #a #ab #aA #aAb #aA #aAc #aAcd #aAcB #aAcBe #S

编译原理(1)50页PPT


编译程序
将一种语言书写的程序翻译成另一种语 言的等价的程序。 编译程序的输入对象称为源程序。 编译程序的输出对象称为目标程序。
高级语言程序的处理过程
常用的翻译工具有3种
根据被翻译语言与执行方式的不同 1.汇编程序
用于特定计算机上的汇编语言的翻译程序。
2.编译程序 3.解释程序
对源程序进行翻译的程序
sum = first+count*10
id1∶=id2+id3*10 四元式(运算符,运算对象1,运算对象2,结果)
5.中间代码优化
任务：通过调整和改变中间代码中某些 操作的次序，最终产生更加高效率的目 标代码 优化所依循的原则是程序的等价变换规 则 其方法有：公共子表达式的提取、循环 优化、删除无用代码等。
任务：扫描源程序，根据语言的词 法规则，分解和识别出每个单词， 并把单词翻译成相应的机内表示。 单词是语言中最小的语义单位 在词法分析阶段工作所依循的是语 言的词法规则。描述词法规则的有 效工具是正规式和有限自动机。
Pascal源程序片断
position := initial + rate * 60
二.编译程序概述
源程序 词法分析 语法分析 语义分析 中间代码生成 代码优化 目标代码生成
目标程序
英译与编译的比较
1.识别出句子中的一个个单 1.词法分析 字
2.分析句子的语法结构
2.语法分析
3.初步翻译句子的含意
3.语义分析中间代码 生成
4.译文修饰
4.优化
5.写出最后译文
5.目标代码生成
1.词法分析
表格与表格管理
编译过程中源程序的各种信息被保留在 种种不同的表格里，编译各阶段的工作 都涉及到构造、查找或更新有关的表格， 因此需要有表格管理的工作

编译原理PPT课件第一章 编译引论


25
五 子程序参数传递
当调用一个子程序时,首先应将所需的数据传递给子程序, 传递方式主要有三种: 传值,传地址,传名 设有如下函数: function distence(x1,y1,x2,y2):real; begin distence:=sqrt((x2-x1)**2+(y2-y1)**2) end; x1,y1,x2,y2 称为形式参数 设主程序调用如下: d=distence(a1,b1,a2,b2); a1,b1,a2,b2 称为实际参数.
子程序空间编译时可确定活动记录运行时可确定可变空间活动记录?连接数据?形式参数?局部变量?数组内情向量表?临时变量等活动记录可变空间堆栈精选ppt32此课件下载可自行编辑修改供参考
1
第一章
一 什么是编译程序？
引论
第一节、编译程序概述
计算机经过几十年的发展， 在程序设计语言方面,已经从 低级语言发展到高级语言;然而,计算机内部的本质只能识别 0 , 1 代码序列（机器语言）,而对高级语言甚至符号语言仍然一窍 不通。 因此用高级语言编写的程序,必须先翻译为机器语言， 才能被计算机理解执行。第一个完成这种翻译任务的编译程序 为FORTRAN编译程序,是上世纪五十年代设计的.
7> 子程序调用 函数调用一般出现在表达式中,形式如下: <函数名>(实际参数) 过程调用一般作为语句,形式如下: <过程名>(实际参数);
24
8> 输入输出语句 read(<变量名表>); write(<输出元表>); 9> 简单句和复合句 简单句是指不包含其它语句的基本语句, 复合句是指句中有句. 例如: V:=E,goto L ,read(a,b) 等都是简单句; if B then S else S, while B do S 等都是复合句.

西安交通大学《编译原理》第二章 期末考试拓展学习7

西交《编译原理》第二章词法分析C# 语言规范输入产生式定义 C# 源文件的词法结构。

C# 程序中的每个源文件都必须符合此词法文法产生式。

input:（输入：）input-sectionopt（输入节可选）input-section:（输入节：）input-section-part（输入节部分）input-section input-section-part（输入节输入节部分）input-section-part:（输入节部分：）input-elementsopt new-line（输入元素可选新行）pp-directive（pp 指令）input-elements:（输入元素：）input-element（输入元素）input-elements input-element（输入元素输入元素）input-element:（输入元素：）whitespace（空白）comment（注释）token（标记）C# 源文件的词法结构由五个基本元素组成：行结束符、空白、注释、标记和预处理指令。

在这些基本元素中，只有标记在 C# 程序的句法文法中具有重要意义。

对C# 源文件的词法处理就是将文件缩减成标记序列，该序列然后即成为句法分析的输入。

行结束符、空白和注释可用于分隔标记，预处理指令可导致跳过源文件中的某些节，除此之外这些词法元素对 C# 程序的句法结构没有任何影响。

当有若干词法文法产生式与源文件中的一个字符序列匹配时，词法处理总是构成尽可能最长的词法元素。

例如，字符序列 // 按单行注释的开头处理，这是因为该词法元素比一个 / 标记要长。

行结束符行结束符将 C# 源文件的字符划分为行。

new-line:（新行：）回车符 (U+000D)换行符 (U+000A)回车符 (U+000D) 后跟换行符 (U+000A)行分隔符 (U+2028)段落分隔符 (U+2029)为了与添加文件尾标记的源代码编辑工具兼容，并能够以正确结束的行序列的形式查看源文件，下列转换按顺序应用到 C# 程序中的每个源文件：如果源文件的最后一个字符为 Control-Z 字符 (U+001A)，则删除此字符。

编译原理-西安交通大学(冯博琴)第三章上下文无关文法


2、二义性问题
定义：
文法G的某一句子有两棵不同的树，则G为二义的。
二义性对语法分析不便，因此希望：
1）判定二义否 2）无二义性的充分条件 3）如何消除二义性
解决办法：尽量去掉二义性
①如对上例，可以通过阐明运算符的优先性和 结合性来解除文法的二义性
②通过重写一个文法，把结合性和优先规则结 合进文法本身中去 注意到，L(G)=L(G’)，G≠G’
该文法的： VN是出现P的左部所有符号集合 V是P的所有符号
∴VT = V \ VN S是该文法所定义的句子名字
∴写出了P ，就能找出其它三元素
2、从此可见
终结符：是用以组成语言中的串的基本符号，与
程序语言中“单词”是同义语； 如：表达式id+(id)*( - id)中，+、－、*、/、↑、id均为 终结符
得到相同的语法树 •有的语法，对于同一句子、应用不同规则进行推
导得到不同的语法树
例4 根据文法G对句子id + id * id进行推导
①文法G E -> E+E|E*E|( E )| i
②推导1 E => E+E => id+E => id+E*E => id+id*E => id+id*id ③推导2 E => E*E => E+E*E => id+E*E => id+id*E => id+id*id
问题： 如何描述语言 定义： 文法是描述语言的语法结构的形式规则（即语法规
则) 目的： 解决语言的有穷说明问题，包含对语法的描述，但
却不表达任何语义
1、文法的描述应达到要求：
  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

2, 用途
A, 不同程序块的变量之间建立联系
主程序:
子程序:
COMMON Z1,Z2,AL,BE,GA
SUBROUTINE QUAD
READ(11,1)AL,BE,GA
COMMON X1,X2, A,B,C
CALL QUAD …
结果
B, 节省单元,2块程序可以公用一个公用块, 特别是数组
无名公用区
初值
1，名字填符号表 2，分局部区号 3，构造数据区的相应存储映象：局部区，公用块
局部数据区的内容
临时变量，数组，简单变量
形式单元
a
寄存器保护区
返回地址
6
COMMON语句介绍 1, 格式
COMMON/n1/a1,a2,…an,/n2/b1,b2,…bn/ /R,X,Y,Z
公用 区名
变量名, 数组名, 数组说明符
k
a+4
4
分层分配方案
1，将源表示成一个有层次的有向图
2，从有向图的最低层开始, 往上逐层对程序块分配存储单元
11 20-30
1 15-18 4
2
3 7 13-19
9 6-14 5
4 5 8-12
如果不重叠, 需
要55个单元
58 0-4
67 0-5
86 0-7
现在只要工作
A11 A21 A12 A22 A13 A23 B1 B2 B3 B4
2) 间接联系 : DIM A(2,3), B(4) EQU(A(1,2),C),(C,B(1))
3) 不可矛盾 : DIM A(10)
A11 A21 A12 A22 A13 A23 C B1 B2 B3 B4
EQU(X, A(1)), (X,A(3)) DIM A(5), B(10) EQU(A(1), B(2))(A(3),B(3))
引入 CMP 后的符号表：
填B1查, CB新O1段.MBF开T1对L区=对IS始BB链TA(1,入表(.F完入LT口无T成,口=L为BnT的为1u=2最l0l1),后l)en结g果th不变
NAME
…
1
A
CMP
02
2
B
03
3
C
0
COMLIST 表：
NAME B1 …
LENGTH …
FT nu1ll
…
LT nu231ll
1
7.1 静态存储管理 --- FORTRAN 存储分配
FORTRAN 的特点： 1，过程不允许递归； 2，每个数据名所需的存储空间是常数（无可变数组） 3，数据名的性质完全确定
FORTRAN 的可调数组：不是可变数组，例子：
子程序：FUNCTION DIA ( A, N, L )
DIMENSION A ( L, L ) DIA = A ( 1, 1 ) DO 6 I = 2, N 6 DIA = DIA + A ( I, I ) RETURN END
1,规则 : a, 对于简单变量 I,J 属一个等价片, 表示 I,J 占用同一单元 b, 对于(X, A2,3),名表中无A2,3, 只有A,要指出 X 与 A 位置关系, 引入 相对数---A11,相对 X 的地址. c, 对于同一个等价元 A11 在不同的片中出现, 表示这两片的等价元存储是 相关的, 他们应予以合并, 原则是后一等价片按照第一片调整相对数.
7
3, 使用
A, COMMON A(2,3)
B, DIMENSION A(2,3) COMMON A
C, COMMON A DIMENSION A(2,3)
组说明符 数组名
交换次序
8
7.1.2 公用语句处理 用途：不同程序段之间共享数据
COMMON /B1/A,B,C COMMON /B1/E,F,G
12
7.1.3 等价语句处理 1, 等价语句介绍
a, 格式: EQUIVALENCE(变量表1),(变量表2)
b, 用途: 同一等价片中的变量共同存储单元 1) 节省: EQU(A,B,C,D) 变量A,B,C,D共同单元 2) 同一量定义不同名字
13
c,使用:
1) 数组等价 : DIMENSION A(2,3), B(4) EQU(A(1,2),B(1))
主程序： DIMENSION X ( 50, 50 ),
DIMENSION Y( 100, 100 ) … P1 = DIA ( X, 10, 50 ) + DIA ( Y, 100,100)
2
7.1.1 数据区 一个 FORTRAN 程序：
主程序 COMPILER 分块编译
目标程序1 常数 局部区
...
11
处理 COMMON /BLK1 /NAM1, NAM2的算法
1，若块名 BLK1 未出现在 COMMLIST 中，则把它填入并形成 它的空链（FT 和 LT 原来已经为 NULL） 2，把符号表中的 NAM1 和 NAM2 标志为属于公用区，并把他们 依次连接到 BLK1 原链的末端。若原链为空则把 NAM1 的入口 填到 FT 栏中。最后，调整 LT 使它指向新链的末端。
目标程序2 常数 局部区
LODER 分块连接
子程序 子程序
目标程序3 常数 局部区
有名公用区
无名公用区
3
子程序：SUBROTINE SWAP ( A, B )
T=A
A=B
B=T
RETURN
END
名字
符号表：
NAME
性质 ATTR
SWAP 子，二目
A
哑，实变
B
哑，实变
T
实变
地址
DA
ADDR
k
a
k
a+2
第九章 运行时空间组织
常见的分配策略：
1，静态分配策略，适用于编译时能完全确定每个数据项存储 空间的位置情况，如 FORTRAN； 2，动态分配策略，编译时不能完全确定数据项的性质，大小 等，如 ALGOL, 它允许递归过程和可变数组，名字作用域和 生存期满足分程序结构所限定的作用范围，可采用栈式动态 分配策略（内存先申请先释放）；当一种语言内存申请和释 放不遵循先请后放时，一般的处理方法是：让运行程序持有 一个大存区（称为堆），凡申请者从堆中分给一块，凡释放 者归还给堆，叫做堆式动态分配策略
B1
A BC
E
FG
9
处理方法 COMMON / B1 / A, B, C ( 50 ) DIMENSION A ( 10, 10 ), B ( 100 ) COMPLEX A, B
当首次扫描到 B1 的时候并不能立即确定每个公用元的相 对地址 怎么办？
10
CMP 和 公用表名 COMLIST
以 COMMON /B1/ A, B, C 为例
A1 A2 A3 A4 A5 A6 … B2 B3 B4 B1 B2 B3 B4
14
2, 等价语句处理
FORTRAN 的等价语句目的在于建立一个程序段中诸变量或数组之间的 存储空间的一致性
例, 处理等价语句： EQUIVALENCE ( X, A( 2, 3 )),(I, J, A( 1, 2 ), K)