语义分析程序
- 格式：doc
- 大小：37.00 KB
- 文档页数：3
下载文档原格式
合集下载
pl0语法分析词法分析语义分析
作者:love冥天出处：PL/O语言是Pascal语言的一个子集，我们这里分析的PL/O的编译程序包括了对PL/O语言源程序进行分析处理、编译生成类PCODE代码,并在虚拟机上解释运行生成的类PCODE代码的功能。
PL/O语言编译程序釆用以语法分析为核心、一遍扫描的编译方法。
词法分析和代码生成作为独立的子程序供语法分析程序调用。
语法分析的同时，提供了出错报告和出错恢复的功能。
在源程序没有错误编译通过的情况下,调用类PCODE解释程序解释执行生成的类PCODE代码。
词法分析子程序分析：词法分析子程序名为getsym,功能是从源程序中读出一个单词符号（token）, 把它的信息放入全局变量sym. id和num中，语法分析器需要单词时,直接从这三个变量中获得。
（注意!语法分析器每次用完这三个变量的值就立即调用getsym子程序获取新的单词供下一次使用。
而不是在需要新单词时才调用getsym iS 程。
）getsym过程通过反复调用getch子过程从源程序过获取字符，并把它们拼成单词。
getch过程中使用了行缓冲区技术以提高程序运行效率。
词法分析器的分析过程:调用getsym时，它通过getch过程从源程序中获得一个字符。
如果这个字符是字母，则继续获取字符或数字，最终可以拼成一个单词，查保留字表，如果查到为保留字，则把sym变量赋成相应的保留字类型值;如果没有查到，则这个单词应是一个用户自定义的标识符（可能是变量名、常量名或是过程的名字），把sym置为ident,把这个单词存入id变量。
查保留字表时使用了二分法查找以提高效率。
如果getch获得的字符是数字，则继续用getch获取数字，并把它们拼成一个整数，然后把sym置为number,并把拼成的数值放入num变量。
如果识别出其它合法的符号(比如:赋值号、大于号、小于等于号等)，则把sym则成相应的类型。
如果遇到不合法的字符，把sym置成nul。
语法分析子程序分析：语法分析子程序采用了自顶向下的递归子程序法，语法分析同时也根据程序的语意生成相应的代码，并提供了出错处理的机制。
程序编译的四个步骤
程序编译的四个步骤程序编译是将高级语言编写的程序翻译成机器语言的过程。
编译器是用来进行编译的工具，它可以将源代码转换为可执行的机器码，从而能够被计算机直接执行。
程序编译通常包括四个主要步骤：词法分析、语法分析、语义分析和代码生成。
1.词法分析词法分析是程序编译的第一步，也是一个很关键的步骤。
在词法分析中，编译器会将源代码分解为一个个的词法单元。
词法单元是程序的最小语法单位，可以是关键字、标识符、运算符、常量等等。
编译器会根据事先定义好的语法规则，将源代码中的字符序列解析成词法单元序列，并且给每个词法单元加上相应的标记，以便后面的步骤进行处理。
2.语法分析语法分析是程序编译的第二步。
在语法分析中，编译器会根据词法分析得到的词法单元序列，构建语法树或抽象语法树。
语法树是一个树状的数据结构，它表示程序的语法结构。
编译器会根据文法规则和词法单元的组合规则，对词法单元序列进行检查，并将其组织成语法树或抽象语法树。
语法树或抽象语法树是编译器进行后续处理的基础，它描述了程序的语法结构，方便后续步骤对程序进行分析和优化。
3.语义分析语义分析是程序编译的第三步。
在语义分析中，编译器会对语法树或抽象语法树进行分析，进行语义检查和语义推导。
语义是指程序中传达的意义和规则，它描述了程序如何运行和产生结果。
编译器会根据语义规则检查程序是否存在语义错误，并进行类型检查和类型推导。
如果程序存在语义错误，则编译器会输出错误信息，提示开发人员进行修正。
另外，编译器还会进行一些语义转换和优化，例如将高级语言中的循环结构转换为汇编语言中的跳转指令。
4.代码生成代码生成是程序编译的最后一步。
在代码生成中，编译器会根据语义分析得到的语法树或抽象语法树，生成目标代码或机器代码。
目标代码是特定平台上的中间代码表示，它与具体的机器相关性较低。
机器代码是目标机器上可以直接执行的二进制代码。
编译器会将目标代码或机器代码生成为对应的输出文件，例如可执行文件、动态链接库或静态链接库。
《编译原理》教学课件 第5章-语义分析
类型分析
作用：把类型表示转换成类型的内部表示
分析过程：读Token序列，识别出各种类型， 返回类型内部表示的地址
array [ 1 .. 10 ] of integer
arrKind … low=1 tp1=intPtr … up=10 tp2=intPtr IndexPtr= (1,subTy, intPtr , 1 ,10) … … ElemPtr=intPtr size=(up-low+1) * sizeof (int)
VariBody:
Next
CaseUni VariUnits t
id CaseTyp Off e
FixBody VariBody Next
set: Size
Kind
BaseType
file: Size
pointer:
Size
Kind CompType Kind TypeName
例有如下的类型定义： at = ARRAY [1..10] OF ARRAY[1..100] OF integer; rt = RECORD x : real ; a : at; CASE u: boolean OF false:(k : integer); true:(y: real; b: boolean) END 构造类型的内部表示。
例有声明如下： CONST pai= 3.14 ;
TYPE vector=ARRAY[1..10] OF integer;
VAR x, y : real ;
r, s : vector ;
设当前层数和可用offset值分别为L和0， 构造标识符 pai, vector, x, y, r 和s 的属性表示,假设整数类型占1个单元，实 数类型占2个单元。
《编译原理教程》第四章语义分析和中间代码生成
控制流分析和数据流分析案例
总结词
控制流分析和数据流分析是编译器设计中两种重要的 语义分析技术。
详细描述
在控制流分析案例中，我们以一个具有条件语句和循环 的程序为例，分析其控制流图（Control Flow Graph， CFG）。CFG是一个有向图，用于表示程序中各个基本块 之间的控制流程关系。通过CFG，编译器可以检测到潜 在的程序错误，如死代码和无限循环。在数据流分析案 例中，我们使用数据流方程来跟踪程序中变量的值在执 行过程中的变化。我们以一个简单的程序为例，该程序 包含一个变量在函数调用后被修改的情况。通过数据流 分析，我们可以确定变量的最新值，以便在后续的语义 分析中使用。
定义
三地址代码是一种中间代码形式，它由一系列的三元组操作数和 操作符组成。
特点
三地址代码具有高度规范化，易于分析和优化，且易于转换成目 标代码。
常见形式
常见的三地址代码有三种基本形式，即加法、减法和赋值。
循环优化
定义
循环优化是指在编译过程中，对循环结构进行优化， 以提高目标代码的执行效率。
常见方法
将源程序分解成一个个的词素或标记。
语法分析
根据语言的语法规则，将词素或标记组合成一个个的语句或表达式。
语义分析
对语法分析得到的语句或表达式进行语义检查，确保其语义正确。
中间代码生成
基于语义分析的结果，生成中间代码。
02
语义分析技术
类型检查
类型检查是编译过程中对源代码进行语义分析的重要环节，其主要目的是 确保源代码பைடு நூலகம்类型安全。
常见的循环优化方法包括循环展开、循环合并、循环 嵌套等。
优化效果
通过循环优化，可以减少循环的次数，提高程序的执 行效率。
语义分析
语义分析
语义分析是编译过程的一个逻辑阶段，语义分析的任务是对结构上正确的源程序进行上下文有关性质的审查，进行类型审查。
语义分析是审查源程序有无语义错误，为代码生成阶段收集类型信息。
比如语义分析的一个工作是进行类型审查，审查每个算符是否具有语言规范允许的运算对象，当不符合语言规范时，编译程序应报告错误。
如有的编译程序要对实数用作数组下标的情况报告错误。
又比如某些程序规定运算对象可被强制，那么当二目运算施于一整型和一实型对象时，编译程序应将整型转换为实型而不能认为是源程序的错误。
语义分析的地位
语义分析的地位:编译程序最实质性的工作；第一次对源程序的语义作出解释，引起源程序质的变化。
语义分析的任务
按照语法分析器识别的语法范畴进行语义检查和处理，产生相应的中间代码或目标代码。
中间代码
介于源语言和目标代码之间的一种代码。
引入中间代码的目的
1）方便生成目标代码；
2）便于优化；
3）便于移植。
语义分析的作用
在一个社会网络中常有节点之间的信息交流。
可以对这种社会网络进行分析的一种强大的用来获得和理解文本信息的技术被称为语义网消息传输分析（语义分析）。
作为一个在人工智能和计算语言学的方法，它为知识推理和语言提供了一个结构和过程。
编程语言的语法与语义分析
编程语言的语法与语义分析编程语言是程序员用来编写计算机程序的一种人造语言。
它具有自己的语法和语义规则，用以描述计算机程序的结构和行为。
在编写程序时，程序员需要通过语法和语义分析来确保程序的正确性和可靠性。
一、语法分析语法分析是编程语言的第一步，它用于检查程序中的语法错误。
语法是一种规则系统，用于定义编程语言中有效语句和表达式的结构。
通过语法分析，程序员可以确定程序是否符合语法规则。
常见的语法分析方法包括上下文无关文法和词法分析。
1. 上下文无关文法上下文无关文法（Context-Free Grammar）是一种形式化的语言描述工具，用于定义编程语言的语法。
它由一组产生式（Production Rules）组成，每个产生式描述了一个语法结构的生成方式。
通过上下文无关文法，程序员可以将程序按照规定的语法结构进行构造。
例如，C语言中的产生式可以定义为"E -> E + T"，表示表达式E的生成方式为"E加T"。
2. 词法分析词法分析（Lexical Analysis）是语法分析的一部分，用于将程序源代码划分为一个个的词法单元（Tokens）。
词法单元是编程语言的最小单位，包括关键字、标识符、操作符等。
通过词法分析，程序员可以检查程序中的词法错误，并将其转化为更易于处理的数据结构。
例如，在C语言中，"for(int i=0; i<10; i++)"可以被词法分析为"for"、"("、"int"、"i"、"="、"0"、";"、"i"、"<"、"10"、";"、"i++"、")"等词法单元。
语义分析
一个C程序片断
int arr[2],b;
b = arr * 10;
源程序的结构是正确的.语义分析将审查类型并报告错误:不能在表达式中使用一个数组变量,赋值语句的右端和左端的类型不匹配.
又比如在语句sum:=first+count*10中，*的两个运算对象：count是实型，10是整型，则语义分析阶段进行类型审查之后，在语法分析所得到的分析树上增加一语义处理结点，表示整型变成实型的一目算符inttoreal.
语义分析的现状：编译器最实质性的工作；对源代码语义的第一次解释，引起了源程序的质的变化。
语义分析的地位:编译程序最实质性的工作；第一次对源程序的语义作出解释，引起源程序质的变化。
按照语法分析器识别的语法范畴进行语义检查和处理，产生相应的中间代码或目标代码.
介于源语言和目标代码之间的一种代码。
在社交网络中，节点之间通常存在信息交换。用于获取和理解可以在此社交网络中进行分析的文本信息的强大技术称为语义Web消息传输分析（语义分析）。作为人工智能和计算语言学的一种பைடு நூலகம்法，它提供了知识推理和语言的结构和过程。
例：id1:=id2+id3*10
经语法分析得知其是Pascal语言，表示成语法树为：
:=
/ \
id1 +
/ \
id2 *
/ \
id3 10
经语义分析得插入语义处理结点的树：
:=
/ \
id1 +
/ \
id2 *
/ \
id3 inttoreal
|
10
在高级程序设计语言翻译中，语义分析阶段的工作不与目标机器的体系结构密切相关，而目标代码生成阶段的工作与目标机器的体系结构密切相关。
int arr[2],b;
b = arr * 10;
源程序的结构是正确的.语义分析将审查类型并报告错误:不能在表达式中使用一个数组变量,赋值语句的右端和左端的类型不匹配.
又比如在语句sum:=first+count*10中，*的两个运算对象：count是实型，10是整型，则语义分析阶段进行类型审查之后，在语法分析所得到的分析树上增加一语义处理结点，表示整型变成实型的一目算符inttoreal.
语义分析的现状：编译器最实质性的工作；对源代码语义的第一次解释，引起了源程序的质的变化。
语义分析的地位:编译程序最实质性的工作；第一次对源程序的语义作出解释，引起源程序质的变化。
按照语法分析器识别的语法范畴进行语义检查和处理，产生相应的中间代码或目标代码.
介于源语言和目标代码之间的一种代码。
在社交网络中，节点之间通常存在信息交换。用于获取和理解可以在此社交网络中进行分析的文本信息的强大技术称为语义Web消息传输分析（语义分析）。作为人工智能和计算语言学的一种பைடு நூலகம்法，它提供了知识推理和语言的结构和过程。
例：id1:=id2+id3*10
经语法分析得知其是Pascal语言，表示成语法树为：
:=
/ \
id1 +
/ \
id2 *
/ \
id3 10
经语义分析得插入语义处理结点的树：
:=
/ \
id1 +
/ \
id2 *
/ \
id3 inttoreal
|
10
在高级程序设计语言翻译中，语义分析阶段的工作不与目标机器的体系结构密切相关，而目标代码生成阶段的工作与目标机器的体系结构密切相关。
词法分析、语法分析、语义分析
词法分析、语法分析、语义分析词法分析（Lexical analysis或Scanning）和词法分析程序（Lexical analyzer或Scanner） 词法分析阶段是编译过程的第⼀个阶段。
这个阶段的任务是从左到右⼀个字符⼀个字符地读⼊源程序，即对构成源程序的字符流进⾏扫描然后根据构词规则识别单词(也称单词符号或符号)。
词法分析程序实现这个任务。
词法分析程序可以使⽤lex等⼯具⾃动⽣成。
语法分析（Syntax analysis或Parsing）和语法分析程序（Parser） 语法分析是编译过程的⼀个逻辑阶段。
语法分析的任务是在词法分析的基础上将单词序列组合成各类语法短语，如“程序”，“语句”，“表达式”等等.语法分析程序判断源程序在结构上是否正确.源程序的结构由上下⽂⽆关⽂法描述.语义分析（Syntax analysis） 语义分析是编译过程的⼀个逻辑阶段. 语义分析的任务是对结构上正确的源程序进⾏上下⽂有关性质的审查, 进⾏类型审查.例如⼀个C程序⽚断: int arr[2],b; b = arr * 10; 源程序的结构是正确的. 语义分析将审查类型并报告错误:不能在表达式中使⽤⼀个数组变量,赋值语句的右端和左端的类型不匹配.Lex ⼀个词法分析程序的⾃动⽣成⼯具。
它输⼊描述构词规则的⼀系列正规式,然后构建有穷⾃动机和这个有穷⾃动机的⼀个驱动程序,进⽽⽣成⼀个词法分析程序.Yacc ⼀个语法分析程序的⾃动⽣成⼯具。
它接受语⾔的⽂法,构造⼀个LALR(1)分析程序.因为它采⽤语法制导翻译的思想,还可以接受⽤C语⾔描述的语义动作,从⽽构造⼀个编译程序. Yacc 是 Yet another compiler compiler的缩写.源语⾔（Source language）和源程序（Source program） 被编译程序翻译的程序称为源程序,书写该程序的语⾔称为源语⾔.⽬标语⾔（Object language or Target language）和⽬标程序（Object program or Target program） 编译程序翻译源程序⽽得到的结果程序称为⽬标程序, 书写该程序的语⾔称为⽬标语⾔.中间语⾔（中间表⽰）（Intermediate language(representation)） 在进⾏了语法分析和语义分析阶段的⼯作之后，有的编译程序将源程序变成⼀种内部表⽰形式，这种内部表⽰形式叫做中间语⾔或中间表⽰或中间代码。
第6章 语义分析(1)
层数为1 x: (1,0);
类型的内部表示
为什么需要类型的内部表示?
– 类型是标识符的重要属性; – 类型检查是语义分析的重要部分; – 类型的结构对类型检查很重要;
程序语言的类型
– 基本类型 Integer (int ) Real (float) Bool Char – 构造类型 数组(Array) 结构体(Structure、record) 联合类型(Union、变体记录) – 枚举类型 – 指针类型
联合类型的内部表示
Kind Body unionT y Body: 指向联合体中域定义链表 Size: 所有域的类型的size中最大值;
Body
FieldName FieldType Next
Size
typedef union{ int i; char name[10]; real x; } test;
基本类型的内部表示
Size intPtr Kind
intSize
boolSize realSize
intTy
boolTy realTy
boolPtr realPtr
charPtr
charSize
charTy
数组类型的内部表示
Size
Kind arrayTy
Low
Up
ElemTy
size = sizeof(ElemTy) (Up-Low+1) ElemTy: 指向数组成分类型的指针; array [2..9] of integer; (8, arrayTy, 2, 9, intPtr)
第六章 语义分析
6.1 语义分析概述
6.2 符号表
6.3 类型的语义分析 6.4 声明的语义分析 6.5 程序体的语义分析 么是符号表(Symbol Table)?
类型的内部表示
为什么需要类型的内部表示?
– 类型是标识符的重要属性; – 类型检查是语义分析的重要部分; – 类型的结构对类型检查很重要;
程序语言的类型
– 基本类型 Integer (int ) Real (float) Bool Char – 构造类型 数组(Array) 结构体(Structure、record) 联合类型(Union、变体记录) – 枚举类型 – 指针类型
联合类型的内部表示
Kind Body unionT y Body: 指向联合体中域定义链表 Size: 所有域的类型的size中最大值;
Body
FieldName FieldType Next
Size
typedef union{ int i; char name[10]; real x; } test;
基本类型的内部表示
Size intPtr Kind
intSize
boolSize realSize
intTy
boolTy realTy
boolPtr realPtr
charPtr
charSize
charTy
数组类型的内部表示
Size
Kind arrayTy
Low
Up
ElemTy
size = sizeof(ElemTy) (Up-Low+1) ElemTy: 指向数组成分类型的指针; array [2..9] of integer; (8, arrayTy, 2, 9, intPtr)
第六章 语义分析
6.1 语义分析概述
6.2 符号表
6.3 类型的语义分析 6.4 声明的语义分析 6.5 程序体的语义分析 么是符号表(Symbol Table)?
第4章 语义分析-编译原理及实践教程(第3版)-黄贤英-清华大学出版社
B0
B1 B2
char g_c1; char *g_ch2; int func1(int a, int b) {
int g_i1 = 5; for(;;){
char g_i1 = ‘b’; int *var1; printf(“Input numbers”); …… printf(“the result is %d”,*var1); } }
4.1语义分析概述
语义分析：在进行翻译之前，必须对这些语法上正确的语法 单位的内部逻辑含义是否正确进行检查。
语义分析的地位和作用
语法树 语法分析
语义分析
建立 符号表
静态语 义检查
语法树
语义错误
编译的后续阶段
符号表
语义分析的任务 对结构上正确的源程序进行上下文有关性质的审查，审查源 程序有无语义错误，为代码生成阶段收集类型信息。
B3 B4
变量表保存源程序中的所有变量定义。 如果语言没有作用域的限制，就可以将所有的变量记录在变量 表中，这种情况下，不允许定义同名变量。
入口 1 2 3 4
……
变量名 g_i1 var1 g_c1 g_ch2 ……
变量长度 变量类型 值 地址
4
int
4
int
4
char
5
char *
……
有作用域的限制的，将从最外层开始到当前作用域的编号组合 起来，其内部元素是每个作用域的编号，即：作用域路径
声明与定义语义检查
（1）变量未声明就使用、变量重定义； （2）函数未声明就定义和调用、函数重定义、函数声明与定
义不匹配、函数调用与声明不匹配、函数和变量重名等； （3）数组长度必须是正整数、数组名不能和变量名、函数名
- 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
- 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
- 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
语义分析程序的设计与实现
实验内容：
编写语义分析程序，实现对算术表达式的类型检查和求值。
要求所分析算术表达式由如下的文法产生。
E→E+T|E-T|T
T→T*F|T/F|F
F→id|(E)|num
实验要求：
用自底向上的语法制导翻译技术实现对表达式的分析和翻译。
(1)写出满足要求的语法制导定义或翻译方案。
(2)编写分析程序，实现对表达式的类型进行检查和求值，并输出：
①分析过程中所有产生式。
②识别出的表达式的类型。
③识别出的表达式的值。
(3)实验方法：利用YACC自动生成工具。
编译环境：YACC
翻译方案：
E ::= T{E'.i:=T.nptr}
E' {E.nptr:=E'.s}
E'::=+T{E'1.i:=mknode(‘+’,E'.i,T.nptr)} E'1 {E'.s:=E1.s}
E'::=-T{E'1.i:=mknode(‘-’,E'.i,T.nptr)} E'1 {E'.s:=E1.s}
E'::=ε{E'.s:= E'.i}
T ::= F{T'.i:=F.nptr} T' {T.nptr:=T'.s}
T'::=*F{T'1.i:=mknode(‘*’,T'.i,F.nptr)}
T'1 {T'.s:=T1.s}
T'::=/F{T'1.i:=mknode(‘/’,T'.i,F.nptr)}
T'1 {T'.s:=T1.s}
T'::=ε{T'.s:= T'.i}
F ::=(E){F.nptr:=E.nptr}
F ::= num{F.nptr:=mkleaf(num,num.val)}
YACC程序：
%{
#include<stdio.h>
#include<stdlib.h>
#include<ctype.h>
typedef struct x{int i;int c;} type; %union{
int num;
char* id;
type c;
}
%token <num> NUM
%token <id> ID
%type <c> expr,term,factor %%
line:expr’\n’
{
if($1.i>=0)
printf(“%d num\n”,$1,i);
else
printf(“id\n”);
}
;
expr:expr’+’term
{
if($1.c==0&&($3.c==0))
{
$$.i=$1.i+$3.i;
$$.c=0;
printf(“E->E+T E.type:num\n”);
}
else
{
$$.c=1;
$$.i=-1;
printf(“E->E+T E.type:id\n”);
}
}
|expr’-’term
{
if($1.c==0&&($3.c==0))
{
$$.i=$1.i-$3.i;
$$.c=0;
printf(“E->E-T E.type:num\n”);
}
else
{
$$.c=1;
$$.i=-1;
printf(“E->E-T E.type:id\n”);
}
}
|term
{
$$.i=$1.i;
$$.c=$1.c;
if($$.c==0)
printf(“E->T E.type:num\n”);
else
printf(“E->T E.type:id\n”);
}
;
term:term’*’factor
{
if($1.c==0&&($3.c==0))
{
$$.i=$1.i*$3.i;
$$.c=0;
printf(“T->T*F T.type:num\n”);
}
else
{
$$.c=1;
$$.i=-1;
printf(“T->T*F T.type:id\n”);
}
}
|term’/’factor
{
if($1.c==0&&($3.c==0))
{
$$.i=$1.i/$3.i;
$$.c=0;
printf(“T->T/F T.type:num\n”);
}
else
{
$$.c=1;
$$.i=-1;
printf(“T->T/F T.type:id\n”);
}
}
|factor
{
$$.c=$1.c;
$$.i=$1.i;
if($$.c==0)
printf(“T->F T.type:num\n”);
else
printf(“T->F T.type:id\n”);
}
;
factor:ID
{
$$.c=1;
$$.i=-1;
}
|’(’expr’)’
{
$$.c=$2.c;
$$.i=$2.i;
if($$.c==0)
printf(“F->(E) F.type:num\n”);
else
printf(“F->(E) F.type:id\n”);
}
|NUM
{
$$.i=$1;
$$.c==0;
}
;
%%
main()
{
return yyparse(); }
int yylex(void) {
static int done=0;
int c;
if(done) return 0;
while((c=getchar())==’’);
if(isdigit(c))
{
ungetc(c,stdin);
yylval.num=c-‘0’;
scanf(“%d”,&yylval);
printf(“\nnum\n”);
printf(“F->num F.type:num\n”);
return(NUM);
}
else if(c<=’z’&&c>=’a’||c<=’Z’&&c>=’A’) {
yylval.id=ID;
printf(“\nid\n”);
printf(“F->id F.type:id\n”);
return{ID};
}
else if(c==’\n’) done=1;
return c;
}
void yyerror(char* s)
{
printf(“%s\n”,s);
}。