# 1 选题背景
## 1.1任务
主要是通过对简单编译器的完整实现,加深课程中关键算法的理解,提高
学生对系统软件编写的能力。
## 1.2目标
本次课程实践目标是构造一个高级语言的子集的编译器,目标代码是汇编语言。按照任务书,实现的方案可以有很多种选择。
## 1.3源语言定义
在本次编译原理实践中,选择MiniC语言作为源语言。
# 2 词法分析和语法分析
## 2.1 单词文法描述
单词是MiniC语言中具有独立意义的最小单位,可分为 5 大类:关键字(保留字)、运算符、界符、常量和标识符。
C语言中的关键字(它们都是保留字)包括:基本类型关键字 int、float、char,分支与循环语句涉及的 if、else、while返回语句 return,还有输入输出语句关键字 Print、Read。
MiniC中的运算符包括:“+ - \* / < <= > >= = == != && || ! [] ()”,涉及到了算术运算和逻辑运算,值得注意的是,在具体的设计时,小括号()和中括号[]被当作了运算符而非界符,因为它们在函数调用、数组访问时都有特殊意义,不能当作单纯的分隔符看待。
MiniC中界符包括:“; , . {}”。
MiniC中的常量包括:空指针(null)、浮点数常量、整型常量(十进制)、字符常量。其中,浮点数常量可以用一般的小数形式表示,例如“6.66666、8888.8”等,在本词法设计中,小数“.0001”与“1. ”都算合法小数;一个整型常量可以是十进制整数,一个十进制整数是一个十进制数字(0-9)的序列,例如“68686”; 一个字符常量是被一对单引号包围的ASCII 字符序列,例如“ ‘a’ ”。
除此之外,本词法分析程序还会识别注释注释包括单行注释和多行注释,单行注释是以//开头直到该行的结尾,多行注释是用“/\*”和“\*/”包含的所有字符(自身除外)。
2.2 语言文法描述
**程序结构:**
一个MiniC程序是由函数、变量定义的序列组成。
一个MiniC程序中必须包含一个名为“main”的主函数,以int类型参数作为返回值,不带任何参数。
**作用域:**
MiniC支持多层次的作用域。每个函数有一个用于声明参数表的参数作用域和存放函数体的局部作用域。局部作用域中一对大括号建立了一个嵌套的局部作用域。内层作用域屏蔽外层作用域。注意点为:
1. 局部作用域的变量必须先声明后使用。局部作用域的变量在声明时不能够在声明的同时进行附初值。
1. 同一个作用域中的标识符是唯一的。
1. 在嵌套的作用域中重新声明的标识符屏蔽外层的同名标识符,但不允许在局部作用域中声 明与外层的局部作用域或参数作用域中的变量同名的变量。
1. 不可访问已经在一个已经关闭的作用域中声明的标识符。
**类型:**
基本类型有:int, float, char。数组类型可以通过任何基本类型建立起来。
**函数:**
函数的定义用于建立函数名字以及与这个名字相关联的类型签名,类型签名包括函数是否是静态的、返回值类型、形参表的大小以及各形参的类型。函数的定义提供类型签名以及组成函数体的语句。函数之间不允许嵌套。函数可以有零或者多个形参。形参的类型可以是int、float、char,不允许有数组类型的形参。用在形参列表中的标识符必须是唯一的(即形参不能重名)。函数的返回类型可以是任何的基本类型。一个函数只能被定义一次。函数中的任何return 语句必须返回一个与该返回类型兼容的值。
所调用的函数必须是有定义的,无论其定义是否出现在调用处之前。函数调用中实参的个数必须与函数所需形参的个数相匹配。函数调用中每个实参的类型必须与对应形参的类型相匹配。函数调用时实参的求值顺序是从左至右。函数调用过程中执行到一个 return 语句或者到达函数在源程序中的结尾时把控制权交还给调用方。函数调用结果的类型是函数声明时候的返回值类型。
## 2.3 词法分析器的设计
词法分析器采用的工具是自动化生成工具 GNU Flex,该工具要求词法规则以正则表达式(正规式)给出,并根据给定的词法规则生成相应的词法分析程序。Flex 的原理是有穷自动机,即 Flex 会将用正则表达式表示的词法规则等价转化为相应的有穷自动机 FA,生成对应的词法分析程序。所以,设计词法分析器的关键便是设计能准确识别各类单词的正则表达式。根据 2.1 的分析,合法单词包括关键字、运算符、界符、常量和标识符,以及其他一些辅助“单词”。关键字的正则表达式十分简单,例如:对于关键字 int 而言,其正则表达式就是“int”(包括引号)。以此类推,不难得到所有关键字的正则表达式。
运算符与界符的正则表达式与关键字的正则表达式类似,都是用引号括起自身即可,于是不再累述。例如+的正则表达式是“+”,{的正则表达式是“{”。
常量的表达式相对复杂。对于一般小数形式的浮点数常量,因为要考虑“36.”和“.36”这样的特殊形式,所以形式比较复杂,要分情况讨论,并用“|”将规则相或,最后设计出的正则表达式为“[+-]?([0-9]\*\.?[0-9]+|[0-9]+\.)”(不包括引号,下同);对于十进制的整型常量,实际上就是 0-9 的序列再加上正负号,所以正则表达式相对简单为“[+-]?[0-9]+”;对于字符常量,应当是由单引号所括起来的字符构成,所以正则表达式设计为“" ' "{char}" ' "”其中“char”为[A-Z]|[a-z]|"!"|"@"|"#"|"$"|"%"|"^"|"&"|"\*"|"("|")"|"\_"|"-"|"+"|"="|"\\"|"{"|"}"|"["|"]"|":"|";"|"'"|"<"|">"|","|"."|"?"|"/"|"~"|"`"
根据标识符的定义,设计其正则表达式时需要对开头第一个字符作限制,即第一个字符只能是 a-z 或 A-Z,由此得到其正则表达式为“\"[^\"\n]\*\"”。不过,这里需要注意的是,对标识符的识别规则应放到关键字的识别规则的后面,否则会将所有的关键字当作标识符处理。
为了能在词法分析和语法分析报错时提供错误的详细位置信息,运用了 Flex的部分高级特性,例如:开启 yylineno 选项,从而全局变量 yylineno 会记录当前正在分析的词法单元在源程序中的行号,并由 Flex 自行维护(初值设为 1)。
## 2.4 语法分析器设计
` `语法分析器的实现采用的是自动化生成工具 GNU Bison,Bison 可以根据给定的语法规则,自动化生成对应的语法分析程序。但是,语法分析的目的不仅仅是判断源程序的语句是否符合语法规则,还应该(如果符合语法规则)构造源程序对应的语法分析树,用于编译的后续阶段。Bison 和 Flex 可以无缝对接,即将Flex进行词法分析后得到的单词序列作为Bison的输入,从而用来进行语法分析。为了实现这一点,需要按照实验指导书上的步骤进行修改和编译,这里不赘述。设计语法分析器的第一步,便是设计相应的语法规则。语法规则在 2.2 中的Decaf 语法规范中已经详细给出,这里需要做的便是将语法规则按照 Bison 的标准写成相应的生成式。在具体的转化过程中,有一个问题:由 MiniC语法规范直接转化来的生成式存在大量的移进-规约冲突或规约-规约冲突,需要通过一定的方法来消除冲突。
二义性与冲突处理,则是通过显示规定优先级和结合性来解决。经过排查移进-规约冲突和规约-规约冲突的来源�
没有合适的资源?快使用搜索试试~ 我知道了~
基于C语言实现高级语言子集的编译器【100012140】
共33个文件
png:19个
c:4个
h:2个
1.该资源内容由用户上传,如若侵权请联系客服进行举报
2.虚拟产品一经售出概不退款(资源遇到问题,请及时私信上传者)
2.虚拟产品一经售出概不退款(资源遇到问题,请及时私信上传者)
版权申诉
0 下载量 69 浏览量
2023-05-15
10:12:29
上传
评论 1
收藏 2.06MB ZIP 举报
温馨提示
词法分析器采用的工具是自动化生成工具 GNU Flex,该工具要求词法规则以正则表达式(正规式)给出,并根据给定的词法规则生成相应的词法分析程序。 单词是MiniC语言中具有独立意义的最小单位,可分为 5 大类:关键字(保留字)、运算符、界符、常量和标识符。 C语言中的关键字(它们都是保留字)包括:基本类型关键字 int、float、char,分支与循环语句涉及的 if、else、while返回语句 return,还有输入输出语句关键字 Print、Read。
资源推荐
资源详情
资源评论
收起资源包目录
100012140-基于C语言实现高级语言子集的编译器.zip (33个子文件)
miniccomposer
lex.l 2KB
lex.yy.c 43KB
parse.output 32KB
test.c 245B
miniC.code-workspace 43B
Doc
编译原理实验报告.docx 1.34MB
LICENSE 1KB
parse.tab.h 3KB
def.h 4KB
ast.c 58KB
img
Aspose.Words.5c1c4ea3-8038-4568-a899-bc8900e9e4c7.016.png 28KB
Aspose.Words.5c1c4ea3-8038-4568-a899-bc8900e9e4c7.011.png 104KB
Aspose.Words.5c1c4ea3-8038-4568-a899-bc8900e9e4c7.018.png 35KB
Aspose.Words.5c1c4ea3-8038-4568-a899-bc8900e9e4c7.015.png 37KB
Aspose.Words.5c1c4ea3-8038-4568-a899-bc8900e9e4c7.019.png 102KB
Aspose.Words.5c1c4ea3-8038-4568-a899-bc8900e9e4c7.008.png 13KB
Aspose.Words.5c1c4ea3-8038-4568-a899-bc8900e9e4c7.010.png 16KB
Aspose.Words.5c1c4ea3-8038-4568-a899-bc8900e9e4c7.004.png 64KB
Aspose.Words.5c1c4ea3-8038-4568-a899-bc8900e9e4c7.017.png 15KB
Aspose.Words.5c1c4ea3-8038-4568-a899-bc8900e9e4c7.007.png 15KB
Aspose.Words.5c1c4ea3-8038-4568-a899-bc8900e9e4c7.002.png 10KB
Aspose.Words.5c1c4ea3-8038-4568-a899-bc8900e9e4c7.006.png 3KB
Aspose.Words.5c1c4ea3-8038-4568-a899-bc8900e9e4c7.013.png 23KB
Aspose.Words.5c1c4ea3-8038-4568-a899-bc8900e9e4c7.009.png 16KB
Aspose.Words.5c1c4ea3-8038-4568-a899-bc8900e9e4c7.012.png 18KB
Aspose.Words.5c1c4ea3-8038-4568-a899-bc8900e9e4c7.005.png 17KB
Aspose.Words.5c1c4ea3-8038-4568-a899-bc8900e9e4c7.014.png 46KB
Aspose.Words.5c1c4ea3-8038-4568-a899-bc8900e9e4c7.001.png 96KB
Aspose.Words.5c1c4ea3-8038-4568-a899-bc8900e9e4c7.003.png 55KB
parse.y 8KB
a.exe 100KB
parse.tab.c 63KB
README.md 25KB
共 33 条
- 1
资源评论
神仙别闹
- 粉丝: 2674
- 资源: 7640
下载权益
C知道特权
VIP文章
课程特权
开通VIP
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功