目 录
1 引言 1
1.1 课题的理论意义和应用价值 1
1.2 国内外研究概况及发展趋势 2
1.3 本论文所做的工作 2
1.4 本文的结构 3
2 软件开发技术简介 3
2.1 软件复杂度 3
2.2 Lex简介 8
2.3 Yacc简介 8
3 微型编译器系统分析 11
3.1 ANSI C99标准的分析 11
3.2 系统构造 12
3.3 确定设计目标 15
4 系统设计 15
4.1 整体设计 15
4.2 输入子系统的设计 16
4.3 预处理子系统的设计 17
4.4 语法解析子系统的设计 17
4.5 语义解析子系统的设计 20
4.6 输出子系统的设计 21
5 系统测试 24
6 系统展望 25
结论 26
致谢 27
参考文献 28
1 引言
作业和批改作业是学校整个教学过程中非常重要的实践性教学环节。通过作业，学生可以巩固课堂所学知识，并从教师批改的反馈信息中改进不足，激励其学习的自觉性；通过作业，教师可以获取学生的作业信息，评价课堂教学效果，了解学生的学习情况，及时调整其教学策略以利教育教学。
长期以来，作业基本上都是书面形式的，而作业的批改方式也基本上是手工的，在这种传统的作业模式下，学生对待作业敷衍了事，缺做、迟交和抄袭现象严重，其次，繁重的批改作业任务给任课教师造成很大的工作负担，即便是在现代网络教学中，作业的递交方式与批改方式也大多是通过电子邮件完成的。
随着多媒体技术和网络技术的快速发展，现行的通过书面、电子邮件来完成作业的方式和传统的作业批改方式已远远不能满足当前作业各个环节的发展需要，为了适应这种形势，我们尝试开发一套适用于程序设计教学的新型远程作业提交自动批改系统，简称OnlineJudge，即在线判决。
该系统的设计思想来源于美国计算机协会的国际大学生程序设计比赛。国际大学生程序设计比赛在比赛中就是利用计算机自动批改各比赛队的源程序，从而得到比赛的结果。
OnlineJudge系统是一个在线的裁判系统。它可以对程序原代码进行编译和执行，并通过预先设计的测试数据来检验程序原代码的正确性。
每个学生提交的程序在OnlineJudge系统下执行时将受到比较严格的限制，包括运行时间限制，内存使用限制和安全限制等。程序执行的结果将被OnlineJudge系统捕捉并保存，然后再转交给一个裁判程序。该裁判程序比较被测程序的输出数据和标准答案的差别，然后进行给分。
OnlineJudge系统有两部分组成，一个是系统的程序，另一个更重要的是题库，题目要根据教学进度，难度要由浅入深。
1.1 课题的理论意义和应用价值
书面作业的收交和整理统计一直都是困扰教师的一大难题。在传统的作业提交和批改方式下，教师不仅需要花费大量的精力去收集作业，批改作业，统计学生的作业成绩。另外，教师批改作业还受时空限制，而且繁重的批改作业任务会使教师产生厌烦情绪，从而导致作业批改的效率和质量较低。教学过程中，学生一般是交作业一周
后，才可以得到教师批改结果，这与课程教学形成一定的滞后和脱节，不利于学生及时掌握学过的知识，不利于作业反馈功能良好发挥。
利用计算机网络来实现教师的作业发布和学生作业的提交，教师只需一台联网的计算机，就可以收集和批改学生的作业。作业的统计分析自动化，排序方便，检查作业情况一目了然。而且学生可以选择合适的时间和合适的地点提交作业，不必严格地受时间和空间的限制，操作方便简单。
我们这个系统能够支持单项选者题，判断题等多种客观题型，支持程序设计题等主观题型。方便教师作业发布，提高了教师发布作业的灵活性，增强了作业题形成方式的多样化，从而也进一步提高了作业题的质量。
1.2 国内外研究概况及发展趋势
目前国内外有很多类似的考试系统编译器，但是都或多或少的存在一定的缺陷性。由于编程语言的不同，所以对每种编程语言都要开发适应于该语言的代码编译器。因此，国外很多公司都做这个方向的开发并做成工具软件产品发布，譬如Telelogic公司，美国康博软件公司等。而在国内，随着软件开发规模的日益庞大以及外包业务中国外客户的需求，也有几家公司在开发类似的源代码规则编译器。但是以上的开发往往只是针对客户的需求或者是针对公司内部的特殊需求开发，所以都有一定的局限性。
但是除却上述的因素外，由于编程语言的不同以及各行各业使用语言的规范不同，源代码规则编译器是不具备通用性的，因此随着软件测试技术理论的不断发展，以及检验代码的一些软件理论的日益成熟，如软件复杂度等，都将会促进代码规则编译器不断更新完善；同时随着计算机在各行各业的普及应用，软件需求的不断增大，必然需妥更多地考虑软件开发的质量才能在软件行业有更好的竞争力，因此代码规则编译器的需求将会逐渐增多，鉴于这的技术形势之下，我们也想开发出功能更加完善的基于局域网的考试系统编译器。
1.3 本论文所做的工作
为了实现基于局域网的考试系统微型编译器，首先应将该编译器用到的软件开发技术进行解释，以方便研究。然后分析实现该工具需要用什么样的软件结构。在前面所做的工作基础上，设计并实现这样的微型编译器。最后，经过系统测试得出该工具
的检查效率，以便该系统具有其他类似软件所不能达到的效果，让使用效果达到显著提高。
1.4 本文的结构
论文的第一部分论文综述简要介绍了本文的背景和动机。在第二部分简要介绍了开发该基于局域网的考试系统微型编译器所用到的软件开发技术，其中包括词法分析生成器（Lexical compiler，以下简称Lex），语法分析器的生成工具（Yet Another Compiler Compiler，以下简称Yacc），软件复杂度等。第三部分分析了美国国家标准代码99（American National Standards Institute Code 99，以下简称ANSI C99）的内容，设计了微型编译器的系统构造。第四部分详细介绍了微型C代码规则编译器的设计和核心部分的实现。最后对该编译器进行了展望，说明该编译器还有需要完善的地方。
2 软件开发技术简介
该基于局域网的考试系统微型编译器在实际中是一个比较大的项目，该项目在实际开发的过程中使用了很多软件开发中较为成熟的软件开发技术。在本节将对使用的技术进行较为详细地说明，这样才能对该工具有更为深刻地了解和研究。
2.1 软件复杂度
在这个系统开发的过程中，需要介绍一下软件复杂度的概念。在硬件的可靠性设计中，有一条基本原则“简单就是可靠”。这个原则同样也适用于软件，与功能的增多或增强相伴的是不断升级与补丁。现在已经有若干种软件复杂性的度量方法可供参考，针对软件的可维护性，目前业界主要存在三种度量参数：Line复杂度、Halstead复杂度和McCabe复杂度。其中Line复杂度以代码的行数作为计算的基准。Halstead以程序中使用到的运算符与运算元数量作为计数目标(直接测量指标)，然后可以据此计算出程序容量、工作量等。McCabe复杂度一般称为圈复杂度(Cyclomatic complexity)，它将软件的流程图转化为有向图，然后以图论来衡量软件的质量。McCabe复杂度包括圈复杂度、基本复杂度、模块设计复杂度、设计复杂度和集成复杂度。其中McCabe 是比较出色和实用的方法。它能够计算出多种软件复杂度，由此可对软件进行检查，从而分析和查明那些可能导致错误的代码。
70年代，软件系统己经变得极其复杂，无论是开发还是维护都是一项成本高昂的工作。人们意识到必须使软件模块化，以便于开发、测试和维护。为此，成立于1976的McCabe&Associates公司开发出了McCabe Cyclomatic Complexity Metric(圈复杂度)技术对软件进行结构测试。Metric以软件复杂度测量的数目为基础，能帮助识别难于测试和维护的模块，圈复杂度已经成为评估软件质量的一个重要标准。人们可以用圈复杂度对软件的复杂度和质量进行衡量，来安排工程进度，在成本、进度和性能之间寻求平衡。
复杂度的种类有模块、类和程序三类复杂度。模块复杂度包含了关于模块的复杂度信息；类复杂度是针对那些使用McCabe面向对象特性的程序，它包含了关于类的复杂度信息；程序复杂度包含了关于程序的复杂度信息。集成复杂度报告对应于三种复杂度的是三种复杂度报告。如果一个报告的复杂度信息不只一种，那么就把这些复杂度信息组合成新的报告。
集成复杂度信息只收集一个部件及其下级的信息。例如：如果一个程序级报告包含一个类复杂度，那么只报告组成程序的类的信息，而不包含类组成的信息。McCabe复杂度是对软件结构进行严格的算术分析得来的，实质上是对程序拓扑结构复杂性的度量，明确指出了任务复杂部分。McCabe复杂度包括：圈复杂度、基本复杂度、模块设计复杂度、设计复杂度、集成复杂度、行数、规范化复杂度、全局数据复杂度、局部数据复杂度、病态数据复杂度。McCabe复杂度的用途在软件工程中有三种使用McCabe复杂性度量的方式。
作为测试的辅助工具。McCabe复杂性度量的结果等于通过一个子程序的路径数，因而需要设计同样多的测试案例以覆盖所有的路径。如果测试案例数小于复杂性数，则有三种情况：一是需要更多的测试；二是某些判断点可以去掉；三是某些判断点可用插入式代码替换。作为程序设计和管理指南。在软件开发中，需要一种简单的方式指出可能出问题的子程序。保持子程序简单的通用方法是设置一个长度限制，例如50行或2页，但这实际上是在缺乏测试简明性的有效方法时无可奈何的替代方法。不少人认为McCabe度量就是这样一种简明性度量。但是要注意，McCabe度量数大的程序，不见得结构化就不好。例如，Case语句是良结构的，但可能有很大的McCabe度量数（依赖于语句中的分C代码规则编译器的设计和实现支数），这可能是由于问题和解决方案所固有的复杂性所决定的。使用者应当自己决定如何使用McCabe度量所提供的信息。
作为网络复杂性度量的一种方法。Hall和Preiser提出了一种组合网络复杂性度量，用于度量可能由多个程序员组按模块化原理建立的大型软件系统的复杂性。McCabe复杂度即可用于度量各个模块的复杂性，也可用于度量网络复杂性。
圈复杂度：圈复杂度是用来衡量一个模块判定结构的复杂程度，数量上表现为独立路径的条数，即合理的预防错误所需测试的最少路径条数，圈复杂度大说明程序代码可能质量低且难于测试和维护，经验表明，程序的可能错误和高的圈复杂度有着很大关系。计算方法节点是程序中代码的最小单元，边代表节点间的程序流。
优点：避免软件中的错误倾向；指出极复杂模块，这样的模块也许可以进一步细化；度量测试计划，确定测试重点：在开发过程中通过限制程序逻辑，指导测试过程：指出将要测试的区域：帮助测试人员确定测试和维护对象；与所用的高级程序设计语言类型无关。应用圈复杂度指出为了确保软件质量应该检测的最少基本路径的数目。在实际中，测试每一条路经是不现实的，测试难度随着路径的增加而增加。但测试基本路径对衡量代码复杂度的合理性是很必要的。McCabe&Associates建议圈复杂度到10，因为高的圈复杂度使测试变得更加复杂而且增大了软件错误产生的概率。
提示：圈复杂度度量是测量在一个软件模块中的分支数目，在所有的开发周期中都要使用。圈复杂度度量以软件的结构流程图为基础。控制流程图描述了软件模块的逻辑结构。一个模块在典型的语言中是一个函数或子程序，有一个入口和一个出口，也可以通过调用/返回机制设计模块。软件模块的每个执行路径，都有与从模块的控制流程图中的入口到出口的节点相符合的路径。
“Cyclomatic”来源于非直接连接基本测试周期的数目，更重要的是.，也通过直接相连的图表给出独立路径的数目。通过图表的相关性，一个节点可到达另一个节点。圈复杂度度量也可作为模块基本流程图路径的数目，其重点在于模块线形组合后，所产生的路径数目是最小的。对圈复杂度的限制现在有许多好方法可以用来限制圈复杂度。过于复杂的模块容易出错，难于理解、测试、更正，所以应当在软件开发的各个阶段有意识地限制复杂度，许多开发者已经成功地实现把对软件复杂度的限制作为软件项目的一部分，尽管在确切的数目上略微有些争议。最初支持的数目是10，现在支持数目可达15。但是，只应当在条件较好的情况下使数目大于10，例如开发者非常有经验，设计合乎正式标准，使用现代化的程序语言、结构程序、代码预排和先进的测试计划。换句话说，开发团队可以选择超过10的R阶数目，但是必须根据经验进行一些取舍，把精力花在比较复杂的模块上。
基本复杂度：基本复杂度是用来衡量程序非结构化程度的，非结构成分降低了程序的质量，增加了代码的维护难度，使程序难于理解。因此，基本复杂度高意味着非结构化程度高，难以模块化和维护。实际上，消除了一个错误有时会引起其他的错误。计算方法将圈复杂度图中的结构化部分简化成一个点，计算简化以后流程图的圈复杂度就是基本复杂度。
优点：衡量非结构化程度；反映代码的质量；预测代码维护量；与所用的高级程序设计语言类型无关。应用当基本复杂度为1，这个模块是充分结构化的；当基本复杂度大于1而小于圈复杂度，这个模块是部分结构化的；当基本复杂度等于圈复杂度，这个模块是完全非结构化的。
模块设计复杂度模块设计复杂度是用来衡量模块判定结构，即模块和其他模块的调用关系。软件模块设计复杂度高意味模块祸合度高，这将导致模块难于隔离、维护和复用。
编译器的设计和实现计算方法模块设计复杂度是从模块流程图中移去那些不包含调用子模块的判定和循环结构后得出的圈复杂度，因此模块设计复杂度不能大于圈复杂度，通常是远小于圈复杂度。
优点：衡量模块对其下层模块的支配作用；衡量一个模块到其子模块进行集成M试的最小数量；定位可能多余的代码；以复杂的计算逻辑和设计来区分模块；是设计复杂度（Design Complexity，以下简称SO）和集成复杂度（Integration Complexity 以下简称S1）计算的基础；与所用的高级程序设计语言类型无关。设计复杂度以数量来衡量程序模块之间的相互作用关系，它提供了系统级模块设计复杂度的概况，有助于衡量进行自底向上集成测试的效果，而且提供了全面衡量程序设计规格和复杂度的数据，不反映独立模块的内部情况。高设计。复杂度的系统意味着系统各部分之间有着复杂的相互关系，这样系统将难以维护。SO是程序中所有模块设计复杂度之和。
优点：可应用于完整的软件，也可应用于任何子系统；指出一个模块整体的复杂度，反映了每个模块和其内部模块的控制关系；揭示了程序中模块调用的复杂度；有助于集成复杂度的计算。
集成复杂度是为了防止错误所必须进行的集成测试的数量表示，另一种说法是程序中独立线性子树的数目，一棵子树是一个有返回的调用序列。就像圈复杂度是测试路径的数目，而集成复杂度是程序或其子系统的独立线性子树。
计算方法：一个程序的集成复杂度和一个模块的圈复杂度是非常相似的，必须计算对程序进行完全测试所需集成测试的数目。
优点：有助于集成测试的实施；量化集成测试工作且反映了系统设计复杂度；有助于从整体上隔离系统复杂度。行数（Number of Lines以下简称nl），行数是模块中总的行数，包括代码和注释。
优点：计算简单，与所用的高级程序设计语言类型无关;指出了模块的行数(即模块的规模)，规模小的模块易于理解和维护。
规范化复杂度（Normalized Complexity以下简称nv）：规范化复杂度是圈复杂度除以行数。计算方法：n- (G )/nl
优点：与所用的高级程序设计语言类型无关;定义那些有着显著判定逻辑密度的模块，这些模块相对于其他常见规范模块需要做更多的维护工作。
全局数据复杂度（Global Data Complexity以下简称gdv(G)）
全局数据复杂度(需有McCabe Data)量化了模块结构和全局数据变量的关系，它说明了模块对外部数据的依赖程度，同时度量了全局数据的测试工作，也描述了模块之间的藕合关系，能反映潜在的维护问题。
局部数据复杂度（Specified Data Complexity以下简称sdv(G)）
局部数据复杂度(需有McCabe Data)量化了模块结构和用户局部数据变量的关系，同时度量了局部数据的测试工作。
我们能够使用McCabe Data的数据字典选择单独的数据元素，指出每个数据元素具体的数据类型。局部数据复杂度还提供了其他的数据选择准则，量化了每个模块中相应数据对模块控制结构的影响。
病态数据复杂度（Pathological Complexity以下简称pv(G)）衡量一个模块包含的完全非结构化成分的程度，标出向循环内部跳入的问题代码，而这些部分具有最大的风险度，通常需要重新设计。
计算方法：编译器的设计和实现所有的非结构部分除去向循环内跳入的结构，转化为线结构，化以后流程图的圈复杂度。
优点：与所用的高级程序设计语言类型无关；指出了可靠性的问题，助识别极不可靠的软件。病态复杂度就等于简喇氏了维护风险；帮Halstead Metrics。
McCabe能够为所选择的语言产生Halstead Metrics复杂度。Halstead复杂度是以程序中出现的运算符和运算元为计数对象，以它们出现的次数作为计数目标(直接测量指标)，然后据此计算出程序容量、工作量。
5 系统测试
该编译器的开发时间较长，所以在实际的项目开发中分为以下几个阶段进行的。开发主系统、预处理子系统、输入输出子系统、语法子系统；语义子系统。在每个开发阶段，每个子系统都要进行单元测试，保证正确性，尽量不把错误带到下一阶段的开发中。在开发过程中，单元测试采用的主要是两种测试方法，一种是书写测试用例后根据用例对代码进行路径分支覆盖侧试等。另外一种则是利用单元测试框架，书写测试用例，最后生成结果以供查看。在完成了编译器的测试后，还进行了一项与同类型产品之间的性能比较，以估计编译器的性能。
测试时，以编译器开发阶段的两个版本以及另外的一个C代码项目作为输入端进行测试。除了检验编译器的有效性，我们还需要测试编译器的时间效率上是否比该编译器有了显著提高，而这也是重新开发编译器的重要要求指标。测试的项目为系统的源代码。以上两个测试指标，开发的编译器若能实现与相同功能编译器同等正确有效性的情况下，时间使用率有较为显著的提升，那将能达到我们开发该编译器的目的。
6 系统展望
由于课题开发周期长的关系，编译器仍然有很多方面需要完善。一些具体的细节以及改进意见还没有完全实现，因此在本文中并没有得到体现。在编译器的未来版本中，还可以提供更加强大的功能。
首先，会提供更加完整的规则检查，在以后的版本中将逐步完善C代码规则编译器，使它功能能够更加完善；其次，目前的编译器虽然能够跨平台运行，但是只是对应了Windows，Linux，Solaris，而对于一些嵌入式开发系统没有进行相应的扩展，所以未来的版本应该能够在更多的平台上使用，这样才能提高工具的普及率；第三，工具的效率仍然需要改进，不管是在输入子系统，还是语法、语义等子系仍然感觉提升效率的可能性很大，所以应该经过对该工具的测试评价后进行相应的改进；最后，工具没有提供图形化界面，在以后的版本开发中应该实现该工具的图形化界面对应版，这样才能使编译器的管理和使用更加人性化，更容易使用。
Directory
1 INTRODUCTION 1
1.1 the theoretical significance and application value a
1.2 Research and development trend of domestic and overseas 2
1.3 This thesis work done by the two
1.4 The structure of this 3
2 Software Development Technical Overview 3
2.1 Software Complexity 3
2.2 Lex Introduction 8
2.3 Yacc Introduction 8
3 Micro-Analysis 11 compiler
3.1 ANSI C99 standard analysis of 11
3.2 System Construction 12
3.3 determine the design goals 15
4 System Design 15
4.1 The overall design 15
4.2 Input Subsystem Design 16
4.3 Preprocessing Subsystem Design 17
4.4 parser subsystem design 17
4.5 Semantic Analysis Subsystem Design 20
4.6 Output Subsystem 21
5 System Test 24
6 System Outlook 25
Conclusion 26
Thanks 27
References 28
1 Introduction
Operations and duties include teaching and learning process in schools as a whole a very important part of practical teaching. Through the work, students can consolidate the classroom what they have learned, and feedback from teachers marking the improved enough to inspire the learning of the consciousness; through the work, teachers can get information on student work, evaluating teaching effectiveness, understanding of students learning timely adjust their teaching strategies to facilitate the education and teaching.
For a long time, operating essentially in writing, while the operation is basically hand-correcting ways, in this traditional mode of operation, the students work perfunctory treatment, lack of doing, the phenomenon of late, and plagiarism serious Second, the heavy duties include tasks to the Teacher cause great burden of work, even in the modern network of teaching, modes of operation and the correcting ways are mostly done via e-mail.
With the multimedia technology and network technology, the rapid development of the current through written, e-mail to complete the work and the traditional way of correcting the way that can not meet current development needs of all aspects of operations, in order to adapt to this situation, we try to to develop a teaching program design for a new auto-correcting system of the remote job submission, referred to as OnlineJudge, which judgment-line.
The system''s design idea came from the U.S. Association for Computing Machinery''s International Collegiate Programming Competition. International Collegiate Programming Competition in the game is to use the computer automatically correcting the source of all race teams to get results of the competition.
OnlineJudge referee system is an online system. It can compile the program source code and implementation, and through the pre-designed test data to test the correctness of program source code.
Submitted by each student under the program OnlineJudge the system implementation will be subject to more stringent restrictions, including restrictions on running time, memory usage restrictions, and security restrictions. Program execution results will be OnlineJudge system to capture and save, and then hand them over to a referee process. The decision procedure is the measured output data and standard procedures for the difference between the answer and then proceed to the sub.
OnlineJudge system has two parts, one is the systematic process, and the other is more important is the item bank is entitled according to the progress of teaching, the difficulty to be implemented progressively.
1.1 the theoretical significance and application value
The collection of written assignments and compiling statistics has always been troubled by a major challenge for teachers. In a traditional job submission and mark the way, teachers not only need to spend a lot of effort to collect operation, these duties, statistics of students operating results. In addition, the teachers, these duties also affected by the constraints of time, and the heavy teaching duties include tasks would produce weariness, leading to efficiency and quality of correcting lower. The teaching process, students hand in papers and generally a week
After correcting the results can be teachers, which is teaching a certain lag and out of touch, is not conducive to the students grasp the knowledge learned is not conducive to a good job feedback feature to play.
Teachers to use computer networks to achieve the operation of distribution and submission of student assignments, teachers, only one networked computer, you can collect and marking of students work. Statistical analysis of operations automation, easy sorting, inspection operations in a glance. And students can choose the right time and right place to submit work, not strictly limited by time and space, easy to operate simple.
Our system can support the individual who questions the election to determine the objective questions and other kinds of questions in support of program design questions such as subjective kinds of questions. To enable teachers to work release, release of teachers to improve operational flexibility, enhanced job title to form the diversity of ways, and thus further enhance the quality of the job title.
1.2 Research and development trend of domestic and foreign
At home and abroad are very similar examination system compiler, but they all more or less the existence of a certain defective. Because of different programming languages, so it should be developed for each programming language adapted to the language of the code compiler. Therefore, many foreign companies have done in this direction, and made the development of tools for software product releases, such as Telelogic Corporation, the U.S. Compuware Corporation. In the home, along with the increasingly large-scale software development and outsourcing services in China''s foreign customers, there are several companies in the development of similar rules of the source code compiler. However, the development of the above are only to customers or for the special needs of the development within the company, so have some limitations.
Apart from the above-mentioned factors, however, due to the different programming languages, as well as norms of all walks of life use of language is different from the compiler source code rules do not have the universal in nature, so as the theory of software testing technology, continuous development, and testing some of the code the theory of increasingly sophisticated software, such as software complexity and so on, the compiler will promote the code rules constantly updated improved; Meanwhile, along with the popularization of computers in all walks of life, the software needs of increasing, more consideration must be properly the quality of software development can be better in the software industry''s competitiveness, so the needs of the compiler code rules will be gradually increased, in view of the technical situation, we would also like to develop a more complete functional test system based on LAN compilation device.
1.3 This thesis work done by the
In order to achieve LAN-based examination system micro-compiler, the compiler should first be used to explain the software development technology in order to facilitate research. Then analyzes the tool needed to achieve what kind of software architecture. In the previous work based on the design and realization of such a mini-compiler. Finally, after a system test of the tool derived
Examination of efficiency, so that the system has other similar software can not be achieved, so that the use of effects to achieve improved significantly.
1.4 Structure of this article
Paper a brief overview of the first part of the paper describes the background and motivation of this article. In the second part briefly describes the development of the examination system based on LAN mini-compiler used by software development technologies, including lexical analysis generator (Lexical compiler, hereinafter referred to as Lex), parser generation tool (Yet Another Compiler Compiler , hereinafter referred to as Yacc), software complexity and so on. Part III analyzes the American National Standards Code 99 (American National Standards Institute Code 99, hereinafter referred to as ANSI C99) of the content, design, compiler of the micro-system construction. The fourth section details the rules of the micro-C code compiler design and implementation of the core. Finally the compiler of the outlook, stating that the compiler still need to improve the place.
2 Software Development Technical Overview
The examination system based on LAN mini-compiler in practice is a relatively large project, the project development process in the actual use of a lot of software development in more mature software development. In this section will be used in a more detailed description of techniques, so that the tool can be more profound understanding and research.
2.1 Software Complexity
In the system development process, the need to introduce the concept of software complexity. The reliability of the hardware design, there is a basic principle of "less is more reliable." The same principle applies to software, and function of the increase or enhancement is accompanied by constant upgrades and patches. There are already several kinds of software complexity metrics for reference for software maintainability, and now there are three key industry metric parameters: Line complexity, Halstead complexity and McCabe complexity. One Line complexity to the number of lines of code calculated on the base. Halstead in order to use the program to the operator and operand count, as the number of targets (direct measurement of indicators), then you can calculate the procedure whereby the capacity of their workload. McCabe complexity, commonly known as the cyclomatic complexity (Cyclomatic complexity), it will flow chart of the software into a directed graph, and then graph theory to measure the quality of the software. McCabe complexity, including cyclomatic complexity, essential complexity, module design complexity, design complexity and integration complexity. In which McCabe is relatively good and practical approach. It can calculate a variety of software complexity, and thus can check the software to analyze and identify those that could cause the error code.
70 years, software systems have become extremely complex, both the development and its maintenance is a costly task. People are aware of the need to make the software modular, in order to facilitate the development, testing and maintenance. To this end, was founded in 1976 in McCabe & Associates has developed a McCabe Cyclomatic Complexity Metric (cyclomatic complexity) technology software structural testing. Metric measurement of software complexity based on the number that can help identify hard to test and maintain the module, cyclomatic complexity assessment of software quality has become an important criterion. People can use cyclomatic complexity of the software complexity and quality to measure, to arrange for progress, in terms of cost, schedule and performance balancing.
There are several varieties complexity modules, classes and procedures for three types of complexity. Module complexity contains information on the complexity of the module; class complexity McCabe against those who use object-oriented features of the program, which contains information on the complexity of the class; program complexity contains information on the program complexity. Integration complexity of the report correspond to the three kinds of complexity is the three kinds of complexity of the report. If a report of the complexity of information more than one, then put the complexity of information combined into a new report.
The complexity of information integration is only one component and its subordinates to collect information. For example: If a program-level report contains a class of complexity, then the program only reports the composition of the classes of information, and does not contain information on the composition of classes. McCabe complexity of software architecture is a rigorous mathematical analysis can be accomplished, the program is essentially a measure of the complexity of topology, clearly pointed out the complexity of the task part of the. McCabe complexity include: cyclomatic complexity, essential complexity, module design complexity, design complexity, integration complexity, the number of rows, standardization complexity, and global data complexity, the complexity of local data, pathological data complexity. McCabe complexity, the use of software engineering there are three kinds of use of McCabe complexity metric approach.
As a test of the auxiliary tool. McCabe complexity metric is equal to the results of the path through a number of subroutines, which need to design the same number of test cases to cover all of the paths. If the test is smaller than the complexity of the number of cases, there are three conditions: First, the need for more testing; two points can get rid of certain judgments; third is that some plug-in code can be used to determine point of replacement. As a program design and management guidelines. In software development, need a simple way to identify possible problems of the subroutine. To maintain a common method is a simple subroutine to set a length limit, for example, 50 lines or two, but it is actually simple in the absence of an effective test method can do nothing alternative. Many people believe that McCabe is such a simple measure of measure. However, to pay attention, McCabe metric several major procedures, is not necessarily a bad thing structured. For example, Case statement is a good structure, but may have great McCabe metric number (depends on the statement in the sub-C code rules compiler design and implementation of count), this may be due to problems and solutions inherent in the complexity of nature of the decision. Users should decide for themselves how to use the information provided by McCabe metrics.
As network complexity metric methods. Hall and Preiser proposed a combination of network complexity metrics for the measure may be caused by several programmers groups according to the modular principle to establish a large-scale software system complexity. McCabe complexity can be used to measure the complexity of each module can also be used to measure the network complexity.
Cyclomatic complexity: cyclomatic complexity is used to measure the complexity of the structure of a module to determine the extent of the quantity expressed as the number of independent paths, that is reasonably required for the prevention of wrong path to be tested for at least the number of big shows cyclomatic complexity code may be of low quality and difficult to test and maintenance, experience has shown that procedures might be wrong and a high cyclomatic complexity has a major contributing factor. Method of calculation program code node is the smallest unit, while the representative of the program flow between nodes.
Benefits: to avoid the tendency of software errors; pointed out that the extremely complex modules, such modules may be further refined; measurement test plan to determine test priorities: In the development process by limiting the program logic to guide the testing process: that will be the test area: to help testers determine the testing and maintenance of the object; with the high-level programming language used type. Application of cyclomatic complexity should be pointed out that the software quality testing to ensure that the minimum number of basic paths. In practice, the test is unrealistic for every one pass the test more difficult as the path increases. However, testing the basic path to measure the reasonableness of the complexity of the code is necessary. McCabe & Associates recommended cyclomatic complexity to 10, because of the high complexity of the circle to make testing even more complex and increases the probability of software errors generated.
Tip: cyclomatic complexity metric is a measure of a software module in the number of branches in all the development cycle to be used. Cyclomatic complexity metrics to the software architecture flowchart-based. Control flow chart describes the logical structure of software modules. In a typical language of a module is a function or subroutine, there is one entrance and one exit, you can also call / return mechanism design module. Software modules for each execution path, there is and from the module''s control flow chart of the entrance to the exit node consistent path.
"Cyclomatic" from the non-directly connected to the number of the basic test cycle, more importantly, yes., But also through directly connected to the chart gives the number of independent paths. Through the correlation chart, one node to another node. Cyclomatic complexity metrics can be used as the basic flow path of the number of modules, which focus on the module linear combination, the path generated by the number of the smallest. Cyclomatic complexity of the restrictions there are many good ways to limit cyclomatic complexity. The module is too complex and error-prone, difficult to understand, test, correction, so it should be in software development at all stages of the complexity of conscious limitations, many developers have successfully achieve the complexity limit the software as a software part of the project, although The exact number of the slightly controversial. The number of initial support is 10, now supports up to 15 numbers. However, should only be better in terms of the number of cases so that more than 10, for example, is very experienced developers, design in line with official standards, the use of modern programming language, structure, procedures, code walkthroughs, and advanced testing program. In other words, the development team can choose more than 10 the number of R-bands, but must make some trade-offs based on experience, the energy spent on the more complex modules.
Basic complexity: basic complexity is used to measure the degree program unstructured, non-structural components to reduce the quality of the program, increasing the difficulty to maintain the code makes the program difficult to understand. Thus, the basic unstructured high complexity means that a high degree of modularity and maintenance is difficult. In fact, the elimination of an error and sometimes give rise to other errors. Method of calculating the cyclomatic complexity of the structured part of the figure reduced to a point, after the flow chart to simplify the calculation of the cyclomatic complexity is the fundamental complexity.
Benefits: measure of unstructured degree; reflect the quality of the code; predict the amount of code maintenance; with the high-level programming language used type. When the basic complexity of applications is 1, this module is fully structured; as the basic complexity of greater than 1 but less than cyclomatic complexity, this module is part of the structured; as the basic circle is equal to the complexity of the complexity of this module is completely unstructured.
Module design complexity of module design complexity is used to measure the module to determine the structure, that is, modules and other modules of the call relationship. A high degree of software module design complexity means that the high heterozygosity module disaster, which will lead to the module difficult to isolate, maintain and reuse.
Compiler design and implementation of the calculation method of the module design complexity is removed from the module flow chart called sub-modules that do not contain the determination and circular structure of the ring obtained complexity, so the module design complexity can not be larger than the cyclomatic complexity is usually much smaller than the cyclomatic complexity.
Benefits: measure the module to its dominant role in the lower module; measure of a module to its integrated sub-module M the minimum number of test; location may be redundant code; to the complex computational logic and design to distinguish between modules; is the design complexity (Design Complexity, hereinafter referred to as SO) and integration complexity (Integration Complexity hereinafter referred to as S1) calculated on the basis; with the high-level programming language used type. Designed to measure quantitatively the complexity of interaction between program modules, which provides system-level overview of the module design complexity can help measure the bottom-up integration testing for the effect, but also provides a comprehensive measure of program design specifications and complexity of the data does not reflect the internal situation of independent modules. High-design. Complexity of the system means that parts of the system there are complex interrelationships between, this system will be difficult to maintain. SO is a program all the module design complexity combined.
Advantages: can be applied to complete the software can also be applied to any subsystem; pointed out that the complexity of a module as a whole, reflecting the modules of each module and the control of its internal relationships; reveals the complexity of the program module called degrees; help in the integrated complexity of calculations.
Integration complexity is to prevent the error must be carried out by the number of integration tests, said another way is to program the number of independent linear sub-tree, a sub-tree is a return to the calling sequence. Cyclomatic complexity as the number of paths to test, while the integrated complexity of a program or its sub-system of independent linear sub-tree.
Calculation method: a program of integration complexity and the complexity of a module of the ring is very similar, the program must calculate the full number of tests required for integration testing.
Advantages: help to integration testing of the implementation; quantitative integration testing and system design reflects the complexity; contribute to isolation from the overall system complexity. The number of rows (Number of Lines hereinafter referred to as nl), the total number of rows is the number of rows in the module, including code and comments.
Advantages: easy to compute, with the use type of high-level programming language has nothing to do; that the number of rows in the module (ie, module size), small-scale module easy to understand and maintain.
Normalized complexity (Normalized Complexity hereinafter referred to as nv): standardization of complexity is the cyclomatic complexity by dividing the number of rows. Calculation method: n-(G) / nl
Advantages: with the use type of high-level programming language has nothing to do; the definition of those with a significant density to determine the logic modules, these modules relative to other common standard modules need to do more maintenance work.
Global Data Complexity (Global Data Complexity hereinafter referred to as gdv (G))
Global data complexity (the need for McCabe Data) to quantify the modular structure and global data on the relationship between variables, it shows the module''s dependence on external data, while a global measure of test data, but also describes the coupling between modules relations, can reflect the potential maintenance issues.
Local Data complexity (Specified Data Complexity hereinafter referred to as sdv (G))
Local Data complexity (the need for McCabe Data) to quantify the module structure and the relationship between the user local data variables, while a partial measure of test data.
We can use the data dictionary McCabe Data choose the individual data elements that each data element of the specific data types. Local Data complexity also provides additional data selection criteria, to quantify the corresponding data for each module of the module control structure.
Pathological data complexity (Pathological Complexity hereinafter referred to as pv (G)) to measure a module that contains the full extent of unstructured elements, mark the question to jump into the code inside the loop, but these parts have the greatest degree of risk, often need to re-design .
Calculation method: Compiler design and implementation of all the non-structural elements to remove the circulating jumped into the structure, into a line structure, after the flow chart of cyclomatic complexity.
Advantages: with the use type of high-level programming language has nothing to do; pointed out the reliability problems, to help identify the most unreliable software. Pathological complexity is equivalent to Jane La''s maintenance risk; help Halstead Metrics.
McCabe language of choice can produce Halstead Metrics complexity. Halstead complexity there is a program operators and operands to count objects, to the number of times they appear as a count of targets (direct measurement of indicators), and accordingly calculate the program capacity, the workload.
5 System Testing
The compiler development time longer, so in the actual project development is divided into the following stages. Development of the main system, pre-processing subsystem, input-output subsystem, grammar subsystem; semantic subsystem. In each development phase, each subsystem should be unit testing to ensure accuracy, try not to an error into the next phase of development. In the development process, unit testing is mainly used two methods, one is writing test cases later in accordance with the code path of the side branch coverage test and so on. Another is to use the unit testing framework, writing test cases, the final results are generated for viewing. Upon completion of the compiler of the test, also carried out a with the same type of performance comparison between products in order to estimate the performance of the compiler.
Test, to the development phase of the compiler, as well as the other two versions of a C-source project as input for testing. In addition to testing the effectiveness of the compiler, we also need to test the time efficiency of the compiler is the compiler than the marked increase, which is also the re-development of an important requirement for the compiler targets. Test project for the system source code. These two test targets, the development of the compiler if the compiler to achieve the same function with equal effectiveness the right circumstances, the time usage to have a more significant upgrade, it will be able to achieve our purpose to develop the compiler.
6 System Outlook
As the subject of the relationship between the long development cycle, the compiler still has a lot to be perfected. Some specific details as well as the improvements have not yet fully realized, so in this article has not been reflected. In future versions of the compiler, you can also provide more powerful features.
First of all, the rules will provide a more complete examination, in a future version of the code rules will be gradually improved C compiler, so that it functions will be more perfect; Second, the current cross-platform compiler, even though it can run, but only corresponds to the Windows, Linux , Solaris, and for a number of embedded development system has not expanded accordingly, so future versions should be able to more platforms, so as to improve the tools for penetration; third, still need to improve the efficiency of tools, whether it is in the input subsystem, or the syntax, semantics and other sub-system is still feeling a great possibility to raise efficiency and should therefore be tested through the evaluation of the tool make the appropriate improvements; Finally, the tool does not provide a graphical interface, in a future version of the of the tool should be developed to achieve the corresponding version of the graphical interface, so as to enable the compiler the management and the use of more humane, easier to use.
