编译原理状态转化矩阵作用

① 通过运行状态转换图识别正则文法的句子。

求解啊

② 【万分紧急】这里想做一个优先矩阵（优先表）转换成优先函数的C语言程序（若是解决得好定追加更多！）

就是读取文件呗，你就按照一定的规则在文件中存储矩阵，读在按照规则读出来放到数组中。

③ 优先函数是什么编译原理

构造算符优先分析表时使用的优先函数，其等价于矩阵表，但存储量小。
定义两个函数，其对应元素的值为优先值，通过循环比较各元素的两个值，每次将优先级大的值改为小的值+1，若相等则都赋为目前较大的值，循环直至结果没有变化，构造OK

④ [高性能计算的三大研究领域]高性能计算领域的研究内容

科学计算、海量信息处理与检索以及正在普及的多核个人计算机是高性能计算的主要研究领域，由于领域的不同，对于高性能计算各自都有不同的研究重点。 美国宇航局(NASA)是超级计算机最大的用户之一

从起源来看，计算机系统的原始需求来自军事，如第一台计算机ENIAC是美国军队为了计算弹道而投资研制的。在随后的30年中，计大逗算机主要应用于与国家安全相关的领域，如核武器设计、密码破译等。到20世纪70年代末，高性能计算机开始应用于石油工业、汽车工业等资本密集型工业。随后，高性能计算机开始广泛进入各个行业，协助进行产品设计、用户分析等等。如医药公司使用高性能计算机辅助进行药物设计，可以大大节省新药的研发开支; 超市使用高性能计算机分析用户消费模式，以推出恰当促销措施等等。在这些领域，更高的计算性能就意味着在产品和服务方面的竞争优势。在科学研究领域，数值模拟方法成为现代科学方法的重要组成部分，这里更高的计算性能就意味着更快的科学发现速度。目前，高性能计算技术已成为促进科技创新和经济发展的重要手段，是一个国家综合国力的重要组成部分。本文将就高性能的几个最重要的应用领域进行介绍。
用高性能计算机解决科学挑战
许多重要的科学问题非常复杂，需要功能非常强大的计算机来进行数值模拟，这些问题被视作科学上的重大挑战，可以分为如下几类:
1. 量子化学、统计力学和相对论物理学;
搜纯2. 宇宙学和天体物理学;
3. 计算流体力学和湍流;
4. 材料设计和超导;
5. 生物学、制药研究、基因组序列分析、基因工程、蛋白质折叠、酶活动和细胞建模;
6. 药物、人类骨骼和器官建模;
7. 全球天气和环境建模。
这些重大世仿咐挑战问题大多可以看作传统的高性能计算应用的延伸，其特点是: 大部分是浮点密集型应用程序，并行算法要求多个并行进程之间进行较为频繁的通信和同步，而非简单的多个计算用例之间的并行，因此无法使用多台规模较小的系统来替代一台大规模系统。
这些重大挑战问题对计算能力的需求远远超出了现有的高性能计算机的性能。以量子化学计算为例，需要20T～100Tflops的持续计算能力才能够对目前进行的实际实验结果进行预测。在核聚变研究领域，需要20Tflops的持续计算能力才能够进行全规模的系统模拟。蛋白质折叠的计算需要1Tflops的持续计算速度。另一方面，重大挑战问题对数据的存储也提出了更高的要求，以计算生物学为例，进行蛋白质分析时需要使用的一台质谱仪每天就可以产生100GB的数据，50台质谱仪1天就可以产生5TB的数据。
目前，世界上最快IBM BlueGene/L的处理器个数为131072个，Linpack速度为280.6TFlops，达到了其峰值速度的76.5%（2005年11月数据）。但一般并行算法要比Linpack的通信更加频繁，访存局部性也没有Linpack好，这使得其并行效率相当低，通常仅能达到系统峰值速度的10％，甚至更低。为了能够有效地解决上述重大挑战性的问题，需要研制千万亿次高性能计算机系统，这就需要攻克系统结构、软件工具和并行算法等多方面的难关:

1. 能耗控制
随着现代处理器频率的增加，其功率也大幅度增加，最新处理器的功耗已经超过100W。这使得高性能计算系统本身的耗电问题已经十分严重。同时由于系统散发的大量热量，必须在机房中采用大功率的空调系统才能保持系统机房的正常温度。这两方面的因素造成系统的整体电能消耗非常巨大，维护成本很高。分析结果表明，未来系统主要的维护成本将来自系统的电能消耗。在研制千万亿次高性能计算机系统时，必须重视系统的能耗问题。
目前有几种方法来处理系统能耗问题，一是给处理器设定较低的工作电压，通过并行性来获得高性能，例如BlueGene/L处理器的工作频率仅有700Mhz，因此单个内核的处理能力远远低于其他高频率的处理器。但BlueGene/L通过大量的处理器来弥补单个处理器能力的不足，达到了较高的整体系统性能，并获得了优化的性能/能耗比。另一种方法是通过软件和硬件传感器确定和预测需要使用的部件和不需要使用的部件，然后将不需要立即使用的部分通过某种措施，如降低频率或完全关闭来减少其耗电量，从而达到降低整个系统功耗的目的。这方面的工作根据控制的粒度不同可分为芯片级、主板/BIOS级以及结点级。

2. 高性能计算软件与算法
大规模并行处理硬件系统仅仅为高性能计算提供了一个平台，真正的功能还要通过高性能计算软件来完成。高性能计算软件与算法的主要工作可以分为3类:
（1） 提出具有较低理论复杂度或较好实际性能的串行算法
尽管可以通过并行计算来加快运算的速度，但并行处理往往需要较大的软件开发成本和硬件成本，因此在进行并行算法的开发之前，必须考察是否存在可以解决问题的更好串行算法。以整数排序问题为例，使用并行的冒泡排序算法，其效果还不如使用串行的快速排序算法。因此，高效的串行算法研究是高性能算法研究的重要课题。着名的算法包括线性规划问题的单纯型法、FFT、快速排序、矩阵特征值的QR算法、快速多极算法等。近年来在算法方面的突破使印度学者在素数判定问题上提出了多项式复杂度算法。
（2） 优化现有算法
算法只提供了理论上的性能，要在实际系统上获得高性能，必须对算法的实现进行优化。现代处理器大多使用多级Cache来隐藏访存延迟，因此必须根据目标系统的Cache参数来优化算法的访存行为。此外，许多处理器还提供了SIMD指令，合理使用这些指令可以达到较高的性能。许多优化的数学库，如ATLAS、Intel公司的MKL等已经为不同的体系结构，特别是Cache配置进行了特别优化，可以达到较高的执行效率，为优化算法实现提供了很好的帮助。
(3) 并行算法与并行应用的开发
并行算法的研究与串行算法有联系也有区别。优秀的串行算法并不一定适合并行化，某些时候在串行算法中并非最优的算法在并行实现时却能体现出较大的优势。对于千万亿次计算机而言，其处理器（核）个数在10万以上，并行应用的并行度需要达到数万个并行进程才能有效地利用千万亿次计算机。并行算法的三个主要优化目标是: 通信优化、负载平衡以及最大化并行区。通信优化的目标是尽量减少通信次数和通信量，减少由于处理器之间通信带宽限制引起的性能下降。在大规模并行程序中，负载平衡问题也非常突出，少数负载不平衡的任务会使得整体性能急剧下降。同样的，根据Amdahl定律，应用加速比的上限是串行区所占比例的倒数，即应用中1％的串行区域就会使得整个应用程序的加速比不可能超过100。因此，要在数万个并行进程的情况下取得理想的加速比给并行算法的开发提出了很大的挑战。

3. 系统可靠性与可管理性
随着系统内结点个数的增加，系统失效的可能性也随着增大。并行程序的特点是只要有一个并行进程失败，整个并行程序都执行不成功。对可靠性问题的处理方法之一是设法提高系统的稳定性，这包括硬件系统可靠性和软件系统的可靠性。但目前公认的结论是: 大规模系统的故障是在设计时必须考虑的前提条件，而并非可以通过技术手段加以解决的问题。因此，必须考虑如何在系统结点出现故障的情况下仍然能够保证系统服务质量不发生显着下降。
故障监测技术和动态系统重构技术可以用来减少或消除系统失效对应用的影响，即尽快隔离出现问题的结点，使得用户可以使用状态正常的结点进行计算。与系统动态重构技术类似的技术还有系统动态划分技术，主要用于向不同的用户提供相互独立的结点集，使得整个系统的管理和使用更加有效和安全。
但是上述技术仅能解决系统对新的应用的服务质量问题，无法保证已经执行的应用在某个计算结点出现问题后的处理。某些并行应用，如石油数据处理需要连续运行几十天的时间，一旦某个结点出现错误，会使得前面的计算前功尽弃，需要从头开始计算。并行检查点技术主要提供应用级的容错，即能够自动地定期记录并行程序的状态（称作检查点），在计算过程中某个结点发生失效后，可以从所记录的并行程序检查点恢复执行，避免了重新执行整个程序。

高性能计算与海量信息处理

人类所产生的信息量以指数速度增长，如何存储、检索和利用这些信息为信息技术提出了重要挑战。从20世纪90年代开始，互联网的飞速发展给信息的传播与服务提供了新的机遇。传统的信息服务系统以数据库为中心，典型应用是OLTP（事务联机处理）。而以Google为代表的海量信息检索与处理服务是另一类重要应用，以Google集群系统为代表的系统体现了高性能计算系统的另一个发展方向。
信息检索与处理服务系统的特点与科学计算非常不同，对处理系统也提出了不同的要求:
1. 信息处理与服务应用需要频繁访问动态的数据结构，包含很多不可预测的分支，使得现有超标量处理器中的许多技术，如分支预测、数据预取、乱序和推测执行等功能无法很好地发挥作用，应用的指令级并行性较差。
2. 大部分信息处理与服务应用具有较好的数据并行性，可以很容易地在分布式系统上执行。以信息检索为例，一个信息检索请求可以被分配到多个服务器上进行并行检索，最后再将搜索结果统一处理返回给用户。这个过程中大多数的访问是只读的数据，并行任务之间的通信非常少，并行效率比较高。
3. 系统的性能指标一般不以单个服务请求的响应时间为量度，而更关注系统整体的吞吐率。以搜索引擎为例，信息服务系统更重视在1分钟内能够完成的用户搜索次数，而对单次搜索在0.5秒内完成还是1秒内完成并不特别敏感。
4. 系统需要很高的可靠性和可维护性。可靠性是对服务而言的，即组成的系统必须能够近乎不间断地为用户提供服务。可维护性是指系统的更换与维修可以简单快捷地完成，新更换的结点可以快捷地加入到系统中。
5. 低成本。这包括系统构建成本和总拥有成本两部分。海量信息处理和服务所需的系统规模极为庞大，Google Cluster在2003年就达到了15000台计算机的规模。如此巨大规模的系统，需要尽可能地降低成本。
为了能够有效满足上述信息处理与服务系统的要求，人们对于如何高效地构建相应的服务系统也展开了研究与实践:
1. 使用副本技术通过软件提供可靠性
在大规模系统中，单个系统结点的失效是不可避免的。现有的通过冗余底层硬件提高系统可靠性的方式，比如冗余电源、RAID技术等，成本较高，性价比较差。相反，在信息服务系统中可以广泛使用软件提供服务级别的可靠性。主要的方法是采用副本，即将服务和数据复制到多个系统结点上，即使单个系统结点的可靠性不是很高，多个副本提供了服务所需的可靠性。另一个使用副本技术的优点在于其提高系统可靠性的同时也提高了系统的性能，即保存副本的多个系统结点可以同时向用户提供服务。
2. 注重系统的性能/价格比
由于信息服务系统应用容易并行的特点，采用大量低端系统组合的方法比使用少量高端系统在性能价格比方面更具有优势（此处所指的低端系统是指1～2个CPU的PC机或入门服务器，高端系统是指大规模处理器服务器，如HP 的Superdom服务器、IBM的P690服务器等）。此外，信息服务系统与用于科学计算的高性能系统面临同样的挑战: 能耗问题。在大规模信息处理与服务系统中，电费成本（包括系统本身耗电和空调系统耗电）将占有总拥有成本的很大一部分。因此，在选用系统时，应选择性能/能耗比较高的系统也是一个重要的原则。
(3) 使用多内核处理器
由于信息服务程序的特点，它更适合使用多个简单内核构成的处理器，这些简单内核仅需要按序执行，并使用较短的流水线。由于信息服务应用的指令级并行度较差，按序执行不会造成太多的性能下降，但可以节省复杂的乱序执行单元电路，从而可以降低功耗。另一方面，较短的流水线可以降低分支预测失效的开销。
并行计算与个人计算机
随着半导体工艺的发展，单个芯片上能够集成的元件个数还将在5～10年内遵循摩尔定律继续以指数级增长。但是当前的芯片散热技术已无法支持芯片频率的进一步提高，而通过提高发射宽度、提高分支预测效率以及数据预取等进一步在体系结构上提高单线程执行速度的方法也逐渐失去了有效性。多内核芯片通过在一个芯片内集成多个处理器内核，采用线程级并行提高处理器性能，已成为微处理器的主要发展趋势。IBM公司在几年前就推出了双内核Power芯片，Intel公司和AMD在2005年推出的双内核芯片更是标志着多内核技术进入了普及阶段。支持更多核心的处理器芯片也正在快速涌现，如Sun公司已经推出了8核的Nigeria芯片，用于面向提高吞吐率的服务器应用; IBM则联合索尼和东芝推出了面向娱乐应用的9内核Cell芯片。Intel公司甚至已经在计划100内核以上的处理器。
多核处理器的出现给计算机的使用带来了新的挑战。随着多内核处理器的普及，成千上万的桌面电脑将成为并行计算机。目前在桌面机上执行的应用程序大多数是单线程程序，无法有效利用多内核处理器提供的能力。如何有效地在个人电脑上利用多个处理器内核成为高性能计算领域一个重要的研究课题，从目前的趋势来看主要有以下几个方向:
1.使用多任务带来的并发性
Intel的 双核ViiV家用电脑是这方面的典型例子。ViiV电脑的典型使用模式是一个人在客厅使用ViiV电脑看电影，另一个在自己的房间里使用同一台电脑玩游戏，两个人使用同一台电脑中的不同处理器内核，从而达到了有效发挥双核能力的目的。但这种依靠多个用户同时使用一台电脑的模式具有很大局限性，因为家庭成员的个数是有限的，对于4内核以上的多内核处理器，这种模式无法提供有效的支持。
2.聚合多内核的能力，加速串行程序的执行速度
计算机科学家们正在研究一种称作推测多线程（TLS: Thread-Level Speculation）的技术，该技术可以自动分析串行程序，推测其中能够并行执行的部分，在多个内核上并行执行。但一旦发现并行执行的部分有冲突，就撤销其中一个冲突线程的执行，执行补偿操作并重新执行该线程。推测多线程技术的优点在于无需用户干预就可以在多内核系统上加速现有单线程程序，其缺点在于对于性能提高的幅度有限,大约在4内核系统上仅能比在单个内核上提高性能30％，而且再增加内核数，其加速比也不会显着增加。因此，这种方式也无法支持更多内核的处理器。
另一种有前途的技术是自动并行化技术。自动并行化技术可以在编译时识别程序中的并行性，并将其转化为多线程并行程序。过去的自动并行化技术主要是面向SMP系统的，但不是很成功，原因是对真实应用程序，自动并行化无法得到满意的加速比。一个程序通过自动并行化在4 CPU的SMP系统上得到20%的加速比是不能令人满意的，因为4 CPU的系统通常价格是单CPU价格的10倍以上，自动并行化无法提供性能价格比上的优势。但是对于多内核系统，如果能够在四内核系统上通过自动并行化得到20％的加速比，应该是比较令人满意的结果，因为这些内核是“免费”提供给用户的，即用户无法用四内核处理器1/4的价格购买一个单内核处理器。因此，多内核处理器在家用电脑上的普及，将大大降低人们对自动并行化效果的期望，使得自动并行化技术重新被接受和应用。
3. 并行化现有的桌面应用
既然采用多内核处理器加速串行应用无法充分利用多内核处理器的能力，那么并行化现有的桌面应用就成为了一个重要选择。这方面的研究主要是分析现有的桌面应用，对有代表性的应用进行手工并行化，这些研究试图回答下面的问题: 哪些桌面应用能够被有效并行化，哪些不能？并行化本身的难度有多大？应如何改进现有的编程模型、编程工具以及系统软件来更好地支持应用的并行化？
研究表明，桌面系统上的大部分应用，如图像处理、3D图形运算、多媒体数据编码与解码、数据与文本挖掘、文本与媒体搜索、游戏与博弈等都可以有效地被并行化，并在多内核系统上得到有效的执行。但是，手工程序并行化的开销仍然很大，并行程序员需要了解并行计算的有关知识，并对计算机体系结构、操作系统、编译原理等有一定了解才能写出有效率的并行程序。并行编程模型与并行编程工具还需要提供更好的支持，以帮助并行程序员开发、调试并行程序。
今天，高性能计算技术已成为整个计算机领域的引领技术。多内核处理器的出现，使得并行计算技术将很快普及到我们的每台计算机，渗入到我们生活的方方面面，这是计算机产业发展史上的一个重大变革，对我国而言是一次难得的机会。在“十一五”期间，我国将进一步加强对高性能计算技术研究的支持，注重引导企业应用高性能计算技术促进产业升级和科技创新，同时更加特别重视高性能计算技术的教育培训工作，在高校的理工专业广泛开设并行程序设计课程，培养更多了解和使用高性能计算技术的人才，在此次变革中实现跨越性的发展。

作者简介
陈文光
清华大学计算机博士，清华大学计算机系副教授，863高性能计算机评测中心副主任。曾任Opportunity International Inc.总工程师。主要研究领域为并行计算的编程模型、并行化编译和并行应用分析。

链接:高性能计算发展趋势
随着应用的需求与计算机技术本身的发展，近年来高性能计算的发展体现出一些新的特点，可以用“大，宽，小”来代表这三个特点:
“大”是指高性能计算系统向更大规模发展，处理器个数可达10万个以上，主要用于解决超大规模的数值模拟问题。
“宽”是指在传统的数值计算之外，高性能计算系统正越来越广泛地应用于信息处理和服务领域，为海量信息的存储与检索以及网络服务提供有效的保证。
“小”是指多内核CPU的出现和普及，将使得今后的每台个人计算机都成为并行计算机，如何有效地利用个人计算机的多个内核是对高性能计算技术提出的新挑战。

⑤ 编译原理NFA转DFA ，请问DFA的初始状态如何确定

NFA确定化的时候，包含NFA初态的那个DFA状态就是确定后的DFA的初态。

DFA的终态就是所有包含了NFA终态的DFA的状态。

对于DFA来说，他的初态就是包含了NFA唯一初态1的那个状态，就是左边的1，2右边的1了。

脱氧核糖-磷酸链在螺旋结构的外面，碱基朝向里面。两条多脱氧核苷酸链反向互补，通过碱基间的氢键形成的碱基配对相连，形成相当稳定的组合。

(5)编译原理状态转化矩阵作用扩展阅读：

将DNA或RNA序列以三个核苷酸为一组的密码子转译为蛋白质的氨基酸序列，以用于蛋白质合成。密码子由mRNA上的三个核苷酸（例如ACU，CAG，UUU）的序列组成，每三个核苷酸与特定氨基酸相关。

例如，三个重复的胸腺嘧啶（UUU）编码苯丙氨酸。使用三个字母，可以拥有多达64种不同的组合。由于有64种可能的三联体和仅20种氨基酸，因此认为遗传密码是多余的（或简并的）：一些氨基酸确实可以由几种不同的三联体编码。

但每个三联体将对应于单个氨基酸。最后，有三个三联体不编码任何氨基酸，它们代表停止（或无意义）密码子，分别是UAA，UGA和UAG 。

⑥ 软考中级软件设计师要学会哪种程序设计语言（我只学过C，C++，汇编）

朋友，我考过，别听他们胡说
软件设计师考试分上午和下午
上午的考试是选择题目，范围很广
C和C++都有，但题目难度不大，汇编语言不考，建议多看看软件工程的理论知识，考得很多，特别在下午。还有操作系统，编译原理等跟计算机专业相关的理论
下面给出大纲：
软件设计师考试大纲
一、考试说明
1．考试要求：
(1) 掌握数据表示、算术和逻辑运算；
(2) 掌握相关的应用数学、离散数学的基础知识；
(3) 掌握计算机体系结构以及各主要部件的性能和基本工作原理；
(4) 掌握操作系统、程序设计语言的基础知识，了解编译程序的基本知识；
(5) 熟练掌握常用数据结构和常用算法；
(6) 熟悉数据库、网络和多媒体的基础知识；
(7) 掌握C程序设计语言，以及C++、Java、Visual、Basic、Visual C++中的一种程序设计语言；
(8) 熟悉软件工程、软件过程改进和软件开发项目管理的基础知识；
(9) 熟悉掌握软件设计的方法和技术；
(10) 掌握常用信息技术标准、安全性，以及有关法律、法规的基本知识；
(11) 了解信息化、计算机应用的基础知识；
(12) 正确阅读和理解计算机领域的英文资料。
2．通过本考试的合格人员能根据软件开发项目管理和软件工程的要求，按照系统总体设计规格说明书进行软件设计，编写程序设计规格说明书等相应的文档，组织和指导程序员编写、调试程序，并对软件进行优化和集成测试，开发出符合系统总体设计要求的高质量软件；具有工程的实际工作能力和业务水平。
3．本考试设置的科目包括：
(1) 计算机与软件工程知识，考试时间为150分钟，笔试；
(2) 软件设计，考试时间为150分钟，笔试。
二、考试范围
考试科目1：计算机与软件工程知识
1． 计算机科学基础
1.1 数制及其转换
• 二进制、十进制和十六进制等常用制数制及其相互转换
1.2 数据的表示
• 数的表示（原码、反码、补码、移码表示，整数和实数的机内表示，精度和溢出）
• 非数值表示（字符和汉字表示、声音表示、图像表示）
• 校验方法和校验码（奇偶校验码、海明校验码、循环冗余校验码）
1.3 算术运算和逻辑运算
• 计算机中的二进制数运算方法
• 逻辑代数的基本运算和逻辑表达式的化简
1.4 数学基础知识
• 命题逻辑、谓词逻辑、形式逻辑的基础知识
• 常用数值计算（误差、矩阵和行列式、近似求解方程、插值、数值积分）
• 排列组合、概率论应用、应用统计（数据的统计分析）
• 运算基本方法（预测与决策、线性规划、网络图、模拟）
1.5 常用数据结构
• 数组（静态数组、动态数组）、线性表、链表（单向链表、双向链表、循环链表）、队列、栈、树（二叉树、查找树、平衡树、线索树、线索树、堆）、图等的定义、存储和操作
• Hash（存储地址计算，冲突处理）
1.6 常用算法
• 排序算法、查找算法、数值计算方法、字符串处理方法、数据压缩算法、递归算法、图的相关算法
• 算法与数据结构的关系、算法效率、算法设计、算法描述（流程图、伪代码、决策表）、算法的复杂性
2． 计算机系统知识
2.1 硬件知识
2.1.1 计算机系统的组成、体系结构分类及特性
• CPU和存储器的组成、性能和基本工作原理
• 常用I/O设备、通信设备的性能，以及基本工作原理
• I/O接口的功能、类型和特性
• I/O控制方式（中断系统、DMA、I/O处理机方式）
• CISC/RISC，流水线操作，多处理机，并行处理
2.1.2 存储系统
• 主存-Cache存储系统的工作原理
• 虚拟存储器基本工作原理，多级存储体系的性能价格
• RAID类型和特性
2.1.3 安全性、可靠性与系统性能评测基础知识
• 诊断与容错
• 系统可靠性分析评价
• 计算机系统性能评测方式
2.2 软件知识
2.2.1 操作系统知识
• 操作系统的内核（中断控制）、进程、线程概念
• 处理机管理（状态转换、共享与互斥、分时轮转、抢占、死锁）
• 存储管理（主存保护、动态连接分配、分段、分页、虚存）
• 设备管理（I/O控制、假脱机）
• 文件管理（文件目录、文件组织、存取方法、存取控制、恢复处理）
• 作业管理（作业调度、作业控制语言（JCL）、多道程序设计）
• 汉字处理，多媒体处理，人机界面
• 网络操作系统和嵌入式操作系统基础知识
• 操作系统的配置
2.2.2 程序设计语言和语言处理程序的知识
• 汇编、编译、解释系统的基础知识和基本工作原理
• 程序设计语言的基本成分：数据、运算、控制和传输，过程（函数）调用
• 各类程序设计语言主要特点和适用情况
2.3 计算机网络知识
• 网络体系结构（网络拓扑、OSI/RM、基本的网络协议）
• 传输介质、传输技术、传输方法、传输控制
• 常用网络设备和各类通信设备
• Client/Server结构、Browser/Server结构
• LAN拓扑，存取控制，LAN的组网，LAN间连接，LAN-WAN连接
• 因特网基础知识以及应用
• 网络软件
• 网络管理
• 网络性能分析
2.4 数据库知识
• 数据库管理系统的功能和特征
• 数据库模型（概念模式、外模式、内模式）
• 数据模型，ER图，第一范式、第二范式、第三范式
• 数据操作（集合运算和关系运算）
• 数据库语言（SQL）
• 数据库的控制功能（并发控制、恢复、安全性、完整性）
• 数据仓库和分布式数据库基础知识
2.5 多媒体知识
• 多媒体系统基础知识，多媒体设备的性能特性，常用多媒体文件格式
• 简单图形的绘制，图像文件的处理方法
• 音频和视频信息的应用
• 多媒体应用开发过程
2.6 系统性能知识
• 性能指标（响应时间、吞吐量、周转时间）和性能设计
• 性能测试和性能评估
• 可靠性指标及计算、可靠性设计
• 可靠性测试和可靠性评估
2.7 计算机应用基础知识
•信息管理、数据处理、辅助设计、自动控制、科学计算、人工智能等基础知识
• 远程通信服务基础知识
• 常用应用系统
3． 系统开发和运行知识
3.1 软件工程、软件过程改进和软件开发项目管理知识
• 软件工程知识
• 软件开发生命周期各阶段的目标和任务
• 软件开发项目管理基础知识（时间管理、成本管理、质量管理、人力资源管理、风险管理等）及其常用管理工具
• 主要的软件开发方法（生命周期法、原型法、面向对象法、CASE）
• 软件开发工具与环境知识
• 软件过程改进知识
• 软件质量管理知识
• 软件开发过程评估、软件能力成熟评估基础知识
3.2 系统分析基础知识
• 系统分析的目的和任务
•结构化分析方法（数据流图（DFD）、数据字典（DD）、实体关系图（ERD）、描述加工处理的结构化语言）
• 统一建模语言（UML）
• 系统规格说明书
3.3 系统设计知识
• 系统设计的目的和任务
• 结构化设计方法和工具（系统流程图、HIPO图、控制流程图）
• 系统总体结构设计（总体布局、设计原则、模块结构设计、数据存储设计、系统配置方案）
• 系统详细设计（代码设计、数据库设计、用户界面设计、处理过程设计）
• 系统设计说明书
3.4 系统实施知识
• 系统实施的主要任务
• 结构化程序设计、面向对象程序设计、可视化程序设计
• 程序设计风格
• 程序设计语言的选择
• 系统测试的目的、类型，系统测试方法（黑盒测试、白盒测试、灰盒测试）
• 测试设计和管理（错误曲线、错误排除、收敛、注入故障、测试用例设计、系统测试报告）
• 系统转换基础知识
3.5 系统运行和维护知识
• 系统运行管理基础知识
• 系统维护基础知识
• 系统评价基础知识
3.6 面向对象开发方法
• 面向对象开发概念（类、对象、属性、封装性、继承性、多态性、对象之间的引用）
• 面向对象开发方法的优越性以及有效领域
• 面向对象设计方法（体系结构、类的设计、用户接口设计）
• 面向对象实现方法（选择程序设计语言、类的实现、方法的实现、用户接口的实现、准备测试数据）
• 面向对象程序设计语言（如C++、Java、Visual、Bsasic、Visual C++）的基本机制
• 面向对象数据库、分布式对象的概念
4． 安全性知识
• 安全性基本概念
• 防治计算机病毒、防范计算机犯罪
• 存取控制、防闯入、安全管理措施
• 加密与解密机制
•风险分析、风险类型、抗风险措施和内部控制
5． 标准化知识
• 标准化意识、标准化的发展、标准制订过程
• 国际标准、国家标准、行业标准、企业标准基本知识
• 代码标准、文件格式标准、安全标准、软件开发规范和文档标准知识
• 标准化机构
6． 信息化基础知识
• 信息化意识
• 全球信息化趋势、国家信息化战略、企业信息化战略和策略
• 有关的法律、法规
• 远程教育、电子商务、电子政务等基础知识
• 企业信息资源管理基础知识
7． 计算机专业英语
• 掌握计算机技术的基本词汇
• 能正确阅读和理解计算机领域的英文资料
考试科目2：软件设计
1． 外部设计
1.1 理解系统需求说明
1.2 系统开发的准备
• 选择开发方法、准备开发环境、制订开发计划
1.3 设计系统功能
• 选择系统结构，设计各子系统的功能和接口，设计安全性策略、需求和实现方法，制订详细的工作流和数据流
1.4 设计数据模型
• 设计ER模型、数据模型
1.5 编写外部设计文档
• 系统配置图、各子系统关系图、系统流程图、系统功能说明书、输入输出规格说明、数据规格说明、用户手册框架
• 设计系统测试要求
1.6 设计评审
2． 内部设计
2.1 设计软件结构
•按构件分解，确定构件功能规格以及构件之间的接口
• 采用中间件和工具
2.2 设计输入输出
• 屏幕界面设计、设计输入输出检查方法和检查信息
2.3 设计物理数据
• 分析数据特性，确定逻辑数据组织方式、存储介质，设计记录格式和处理方式
• 将逻辑数据结构换成物理数据结构，计算容量，进行优化
2.4 构件的创建和重用
• 创建、重用构件的概念
• 使用子程序库或类库
2.5 编写内部设计文档
• 构件划分图、构件间的接口、构件处理说明、屏幕设计文档、报表设计文档、文件设计文档、数据库设计文档
2.6 设计评审
3．程序设计
3.1 模块划分（原则、方法、标准）
3.2 编写程序设计文档
• 模块规格说明书（功能和接口说明、程序处理逻辑的描述、输入输出数据格式的描述）
• 测试要求说明书（测试类型和目标、测试用例、测试方法）
3.3 程序设计评审
4．系统实施
4.1 配置计算机系统及其环境
4.2 选择合适的程序设计语言
4.3 掌握C程序设计语言，以及C++、Java、Visual、Basic、Visual C++中任一种程序设计语言，以便能指导程序员进行编程和测试，并进行必要的优化
4.4 系统测试
• 指导程序员进行模块测试，并进行验收
• 准备系统集成测试环境和测试工具
• 准备测试数据
• 写出测试报告
5．软件工程
• 软件生存期模型（瀑布模型、螺旋模型、喷泉模型）和软件成本模型
• 定义软件需求（系统化的目标、配置、功能、性能和约束）
• 描述软件需求的方法（功能层次模型、数据流模型、控制流模型、面向数据的模型、面向对象的模型等）
• 定义软件需求的方法（结构化分析方法、面向对象分析方法）
• 软件设计（分析与集成、逐步求精、抽象、信息隐蔽）
• 软件设计方法（结构化设计方法、Jackson方法、Warnier方法、面向对象设计方法）
• 程序设计（结构化程序设计、面向对象程序设计）
• 软件测试的原则与方法
• 软件质量（软件质量特性、软件质量控制）
• 软件过程评估基本方法、软件能力成熟度评估基本方法
• 软件开发环境和开发工具（分析工具、设计工具、编程工具、测试工具、维护工具、CASE）
• 软件工程发展趋势（面向构件，统一建模语言（UML））
•软件过程改进模型和方法

⑦ 编译原理试题·

Lex和Yacc应用方法(一).初识Lex
草木瓜 20070301
Lex(Lexical Analyzar 词法分析生成器)，Yacc(Yet Another Compiler Compiler
编译器代码生成器)是Unix下十分重要的词法分析，语法分析的工具。经常用于语言分
析，公式编译等广泛领域。遗憾的是网上中文资料介绍不是过于简单，就是跳跃太大，
入门参考意义并不大。本文通过循序渐进的例子，从0开始了解掌握Lex和Yacc的用法。

一.Lex(Lexical Analyzar) 初步示例
先看简单的例子(注：本文所有实例皆在RetHat linux下完成):
一个简单的Lex文件 exfirst.l 内容：
%{
#include "stdio.h"
%}
%%
[\n] ;
[0-9]+ printf("Int : %s\n",yytext);
[0-9]*\.[0-9]+ printf("Float : %s\n",yytext);
[a-zA-Z][a-zA-Z0-9]* printf("Var : %s\n",yytext);
[\+\-\*\/\%] printf("Op : %s\n",yytext);
. printf("Unknown : %c\n",yytext[0]);
%%
在命令行下执行命令flex解析，会自动生成lex.yy.c文件：
[root@localhost liweitest]flex exfirst.l
进行编译生成parser可执行程序：
[root@localhost liweitest]cc -o parser lex.yy.c -ll
[注意：如果不加-ll链结选项，cc编译时会出现以下错误，后面会进一步说明。]
/usr/lib/gcc-lib/i386-redhat-linux/3.2.2/../../../crt1.o(.text+0x18): In function `_start':
../sysdeps/i386/elf/start.S:77: undefined reference to `main'
/tmp/cciACkbX.o(.text+0x37b): In function `yylex':
: undefined reference to `yywrap'
/tmp/cciACkbX.o(.text+0xabd): In function `input':
: undefined reference to `yywrap'
collect2: ld returned 1 exit status

创建待解析的文件 file.txt：
title
i=1+3.9;
a3=909/6
bcd=4%9-333
通过已生成的可执行程序，进行文件解析。
[root@localhost liweitest]# ./parser < file.txt
Var : title
Var : i
Unknown : =
Int : 1
Op : +
Float : 3.9
Unknown : ;
Var : a3
Unknown : =
Int : 909
Op : /
Int : 6
Var : bcd
Unknown : =
Int : 4
Op : %
Int : 9
Op : -
Int : 333
到此Lex用法会有个直观的了解：
1.定义Lex描述文件
2.通过lex，flex工具解析成lex.yy.c文件
3.使用cc编译lex.yy.c生成可执行程序

再来看一个比较完整的Lex描述文件 exsec.l ：

%{
#include "stdio.h"
int linenum;
%}
%%
title showtitle();
[\n] linenum++;
[0-9]+ printf("Int : %s\n",yytext);
[0-9]*\.[0-9]+ printf("Float : %s\n",yytext);
[a-zA-Z][a-zA-Z0-9]* printf("Var : %s\n",yytext);
[\+\-\*\/\%] printf("Op : %s\n",yytext);
. printf("Unknown : %c\n",yytext[0]);
%%
showtitle()
{
printf("----- Lex Example -----\n");
}
int main()
{
linenum=0;
yylex(); /* 进行分析 */
printf("\nLine Count: %d\n",linenum);
return 0;
}
int yywrap()
{
return 1;
}
进行解析编译：
[root@localhost liweitest]flex exsec.l
[root@localhost liweitest]cc -o parser lex.yy.c
[root@localhost liweitest]./parser < file.txt
----- Lex Example -----
Var : i
Unknown : =
Int : 1
Op : +
Float : 3.9
Unknown : ;
Var : a3
Unknown : =
Int : 909
Op : /
Int : 6
Var : bcd
Unknown : =
Int : 4
Op : %
Int : 9
Op : -
Int : 333
Line Count: 4
这里就没有加-ll选项，但是可以编译通过。下面开始着重整理下Lex描述文件.l。

二.Lex(Lexical Analyzar) 描述文件的结构介绍
Lex工具是一种词法分析程序生成器，它可以根据词法规则说明书的要求来生成单词识
别程序，由该程序识别出输入文本中的各个单词。一般可以分为<定义部分><规则部
分><用户子程序部分>。其中规则部分是必须的，定义和用户子程序部分是任选的。

(1)定义部分
定义部分起始于 %{ 符号，终止于 %} 符号，其间可以是包括include语句、声明语句
在内的C语句。这部分跟普通C程序开头没什么区别。
%{
#include "stdio.h"
int linenum;
%}
(2) 规则部分
规则部分起始于"%%"符号，终止于"%%"符号，其间则是词法规则。词法规则由模式和
动作两部分组成。模式部分可以由任意的正则表达式组成，动作部分是由C语言语句组
成，这些语句用来对所匹配的模式进行相应处理。需要注意的是，lex将识别出来的单
词存放在yytext[]字符数据中，因此该数组的内容就代表了所识别出来的单词的内容。
类似yytext这些预定义的变量函数会随着后面内容展开一一介绍。动作部分如果有多
行执行语句，也可以用{}括起来。
%%
title showtitle();
[\n] linenum++;
[0-9]+ printf("Int : %s\n",yytext);
[0-9]*\.[0-9]+ printf("Float : %s\n",yytext);
[a-zA-Z][a-zA-Z0-9]* printf("Var : %s\n",yytext);
[\+\-\*\/\%] printf("Op : %s\n",yytext);
. printf("Unknown : %c\n",yytext[0]);
%%
A.规则部分的正则表达式
规则部分是Lex描述文件中最为复杂的一部分，下面列出一些模式部分的正则表达式字
符含义：
A-Z, 0-9, a-z 构成模式部分的字符和数字。
- 指定范围。例如：a-z 指从 a 到 z 之间的所有字符。
\ 转义元字符。用来覆盖字符在此表达式中定义的特殊意义，
只取字符的本身。

[] 表示一个字符集合。匹配括号内的任意字符。如果第一个字
符是^那么它表示否定模式。例如: [abC] 匹配 a, b, 和C
的任何一个。

^ 表示否定。
* 匹配0个或者多个上述模式。
+ 匹配1个或者多个上述模式。
? 匹配0个或1个上述模式。
$ 作为模式的最后一个字符时匹配一行的结尾。
{ } 表示一个模式可能出现的次数。 例如: A{1,3} 表示 A 可
能出现1次或3次。[a-z]{5} 表示长度为5的，由a-z组成的
字符。此外，还可以表示预定义的变量。

. 匹配任意字符，除了 \n。
( ) 将一系列常规表达式分组。如：{Letter}({Letter}|{Digit})*
| 表达式间的逻辑或。
"一些符号" 字符的字面含义。元字符具有。如："*" 相当于 [\*]。
/ 向前匹配。如果在匹配的模式中的"/"后跟有后续表达式，
只匹配模版中"/"前面的部分。如：模式为 ABC/D 输入 ABCD，
时ABC会匹配ABC/D，而D会匹配相应的模式。输入ABCE的话，
ABCE就不会去匹配ABC/D。

B.规则部分的优先级

规则部分具有优先级的概念，先举个简单的例子：

%{
#include "stdio.h"
%}
%%
[\n] ;
A {printf("ONE\n");};
AA {printf("TWO\n");};
AAAA {printf("THREE\n");};
%%
此时，如果输入内容：
[root@localhost liweitest]# cat file1.txt
AAAAAAA
[root@localhost liweitest]# ./parser < file1.txt
THREE
TWO
ONE
Lex分析词法时，是逐个字符进行读取，自上而下进行规则匹配的，读取到第一个A字符
时，遍历后发现三个规则皆匹配成功，Lex会继续分析下去，读至第五个字符时，发现
"AAAA"只有一个规则可用，即按行为进行处理，以此类推。可见Lex会选择最长的字符
匹配规则。
如果将规则
AAAA {printf("THREE\n");};
改为
AAAAA {printf("THREE\n");};
./parser < file1.txt 输出结果为：
THREE
TWO

再来一个特殊的例子：
%%
title showtitle();
[a-zA-Z][a-zA-Z0-9]* printf("Var : %s\n",yytext);
%%
并输入title，Lex解析完后发现，仍然存在两个规则，这时Lex只会选择第一个规则，下面
的则被忽略的。这里就体现了Lex的顺序优先级。把这个例子稍微改一下：
%%
[a-zA-Z][a-zA-Z0-9]* printf("Var : %s\n",yytext);
title showtitle();
%%
Lex编译时会提示：warning, rule cannot be matched.这时处理title字符时，匹配
到第一个规则后，第二个规则就无效了。
再把刚才第一个例子修改下，加深下印象！
%{
#include "stdio.h"
%}
%%
[\n] ;
A {printf("ONE\n");};
AA {printf("TWO\n");};
AAAA {printf("THREE\n");};
AAAA {printf("Cannot be executed!");};
./parser < file1.txt 显示效果是一样的，最后一项规则肯定是会忽略掉的。

C.规则部分的使用变量
且看下面示例：
%{
#include "stdio.h"
int linenum;
%}
int [0-9]+
float [0-9]*\.[0-9]+
%%
{int} printf("Int : %s\n",yytext);
{float} printf("Float : %s\n",yytext);
. printf("Unknown : %c\n",yytext[0]);
%%
在%}和%%之间，加入了一些类似变量的东西，注意是没有;的，这表示int，float分
别代指特定的含义，在两个%%之间，可以通过{int}{float}进行直接引用，简化模
式定义。

(3) 用户子程序部分
最后一个%%后面的内容是用户子程序部分，可以包含用C语言编写的子程序，而这些子
程序可以用在前面的动作中，这样就可以达到简化编程的目的。这里需要注意的是，
当编译时不带-ll选项时，是必须加入main函数和yywrap(yywrap将下后面说明)。如：
...
%%
showtitle()
{
printf("----- Lex Example -----\n");
}
int main()
{
linenum=0;
yylex(); /* 进行Lex分析 */
printf("\nLine Count: %d\n",linenum);
return 0;
}
int yywrap()
{
return 1;
}

三.Lex(Lexical Analyzar) 一些的内部变量和函数
内部预定义变量：
yytext char * 当前匹配的字符串
yyleng int 当前匹配的字符串长度
yyin FILE * lex当前的解析文件，默认为标准输出
yyout FILE * lex解析后的输出文件，默认为标准输入
yylineno int 当前的行数信息
内部预定义宏：
ECHO #define ECHO fwrite(yytext, yyleng, 1, yyout) 也是未匹配字符的
默认动作

内部预定义的函数：
int yylex(void) 调用Lex进行词法分析
int yywrap(void) 在文件(或输入)的末尾调用。如果函数的返回值是1，就停止解
析。 因此它可以用来解析多个文件。代码可以写在第三段，这
样可以解析多个文件。 方法是使用 yyin 文件指针指向不同的
文件，直到所有的文件都被解析。最后，yywrap() 可以返回1
来表示解析的结束。

lex和flex都是解析Lex文件的工具，用法相近，flex意为fast lexical analyzer generator。
可以看成lex的升级版本。

相关更多内容就需要参考flex的man手册了，十分详尽。

四.关于Lex的一些综述
Lex其实就是词法分析器，通过配置文件*.l，依据正则表达式逐字符去顺序解析文件，
并动态更新内存的数据解析状态。不过Lex只有状态和状态转换能力。因为它没有堆栈，
它不适合用于剖析外壳结构。而yacc增加了一个堆栈，并且能够轻易处理像括号这样的
结构。Lex善长于模式匹配，如果有更多的运算要求就需要yacc了。

⑧ 对给定的正规式b(a|b)*aa,构造其NFA M，并将其确定化。

表示方法：五元组（S，Z，f，S0，z）

S：状态集

Z：字母表

f：映射关系

s0：初态

z：终态

（2）确定有限自动机DFA：f为单值映射

（3）非确定有限自动机NFA：f为多值映射

（4）状态转换图和状态转换矩阵

(8)编译原理状态转化矩阵作用扩展阅读

假定DFAMd＝（｛s0，s1，s2｝，｛a，b｝，f，s0，｛s2｝）：

f：

f（s0，a）＝s1f（s0，b）＝s2

f（s1，a）＝s1f（s1，b）＝s2

f（s2，a）＝s2f（s2，b）＝s1

试着给出Md的状态转换图和状态转换矩阵。

状态转换矩阵如下

ab

s0s1s2

s1s1s2

s2s2s1