精华内容
下载资源
问答
  • 编译技术语义分析
    千次阅读
    2020-10-28 13:55:09

    作用域(Scope)

    作用域是指计算机语言中变量、函数、类等起作用的范围

    • 变量的作用域有大有小,外部变量在函数内可以访问,而函数中的本地变量,只有本地才可以访问。
    • 变量的作用域,从声明以后开始。
    • 在函数里,我们可以声明跟外部变量相同名称的变量,这个时候就覆盖了外部变量。
    • 变量的使用范围由作用域决定,作用域由词法规则决定,词法分析生成作用域链,之后查找变量就沿着这条作用域链查找,与函数调用栈就没有关系了。一般函数的生存期就是出栈后就结束了,如果是引用对象会在本次GC中回收,如果产生了闭包,那就要等到引用闭包的变量销毁,生存期才结束。

    生存期(Extent)

    生存期是变量可以访问的时间段,也就是从分配内存给它,到收回它的内存之间的时间。

    • Java 对象所采用的内存超出了申请内存时所在的作用域,所以也就没有办法自动收回。所以 Java 采用的是自动内存管理机制,也就是垃圾回收技术。

    程序运行过程中栈的变化
    在这里插入图片描述

    • 代码执行时进入和退出一个个作用域的过程,可以用栈来实现。每进入一个作用域,就往栈里压入一个数据结构,这个数据结构叫做栈桢(Stack Frame)。栈桢能够保存当前作用域的所有本地变量的值,当退出这个作用域的时候,这个栈桢就被弹出,里面的变量也就失效了。
    • 变量的使用范围由作用域决定,作用域由词法规则决定,词法分析生成作用域链,之后查找变量就沿着这条作用域链查找,与函数调用栈就没有关系了。一般函数的生存期就是出栈后就结束了,如果是引用对象会在本次GC中回收,如果产生了闭包,那就要等到引用闭包的变量销毁,生存期才结束。

    根据类型检查是在编译期还是在运行期进行的,我们可以把计算机语言分为两类:
    静态类型语言(全部或者几乎全部的类型检查是在编译期进行的)。
    动态类型语言(类型的检查是在运行期进行的)。

    类型系统

    高级语言为什么要增加类型这种机制呢?

    类型是针对一组数值,以及在这组数值之上的一组操作。比如,对于数字类型,你可以对它进行加减乘除算术运算,对于字符串就不行。

    • 类型是高级语言赋予的一种语义,有了类型这种机制,就相当于定了规矩,可以检查施加在数据上的操作是否合法。因此类型系统最大的好处,就是可以通过类型检查降低计算出错的概率。所以,现代计算机语言都会精心设计一个类型系统,而不是像汇编语言那样完全不区分类型。

    根据类型检查是在编译期还是在运行期进行的,我们可以把计算机语言分为两类:

    • 静态类型语言(全部或者几乎全部的类型检查是在编译期进行的)。
    • 动态类型语言(类型的检查是在运行期进行的)。

    静态类型和动态类型说的是什么时候检查的问题,强类型和弱类型说的是就算检查,也检查不出来,或者没法检查的问题。

    面向对象的语义特征

    从类型角度

    • 类型处理是语义分析时的重要工作。现代计算机语言可以用自定义的类来声明变量,这是一个巨大的进步。因为早期的计算机语言只支持一些基础的数据类型,比如各种长短不一的整型和浮点型,像字符串这种我们编程时离不开的类型,往往是在基础数据类型上封装和抽象出来的。所以,我们要扩展语言的类型机制,让程序员可以创建自己的类型。

    从作用域角度

    • 首先是类的可见性。作为一种类型,它通常在整个程序的范围内都是可见的,可以用它声明变量。当然,一些像 Java 的语言,也能限制某些类型的使用范围,比如只能在某个命名空间内,或者在某个类内部。
    • 对象的成员的作用域是怎样的呢?我们知道,对象的属性(“属性”这里指的是类的成员变量)可以在整个对象内部访问,无论在哪个位置声明。也就是说,对象属性的作用域是整个对象的内部,方法也是一样。这跟函数和块中的本地变量不一样,它们对声明顺序有要求,像 C 和 Java 这样的语言,在使用变量之前必须声明它。

    从生存期的角度

    • 对象的成员变量的生存期,一般跟对象的生存期是一样的。在创建对象的时候,就对所有成员变量做初始化,在销毁对象的时候,所有成员变量也随着一起销毁。当然,如果某个成员引用了从堆中申请的内存,这些内存需要手动释放,或者由垃圾收集机制释放。
    • 但还有一些成员,不是与对象绑定的,而是与类型绑定的,比如 Java 中的静态成员。静态成员跟普通成员的区别,就是作用域和生存期不同,它的作用域是类型的所有对象实例,被所有实例共享。生存期是在任何一个对象实例创建之前就存在,在最后一个对象销毁之前不会消失。

    你知道的越多,你不知道的越多。
    有道无术,术尚可求,有术无道,止于术。
    如有其它问题,欢迎大家留言,我们一起讨论,一起学习,一起进步

    更多相关内容
  • 编译原理-语义分析

    2014-05-11 16:48:17
    实验报告内容要求:要给出所分析简单语言语法结构的词法说明、上下文无关文法描述,单词的种别编码方案,词法分析程序的主要算法思想,以及所采用的语法语义分析方法的算法思想的详细描述,测试结果与分析,实验总结...
  • 编译原理及实现技术:17.语义分析_语义表示基础.ppt
  • 目的:充分理解语义分析的方法及相关语义计算的执行时机。 要求: 1.以S属性的语法制导定义为基础,将下表的语义规则嵌套在语法分析的过程中,即实现语法制导的翻译过程。 产 生 式 语 义 规 则 L E n print ...
  • 编译原理 语义分析

    千次阅读 2020-01-08 09:20:19
    重点:语义分析的两个作用 <3> 语义分析的方法 2. 中间代码 重点:要求中间代码具有如下特性,以便于编译器的开发移植和代码的优化: 3.后缀式 定义 算法实现 4.后缀式的计算 5.三地址码 6.四元式主要由四部分组成:...

    1. 语义与语法的区别

    在这里插入图片描述
    <1> 语法与语义的关系
    语法是指语言的结构、即语言的“样子”;语义是指附着于语言结构上的实际含意 ,即语言的“意义”。
    对于语法和语义:
    语义不能离开语法独立存在;
    语义远比语法复杂;
    同一语言结构可包含多种含意,不同语言结构可表示相同含意;
    语法与语义之间没有明确的界线。

    重点:语义分析的两个作用

    1.检查是否结构正确的句子所表示的意思也合法;
    2.执行规定的语义动作,如:
    表达式求值
    符号表填写
    中间代码生成等

    <3> 语义分析的方法

    语法制导翻译

    2. 中间代码

    在这里插入图片描述

    重点:要求中间代码具有如下特性,以便于编译器的开发移植和代码的优化:

    便于语法制导翻译;
    既与机器指令的结构相近,又与具体机器无关。

    3.后缀式

    在这里插入图片描述

    定义

    一个表达式E的后缀形式可以如下定义:
    (1)如果E是一个变量或常量,则E的后缀式是E本身。
    (2)如果E是E1 op E2形式的表达式,这里op是任何二元操作符,则E的后缀式为E1’E2’ op,这里E1’和E2’分别为E1和E2的后缀式。
    (3)如果E是(E1)形式的表达式,则E1的后缀式就是E的后缀式。
    如:我们平时写a+b,这是中缀表达式,写成后缀表达式就是:ab+
    (a+b)c-(a+b)/e的后缀表达式为:
    (a+b)c-(a+b)/e
    →((a+b)c)((a+b)/e)-
    →((a+b)c
    )((a+b)e/)-
    →(ab+c
    )(ab+e/)-
    →ab+c
    ab+e/-

    算法实现

    将一个普通的中序表达式转换为逆波兰表达式的一般算法是:
    首先需要分配2个栈,一个作为临时存储运算符的栈S1(含一个结束符号),一个作为输入逆波兰式的栈S2(空栈),S1栈可先放入优先级最低的运算符#,注意,中缀式应以此最低优先级的运算符结束。可指定其他字符,不一定非#不可。从中缀式的左端开始取字符,逐序进行如下步骤:
    (1)若取出的字符是操作数,则分析出完整的运算数,该操作数直接送入S2栈
    (2)若取出的字符是运算符,则将该运算符与S1栈栈顶元素比较,如果该运算符优先级(不包括括号运算符)大于S1栈栈顶运算符优先级,则将该运算符进S1栈,否则,将S1栈的栈顶运算符弹出,送入S2栈中,直至S1栈栈顶运算符低于(不包括等于)该运算符优先级,最后将该运算符送入S1栈。
    (3)若取出的字符是“(”,则直接送入S1栈顶。
    (4)若取出的字符是“)”,则将距离S1栈栈顶最近的“(”之间的运算符,逐个出栈,依次送入S2栈,此时抛弃“(”。
    (5)重复上面的1~4步,直至处理完所有的输入字符
    (6)若取出的字符是“#”,则将S1栈内所有运算符(不包括“#”),逐个出栈,依次送入S2栈。
    完成以上步骤,S2栈便为逆波兰式输出结果。不过S2应做一下逆序处理。便可以按照逆波兰式的计算方法计算了!

    4.后缀式的计算

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

    5.三地址码

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

    6.四元式主要由四部分组成:

    (OP,arg1,arg2,result)
    其中,OP是运算符,argl,arg2分别是第一和第二个运算对象,result是编译程序为存放中间运算结果而引进的变量,常称为临时变量。当OP是一目运算时,常常将运算对象定义为arg1。
    在这里插入图片描述
    四元式出现的顺序和语法成份的计值顺序相一致。
    四元式之间的联系是通过临时变量实现的,这样易于调整和变动四元式。
    便于优化处理。

    三地址代码

    三地址代码是四元式的另一种表示形式

    在这里插入图片描述

    例题有文法 G 和 G 的语法制导翻译如下:

    E → E1*T { E.place=newtemp;

    emit(*,E1.place,T.place,E.place; }

    | T { E.place=T.place; }

    T → T1+F { T.place=newtemp;

    emit(+,T1.place,F.place,T.place; }

    | F { T.place=F.place; }

    F → (E) { F.place=E.place; }

    | id { F.place=id.name; }

    (a) 求句型 (T+F)*id 的短语、直接短语以及句柄;

    (b) 根据语法制导翻译写出句子 ab+cd 的中间代码;

    © (若 a=3 , b=5 , c=7 , d=8 ,请给出中间代码计算结果;

    (d) 将文法 G 简化为: E → E*T|T , T → T+F|F , F → id 。给出它的识别活前缀的 DFA 。
    在这里插入图片描述
    在这里插入图片描述

    7.符号表

    在这里插入图片描述

    8. 数组元素的引用

    (1)数组元素的地址计算

    注意是行主存储还是列主存储
    在这里插入图片描述
    (2)☆数组元素引用的语法制导翻译(考试热点之一)

    9. 布尔表达式

    在这里插入图片描述
    布尔表达式的计算有两种方法:数值表示的直接计算和逻辑表示的短路计算
    在这里插入图片描述
    在这里插入图片描述

    ☆ 布尔表达式短路计算的翻译:短路计算的控制流,真出口与假出口,真出口链与假出口链,拉链回填技术(P207 例4.41)(考试热点之一)

    10. 控制语句

    控制语句的分类:①无条件转移、②条件转移、③循环语句、④分支语句

    无条件转移(goto)\条件转移(if、while)
    条件转移的语法制导翻译:P213 例4.42

    11.过程的定义与声明

    在这里插入图片描述

    左值和右值

    在这里插入图片描述
    在这里插入图片描述
    左值式地址,右值是值
    根据参数传递的左右值不同
    调用可分为:
    1.值调用 (传递右值)
    2.引用调用 (传递左值)

    拉链回填

    在这里插入图片描述

    展开全文
  • 十、设计SAMPLE语言的语法、语义分析器,输出四元式的中间结果。 检查要求: a)启动程序后,先输出作者姓名、班级、学号(可用汉语、英语或拼音)。 b)请求输入测试程序名,键入程序名后自动开始编译。 c)输出四元式...
  • 编译技术:第05章 语义分析.ppt
  • 北邮计算机科学与技术编译原理语义分析[收集].pdf
  • 编译原理 语义分析

    千次阅读 2021-05-23 20:40:41
    实验五 语义分析器一、实验目的二、实验任务三、实验内容(一)学习经典的语义分析器1.选择一个编译器2.阅读语义分析源程序并理解3.理解符号表的定义4.测试语义分析器(二)实现一门语言的语义分析器四、系统设计(C...

    链接: 代码工程.

    一、实验目的

    1.学习已有编译器的经典语义分析源程序。
    2.通过本次实验,加深对语义分析的理解,学会编制语义分析器。

    二、实验任务

    1.阅读已有编译器的经典语义分析源程序,并测试语义分析器的输出。
    2.用C或JAVA语言编写一门语言的语义分析器。

    三、实验内容

    (一)学习经典的语义分析器

    1.选择一个编译器

    选择TINY编译器来进行语义分析器部分的学习。

    2.阅读语义分析源程序并理解

    对相关函数与重要变量的作用与功能进行稍微详细的描述。
    2.1.相关文件
    如图所示,语义分析部分相对于前面已经学习过的语法分析器多了四个文件,分别是analyze.c、analyze.h、symtab.c、symtab.h;
    symtab.h、symtab.c文件是符号表的相关代码,作用是实现了一个分离的链式杂凑表结构的符号表;
    analyze.h、analyze.c文件是符号表生成以及语义检查的相关代码,具体作用就是遍历语法分析生成的语法树将各个变量插入到符号表中,以及对抽象语法树进行类型检查;
    在这里插入图片描述

    接下来根据四个文件中的函数与变量进行详细的分析。

    2.2.重要变量/结构
    ①LineListRec
    在这里插入图片描述
    动态分配链表,类型名为LineList,存储记录在杂凑表中每个标识符记录的相关行号(一个变量仅有一个定义但是会在多行出现)。

    ②BucketListRec
    在这里插入图片描述
    “桶”列表记录标识符信息,包括名字、在代码中出现的行号链表(用上述的LineList记录)、第一次定义的位置、下一个桶的指针,类型名为BucketList。

    ③hashTable
    哈希表,也就是我们要求的符号表,表结构就是上述的BucketList;
    在这里插入图片描述

    2.3.相关函数
    ①hash
    在这里插入图片描述
    通过标识符的名字字符串来计算将该标识符放入hashTable中的哪一个桶链表中,加上hash函数可以将标识符平均的分配到各个桶链表中,加快后面运行过程中的查询速度。
    ②st_insert
    在这里插入图片描述
    该函数的作用很直观,将存储位置位于loc、行号为lineno、名字为name的标识符加入到哈希表中,如果已经存在则将行号加入到相应的LineList中,否则需要新开辟一个桶。

    ③st_lookup
    在这里插入图片描述
    该函数就是为了查找标识符的位置,也就是桶结构中的memloc,未找到则返回-1,用于语义分析中的类型检查。

    ④insertNode
    在这里插入图片描述
    该函数非常重要,是建立符号表的主要函数它根据抽象语法树的结点类型调用st_insert来将标识符插入到符号表中。

    ⑤buildSymtab
    在这里插入图片描述
    顾名思义,该函数就是建立符号表的入口函数,它会通过前序遍历的方式遍历所有树结点并且调用insertNode将所有标识符加入到符号表中。
    ⑥checkNode
    在这里插入图片描述
    该函数是类型检查的主要函数,也也是根据标识符号的类型检查是否有错误出现,并将标识符的计算结果的类型层层上传。
    ⑦typeCheck
    在这里插入图片描述
    与bulidSymtab相似的实现方式,是类型检查的入口函数。

    ⑧traverse
    在这里插入图片描述
    该函数较为重要,因此详细的进行解释:
    这里的参数是两个函数指针,分别进行前序遍历的处理部分以及后序遍历的处理部分;也就是说我们的前序遍历和后序遍历都可以通过调用该函数实现,只是在调用时,需要考虑前序遍历和后序遍历的处理函数,比如对于前序遍历的处理函数指针preProc,为了通过前序遍历实现符号表的构建,我们需要将上述的insertNode作为函数指针传递进去;

    3.理解符号表的定义

    理解符号表(栏目设置)与基于抽象语法树的类型检查/推论的实现方法(树遍历)。
    3.1.树遍历的实现方法
    为强调标准的树遍历技术,实现buildSymtab和typeCheck使用了相同的通用遍历函数 traverse(上面已有他的介绍),它接受两个作为参数的过程(和语法树),一个完成每个节点的前序处理,一个进行后序处理;
    给定这个过程,为得到一次前序遍历,当传递一个“什么都不做”的过程作为 p r e p r o c
    时,需要说明一个过程提供前序处理并把它作为 p r e p r o c传递到t r a v e r s e。对于T I N Y符号表的情况,前序处理器就是 i n s e r t N o d e,因为它完成插入到符号表的操作。“什么都不做”的过程称作n u l l P r o c,它用一个空的过程体说明 。然后建立符号表的前序遍历由b u i l d S y m t a b过程内的单个调用:**traverse (syntaxTree, insertNode, nullProc);**完成。
    类似地,t y p e C h e c k要求的后序遍历由单个调用traverse (syntaxTree, nullProc, checkNode);完成。
    事实上,有了这样的标准的树遍历方法traverse之后我们是可以只使用一个traverse (syntaxTree, insertNode, checkNode) 就可以实现符号表的建立以及类型检查了,这得益于TINY不需要检查变量的定义,否则需要首先建立符号表。

    3.2.符号表的定义
    从上述的重要结构声明其实很容易就可以得到符号表的详细结构,我将它用图画出来表示为:
    在这里插入图片描述

    4.测试语义分析器

    对TINY语言要求输出测试程序的符号表与测试结果。
    4.1.修改主函数,使得TINY编译器进行语义分析;
    在这里插入图片描述
    4.2.测试用例一:sample.tny。
    样例与测试结果:
    在这里插入图片描述
    此样例是多次使用的指导书上的样例,语法分析输出结果正确(共x、fact两个变量,x在5、6、9、10、10、11行出现、fact在7、9、9、12行出现)。
    4.3.测试用例二
    用TINY语言自编一个程序计算任意两个正整数的最大公约数与最大公倍数。
    自己编写的最大公约数与最大公倍数的程序:
    因为没有%求余符号,只能通过下面的乘法与除法结合的方式实现求余。
    此外,不知道是不是因为提供的TINY的bug的原因,end、until的前面的语句不能有分号,且程序最后一行也不能有分号!
    在这里插入图片描述
    在这里插入图片描述

    测试结果:在这里插入图片描述

    (二)实现一门语言的语义分析器

    1.语言确定:
    C-语言,其定义在《编译原理及实践》附录A中。
    2.C-语言的语义分析器具体设计见下面的系统设计
    3.具体代码见源程序。

    四、系统设计(C-语言的语义分析器)

    1.完成C-语言的符号表的定义设计。规划类型检查/推论的实现方法。

    1.1.文件结构

    在这里插入图片描述
    前面的语法分析实验,扩展语义分析部分的功能,将符号表的相关结构定义全部定义在了Globals.h中,语义分析部分功能的实现都写在了analyse.cpp中,而analyse.h头文件中仅含有语义分析函数的声明void Semantic_parse(TreeNode* syntaxTree);
    从文件可以看出,我是通过unbuntu实现的语义分析器,并且通过编写makefile文件来进行工程的编译链接。

    1.2.重要数据结构(符号表的设计)

    这里将主要的符号表相关数据都定义在Globals.h中,下面逐一进行分析:
    ①函数存储结构
    在这里插入图片描述

    首先是函数在符号表中的数据结构,即存储定义函数的参数个数、各个参数的类型(通过vector实现),函数返回的类型、函数的栈大小(用于后面实验的代码生成)

    ②变量存储结构
    在这里插入图片描述
    此处表示变量在符号表中的存储结构,其中包括在源码中的行数(仅存储定义的位置)、在内存中分配的位置(如果表示的是函数参数,那么这里表示参数的位置,即第几个参数)、作用域(0表示全局域、1表示函数参数、2表示函数体、接下来则是根据while或者if的{}来决定作用域、每多加深嵌套一层则scope加1)、变量类型、大小。
    作用域的划分如上右图!

    ③同名变量在不同作用域中的定义实现
    在这里插入图片描述
    这里使用一个vector来存储同函数中同名变量(作用域不同),比如在while循环中定 义了与参数同名的变量。或者如上右图中在while循环中定义了一个同名变量a,在我 的代码实现中,就是存储在了vectorLines中;

    1.3.符号表的组成

    在这里插入图片描述
    这里是最重要的符号表实现部分,上面的三个结构体只是符号表的相关存储结构;
    可以很明显的看到,我是使用了map的数据结构来进行符号表的相关映射的;
    其中共有两个符号表,分别是函数的符号表以及各个函数中变量的符号表,这里的函数符号表的string代表函数的名字,即通过函数名字来进行映射;而变量的符号表比较复杂,首先通过函数名映射到函数中变量的符号表,接着再通过变量名映射到变量的相关信息结构(即第一个string是函数名称、第二个string是指变量名称)。
    这里没有专门定义全局变量的符号表,因此直接将全局也看成一个函数,即”GLOBALS”表示全局变量的“函数”名,我们访问全局变量,可以通过以下方式:sys_table[“GLOBALS”][“变量名”]. line实现。

    1.4.符号表图示

    无法清楚描述符号表的组成,因此画出一个图示(通过wps流程图绘制):
    在这里插入图片描述
    通过这张图示就可以比较清晰的理解我的符号表的组成了。

    1.5.简单规划设计

    在TINY中直接使用前序遍历进行符号表的构建、后序遍历实现类型的检查,但是在C-中因为加入了函数、while等等可以增加新的作用域的语法,因此这里在进行符号表的构建时需要加上scope的栈式结构,即进入一个作用域时scope++,入栈,退出该作用域时直接弹出栈顶元素。
    语义分析主要是要生成符号表,为各个变量分配好栈中地址,计算函数栈的大小。
    使用变量时要找出正确作用域中声明的变量,因为可能存在同一名字的变量在不同的作用域被声明,这是重点也是难点。为此,可以使用一个栈来保存当前可以访问的所有作用域,每进入一个花括号,作用域加一,同时将该作用域压栈,退出花括号时,栈顶作用域出栈。全局域的作用域为0,函数的作用域从1开始,函数参数中的作用域为1,以此递增。退出函数时,作用域归0。这样,栈顶作用域为当前作用域,栈中的所有作用域为当前可以访问的作用域,在这些作用域中寻找最近声明的变量作为使用的变量。
    作用域栈的表示如下:
    在这里插入图片描述

    栈的实现方式:
    在这里插入图片描述
    通过vector来实现,入栈则push_back,出栈则是pop_back,查看栈顶元素则是back();
    也因此在实现前序/后序遍历的过程中,需要加入scope的入栈出栈过程,确保正确建立符号表以及类型检查:
    在这里插入图片描述
    在进行前序处理preProc之前,首先根据当前节点的类型进行判断,如果出现了COM_SK,即{号,那么代表进入了一个新的作用域,此时需要入栈;
    在这里插入图片描述
    在进行后序处理PostProc之后,需要根据结点的类型进行出栈的操作;

    2.仿照前面学习的语义分析器,编写选定语言的语义分析器。

    通过1.5简单规划中的分析,代码实现部分已经非常明确了,下面对于各个函数,进行简单的分析;

    2.1.主函数main

    首先通过语法分析函数生成抽象语法树tree,接着将tree作为参数调用语义分析函数,最关键的语句如下:

    TreeNode* tree;
    tree=Syntax_parse();
    Semantic_parse(tree);
    

    2.2.Semantic_parse语义分析入口

    首先调用函数符号表的初始化函数,接着就进行符号表建立和类型检查的buildSymtab()、typeCheck()函数,关键语句如下:

    fun_table_init();
    buildSymtab(syntaxTree);
    typeCheck(syntaxTree);
    

    2.3.fun_table_init()

    这个函数就是上面调用的函数符号表初始化函数,它所做的就是简单的将C-语言的输入输出函数input、output加入到函数符号表中。
    这里如果不将output、input加入到函数符号表的话,将会产生很明显的问题,即无法使用input、output(未定义)。
    因为无论是函数符号表还是函数对应的变量符号表,都是通过map来进行名字与表结构的映射的,因此这里加入的方法很简单;
    ①对input、output的函数表结构进行赋值
    前者参数个数为0,后者为1、返回类型前者为int、后者为void,以input为例:

    fun_table["input"].p_num=0;
    fun_table["input"].return_type=Integer;
    fun_table["input"].p_type.clear();		//简单的映射
    

    ②初始化Globals(将全局信息也作为一个函数看待)对应的变量表(函数是Globals中的变量看待)
    作用域为0、input设置类型为Integer、output设置为Void、栈内存位置设置为-1(因为并不需要占用栈)、行号设置为0(并没有明确的定义input、output,将其看作是库函数),以input为例:

    LineList l;
    	l.scope=0;	l.ty=Integer; 	l.sizes=0;		l.linepoc=0;	l.loc=-1;
    	sys_table["GLOBALS"]["input"].lines.push_back(l);
    

    通过映射将Globals全局“函数”中的input标识符的信息l加入到变量表;

    2.4.buildSymtab、typeCheck

    调用这两个函数实现符号表的构建、类型的检查,无论是哪一个都是通过调用遍历语法树的traverse函数实现的(与TINY语音一样),这里的调用方法也与TINY一致:

    traverse(syntaxTree,insertNode,nullProc);		//符号表的构建
    traverse(syntaxTree,nullProc,checkNode);		//类型的检查
    

    traverse函数与TINY不同的点在上面进行简单分析的时候已经确定了,需要进行作用域栈的维护,入{则入栈、出}则出栈;
    但是在调用之前需要做好准备工作,主要就是作用域栈的初始化,将表示全局的scope=0入栈:

    scope=0;
    scopes.clear();
    scopes.push_back(scope);
    

    2.5.insertNode

    traverse遍历函数通过传入函数指针的方式将inserNode函数作为遍历过程中的前序遍历的处理函数,即向符号表中插入结点;
    插入结点到符号表的操作比较简单,根据结点的类型(主要是定义的)与符号表的组成进行插入即可,此外插入函数还需要判断当前使用的ID是否是定义过的(符号表中是否已经存在),这个过程在前序遍历中实现较为简单;
    因为含有两个表,函数符号表以及对应的变量符号表,因此对不同的定义节点需要插入到不同的表(函数定义部分对应插入函数符号表、变量定义部分插入变量符号表);

    以变量声明结点为例进行分析:
    在这里插入图片描述
    首先,如果当前作用域为0,那么需要手动将当前函数名替换为GLOBALS(因为这是我们假设的函数),将loc赋值为gloloc,gloloc是存储全局内存使用情况的(描述可能不清晰,简单来讲如果此前已经定义过一个int变量了,它需要4个内存位置,因此此时再为变量分配内存的话就需要从4开始)。
    接着获得当前加入的变量的名字;
    在这里插入图片描述
    这一部分是检查是否出现重定义,具体做法是:
    ①判断同名变量表是否为空,非空得到该Var_sym;
    ②在Var_sym中遍历所有的该变量名的定义,查看是否有相同作用域的定义
    ③有的话那就是重定义、没有则进入下面的插入操作;
    注意:重定义的检查只能出现在插入结点过程中(即前序遍历),因为作用域栈的关系,只能插入前检查。

    在这里插入图片描述
    前面已经完成了相同作用域的重定义检查,如果未冲突,那么进行以上插入操作;
    具体来说就是讲变量的相关信息赋值到LinList结构变量中,然后将该LineList加入到该函数中该变量名对应的Var_sym中;
    ①对LineList进行赋值,包括所处的是scope、loc、sizes、ty、linepoc
    ②如果是全局变量,那么在将loc修改后应该保存到gloloc中备用;
    ③通过映射的方式将LineList存入sys_table(即最后一个语句)。

    变量的声明部分就结束了,此外还有函数声明、变量使用、return、CALLK等结点的相关处理;这里需要对变量的使用IDK结点进行检查,即是否已经定义过,若没有则报错、对RETURN的返回值进行检查、对函数调用CALLK结点检查参数个数是否正确等;
    以上检查也只能通过前序遍历进行(前序遍历过程中维护的作用域栈的原因),具体实现见源码;

    2.6.checkNode

    traverse遍历函数通过传入函数指针的方式将checkNode函数作为遍历过程中的后序遍历的处理函数,即类型检查;
    类型的检查函数与TINY语言的检查函数checkNode类似,但是需要扩展很多新的结点类型,大致上检查返回、赋值、运算等等类型即可。

    对于扩展的CALLK结点的类型检查分析如下:
    在这里插入图片描述
    首先获得该节点的函数名字,然后通过名字从函数符号表中得到该函数的返回类型;
    再得到表示参数的结点,即child[1];
    在这里插入图片描述
    如果参数不为空,那么我们需要进行参数类型的判断,这里先得到所有实参的类型temp->type,存入vector tv1当中,对参数的遍历使用了while循环的方式;
    在这里插入图片描述
    形参的参数类型保存在函数符号表的p_type中,这也是一个vector结构,接下来将实参的类型与其比较,不同则说明出现问题(还可以检查参数个数是否正确);

    至此CALLK的检查就结束了,其余的还有计算方面的检查(两个运算数类型是否相同)、赋值语句的检查、数组下标的检查等等,具体见源码;

    3.准备2~3个测试用例,测试并解释程序的运行结果。

    3.1.test.cm

    这里的测试样例使用C-指导书中的样例(即最大公约数);
    在这里插入图片描述
    输出如下:
    在这里插入图片描述
    scope表示作用域、size表示大小、location表示栈空间、linepoc表示定义的位置、type表示类型;
    上面也提到过将全局看成一个函数、全局中的函数定义并不占空间、参数列表中的location表示第几个参数;下面几行为各个函数需要的栈空间、这里只有main函数的x、y定义需要占用栈空间、每个大小都是4,因此总的大小需要是2;
    因此具体来看输出正确;

    3.2.test1.cm

    在这里插入图片描述
    为了详细的展示作用域以及var_sym的作用,用该例子进行分析;
    这里在全局(scope=0)定义了x、y,接下来在main函数中(scope=2,scope=1表示参数)定义了x、y,然后在while循环中(scope=3)再次定义x、y,接着在while中嵌套while(scope=4),并且定义x、y;
    我们查看输出结果:
    在这里插入图片描述
    可以看出在main函数中有三对x、y的定义,它们位于不同的作用域因此并不会报错,并且在栈中的位置是分配好的,main函数的栈大小共24(6个int变量);
    对于函数main的x这一个名字的Var_sym就用vector存储了所有的三个不同作用域中x的定义。

    3.3.test2.tm

    下面是一些错误样例:
    ① 类型错误
    在这里插入图片描述
    output的返回类型是void,这里用于赋值会报错(符号表可以正确建立,但类型检查会报错)
    结果如下:
    在这里插入图片描述
    在第5行报错,这里因为不支持中文的原因出现乱码。

    ② 未定义
    在这里插入图片描述
    未定义直接使用,会报错;
    结果如下:
    在这里插入图片描述
    ③ 重复定义
    在这里插入图片描述
    重复定义错误,同样报错;
    报错如下:
    在这里插入图片描述

    五、实验总结

    实验到此就结束了,这次实验非常的有难度,但也带来了很大的收获。
    从学习TINY的符号表设计、语义分析的实现,到设计自己的符号表结构、语义的分析部分,每一步都学习到了很多新东西,尤其是当前作用域栈的保存部分是参考了非常多的源码后逐渐实现的。因为C-比TINY复杂的多,它的作用域分析算是其中的难点与重点部分了,因此刚开始是想到了课堂上讲解的方法,把符号表整个入栈,但是后面仔细思考发现我们需要保留一整个符号表,但是入栈出栈的操作势必损失一定的符号表(用完就删了),对符号表的保存比较麻烦,这里借鉴C-语法分析的资料后参考实现了这种作用域栈与符号表分离的方式。
    这次实验最大的体会就是,阅读代码的能力也很重要!!一开始没有明确的思路,于是上github搜集了很多资料,也看过老师给的资料。查阅了现有的一些C-编译器的源码。与此同时我也发现了,书上学的和实际用的并没有什么很大的关联,有的只是思路,等到真正实践的时候还是要自己对理论进行适当的修改。
    遗憾的是这次代码实现做的比较粗糙,尤其是类型检查非常的宽松,只能说勉强实现了一些功能,很多情况并没有检查到,但是也让我们认识了编译器的符号表以及类型检查的方法。

    展开全文
  • 文章目录1 实验目的和内容1.1 实验目的1.2 实验内容1.3 实验要求2 设计思想2.1 语义规则2.2 递归下降翻译器2.3 递归下降子程序伪代码3 算法流程4 源程序5 调试数据5.1 测试...(2)掌握目前普遍采用的语义分析方法─

    1 实验目的和内容

    1.1 实验目的

    (1)通过上机实习,加深对语法制导翻译原理的理解,掌握将语法分析 所识别的语法范畴变换为某种中间代码的语义翻译方法。

    (2)掌握目前普遍采用的语义分析方法──语法制导翻译技术。

    (3)给出 PL/0 文法规范,要求在语法分析程序中添加语义处理,对于语法正确的表达式,输出其中间代码;对于语法正确的算术表达式,输出其计算值。

    1.2 实验内容

    已给 PL/0 语言文法,在实验二或实验三的表达式语法分析程序里,添加语义处理部分,输出表达式的中间代码,用四元式序列表示。

    1.3 实验要求

    (1)语义分析对象重点考虑经过语法分析后已是正确的语法范畴,本实 验重点是语义子程序。

    (2)在实验二或实验三“语法分析器”的里面添加 PL/0 语言“表达式”部分的语义处理,输出表达式的中间代码,计算表达式的语义值。

    (3)中间代码用四元式序列表示。

    2 设计思想

    2.1 语义规则

    属性计算的过程即是语义处理的过程对于文法的每一个产生式配备一组属性的计算规则,则称为语义规则。

    (1)终结符只有综合属性,它由词法分析器提供。

    (2)非终结符既可以有综合属性也可以有继承属性,文法开始符号的所有继承属性作为属性计算前的初始值。

    (3)产生式右边符号的继承属性和产生式左边符号的综合属性都必须提供一个计算规则。

    (4)产生式左边符号的继承属性和产生式右边符号的综合属性由其它产生式的属性规则计算。

    2.2 递归下降翻译器

    递归下降分析法的原理是利用函数之间的递归调用来模拟语法树自上而下的构建过程。从根节点出发,自顶向下为输入串中寻找一个最左匹配序列,建立一棵语法树。对于每个非终结符的继承属性当作形式参数,函数的返回值当作非终结符的继承属性;对于终结符要初始化所有的继承属性。再进行分析过程中,非终结符根据当前的输入符号决定使用哪个产生式候选。

    2.3 递归下降子程序伪代码

    (1)表达式

    function表达式:string;
    string s1, s2, s3, result;
    BEGIN
      IF SYM=+’ OR SYM=-’ THEN
      ADVANCE;
      ELSE IF SYM =FIRST() 
      ELSE ERROR;
      BEGIN s1:=;
      END;
      WHILE SYM=+’ OR SYM=-’ THEN
      BEGIN
        ADVANCE;
        S2:=;
        result := newtemp();
        emit(SYM,s1,s2,result);
        s1:= result;
      END;
      Return result;
    END;
    

    (2)项

    function 项:string;
    string s1, s2, s3, result;
    BEGIN
      IF SYM =FIRST(因子) THEN
      BEGIN
        s1:=因子;
      END;
      ELSE ERROR;
      WHILE SYM =*’OR SYM=/’ THEN
    IF SYM =FIRST(因子) THEN 
      BEGIN 
        ADVANCE;
        S2:=因子;
        result := newtemp();
        emit(SYM,s1,s2,result);
        s1:= result;
      END;
      Return result;
    END;
    ELSE ERROR;
    

    (3)因子

    function 因子:string;
    string s;
    BEGIN
      IF SYM =(’ THEN
      ADVANCE;
      s:=表达式;
    ADVANCE; 
      IF SYM=)’ THEN
      ADVANCE;
    Return s; 
    ELSE ERROR; 
      ELSE IF SYM =FIRST(因子) THEN
    ADVANCE;
      ELSE ERROR;
    END;
    

    3 算法流程

    算法流程图如下所示,首先输入表达式,然后进行词法分析,把词法分析的结果存在结构体中,之后调用递归下降分析器中的表达式子程序进行分析,最后得到四元组并存在相应的结构体中,下一步进行判断,如果是算术表达式,就计算该算术表达式的值并输出,如果不是算术表达式,就不做处理,直接输出四元组,最后判断程序的输入是否结束,如果没有结束,就再次输入表达式,重复上述步骤,如果结束,则程序退出。

    [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-fM7peODy-1634978806002)(file:///C:\Users\User\AppData\Local\Temp\ksohtml\wps7B8D.tmp.jpg)]

    图1 算法流程图

    4 源程序

    #include<iostream>
    #include<stdlib.h>
    #include<stdio.h>
    #include<string.h>
    using namespace std; 
    
    //存储词法分析的结果
    struct cf_tv
    {
      string t;  //词法分析的类型
      string v;  //词法分析变量的值
    };
    
    //存储四元组
    struct qua
    {
      string symbal;  //符号
      string op_a;   //第一个操作数
      string op_b;   //第二个操作数
      string result;  //结果
    };
    
    string input; //全局输入
    int cnt;    //全局变量
    int k=0;    //tv输入
    int ljw=0;
    cf_tv result[200]; //存放结果
    qua output[200];  //存放输出的四元组
    int x=0;      //qua 的下标
    int ans=0;     //遍历的时候的下标
    bool error=true;  //出错标志
    int is_letter=0;
    int t[1001];    //临时存放空间
    string item();
    string factor();
    
    //产生新变量名t1,t2等
    string new_temp()
    {
      char *pq;
      char mm[18];
      pq=(char*)malloc(18);
      ljw++;
      //转换成字符串格式
      snprintf(mm,sizeof(mm),"%d",ljw);
      strcpy(pq+1,mm);
      pq[0]='t';
      string s;
      s=pq;
      return s;
    }
    
    //判断是否和目标串匹配
    bool judge (string input, string s)
    {
      if (input.length()!=s.length()) return false;
      else
      {
        for(unsigned int i=0;i<s.length();i++)
        {
          if(input[i]!=s[i]) return false;  //遍历
        }
        return true;
      }
    }
    
    //判断是否和目标串匹配
    bool judge1 (string input, string s)
    {
      if(input[0]==s[0]) return true;
      else return false;
    }
    
    //判断非符号的程序,包含判断关键字,标识符,常数
    void not_fh(string p)
    {
      //判断是否跟目标串相同,相同的话输出结果
      if(judge (p,"begin"))
         {
           result[k].t="beginsym";
           result[k].v=p;
           k++;
         }
         //判断是否跟目标串相同,相同的话输出结果
         else if(judge (p,"call"))
         {
           result[k].t="callsym";
           result[k].v=p;
           k++;
         }
         //判断是否跟目标串相同,相同的话输出结果
         else if(judge (p,"const"))
         {
           result[k].t="constsym";
           result[k].v=p;
           k++;
         }
         //判断是否跟目标串相同,相同的话输出结果
         else if(judge (p,"do"))
         {
           result[k].t="dosym";
           result[k].v=p;
           k++;
         }
         //判断是否跟目标串相同,相同的话输出结果
         else if(judge (p,"end"))
         {
           result[k].t="endsym";
           result[k].v=p;
           k++;
         }
         //判断是否跟目标串相同,相同的话输出结果
         else if(judge (p,"if"))
         {
           result[k].t="ifsym";
           result[k].v=p;
           k++;
         }
         //判断是否跟目标串相同,相同的话输出结果
         else if(judge (p,"odd"))
         {
           result[k].t="oddsym";
           result[k].v=p;
           k++;
         }
         //判断是否跟目标串相同,相同的话输出结果
         else if(judge (p,"procedure"))
         {
           result[k].t="proceduresym";
           result[k].v=p;
           k++;
         }
         //判断是否跟目标串相同,相同的话输出结果
         else if(judge (p,"read"))
         {
           result[k].t="readsym";
           result[k].v=p;
           k++;
         }
         //判断是否跟目标串相同,相同的话输出结果
         else if(judge (p,"var"))
         {
           result[k].t="varsym";
           result[k].v=p;
           k++;
         }
         //判断是否跟目标串相同,相同的话输出结果
         else if(judge (p,"then"))
         {
           result[k].t="thensym";
           result[k].v=p;
           k++;
         }
         //判断是否跟目标串相同,相同的话输出结果
         else if(judge (p,"write"))
         {
           result[k].t="writesym";
           result[k].v=p;
           k++;
         }
         //判断是否跟目标串相同,相同的话输出结果
         else if(judge (p,"while"))
         {
           result[k].t="whilesym";
           result[k].v=p;
           k++;
         }
         else
         {
           int flag = 0;
           for(unsigned int i=0;i<p.length();i++)
           {
             //判断是否是标识符
             if(!isdigit(p[i]))
             {
               flag = 1;
               result[k].t="ident";
               result[k].v=p;
               k++;
               break;
             }
           }
           //判断是否是数字
           if(!flag)
           {
             result[k].t="number";
             result[k].v=p;
             k++;
           }
         }
    }
    
    //防止多个运算符组成,返回正确下标
    int change(string str,int cnt)
    {
      int y=0;
      char fh[15]={'+','-','*','/','=','<','>',':','(',')',',',';','.'};
      for(int i=0;i<13;i++)
      {
        if(str[cnt]==fh[i])
        {
          y=i;
        }
      }
      if(y==5)
      {
        //如果运算符是两个符号组成,cnt+1
        if(str[cnt+1]=='>')
        {
          cnt=cnt+1;
          return cnt;
        }
        //判断两个运算符相连
        else if(str[cnt+1]=='=')
        {
          cnt=cnt+1;
          return cnt;
        }
      }
      //判断:=
      if(y==7)
      {
        cnt=cnt+1;
        return cnt;
      }
      return cnt;
    }
    
    //对运算符和界符的输出
    void fh_1(string str,int cnt)
    {
      int y=0;
      char fh[15]={'+','-','*','/','=','<','>',':','(',')',',',';','.'};
      for(int i=0;i<13;i++)
      {
        if(str[cnt]==fh[i]) y=i;
      }
      //plus
      if(y==0)
      {
         result[k].t="plus";
         result[k].v=fh[y];
         k++;
      }
      //minus
      if(y==1)
      {
         result[k].t="minus";
         result[k].v=fh[y];
         k++;
      }
      //times
      if(y==2)
      {
         result[k].t="times";
         result[k].v=fh[y];
         k++;
      }
      //slash
      if(y==3)
      {
         result[k].t="slash";
         result[k].v=fh[y];
         k++;
      }
      //eql
      if(y==4)
      {
         result[k].t="eql";
         result[k].v=fh[y];
         k++;
      }
      if(y==5)
      {
        //neq
        if(str[cnt+1]=='>')
        {
          cnt=cnt+1;
          result[k].t="neq";
          result[k].v="<>";
          k++;
        }
        //leq
        else if(str[cnt+1]=='=')
        {
           result[k].t="leq";
           result[k].v="<=";
           k++;
        }
        //lss
        else
        {
           result[k].t="lss";
           result[k].v="<";
           k++;
        }
      }
      if(y==6)
      {
        //geq
        if(str[cnt+1]=='=')
        {
           result[k].t="geq";
           result[k].v=">=";
           k++;
        }
        //gtr
        else
        {
           result[k].t="gtr";
           result[k].v=">";
           k++;
        }
      }
      //becomes
      if(y==7)
      {
        result[k].t="becomes";
        result[k].v=":=";
        k++;
      }
      //lparen
      if(y==8)
      {
        result[k].t="lparen";
        result[k].v="(";
        k++;
      }
      //rparen
      if(y==9)
      {
        result[k].t="rparen";
        result[k].v=")";
        k++;
      }
      //comma
      if(y==10)
      {
        result[k].t="comma";
        result[k].v=",";
        k++;
      }
      //semicolon
      if(y==11)
      {
        result[k].t="semicolon";
        result[k].v=";";
        k++;
      }
      //period
      if(y==12)
      {
        result[k].t="period";
        result[k].v=".";
        k++;
      }
    }
    
    //词法分析
    void cifa()
    {
      string str;
      while(cin>>str)
      {
        cnt=0;
        const char *d = " +-*/=<>:(),;.";
        char *p;
        //运用空格和运算符和界符分割字符串并且遍历
        char buf[1001] ;
        //字符串转成数组
        strcpy(buf , str.c_str());
        //p是一个char*
        p = strtok(buf,d);
        while(p)
        {
          //当前无符号
          if(str[cnt]==p[0])
          {
             not_fh(p);
             cnt=cnt+strlen(p);
          }
          //当前是符号
          else
          {
            while(str[cnt]!=p[0])
            {
              fh_1(str,cnt);
              cnt=change(str,cnt);
              cnt=cnt+1;
            }
            not_fh(p);
            cnt=cnt+strlen(p);
          }
          //下移一位,进行遍历
          p=strtok(NULL,d);
        }
        for(unsigned int i=cnt;i<str.length();i++)
        {
          //防止最后有多个符号
          fh_1(str,i);
        }
      }
    }
    
    //判断是哪种类型的计算
    void judge_type()
    {
      for(int i=0;i<k;i++)
      {
        if(judge(result[i].t,"ident"))
        {
          is_letter=1;
          break;
        }
      }
    }
    
    //表达式的递归下降分析函数
    string bds()
    {
      string s;
      string s1,s2,s3;
      if(ans>k) return NULL;
      //加减符号
      if(judge(result[ans].v,"+") || judge(result[ans].v,"-"))
      {
        ans++;
        if(ans>k)
        {
          cout<<1<<endl;
          //error
          error=false;
        }
        s1=item();
      }
      else if( judge(result[ans].v,"(") ||judge(result[ans].t,"ident") ||judge(result[ans].t,"number"))
      {
        //项目判定,前面条件是first集合
        s1=item();
      }
      else
      {
        cout<<2<<endl;
        //error
        error=false;
      }//
      while(judge(result[ans].v,"+") || judge(result[ans].v,"-"))
      {
        int ans_temp=ans;
        ans++;
        if(ans>k)
        {
          cout<<3<<endl;
          //error
          error=false;
        }
        //项目循环
        s2=item();
        output[x].symbal=result[ans_temp].v;
        output[x].op_a=s1;
        output[x].op_b=s2;
        output[x].result=new_temp();
        s=output[x].result;
        s1=s;
        x++;
      }
      return s;
    }
    
    //项的递归下降分析函数
    string item()
    {
      string s;
      string s1,s2,s3;
      if(ans>k) return NULL;
      //因子判断
      s1=factor();
      while(judge(result[ans].v,"*") || judge(result[ans].v,"/"))
      {
        int ans_temp=ans;
        ans++;
        if(ans>k)
        {
          cout<<4<<endl;
          //error
          error=false;
        }
        s2=factor();
        output[x].op_a=s1;
        output[x].symbal=result[ans_temp].v;
        output[x].op_b=s2;
        output[x].result=new_temp();
        s=output[x].result;
        s1=s;
        x++;
      }
      return s1;
    }
    
    //因子的递归下降分析函数
    string factor()
    {
      string s;
      if(ans>=k) return NULL;
      //开头字母或数字
      if(judge(result[ans].t,"ident") ||judge(result[ans].t,"number"))
      {
        s=result[ans].v;
        ans++;
        if(ans>k)
        {
          cout<<5<<endl;
          //error
          error=false;
        }
      }
      //左括号
      else if(judge(result[ans].v,"("))
      {
        ans++;
        //表达式
        s = bds();
        //右括号
        if(judge(result[ans].v,")"))
        {
         ans++;
         if(ans>k)
         {
           cout<<6<<endl;
           //error
           error=false;
         }
        }
      }
      else
      {
        cout<<7<<endl;
        //error
        error=false;
      }
      return s;
    }
    
    //删除第一个字母
    string del(string s)
    {
      char c[101];
      for(unsigned int i=0;i<s.length()-1;i++)
      {
        c[i]=s[i+1];
      }
      return c;
    }
    
    void js(int i)
    {
      char* end;
      //如果是乘法
      if(judge(output[i].symbal,"*"))
      {
        //判断第一个符号是字母还是数字
        if(!judge1(output[i].op_a,"t"))
        {
          if(!judge1(output[i].op_b,"t"))
          {
            //强制类型转换
            t[i+1]=static_cast<int>(strtol(output[i].op_a.c_str(),&end,10))*static_cast<int>(strtol(output[i].op_b.c_str(),&end,10));
          }
        }
      }
      else
      {
        if(!judge1(output[i].op_b,"t"))
        {
          string ss;
          ss=del(output[i].op_a);
          //强制类型转换
          int z=static_cast<int>(strtol(ss.c_str(),&end,10));
          t[i+1]=t[z]*static_cast<int>(strtol(output[i].op_b.c_str(),&end,10));
        }
        else
        {
          string s;
          s=del(output[i].op_a);
          int yy=static_cast<int>(strtol(s.c_str(),&end,10));
          string ss;
          ss=del(output[i].op_b);
          int zz=static_cast<int>(strtol(ss.c_str(),&end,10));
          t[i+1]=t[yy]*t[zz];
        }
      if(judge(output[i].symbal,"+"))
      {
        if(!judge1(output[i].op_a,"t"))
        {
          if(!judge1(output[i].op_b,"t"))
          {
            t[i+1]=static_cast<int>(strtol(output[i].op_a.c_str(),&end,10))+static_cast<int>(strtol(output[i].op_b.c_str(),&end,10));
          }
          else
          {
            string ss;
            ss=del(output[i].op_b);
            int yy=static_cast<int>(strtol(output[i].op_a.c_str(),&end,10));
            int zz=static_cast<int>(strtol(ss.c_str(),&end,10));
            t[i+1]=yy+t[zz];
          }
        }
        else
        {
          if(!judge1(output[i].op_b,"t"))
          {
            string ss;
            ss=del(output[i].op_a);
            int zz=static_cast<int>(strtol(ss.c_str(),&end,10));
            t[i+1]=t[zz]+static_cast<int>(strtol(output[i].op_b.c_str(),&end,10));
          }
          else
          {
            string s;
            s=del(output[i].op_a);
            int yy=static_cast<int>(strtol(s.c_str(),&end,10));
            string ss;
            ss=del(output[i].op_b);
            int zz=static_cast<int>(strtol(ss.c_str(),&end,10));
            t[i+1]=t[yy]+t[zz];
          }
        }
      }
     }
    }
    
    int main()
    {
      //词法分析函数
      cifa();
      //判断类型
      judge_type();
      //语法分析和语义分析
      bds();
      //进行输出
      if(is_letter==1)
      {
         for(int i=0;i<x;i++)
        {
          cout<<"("<<output[i].symbal<<","<<output[i].op_a<<","<<output[i].op_b<<","<<output[i].result<<")"<<endl;
        }
      }
      //进行输出,计算结果
      else
      {
        for(int i=0;i<x;i++)
        {
          js(i);
        }
        cout<<t[x]<<endl;
      }
      return 0;
    }
    

    5 调试数据

    5.1 测试样例一

    【样例输入】
    2+3*5
    
    【样例输出】
    17
    

    样例一结果如下所示

    [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-RjiL6KMD-1634978806011)(file:///C:\Users\User\AppData\Local\Temp\ksohtml\wps7C1B.tmp.jpg)]

    图2 样例一测试结果

    5.2 测试样例二

    【样例输入】
    2+3*5+7
    
    【样例输出】
    24
    

    样例二结果如下所示

    [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-OdYoOdcP-1634978806014)(file:///C:\Users\User\AppData\Local\Temp\ksohtml\wps7C2C.tmp.jpg)]

    图3 样例二测试结果

    5.3 测试样例三

    【样例输入】
    a*(b+c) 
    
    【样例输出】
    (+,b,c,t1)
    (*,a,t1,t2)
    

    样例三结果如下所示

    [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-2ElSTqE0-1634978806025)(file:///C:\Users\User\AppData\Local\Temp\ksohtml\wps7C2D.tmp.jpg)]

    图4 样例三测试结果

    5.4 测试样例四

    【样例输入】
    a*(b+c)+d
    
    【样例输出】
    (+,b,c,t1)
    (*,a,t1,t2)
    (+,t2,d,t3)
    

    样例四结果如下所示

    [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-3TAgwESy-1634978806030)(file:///C:\Users\User\AppData\Local\Temp\ksohtml\wps7C2E.tmp.jpg)]
    图5 样例四测试结果

    6 实验调试情况及体会

    6.1 实验调试情况

    由上一步中的四个测试样例可以得到,所有的测试样例均得到了相应的输出结果,说明代码编写成功,并且在代码中设置了出错处理,以便解决其他情况。

    6.2 实验体会

    这次实验在上课之前及时的进行了预习,在编写代码之前需要写出递归下降翻译器的伪代码,重点就是要找到对于每个非终结符的属性哪些是继承属性,哪些是综合属性。然后将继承属性作为参数,综合属性作为返回值,进行计算。

    编写代码的时候,需要用到实验一和实验二的代码,写实验一代码的时候没考虑到后面会用到,直接将结果输出并没有保存中间结果,以至于自己在编码的时候需要先将实验一的结果存放在一个自定义的结构体中,里面包含词法分析的两个因素:值和类型。而分析器分析的时候,直接调取这个结构体的内容,四元式的结果也会放在一个特殊的结构体,里面记录了四元式的四个值,方便输出。如果是数字运算式,可以模拟计算器对于这四个值进行计算,并且需要数组和判定运算符函数来判断是数字还是辅助变量,根据对应符号进行运算。

    通过这次实验,从词法分析到语法分析到语义分析的知识点有了大致的回顾,并且重点回顾了每个阶段输入什么,输出什么,这些信息怎么存储,用什么算法来计算。还需要进一步优化自己的代码,比如在这次的实验代码过程中,需要改进的是将词法分析和语法分析合并,降低时间复杂度,提高执行效率。

    通过这四次的实验过程,让我对于编译原理这门课有了比较清晰的认识,可能理论课当时听懂了,过一会可能就会遗忘。通过学习编译原理,感觉用到了数据结构,算法等思维理解,又需要对于许多概念的理解记忆。这也是这门课的难点所在。通过这次学习,懂得更要注重对于基础科目的掌握,不断加强和拓展自己的计算机思维。

    最后感谢刘善梅老师对我一学期的悉心指导,不胜感激,我会继续努力学好接下来的每一门专业课程,不负老师厚望!

    展开全文
  • 编译原理 —— 什么是语义分析

    千次阅读 2019-02-03 11:17:54
    分析语句和声明是如何构成程序的 收集标识符的属性信息 种属 简单变量 复合变量 过程 类型 整型 实型 字符型 布尔型 指针型 存储位置、长度 值 作用域 参数和返回值信息 使用符号表和字符串表来存储这些信息...
  • 语义分析 编译原理 北邮 大三 实验要求:编写语义分析程序,实现对算术表达式的类型检查和求值。要求所分析算术表达式由如下的文法产生。 实验要求:用自底向上的语法制导翻译技术实现对表达式的分析和翻译。 (1) ...
  • 编译原理与技术讲义 第8章 属性文法和语义分析.ppt
  • 第七章 语义分析和中间代码产生 本章感觉有点难,看得不太懂,谁有好的资料,欢迎分享; 按我的思路整理,重点如下: 三地址代码、四元式序列 适用于一遍扫描分析的回 填技术。 用回填技术实现布尔表达式和控制流...
  • 编译原理及实现技术:18.语义分析_抽象地址和符号表.ppt
  • 上海电力学院 编译原理 课程实验报告 实验名称 实验三 自下而上语法分析及语义分析 院 系 计算机科学和技术学院 专业年级 学生姓名 学号 指导老师 实验日期 实验三自上而下的语法分析 一实验目的 通过本实验掌握LR...
  • 实验目的:用c语言对一个简单语言的子集编制一个一遍扫描的编译程序,以加深对编译原理的理解,掌握编译程序的实现方法和技术。 语法分析 C2.1 实验目的 编制一个递归下降分析程序,实现对词法分析程序所提供的单词...
  • 语义分析的必要性 语法和语义的区别 语法关于什么样的字符串才是该语言 在组成结构上合法的程序的法则 语义关于结构上合法的程序的意义的 法则 语义分析的分类 语义种类 静态语义在编译阶段(从程序文本上)可 以检查...
  • 编译原理(静态语义分析

    千次阅读 2020-09-03 16:49:12
    语义分析的作用 检查结构正确的句子表达的意思是否正确 执行规定的语义动作 中间代码简介 后缀式 逆波兰式,a+bc的后缀式表示为abc+操作符紧跟在操作数的后面 三地址码 三地址码式不超过三个地址...
  • 编译原理实验五 / 语义分析

    千次阅读 2021-01-25 19:53:23
    实验五 语义分析器 代码已开源:https://github.com/LinXiaoDe/Quary/tree/master/lab5 一. 学习经典的语义分析器(2小时) 一、实验目的 学习已有编译器的经典语义分析源程序。 二、实验任务 阅读已有编译器的...
  • 编译原理及实现技术:19.语义分析_符号表管理_goto语句.ppt
  • 天津理工大学编译原理实验:语义分析与中间代码生成学案.pdf
  • 最近在学习编译原理相关知识,主要看的是编译器前端分析技术,主要学习的有词法分析、语法分析、语义分析、有限自动机、上下文无关文法、BNF范式、语法分析树等相关前端概念内容,后续可能使用Anltr或Peg对特定的DSL...
  • 递归下降分析方法,词法、语法、语义分析生成四元式
  • 标准文档 语义分析及中间代码生成程序设计原理与实现技术 XXX 1028XXX2 计科1XXX班 1. 程序功能描述 完成以下描述赋值语句和算术表达式文法的语法制导生成中间代码四元式的过程 G[A]:AV:=E EE+TE-T TT*FT/FF F(E)i ...
  • 编译技术:第03章 词法分析.ppt

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 45,090
精华内容 18,036
关键字:

编译技术语义分析