基本信息

内容简介
目录
前言
第1章 词法分析与语法分析 1
1.1 实验内容 1
1.1.1 实验要求 1
1.1.2 输入格式 2
1.1.3 输出格式 2
1.1.4 测试环境 3
1.1.5 提交要求 3
1.1.6 样例(必做内容) 4
1.1.7 样例(选做要求) 7
1.2 实验指导 11
1.2.1 词法分析概述 12
1.2.2 GNU Flex介绍 13
1.2.3 Flex:编写源代码 14
1.2.4 Flex:书写正则表达式 17
1.2.5 Flex:高级特性 19
1.2.6 词法分析提示 21
1.2.7 语法分析概述 22
1.2.8 GNU Bison介绍 24
前言
需要指出的是,虽然本书配合课本使用,但其内容已经包括所有相关的资料,因而它是内在完整的。这意味着,即使教学时使用其他编译原理相关的教材,本书仍能作为实践课程的教材,而不会出现所需资料不完整的情况。
设计思想
通常而言,编译原理实践课程较难设计,原因是其对应的理论教材以传授知识为主,离具体实践有较大的距离。而常规的实践课程大多会给出一门简易语言的语法,要求学生实现对应于该语言的编译器。由于缺乏规范化的指导,时常导致要么降低教学要求,允许学生较为随意地实现编译器;要么要求过高,致使学生们无从下手,从而对编译原理实践课程产生较大的抵触心理。针对这些问题,本书面向开设计算机学科的大专院校,提供一门接近实际C/C++的C––语言语法,给出了详细的实验步骤和指导过程,引导性地完成一个实际可用的编译器,并提供了充分的测试样例来验证编译器实现的正确性。
本书共分为四章,分别关注编译器设计的四个重要阶段—词法分析与语法分析、语义分析、中间代码生成以及目标代码生成。每章都给出具体的实验要求、实验指导以及测试样例等,它们共同覆盖了一个实用编译器的设计与实现的全过程。
本书的实验设计具有四个特点:一是接近实际,所采用的语言是C––,接近现实中常用的C/C++,这使得所设计的编译器非常实用,甚至在特定的领域可以直接或经过少量修改后使用;二是配有指导教程,引导性地完成整个编译器的设计与实现,不会出现面对实验要求无从下手或不得不求助第三方资料的情况;三是具备验证帮助,提供大量的测试样例来验证编译器实现的正确性,而无需自行特别设计测试用例;四是难度可调,提供多种实验执行方案,既可统一难度要求,也可区分必做内容和选做内容,更可实现分组方案,使得每个组队实现不同的功能组合,激发学生的思考和锻炼协作能力。
使用方式
本书四章对应四个实验,前后贯穿,分别为词法分析与语法分析、语义分析、中间代码生成以及目标代码生成,简称为实验一、实验二、实验三和实验四。每个实验依赖于其前面的实验,需按顺序进行。
在四个实验中,除了最后的实验之外,前三个实验均有必做部分和选做部分,而选做部分又进一步分为几个不同的要求。具体而言,实验一的要求包括必做部分和三个选做部分(要求1.1、要求1.2和要求1.3),实验二的要求包括必做部分和三个选做部分(要求2.1、要求2.2和要求2.3),实验三的要求包括必做部分和两个选做部分(要求3.1和要求3.2),最后的实验四则只有必做部分的要求。
这四个实验的设计特别考虑了不同院校的不同学生的能力和考核要求上的差异,具备多种使用方式。
1)所有学生相同要求这是最简单的使用方式,适用于学习编译原理的所有学生需要通过相同考核要求的情况。具体而言,可细分为下面三种情况: 所有学生最低要求:完成所有实验的必做部分即可得满分。 所有学生最高要求:完成所有实验的必做部分和选做部分才可得满分。 所有学生自选要求:完成所有实验的必做部分即可得满分;若能完成实验的选做部分,则视完成情况给予额外奖励。
2)不同学生不同要求这种使用方式适用于学习编译原理的学生需要通过不同考核要求的情况。比如强化班和普通班的学生一起上编译原理课程,则可要求强化班的学生完成所有实验的必做部分和选做部分才可得满分,而普通班的学生完成所有实验的必做部分即可得满分,若能完成实验的选做部分,则可获得额外奖励。
3)不同组队不同要求这是最复杂的使用方式,适用于允许学生自由组队以共同完成实验要求的情况。推荐的组队规模是1~3人,如两人组队则为正常模式可获得实验满分,如三人组队则为互助模式需减少实验总分(如变为原来满分的90%),如单人组队则为高手模式可提高实验总分(如变为原来满分的110%)。在实验要求方面,仍可考虑不同的考核要求而选择不同的必做和选做部分,或者完成指定的或随机选择的实验要求。比如一位强化班的学生需要完成所有实验的必做部分和选做部分才可得满分,他可以单人组队进入高手模式以获得更高的总分,也可以两人组队进入正常模式以减少实验的难度。
4)编译优化额外奖励实验三的设计特别考虑了编译优化的程度,即中间代码的执行效率(具体要求见实验三的实验内容部分)。编译优化属于额外奖励部分,如果中间代码的执行效率位于所有学生实验的前50%,则可获得实验三满分额外20%的奖励(即总分变为原来满分的120%);如果中间代码的执行效率位于所有学生实验的前20%,则可获得实验三满分额外50%的奖励(即总分变为原来满分的150%)。这部分额外奖励与前面的三种使用方式既不重叠也不冲突,可根据实际情况考虑是否采用。
时间安排
四个实验的安排依顺序进行,每个实验持续四周,每完成一个实验即可开始下一个实验,但实验一的开始可推迟两周,以等待对应的课本知识讲授。一般而言,如果一个学期时长18周,从第3周开始实验一,在第6周末结束实验一并在第7周开始实验二,在第10周末结束实验二并在第11周开始实验三,在第14周末结束实验三并在第15周开始实验四,在第18周末结束实验四以完成整个编译实践。如果一个学期时长更短或更长,可做相应调整。比如在更短的情况下,可以适当减少实验一的推迟时间(由两周减为一周)或实验三的时间(由四周减为三周)。
上面的实验时间安排是根据课本的知识体系而制订的,如果是其他编译原理教材,只要有下述的内容,也可模仿进行:
第1~6周:引论、词法分析、语法分析(实验一);
第7~10周:语法制导的翻译、中间代码生成(实验二);
第11~14周:中间代码生成、运行时刻环境、代码生成(实验三);
序言
——计算机专业学生系统能力培养和系统课程设置的研究
未来的5~10年是中国实现工业化与信息化融合,利用信息技术与装备提高资源利用率、改造传统产业、优化经济结构、提高技术创新能力与现代管理水平的关键时期,而实现这一目标,对于高效利用计算系统的其他传统专业的专业人员需要了解和掌握计算思维,对于负责研发多种计算系统的计算机专业的专业人员则需要具备系统级的设计、实现和应用能力。
1.计算技术发展特点分析
进入本世纪以来,计算技术正在发生重要发展和变化,在上世纪个人机普及和Internet快速发展基础上,计算技术从初期的科学计算与信息处理进入了以移动互联、物物相联、云计算与大数据计算为主要特征的新型网络时代,在这一发展过程中,计算技术也呈现出以下新的系统形态和技术特征。
(1)四类新型计算系统
1)嵌入式计算系统在移动互联网、物联网、智能家电、三网融合等行业技术与产业发展中,嵌入式计算系统有着举足重轻和广泛的作用。例如,移动互联网中的移动智能终端、物联网中的汇聚节点、“三网融合”后的电视机顶盒等是复杂而新型的嵌入式计算系统;除此之外,新一代武器装备,工业化与信息化融合战略实施所推动的工业智能装备,其核心也是嵌入式计算系统。因此,嵌入式计算将成为新型计算系统的主要形态之一。在当今网络时代,嵌入式计算系统也日益呈现网络化的开放特点。
2)移动计算系统在移动互联网、物联网、智能家电以及新型装备中,均以移动通信网络为基础,在此基础上,移动计算成为关键技术。移动计算技术将使计算机或其他信息智能终端设备在无线环境下实现数据传输及资源共享,其核心技术涉及支持高性能、低功耗、无线连接和轻松移动的移动处理机及其软件技术。
3)并行计算系统随着半导体工艺技术的飞速进步和体系结构的不断发展,多核/众核处理机硬件日趋普及,使得昔日高端的并行计算呈现出普适化的发展趋势;多核技术就是在处理器上拥有两个或更多一样功能的处理器核心,即将数个物理处理器核心整合在一个内核中,数个处理器核心在共享芯片组存储界面的同时,可以完全独立地完成各自操作,从而能在平衡功耗的基础上极大地提高CPU性能;其对计算系统微体系结构、系统软件与编程环境均有很大影响;同时,云计算也是建立在廉价服务器组成的大规模集群并行计算基础之上。因此,并行计算将成为各类计算系统的基础技术。
4)基于服务的计算系统无论是云计算还是其他现代网络化应用软件系统,均以服务计算为核心技术。服务计算是指面向服务的体系结构(SOA)和面向服务的计算(SOC)技术,它是标识分布式系统和软件集成领域技术进步的一个里程碑。服务作为一种自治、开放以及与平台无关的网络化构件可使分布式应用具有更好的复用性、灵活性和可增长性。基于服务组织计算资源所具有的松耦合特征使得遵从SOA的企业IT架构不仅可以有效保护企业投资、促进遗留系统的复用,而且可以支持企业随需应变的敏捷性和先进的软件外包管理模式。Web服务技术是当前SOA的主流实现方式,其已经形成了规范的服务定义、服务组合以及服务访问。
(2)“四化”主要特征
1)网络化在当今网络时代,各类计算系统无不呈现出网络化发展趋势,除了云计算系统、企业服务计算系统、移动计算系统之外,嵌入式计算系统也在物联时代通过网络化成为开放式系统。即,当今的计算系统必然与网络相关,尽管各种有线网络、无线网络所具有的通信方式、通信能力与通信品质有较大区别,但均使得与其相联的计算系统能力得以充分延伸,更能满足应用需求。网络化对计算系统的开放适应能力、协同工作能力等也提出了更高的要求。
2)多媒体化无论是传统Internet应用服务,还是新兴的移动互联网服务业务,多媒体化是其面向人类、实现服务的主要形态特征之一。多媒体技术是利用计算机对文本、图形、图像、声音、动画、视频等多种信息进行综合处理、建立逻辑关系和人机交互作用的新技术。多媒体技术使计算机可以处理人类生活中最直接、最普遍的信息,从而使得计算机应用领域及功能得到了极大的扩展,使计算机系统的人机交互界面和手段更加友好和方便。多媒体具有计算机综合处理多种媒体信息的集成性、实时性与交互性特点。
3)大数据化随着物联网、移动互联网、社会化网络的快速发展,半结构化及非结构化的数据呈几何倍增长。数据来源的渠道也逐渐增多,不仅包括本地的文档、音视频,还包括网络内容和社交媒体;不仅包括Internet数据,更包括感知物理世界的数据。从各种类型的数据中快速获得有价值信息的能力,称为大数据技术。大数据具有体量巨大、类型繁多、价值密度低、处理速度快等特点。大数据时代的来临,给各行各业的数据处理与业务发展带来重要变革,也对计算系统的新型计算模型、大规模并行处理、分布式数据存储、高效的数据处理机制等提出了新的挑战。
4)智能化无论是计算系统的结构动态重构,还是软件系统的能力动态演化;无论是传统Internet的搜索服务,还是新兴移动互联的位置服务;无论是智能交通应用,还是智能电网应用,无不显现出鲜明的智能化特征。智能化将影响计算系统的体系结构、软件形态、处理算法以及应用界面等。例如,相对于功能手机的智能手机是一种安装了开放式操作系统的手机,可以随意安装和卸载应用软件,具备无线接入互联网、多任务和复制粘贴以及良好用户体验等能力;相对于传统搜索引擎的智能搜索引擎是结合了人工智能技术的新一代搜索引擎,不仅具有传统的快速检索、相关度排序等功能,更具有用户角色登记、用户兴趣自动识别、内容的语义理解、智能信息化过滤和推送等功能,其追求的目标是根据用户的请求从可以获得的网络资源中检索出对用户最有价值的信息。
2. 系统能力的主要内涵及培养需求
(1)主要内涵
计算机专业学生的系统能力的核心是掌握计算系统内部各软件/硬件部分的关联关系与逻辑层次;了解计算系统呈现的外部特性以及与人和物理世界的交互模式;在掌握基本系统原理的基础上,进一步掌握设计、实现计算机硬件、系统软件以及应用系统的综合能力。
(2)培养需求
要适应“四类计算系统,四化主要特征”的计算技术发展特点,计算机专业人才培养必须“与时俱进”,体现计算技术与信息产业发展对学生系统能力培养的需求。在教育思想上要突现系统观教育理念,在教学内容中体现新型计算系统原理,在实践环节上展现计算系统平台技术。