编译原理：语法分析（语法制导翻译）、语义分析（类型检查、中间代码生成）

编译器在做语法分析的过程中，除了回答程序代码的语法是否合法（LL,LR能否接收）外，还需要完成后续的工作（包括构建语法树、类型检查、中间代码生成、目标代码生成），这些后续工作一般都可以通过语法制导的翻译来完成。

语法制导翻译

在规约时加入相应的动作，完成表达式计算
在这里插入图片描述在这里插入图片描述
左边是产生式，右边是语义规则

语法制导翻译的目的
计算编译所需的额外信息（Additional Information）超出了
上下文无关语法和标准解析算法的能力

语法制导翻译的定义
语法制导是一个上下文无关文法和属性及规则的结合。其中，属性和
文法的符号相关，而规则和产生式相关联。

举例：
在规约时，多加入一个属性值，这样每次需要弹出的数目是3倍的右部长度：
在这里插入图片描述

属性，属性文法

属性：变量的数据类型(int)，表达式的值（‘a’)，变量在内存中的位置（jvm垃圾回收，内存地址管理）,过程或函数或程序的目标代码,数的有效位数(高精度计算用）
属性的存在利于优化

为什么定义这些属性：

  1. 语义分析，作类型检查（程序语言要求的类型匹配规则）
  2. 计算中间结果（例如：解释性语言中）
  3. 内存分配管理、数据溢出管理等
  4. 中间代码生成、代码优化
  5. 抽象语法树的构建

属性的分类：
静态属性与动态属性（根据属性绑定的时机）
① 静态属性：在代码执行前绑定的属性
② 动态属性：在代码执行中绑定的属性
综合属性和继承属性
L属性和S属性
在这里插入图片描述
X的属性不止一个，一个属性可以用多个属性的函数计算
在这里插入图片描述

发现有一些X加了1，2，这是为了区分他们
在这里插入图片描述
可见词法可以融入语法
在这里插入图片描述
从这个例子中发现，有一些属性，是从右向左传递的，但另外一些是从左往右，或者右部里面从左往右传递的。
在这里插入图片描述在这里插入图片描述

在这里插入图片描述在这里插入图片描述

依赖图和求值顺序（考）

依赖图：描述了某个语法分析树中属性实例之间的信息流 （拓扑排序）
在这里插入图片描述
在这里插入图片描述
兄弟结点的传递，分析树用虚线表示，依赖关系用实线表示
在这里插入图片描述
在这里插入图片描述

在这里插入图片描述
在这里插入图片描述

综合属性和继承属性

综合属性（合成属性）：在分析树结点N上的非终结符号A的综合属性是由N上的产生式所关联的语义规则来定义的。（结点N上的综合属性，只能通过N的子结点或者N本身的属性值来定义） （返回值，自底向上，后序遍历）
继承属性：在分析树结点N上的非终结符号B的继承属性是由N的父结点上的产生式所关联的语义规则来定义的。（结点N上的继承属性，只能通过N的父结点、N本身和N的兄弟节点上的属性值来定义） （传参，自顶向下，前序遍历或结合中序）

定理：给定一个属性文法，通过适当地修改文法，而无须改变文法的语言，所有的继承属性可以改变成综合属性。

S属性，L属性

S属性：如果一个语法制导定义中的每个属性都是综合属性，这个语法制导
定义就是S属性的。
L属性：如果一个语法制导定义所产生的依赖图中的边总是从左到右，而不
能从右到左，这个语法制导定义就是L属性的，更准确的讲，所有属性：
① 要么是综合属性
② 要么是继承属性，假设存在X0 -> X1X2…Xn，则
Xi.aj= fij(X0.a1,…,X0.ak, …, X1.al, …, Xi-1.a1, …Xi-1.ak)
也就是Xi依赖于X0~Xi-1，只有前面的算出来，后面的才能用
S属性文法属于L属性文法

在这里插入图片描述
表6.6的语法制导定义不是L-属性定义，因为文法符号Q的继承属性依赖于它右边文法符号R的属性。

代码实现

综合属性算法实现：自底向上或后序遍历分析树或语法树。

procedure PostEval (T : treenode);
begin
	for each child C of T do
		PostEval(C);
		Compute all synthesized attributes of T;
end;

例子：算术表达式

//算术表达式语法树的结构定义
typedef enum { Plus, Minus, Times } OpKind;
typedef enum { Opkind, ConstKind} ExpKind;
typedef struct streenode {
	ExpKind kind;
	OpKind op;
	struct streenode *lchild,*rchild;
	int val;
} STreeNode;
typedef STreeNode * SyntaxTree;

void postEval( SyntaxTree t )
{
	int temp;
	if ( t->kind == OpKind ) {
		postEval( t->lchild ); /* 遍历左子树 */
		postEval( t_rchild ); /* 遍历右子树 */
		switch ( t->op ) {
		case Plus:
			t->val = t->lchild->val + t->rchild->val;
			break;
		case Minus:
			t->val = t->lchild->val - t->rchild->val;
			break;
		case Times:
			t->val = t->lchild->val * t->rchild->val;
			break;
		} /* end switch */
	} /* end if */
} /* end postEval */

继承属性算法实现：前序（前序中序组合）遍历分析树或语法树

procedure PreEval(T: treenode);
begin
	for each child C of T do
		Compute all inherited attributes of C;
		PreEval(C);
end;

例子：变量申明中的dtype

// 变量申明的语法树的结构定义
typedef enum {decl, type, id} NodeKind;
typedef enum {integer, real} TypeKind;
typedef struct treenode {
	NodeKind kind;
	struct treenode *lchild,*rchild,* sibling;
	TypeKind dtype; /* for type and id nodes */
	char *name; /* for id nodes only */
} *SyntaxTree;

procedure EvalType(T: treenode);
begin
	case nodekind of T of
	decl:
		EvalType( type child of T );
		Assign dtype of type child of T to var-list child of T;
		EvalType( var-list child of T );
	type:
		if child of T = int then T.dtype := integer
		else T.dtype :=real;
	var-list:
		Assign T.dtype to first child of T;
		if third child of T is not nil then
			Assign T.dtype to third child;
			EvalType( third child of T );
	end case;
end EvalType;

void evalType (SyntaxTree t)
{
	switch (t->kind){
		case decl:
			t->rchild->dtype = t->lchild->dtype
			evalType( t->rchild );
			break;
		case id:
			if(t->sibling != NULL) {
				t->sibling->dtype = t->dtype;
				evalType( t->sibling evalType);
			}
			break;
	}
}

或者

void evalType(SyntaxTree t)
{
		if(t->kind == decl){
			SyntaxTree p = t->rchild;
			p->dtype = t->lchlild->dtype;
			while (p->sibling !=NULL){
			p->sibling->dtype = p->dtype;
			p = p->sibling;
		}
	}
}

在组合综合属性和继承属性的文法中，如果
① 综合属性依赖于继承属性（及其它的综合属性），
② 继承属性不依赖于任何综合属性，
那么就可能在分析树或语法树的一遍遍历中计算所有的属性。

综合属性和继承属性组合的文法

procedure CombinedEval(T:treenode);
begin
	for each child C of T do
		Compute all inherited attributes of C;
		CombinedEval( C );
	Compute all synthesized attributes of T. 
end;

存储属性值

作为参数和返回值的属性

在分析过程中，很多属性值都相同，或者只是在计算其他属性时临时使用，此时，并不需要在语法树中存储。那么，对于综合属性和继承属性，有如下的性质：
① 综合属性：可在后序遍历中计算，通常看作是过程的返回值。
② 继承属性：可在前序遍历中计算，通常看作是过程的参数

使用扩展数据结构存储属性值

对于那些不方便用参数或返回值传递的属性，同时，将属性值存储在语法树的结点里也是不合理时。此时，可以考虑扩展数据结构存储属性值。
重新考虑无符号整型数的例子。因为属性一旦设置，在计算过程中就固定了，因此，可以使用一个非局部变量存储它的值，而不是每次作为一个参数进行传递。

翻译模式

翻译模式是语法制导定义的一种便于翻译的书写形式。其中属性与文法符号相对应，语义规则或语义动作用花括号｛｝括起来，可被插入到产生式右部的任何合适的位置上。
这是一种语法分析和语义动作交错的表示法，它表达在按深度优先遍历分析树的过程中何时执行语义动作。
翻译模式给出了使用语义规则进行计算的顺序。可以看成是分析过程中翻译的注释。
在这里插入图片描述
在这里插入图片描述

设计翻译模式

条件：
语法制导定义是L-属性定义。
保证语义动作不会引用还没有计算的属性值。
方法：分两类讨论
① 只有综合属性的情况
② 既有综合属性，又有继承属性的情况

只有综合属性的情况：为每一个语义规则建立一个包含赋值的动作，并把这个动作放在相应的产生式右边的末尾。
既有综合属性，又有继承属性的情况：
① 产生式右边的符号的继承属性必须在这个符号以前的动作中计算出来。
② 一个动作不能引用这个动作右边符号的综合属性。
③ 产生式左边非终结符号的综合属性只有在它所引用的所有属性都计算出来以后才能计算。计算这种属性的动作通常可放在产生式右端的未尾。
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

语法制导翻译应用（抽象语法树构建）

利用语法制导翻译，自动构建抽象语法树，即：在语义动作中，加入生成抽象语法树的相关代码，自动生成对应的抽象语法树。
在这里插入图片描述
在这里插入图片描述
return p5 （根节点）

在这里插入图片描述

类型检查（语义分析）

输入：抽象语法树
输出：合法性、中间表示

语义分析也称为类型检查、上下文相关分析。
负责检查程序（抽象语法树表示）的上下文相关属性

符号表：哈希表结构

符号表是编译器的主要继承属性，也是主要的数据结构。用来存储程序中变量的相关信息。符号表的处理必须非常高效（程序中的变量规模会很大）

符号表的接口（数据结构与操作）
操作：新建、查找、插入与删除。
1 新建（New）：新建并初始化符号表。
2 查找（Lookup）：根据名字查找符号表（名字和结点对应）。
3 插入（Insert）：根据结点的名字和内容，将结点加入符号表。
4 删除（Delete）：根据结点的名字，删去对应结点（当符号不再有效时） 。

数据结构：（主要目标是实现高效）
A 线性表：

  1. 简洁，方便实现。
  2. 不高效，查找时间是线性时间O(N)。
  3. 适用于对时间要求不高的编译器。
  4. 举例：原型或实验编译器、小规模程序的编译器。

B 各种搜索树结构：

  1. 实现方式：二叉搜索树、平衡树（AVL trees）、B树。
  2. 相对高效，但并不是最高效，查找时间是O(logN)。
  3. 删除节点操作复杂。
  4. 实际中使用相对较少。

C Hash Tables（哈希表、杂凑表、或散列表）：

  1. 查找、插入与删除高效，时间是O(1)。
  2. 空间浪费比较严重。
  3. 实际中使用较多

哈希表是一个入口（entries）数组，称为桶（buckets），使用一个索引（index），通常定义在整数范围。同时，需要定义一个哈希函数（hash function），该函数可以直接把搜索键值（key value）转化为哈希值（hash value），该数值对应于索引。
有效性：哈希方法的有效性主要依赖于哈希函数的设定。
冲突：两个键值可能被哈希函数会映射到同一个索引
解决方案： ① 开放地址值法：将冲突的项目放在后续的桶（buckets）中。
问题1：会降低哈希表的性能。
问题2：删除样本时，操作复杂。
② 分离链表：每个桶看作是一个链表，将冲突的项目插入到该链表中。是目前主流的实现方式。

作用域
① 变量使用前说明（没有该条规则，编译器无法单趟完成编译）
② 最近嵌套原则。
块结构：程序语言的一块（block）是能包含说明的任意结构

在这里插入图片描述
方法1：一张Hash表的方法
① 进入作用域时，插入元素
② 退出作用域时，删除元素
方法2：采用符号表构成的栈。
① 进入作用域时，插入新的符号表
② 退出作用域时，删除新的符号表

类型检查

类型推断（type inference）和类型检查（type checking）是编译器的
核心
任务。这两个任务紧密相关，通常也一起执行，统一看作类型检查。
数据类型：显式表示（explicit）与隐式表示（implicit）

数据类型“
简单数据类型：例如 int, double, boolean, char
特殊例子：在C语言中，void这个类型没有值，表示空的集合。用于表示
没有返回值的函数，或表示一个指针指向未知类型。

中间代码生成

现代的编译器的语义分析模块，除了做语义分析外，还要负责生成中间
代码或者目标代码
在这里插入图片描述
在这里插入图片描述
为什么要划分不同的中间表示：高级语言、机器语言的组合

中间代码

定义：中间代码（intermediate representation; IR）是源程序的一种内部表示，
不依赖目标机的结构，易于生成目标代码与优化分析的中间表示。

中间代码的常见类型
1 三地址码（Three-address Code）
2 波兰式
3 P-代码（P-code）

三地址码（Three-address Code）

基本形式：x = y op z。该定义表示：对y和z的值进行op操作，并将值赋给x。
p：既可以是算术运算符，也可以是其他能操作y和z的操作符
为什么叫三地址码：基本形式包含x，y和z，代表了内存中的三个地址
注意：x的地址和y与z的使用不同。y和z可以代表常量等。

在这里插入图片描述
后序遍历
在这里插入图片描述
分支和循环都用跳转实现
实现方式：四元式（Quadruple）和三元式（Triple）
四元式：1个操作符以及三个地址。（对于少于3个地址的指令，将一个或更多的域设置成null或“empty”）
三元式：用自己的指令来代表临时变量。即：三地址码指令中的目标地址总是一个临时变量，供后续引用。
在这里插入图片描述
在这里插入图片描述
注意：取消了label指令，用三元式的引用代替。

//四元式的数据结构
	typedef enum { rd, gt, if_f, asn, lab, mul, sub, eq, wri, halt, …} OpKind;
	typedef enum { Empty, IntConst, String } AddrKind;
	typedef struct {
	AddrKind kind;
	Union {
		int val;
		char * name;
	} contents;
}Address;

typedef struct {
	OpKind op;
	Address addr1, addr2,addr3;
} Quad;

中间代码生成

在这里插入图片描述
在这里插入图片描述

代码优化

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/728600.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

板凳--------第60章 SOCKET：服务器设计

板凳--------第60章 SOCKET：服务器设计

60.1 迭代型和并发型服务器 1016 1.迭代型： 服务器每次只处理一个客户端，只有当完全处理完一个客户端的请求后才会去处理下一个客户端。只适用于快速处理客户端请求的场景，因为每个客户端都必须等待，直到前面所有的客户端都处理完…
阅读更多...
10年265倍！动态展示全球第一股英伟达10年股价走势

10年265倍！动态展示全球第一股英伟达10年股价走势

英伟达在过去十年的股价走势展示了其在市场上的强劲表现和显著增长。自1999年上市以来，英伟达的股价经历了多次显著的涨幅，并在2024年达到了历史新高。 从2023年6月的数据来看，英伟达的股价为386.54美元/股，市值为9548亿美元。然…
阅读更多...
redis以后台的方式启动

redis以后台的方式启动

文章目录 1、查看redis安装的目录2、Redis以后台的方式启动3、通过客户端连接redis4、连接后，测试与redis的连通性 1、查看redis安装的目录 [rootlocalhost ~]# cd /usr/local/redis/ [rootlocalhost redis]# ll 总用量 112 drwxr-xr-x. 2 root root 150 12月 6…
阅读更多...
Excel中插入的图片在不同电脑上消失的问题及解决方法

Excel中插入的图片在不同电脑上消失的问题及解决方法

在使用Excel时插入图片，然后在不同电脑上打开却发现图片消失并被替换为链接地址，这个问题通常出现于文件中的图片路径没有正确保存或者电脑上缺少相关的图片文件。下面让我们来详细解释这个问题以及可能的解决方法。 ### 问题原因分析1. **相对路径问题…
阅读更多...
数据结构—排序、查找、图论和字符串算法之Java实例

数据结构—排序、查找、图论和字符串算法之Java实例

一：引言 在编程的海洋中，算法是程序员的灵魂之光。它们不仅指引着代码的前进方向，更能解决难题，提升效率。虽然各式各样的算法琳琅满目，但其中有一些却是每位程序员必定会遇到且应当深刻掌握的。本文将带您走进这些至…
阅读更多...
从零开始学WEB前端——HTML理论讲解

从零开始学WEB前端——HTML理论讲解

有同学可能就会问：为什么我的创建的记事本文件名字叫“新建文本文档”而不是“新建文本文档.txt”呢？ 这是因为.txt是后缀名，表示的是打开方式，就比如.docx后缀的都是默认用word打开，.xlsx的都是默认用excel打开。 常…
阅读更多...
Linux ls-al命令实现，tree命令实现，不带缓存的文件IO（open,read,write）

Linux ls-al命令实现，tree命令实现，不带缓存的文件IO（open,read,write）

shell命令 ls -al 实现 #include <43func.h> void error_check(int ret, const char *msg) {if (ret -1) {perror(msg);exit(EXIT_FAILURE);} }char get_file_type(mode_t mode) {if (S_ISREG(mode)) return -;//检查给定的文件模式&#xff08;通常是从 stat 或 lst…
阅读更多...
【vite】define 全局常量定义

【vite】define 全局常量定义

&#x1f9ed; define 说明 类型&#xff1a; Record<string, any> 定义全局常量替换方式。其中每项在开发环境下会被定义在全局&#xff0c;而在构建时被静态替换。 Vite 使用 esbuild define 来进行替换&#xff0c;因此值的表达式必须是一个包含 JSON 可序列化值&a…
阅读更多...
WebHttpServletRequestResponse（完整知识点汇总）

WebHttpServletRequestResponse（完整知识点汇总）

额外知识点 Web核心 Web 全球广域网&#xff0c;也成为万维网&#xff08;www&#xff09;&#xff0c;可通过浏览器访问的网站 JavaWeb 使用Java技术来解决相关Web互联网领域的技术栈 JavaWeb技术栈 B/S架构&#xff1a;Browser/Server&#xff0c;即浏览器/服务器 架构模式…
阅读更多...
海康威视-下载的录像视频浏览器播放问题

海康威视-下载的录像视频浏览器播放问题

目录 1、播放异常比对 2、视频编码检查 2.1、正常视频解析 2.2、海康视频解析 2.3、比对工具 3、转码 3.1、maven依赖 3.2、实现代码 4、验证 在前面的文章&#xff08;海康威视-按时间下载录像文件_海康威视 sdk 下载录像 大小0-CSDN博客&#xff09;中&#xff0c;通…
阅读更多...
.NET+Python量化【1】——环境部署和个人资金账户信息查询

.NET+Python量化【1】——环境部署和个人资金账户信息查询

前言&#xff1a;量化资料很少&#xff0c;.NET更少。那我就来开个先河吧~ 以下是使用QMT进行量化开发的环境部署和基础信息获取有关操作。 1、首先自己申请券商的QMT权限&#xff0c;此步骤省略。 2、登陆QMT&#xff0c;选择极简模式&#xff0c;或者独立交易模式之类的。会进…
阅读更多...
C语言 | Leetcode C语言题解之第171题Excel表列序号

C语言 | Leetcode C语言题解之第171题Excel表列序号

题目&#xff1a; 题解&#xff1a; int titleToNumber(char* columnTitle) {int number 0;long multiple 1;for (int i strlen(columnTitle) - 1; i > 0; i--) {int k columnTitle[i] - A 1;number k * multiple;multiple * 26;}return number; }
阅读更多...
【Mybatis-plus】查询及更新为null或空字符串

【Mybatis-plus】查询及更新为null或空字符串

前言 查询为 null 或者 空字符串时&#xff0c;可以使用 or() 关键字。 提示&#xff1a;以下是本篇文章正文内容&#xff0c;下面案例可供参考 查询 使用 LambdaQueryWrapper 查询 parentCode 为 null 或者 空字符串 的数据。 LambdaQueryWrapper<CompanyEntity> qu…
阅读更多...
go 1.22 增强 http.ServerMux 路由能力

go 1.22 增强 http.ServerMux 路由能力

之前 server func main() {http.HandleFunc("/", func(w http.ResponseWriter, r *http.Request) {fmt.Println("Received request:", r.URL.Path)fmt.Fprintf(w, "Hello, client! You requested: %s\n", r.URL.Path)})log.Println("Serv…
阅读更多...
Gone——golang依赖注入框架介绍

Gone——golang依赖注入框架介绍

文章目录 Gone是什么特性小试牛刀概念与启动流程人话版本鬼话版本代码版本 关于Logo Gone是什么 首先&#xff0c;Gone是Golang的一个轻量级的依赖注入框架&#xff0c;目前依赖注入的装配流程是通过反射来实现的&#xff1b;虽然golang的反射一直被人诟病太慢&#xff0c;但是…
阅读更多...
RK3568平台（音频篇）音频ALSA框架

RK3568平台（音频篇）音频ALSA框架

一.ALSA框架简介 ALSA表示先进linux声音架构&#xff08;Advanced Linux Sound Archiecture&#xff09;&#xff0c;它由一系列的内核驱动、应用程序编程接口&#xff08;API&#xff09;以及支持linux下声音的应用程序组成、 ALSA项目发起的原有是linux下的声卡驱动&#x…
阅读更多...
【论文笔记】LoRA LOW-RANK ADAPTATION OF LARGE LANGUAGE MODELS

【论文笔记】LoRA LOW-RANK ADAPTATION OF LARGE LANGUAGE MODELS

题目&#xff1a;LoRA: LOW-RANK ADAPTATION OF LARGE LANGUAGE MODELS 来源: ICLR 2022 模型名称: LoRA 论文链接: https://arxiv.org/abs/2106.09685 项目链接: https://github.com/microsoft/LoRA 文章目录 摘要引言问题定义现有方法的问题方法将 LORA 应用于 Transformer 实…
阅读更多...
双写一致性

双写一致性

双写一致性 当修改了数据库的数据也要同时更新缓存的数据&#xff0c;缓存和数据库的数据要保持一致。 注意这里是对数据库进行写操作而不是读操作&#xff0c;通常我们有两种方式完成这个写操作&#xff0c;分别是&#xff1a;先删除缓存再修改数据库 和 先修改数据库再删除…
阅读更多...
并发锁机制

并发锁机制

JDK1.6 synchronized &#xff08;底层是由C实现的&#xff09;&#xff1a; synchronized: 互斥锁&#xff0c;悲观 锁&#xff0c;同步锁&#xff0c;重量级锁&#xff08;耗性能&#xff09;&#xff0c;多线程使用重量级锁很容易发生线程阻塞&#xff0c;因为涉及到多个线程…
阅读更多...
elementUI的el-table自定义表头

elementUI的el-table自定义表头

<el-table-column label"昨日仪表里程(KM)" align"left" min-width"190" :render-header"(h, obj) > renderHeader(h, obj, 参数)" > <template slot-scope"scope"> <span>{{ scope.row.firstStartMil…
阅读更多...
最新文章

Copyright @ 2022~2023