北京理工大学软件学院编译原理第一次实验作业

《编译原理》第一次作业参考答案一、下列正则表达式定义了什么语言（用尽可能简短的自然语言描述）？1.bR(abRabR)R所有含有偶数个a的由a和b组成的字符串.2.cRa(a|c)Rb(a|b|c)R|cRb(b|c)Ra(a|b|c)R答案一：所有至少含有1个a和1个b的由a，b和c组成的字符串.答案二：所有含有子序列ab或子序列ba的由a，b和c组成的字符串.说明：答案一要比答案二更好，因为用自然语言描述是为了便于和非专业的人员交流，而非专业人员很可能不知道什么是“子序列”，所以相比较而言，答案一要更“自然”.二、设字母表∑={a,b}，用正则表达式（只使用a，b， ，|，R，+，？）描述下列语言：1.不包含子串ab的所有字符串.bRaR2.不包含子串abb的所有字符串.bR(ab?)R3.不包含子序列abb的所有字符串.bRaRb?aR注意：关于子串（substring）和子序列（subsequence）的区别可以参考课本第119页方框中的内容.~\(≧▽≦)/~~\(≧▽≦)/~~\(≧▽≦)/~~\(≧▽≦)/~~\(≧▽≦)/~~\(≧▽≦)/~~\(≧▽≦)/~~\(≧▽≦)/~《编译原理》第二次作业参考答案一、考虑以下NFA：1.这一NFA接受什么语言（用自然语言描述）？所有只含有字母a和b，并且a出现偶数次或b出现偶数次的字符串.2.构造接受同一语言的DFA.答案一（直接构造通常得到这一答案）：答案二（由NFA构造DFA得到这一答案）：二、正则语言补运算3.画出一个DFA，该DFA恰好识别所有不含011子串的所有二进制串.1.画出一个DFA，该DFA恰好识别所有不含011子串的所有二进制串.规律：构造语言L的补语言L’的DFA，可以先构造出接受L的DFA，再把这一DFA的接受状态改为非接受状态，非接受状态改为接受状态，就可以得到识别L’的DFA.说明：在上述两题中的D状态，无论输入什么符号，都不可能再到达接受状态，这样的状态称为“死状态”.在画DFA时，有时为了简明起见，“死状态”及其相应的弧（上图中的绿色部分）也可不画出.2.再证明：对任一正则表达式R，一定存在另一正则表达式R'，使得L(R')是L(R)的补集.证明：根据正则表达式与DFA的等价性，一定存在识别语言L(R)的DFA.设这一DFA为M，则将M的所有接受状态改为非接受状态，所有非接受状态改为接受状态，得到新的DFAM’.易知M’识别语言L(R)的补集.再由正则表达式与DFA的等价性知必存在正则表达式R’，使得L(R’)是L(R)的补集.三、设有一门小小语言仅含z、o、/（斜杠）3个符号，该语言中的一个注释由/o开始、以o/结束，并且注释1.请给出单个正则表达式，它仅与一个完整的注释匹配，除此之外不匹配任何其他串.书写正则表达式时，要求仅使用最基本的正则表达式算子（ ，|，R，+，？）.参考答案一：/o(oRz|/)Ro+/思路：基本思路是除了最后一个o/，在注释中不能出现o后面紧跟着/的情况；还有需要考虑的是最后一个o/之前也可以出现若干个o.参考答案二（梁晓聪、梁劲、梁伟斌等人提供）：/o/R(z/R|o)Ro/2.给出识别上述正则表达式所定义语言的确定有限自动机（DFA）.你可根据问题直接构造DFA，不必运用机械的算法从上一小题的正则表达式转换得到DFA.~\(≧▽≦)/~~\(≧▽≦)/~~\(≧▽≦)/~~\(≧▽≦)/~~\(≧▽≦)/~~\(≧▽≦)/~~\(≧▽≦)/~~\(≧▽≦)/~《编译原理》第三次作业参考答案一、考虑以下DFA的状态迁移表，其中0，1为输入符号，A~H代表状态：其中A为初始状态，D为接受状态，请画出与此DFA等价的最小DFA，并在新的DFA状态中标明它对应的原DFA状态的子集.说明：有些同学没有画出状态H，因为无法从初始状态到达状态H.从实用上讲，这是没有问题的.不过，如果根据算法的步骤执行，最后是应该有状态H的.二、考虑所有含有3个状态（设为p，q，r）的DFA.设只有r是接受状态.至于哪一个状态是初始状态与本问题无关.输入符号只有0和1.这样的DFA总共有729种不同的状态迁移函数，因为对于每一状态和每一输入符号，可能迁移到3个状态中的一个，所以总共有3^6=729种可能.在这729个DFA中，有多少个p和q是不可区分的（indistinguishable）？解释你的答案.解：考虑对于p和q，在输入符号为0时的情况，在这种情况下有5种可能使p和q无法区分：p和q在输入0时同时迁移到r（1种可能），或者p和q在输入0时，都迁移到p或q（4种可能）.类似地，在输入符号为1时，也有5种可能使p和q无法区分.如果再考虑r的迁移，r的任何迁移对问题没有影响.于是r在输入0和输入1时各有3种可能的迁移，总共有因此，总共有5R5R9=225个DFA，其中p和q是不可区分的.三、证明：所有仅含有字符a，且长度为素数的字符串组成的集合不是正则语言.证明：用反证法.假设含有素数个a的字符串组成的集合是正则语言，则必存在一个DFA接受这一语言，设此DFA为D.由于D 的状态数有限，而素数有无限多个，所以必存在两个不同的素数p和q（设p<q），使得从D的初始状态出发，经过p个a和q个a后到达同一状态s，且s为接受状态.由于DFA每一步的迁移都是确定的，所以从状态s 出发，经过(q-p)个a，只能到达状态s.考虑仅含有字母a，长度为p+p(q-p)的字符串T.T从初始状态出发，经过p个a到达状态s，再经过(q-p)个a 仍然到达s；同样，经过p(q-p)个a后仍然到达s.因此，从初始状态出发，经过p+p(q-p)个a后必然到达状态s.由于p+p(q-p)=p(q-p+1)是合数，而s为接受状态，因而得出矛盾.原命题得证.~\(≧▽≦)/~~\(≧▽≦)/~~\(≧▽≦)/~~\(≧▽≦)/~~\(≧▽≦)/~~\(≧▽≦)/~~\(≧▽≦)/~~\(≧▽≦)/~一、用上下文无关文法描述下列语言：1.定义在字母表∑={a,b}上，所有首字符和尾字符相同的非空字符串.S→aTa|bTb|a|bT→aT|bT|є说明：1.用T来产生定义在字母表∑={a,b}上的任意字符串；2.注意不要漏了单个a和单个b的情况.2.L={0i1j|i≤j≤2i且i≥0}.S→0S1|0S11|є3.定义在字母表∑={0,1}上，所有含有相同个数的0和1的字符串（包括空串）.S→0S1|1S0|SS|є思路：分两种情况考虑.1)如果首尾字母不同，那么这一字符串去掉首尾字母仍应该属于我们要定义的语言，因此有S→0S1|1S0；2)如果首尾字母相同，那么这一字符串必定可以分成两部分，每一部分都属于我们要定义的语言，因此有S→SS.二、考虑以下文法：S→aABeA→Abc|bB→d1.用最左推导（leftmostderivation）推导出句子abbcde.S==>aABe==>aAbcBe==>abbcBe==>abbcde2.用最右推导（rightmostderivation）推导出句子abbcde.S==>aABe==>aAde==>aAbcde==>abbcde3.画出句子abbcde对应的分析树（parsetree）.三、考虑以下文法：S→aSbS→aSS→1.这一文法产生什么语言（用自然语言描述）？所有n个a后紧接m个b，且n>=m的字符串.2.证明这一文法是二义的.对于输入串aab，有如下两棵不同的分析树3.写出一个新的文法，要求新文法无二义且和上述文法产生相同的语言.答案一：S→aSb|TT→aT|ε答案二：S→TS’T→aT|εS’→aS’b|ε~\(≧▽≦)/~~\(≧▽≦)/~~\(≧▽≦)/~~\(≧▽≦)/~~\(≧▽≦)/~~\(≧▽≦)/~~\(≧▽≦)/~一、考虑以下文法：S→aTUV|bVT→U|UUU→ε|bVV→ε|cV写出每个非终端符号的FIRST集和FOLLOW集.FIRST(S)={a,b}FIRST(T)={є,b}FIRST(U)={є,b}FIRST(V)={є,c}FOLLOW(S)={$}FOLLOW(T)={b,c,$}FOLLOW(U)={b,c,$}FOLLOW(V)={b,c,$}二、考虑以下文法：S→(L)|aL→L,S|S1.消除文法的左递归.S→(L)|aL→SL’L’→,SL’|ε2.构造文法的LL(1)分析表.FIRST(S)={‘(‘,‘a’}FIRST(L)={‘(‘,‘a’}FIRST(L’)={‘,’,ε}FOLLOW(S)={‘$’,‘,’,‘)’}FOLLOW(L)={‘)’}FOLLOW(L’)={‘)’}3.三、考虑以下文法：S→aSbS|bSaS|ε这一文法是否是LL(1)文法？给出理由.这一文法不是LL(1)文法，因为S有产生式S→ε，但FIRST(S)={a,b,ε}，FOLLOW(S)={a,b}，因而FIRST(S)∩FOLLOW(S)≠∅.根据LL(1)文法的定义知这一文法不是LL(1)文法.~\(≧▽≦)/~~\(≧▽≦)/~~\(≧▽≦)/~~\(≧▽≦)/~~\(≧▽≦)/~~\(≧▽≦)/~~\(≧▽≦)/~~\(≧▽≦)/~一、考虑以下文法：(0)E’→E(1)E→E+T(2)E→T(3)T→TF(4)T→F(5)F→FR(6)F→a(7)F→b1. 写出每个非终端符号的FIRST集和FOLLOW集.FIRST(E’)=FIRST(E)=FIRST(T)=FIRST(F)={a,b}FOLLOW(E’)={$}FOLLOW(E)={+,$}FOLLOW(T)={+,$,a,b}FOLLOW(F)={+,R,$,a,b}2. 构造识别这一文法所有活前缀（viableprefiRes）的LR(0) 自动机（参照课本4.6.2节图4.31）.~\(≧▽≦)/~~\(≧▽≦)/~~\(≧▽≦)/~~\(≧▽≦)/~~\(≧▽≦)/~~\(≧▽≦)/~~\(≧▽≦)/~~\(≧▽≦)/~《编译原理》第八次作业参考答案最终答案：34二、以下文法定义了二进制浮点数常量的语法规则：S→L.L|LL→LB|BB→0|1试给出一个S属性的语法制导定义，其作用是求出该二进制浮点数的十进制值，并存放在开始符号S相关联的一个综合属性value中。

汇编语言实验报告实验一 DOS环境下的汇编语言编程环境使用(基础与验证型）班级：05211002姓名：张宁学号：1120102310实验日期：2012.9.7晚6：00~9：00汇编语言实验报告实验一 DOS 环境下的汇编语言编程环境使用(基础与验证型）一、实验要求和目的1、掌握汇编语言程序设计的基本流程和学会上机开发简单程序；2、熟练掌握宏汇编程序MASM 的使用；3、熟练掌握连接程序LINK 的使用；4、熟练掌握DEBUG 的使用；二、软硬件环境1、硬件环境：计算机系统windows；2、软件环境：装有MASM、DEBUG、LINK、等应用程序。

三、实验涉及的主要知识汇编语言程序设计上机开发过程如图1.1 所示。

四、实验内容与步骤1、汇编、链接并调试给出的简单程序，找出程序中的错误。

（一）录入并建立汇编语言源程序文件(ASM 文件)（二）用汇编程序MASM 将ASM 文件汇编成目标程序文件(OBJ 文件)（三）用连接程序LINK 生成可执行程序文件(EXE 文件)（四）程序的调试2、完成程序设计：分类统计字数组data 中正数、负数和零的个数，并分别存入内存字变量Positive、Negative 和Zero 中，数组元素个数保存在其第一个字中。

使用Debug 查看Positive、Negative 和Zero 三个变量的数据。

五、实验过程及结果：实验一：1.输入给出的程序2.运行输入的程序，发现了三处错误：根据错误提示，发现错误为ADDITION后未打冒号，CMP错打为COM。

修改原代码:改为：3.代码编译成功，生成OBJ文件，再生成EXE文件，可成功运行。

4.在原程序代码后添加两行代码，以验证ADDITION的逻辑正确性，改动如下：现实在DA TA1中添加字节型sum ，再将ADDITION的运行结果，从AX送到sum中去。

5.调试发现ADDITION并没用正确运行。

检查语句逻辑性发现，应将JAE改成JB，才能实现累加并终结。

《数据结构与算法设计》实验报告——实验一学院：自动化学院班级：06111001学号：1120100001姓名：宝竞宇一、实验目的实现链表的基本操作，如：建立，插入，删除等。

应用链表解决实际问题。

二、实验内容采用单向环表实现约瑟夫环。

①从键盘输入整数m，通过create函数生成一个具有m个结点的单向环表。

环表中的结点编号依次为1，2，……，m。

②从键盘输入整数s（1<=s<=m）和n，从环表的第s个结点开始计数为1，当计数到第n个结点时，输出该第n结点对应的编号，将该结点从环表中消除，从输出结点的下一个结点开始重新计数到n，这样，不断进行计数，不断进行输出，直到输出了这个环表的全部结点为止。

例如，m=10，s=3，n=4。

则输出序列为：6，10，4，9，5，2，1，3，8，7。

三、程序设计1、概要设计本程序要用到一个抽象的数据类型：链表节点。

其中包括一个数值项，和指针项。

宏定义“错误”，与程序成功后返回的“成功。

”建立一个“生成函数”来生成，环表。

在建立一个“查找输出函数”，来实现约瑟夫的输出。

在主程序中先定义一个链表节点定义，然后在调用“生成函数”来生成约瑟夫表。

接下来调用“查找输出函数”，输出题目要求的数字编号序列。

2、详细设计抽象数据类型定义：typedef struct NODE{int num;struct NODE *next;}linklist;宏定义：#define ERROR 0#define OK 1生成函数：该函数的输入值为n值，返回为linklist型的指针变量指向生成的环表的头结点。

其中先定义一个头结点，给其分配储存空间head=p=(linklist*)malloc(sizeof(linklist));然后再用一个for循环连续的生成，插入节点到该函数中for(i=2;i<=n;i++){q=(linklist *)malloc(sizeof(linklist));if(q==0)return(ERROR);q->num=i;p->next=q;p=q;}程序错误返回ERROR。

编译原理第一次作业第一章1.6.1（a）X=9 Y=13 Z=9 w=13（b）X=7 Y=13 Z=7 W=91.6.3答案：1.6.4答：打印结果是：32第三章3.3.2（1）a( a|b )*a答: 穷举法{ aa, aaa, aba, aaaa, aaba, abaa, abba, ... }（2）（（ε|a)b*））*答: 由 a 和 b 组成的任意符号串（3）（a|b）* a(a|b)(a|b)答: 倒数第 3 个符号为 a 的长度大于等于 3 的a,b串（4）a*ba*ba*ba*答: 有且仅有三个 b 的由 a 和 b 构成的所3.3.5（1）包含 5 个元音的所有小写字母串，这些串中的元音按顺序出现答：e.g. :{ aeiou, xaxeiou, xaxabcxeeiioouu... }consonant->[b-df-hj-np-tv-z]ctnvowels->(consonant*)(((a+)(consonant*))+)(((e+)(consonan t*))+)(((i+)(consonant*))+)(((o+)(consonant*))+)(((u+)(consonant*))+) 注：consonant 为除五元音外的小写字母，记号ctnvowels 对应的定义即为题目要求的正则定义。

(2) 所有由按字典顺序递增序排列的小写字组成的串。

答：答：a*b*……z*（3)注释，即/*和*/之间的串，且串中没有不在双引号（“）中的*/。

答：head——>/*tail ——>*/incomment->(~(*/)|“. *”) *comment->head incomment tail（9）所有由 a 和 b 组成且不含有子串abb的串。

答：A->b *(a︱ab)* 33.4.1（1）a( a|b )*a 的状态转换图如下：（2）（3）（4）3.7.3（1）○1将正则表达式转化为NFA○2根据子集构造法由NFA构造DFA。

北京理工大学汇编语言实验报告实验五子程序设计实验实验五子程序设计实验（设计性实验）一、实验要求和目的1．熟悉汇编语言程序设计结构；2．熟悉汇编语言子程序设计方法；3．熟悉利用汇编语言子程序参数传递方法；4．熟悉汇编语言字符串处理基本指令的使用方法；5．掌握利用汇编语言实现字符串的输入输出程序设计方法；6．掌握数制转换程序实现方法。

二、软硬件环境1、硬件环境：计算机系统windows；2、软件环境：装有MASM、DEBUG、LINK、等应用程序。

三、实验涉及的主要知识A）子程序知识要点：1、掌握子程序的定义语句；过程名 PROC [near/far]过程体RET过程名 ENDP2.子程序结构形式一个完整的子程序一般应包含下列内容:1. ）子程序的说明部分在设计了程序时,要建立子程序的文档说明,使用户能清楚此子程序的功能和调用方法. 说明时,应含如下内容:.子程序名:命名时要名中见意..子程序的功能:说明子程序完成的任务;.子程序入口参数:说明子程序运行所需参数及存放位置;.子程序出口参数:说明子程序运行结果的参数及存放位置;.子程序所占用的寄存器和工作单元；.子程序调用示例；2、）掌握子程序的调用与返回在汇编语言中，子程序的调用用CALL，返回用RET 指令来完成。

.段内调用与返回：调用子程序指令与子程序同在一个段内。

因此只修改IP；.段间调用与返回：调用子程序与子程序分别在不同的段，因此在返回时，需同时修改CS：IP。

3．）子程序的现场保护与恢复保护现场：在子程序设计时，CPU 内部寄存器内容的保护和恢复。

一般利用堆栈实现现场保护和恢复的格式：过程名PROC [NEAR/FAR]PUSH BXPUSH DXPOP DXPOP AXRET过程名 ENDP4.子程序的参数传递方法1．寄存器传递参数这种方式是最基本的参数传递方式。

2．存储器单元传（变量）递参数这种方法是在主程序调用子程序前，将入口参数存放到约定的存储单元中；子程序运行时到约定存储位置读取参数；子程序执行结束后将结果也放在约定存储单元中。

编译原理第一次上机实验报告姓名：李x班级：软工140x班学号：U2014172xx实验一设计实现简单语言的词法分析器1、实验目的通过该实验,熟练应用编译原理关于词法分析的基本理论和方法；学会用C/C++高级程序设计语言设计一个词法分析器；加深对编译原理理论的分析理解，提高实际操作和解决具体问题的能力。

2、实验条件计算机上安装C/C++编译处理软件。

3、实验内容及要求对下述单词表定义的语言设计编制一个词法分析器。

单词符号及种别表和词法分析器功能及基本要求如下：（1）单词符号及种别表（2）词法分析器功能及基本要求处理用户提交的符合上述词法的源代码序列，进行词法分析，并输出单词二元组。

(1)总体设计思想算法的基本任务是从字符串表示的源程序中识别出具有独立意义的单词符号，其基本思想是根据扫描到单词符号的第一个字种类，拼出相应的单一符号；(2)详细算法设计当ch!=’$’时，while循环扫描输入的每一个字符；跳过空格、换行、注释；如果是字符，则拼字符串；判断是否为关键字，是则输出对应关键字的单词种别码，否则表明是l(l|d)*即内部字符串；如果是数字，则拼数，整型、浮点型、指数；如果是运算符、界符，输出相应种别码；算符中应该注意+号和-号，做出相应判断是运算符还是表示数字的正负号；如果是表示正负号则调到判断数字的地方；其他则报错；(3) 流程框图(4) 函数相关说明void main()主函数void scanner()扫描判断函数char input[300];//存放输入的字符串char token[20];//存放符合C语言词法规则的单词char ch;//单个字符char previous;//ch的前一个字符char latter;//ch的后一个字符char ch1, ch2;//当处理注释的时候使用int typenum;//表示单词的种别码int p, m, n, cx;double decimal;//记录小数double sum;//存放数字int index;//存放指数int isNum;//是否是数字int isDecimal;//记录是否为小数int isExp;//记录是否为指数int isNegative;//是否带负号（对于指数）int isNegative1;//是否为负数(5)输入与输出（包括出错处理）输入以$结束回车即可运行程序输出以（xxx,typenumber）的形式;出错则会报error!例如：输入：a+b=5$输出：(10, a)(22, +)(10, b)(21, =) (20, 5)(0, $)(6) 程序运行结果（屏幕截图）1.+++-123.456e-127*+45.99e+200++abc+-cnt++49(7) 词法分析器使用说明打开编译器VS或者VC++；文件→新建→项目；将代码复制粘贴，编译运行，按照提示输入即可使用；(8) 心得与体会提高了自己的编程能力，在上机实验中，特别是后期细节的处理很繁琐，需要很多的判断，判断+、-号是否为数字正负号时需要判断前面和后面的字符；又分为好几种情况，每一种情况的判断语句很长容易出错；同时还有指数的处理，e/E后面需要判断正负号以及把字符转换成数字以及识别数字的DFA和运算符加减等融合在一起；(9) 源程序清单// 词法编译器01.cpp : 定义控制台应用程序的入口点。

1.一元多项式相加(10分)成绩: 10 / 折扣: 0.8题目说明：编写一元多项式加法运算程序。

要求用线性链表存储一元多项式（参照课本）。

该程序有以下几个功能：1. 多项式求和输入：输入三个多项式，建立三个多项式链表Pa、Pb、Pc（提示：调用CreatePolyn(polynomial &P,int m)。

输出：显示三个输入多项式Pa、Pb、Pc、和多项式Pa+Pb、多项式Pa+Pb+Pc （提示：调用AddPolyn(polynomial &Pa, polynomial Pb), 调用PrintPolyn(polynomial P))。

0. 退出输入：根据所选功能的不同，输入格式要求如下所示（第一个数据是功能选择编号，参见测试用例）：∙ 1多项式A包含的项数，以指数递增的顺序输入多项式A各项的系数（整数）、指数（整数）多项式B包含的项数，以指数递增的顺序输入多项式B各项的系数（整数）、指数（整数）多项式C包含的项数，以指数递增的顺序输入多项式C各项的系数（整数）、指数（整数）∙0 －－－操作终止，退出。

输出：对应一组输入，输出一次操作的结果（参见测试用例）。

∙ 1 多项式输出格式：以指数递增的顺序输出: <系数,指数>,<系数,指数>,<系数,指数>,参见测试用例。

零多项式的输出格式为<0,0>∙0 无输出1.#include<iostream>#include<stdlib.h>using std::cin;using std::cout;using std::endl;struct date{int a;int b;struct date* pnext;};typedef struct date DATE;typedef struct date* PDATE;void output(PDATE p){int f=0;p=p->pnext;while(p!=NULL){if(p->a!=0){f=1;cout<<"<"<<p->a<<","<<p->b<<">";if(p->pnext==NULL)cout<<endl;elsecout<<",";}p=p->pnext;}if(f==0)cout<<"<0,0>"<<endl;}void add(PDATE a,PDATE b,PDATE c){PDATE p1,p2,p3;p1=a;p2=b;p3=c;if(p1!=NULL) p1=p1->pnext; //skip head if(p2!=NULL) p2=p2->pnext;while((p1!=NULL)&&(p2!=NULL)){if(p1->b>p2->b){p3->pnext=(PDATE)malloc(sizeof(DATE));p3=p3->pnext;p3->a=p2->a;p3->b=p2->b;p3->pnext=NULL;p2=p2->pnext;}else if(p1->b<p2->b){p3->pnext=(PDATE)malloc(sizeof(DATE));p3=p3->pnext;p3->a=p1->a;p3->b=p1->b;p3->pnext=NULL;p1=p1->pnext;}else{p3->pnext=(PDATE)malloc(sizeof(DATE));p3=p3->pnext;p3->a=p1->a+p2->a;p3->b=p1->b;p3->pnext=NULL;p1=p1->pnext;p2=p2->pnext;}}//end whileif(p1==NULL)p3->pnext=p2;if(p2==NULL)p3->pnext=p1;}int main(){int flag;int n;PDATE P[6]={NULL};PDATE p=NULL;for(int i=0;i<6;i++){P[i]=(PDATE)malloc(sizeof(DATE));P[i]->a=0;P[i]->b=0;P[i]->pnext=NULL;}cin>>flag;if(flag==1){for(int i=1;i<4;i++){p=P[i];cin>>n;while(n--!=0){p->pnext=(PDATE)malloc(sizeof(DATE));p=p->pnext;cin>>p->a>>p->b;p->pnext=NULL;}output(P[i]);}}add(P[1],P[2],P[4]);output(P[4]);add(P[4],P[3],P[5]);output(P[5]);}0 约瑟夫问题(10分)成绩: 10 / 折扣: 0.80 约瑟夫问题成绩10分折扣0.8(本题要求用循环链表实现)0 ,1, 2, 3题,只能选做三题.约瑟夫问题是一个经典的问题。

作业一：
1，简述多道程序设计技术的基本思想。

为什么采用多道程序设计技术可以提高资源的利用率？
答：多道程序设计技术通过组织作业使CPU总有一个作业可执行，从而提高了CPU的利用率。

在单通道技术中，对于每个作业，操作系统占用时长均为CPU处理时间加上I/O时间，多个作业处理情况下，时间为单个作业处理时间的累加，CPU在第一个作业处理I/O时不会对其他作业进行处理。

而通过多道程序设计技术，将作业分为I/O部分与CPU处理部分，在这种情况下，操作系统将作业进行I/O的时间合理的利用了起来，多个作业可以并发执行，I/O设备和CPU同时工作，实现并行。

操作系统在进行一个作业的I/O时，CPU不进入等待的过程，而是对其他作业进行处理，避免了资源的浪费，所以提高了资源的利用率。

2，举一个现实生活中的并发和共享的例子。

答：并发：
在大学生体检过程中，有很多项目，但是为了提高效率不是一个人将所有项目都完成后才进行下一个人，而是让每个
体检项目的医生都处于忙碌状态，体检完一个人后，立马体
检另一个人，在这里每个人就相当于一个作业，有的医生相当
于CPU，有的医生相当于I/O等。

体现了并发。

共享：
互斥共享方式：
在上课过程中，不同课程共享同一间教室，每一个教室在一个时间段内只允许上一节课，只有一节课上完，才能上另一节课。

同时访问方式：
在课间这个时间段内，多个同学都向老师提问问题，在这个宏观的角度来看，是同时发生的，但是细分到小的时间间隔，这些交替进行的，可能一个同学问一句，另一个同学问一句，体现了同时访问。

实验一请在数据段中定义两个数，要求编写程序分别计算出这两个数的和、差、积、商，并用Debug 的相关命令查询计算结果。

(略)实验二内存自TABLE开始的连续16个单元中存放着0 —15的平方值，查表求DATA中任意数X(0 < X < 15)的平方值，并将结果放在RESULT中。

DATA1 SEGMENTTABLE DB 0,1,4,9,16,25,36,49,64,81,100,121,144,169,196,225DATA DB 10RESULT DB ?DATA1 ENDSSTAC SEGMENTDB 100 DUP (?)STAC ENDSCODE SEGMENTASSUME DS:DATA1,SS:STAC,CS:CODESR:MOV AX,DATA1MOV DS,AXMOV AX,STACMOV SS,AXLEA BX,TABLEMOV AH,0MOV AL,DATAXLATMOV RESULT,ALMOV AH,4CHINT 21HCODE ENDSEND SR实验三试编写一程序：比较两个字符串STRING1和STRING2所含的字符是否相同。

若相同则显示'MATCH,否则显示’NO MATC'DATA1 SEGMENTSTRING1 DB 10,?,10 DUP (?)STRING2 DB 10,?,10 DUP (?)REM1 DB 'PLEASE INPUT STR1: $'REM2 DB 'PLEASE INPUT STR2: $'MESS1 DB 'MATCH$'MESS2 DB 'NO MATCH$'DATA1 ENDSCODE1 SEGMENTASSUME CS:CODE1,DS:DATA1STT: MOV AX,DATA1MOV DS,AXMOV ES,AXLEA DX,REM1MOV AH,09HINT 21HLEA DX, STRING1MOV AH, 0AHINT 21HMOV DL, 0DHMOV AH, 6INT 21HMOV DL, 0AHMOV AH, 6INT 21HLEA DX,REM2MOV AH,09HINT 21H LEA DX, STRING2 MOV AH, 0AH INT 21H MOV DL,0DH MOV AH,6 INT 21H MOV DL,0AH MOV AH,6 INT 21H LEA SI, STRING1LEA DI,STRING2MOV CL,[SI+1]MOV BL,[DI+1]CMP CL,BLJNE NOMCLDMOV CH,0ADD CL,2REPZ CMPSBJNZ NOMMAT: LEA DX,MESS1JMP SHORT DISP1NOM: LEA DX,MESS2DISP1: MOV AH,09HINT 21HMOV AH,4CHINT 21HCODE1 ENDSEND STT实验四设有10 个学生的成绩分别为：56，69，84，82，73，88，99，63，100，80 分。

第1次作业一、单项选择题（本大题共100分，共40小题，每小题2.5分）1. 若执行以下程序段，其运行结果是（）char c [[二{'a', ' b', ' \0', ' c', ' \0'} ; printf （，，%s\n ，/, c ）; A. ab cB. 'a''b'C. abcD. ab2. 一个C 语言程序是由（）组成A.主程序B.子程序C.函数D.过程3. 已知各变量定义如下：int i 二& a, b; double x=l. 42, y=5. 2;则以下符合C 语言语法的表达式是 （）A. a+二a -二（b 二4） * （a 二3）B. ei 二a*3二2C. x%（-3）D.（y+i ）++ 4. 下列程序的输岀结果为()void main () { int &□二{1, 2, 3, 4, 5}, *p;P=a; * (p+4)+=5;printf %d\n\ *p, * （p+4））; } A. 4,10 B. 10,4 C. 1,4 D. 1, 105. 下列数据屮，属于“字符串常量”的是（）A. Abcddd B. 〃3bcddd 〃 C. ，abcddd ， D. <a ,6. 以下语句或语句组中，能正确进行字符串赋值的是（）A. char*sp;*sp 二〃right!" B. char s[10];s 二〃right!〃 C. char s[10];*s 二〃right!〃 D. char *sp 二〃right!"7. 已知 long a=-2L ； printf （z ，%d\ n ，z , a ）；则有（）A.赋值不合法 B. 输出值为-2 C.输出为不确定值D.输出值为2&在C 语言屮，类型名char 表示的数据类型是（）A.实型B.字符型C. 整型D.双精度实型9. 判断char 型变量cl 是否小写字母的正确表达式为（）A.，a<=cl<=z ，B. （cl>二'a'）&&（cl 〈二'z'） C. （cl>=a ）&&（cl<=z ） D.（务‘〈二cl ） | | （'z'>二cl ）10. 下列有关共同体说法正确的是（）A.任一时刻，只有一个分量有效，其他 分量无意义B.共同体变量可以用作函数参数C.结构变量可以出现在共同体 类型中，而共同体变量不能出现在结构类型中D.在定义共同体变量时不能为 其初始化11・以下程序的输岀结果是（）void main （） {int x=020^ y=0x20^ z=20; 32, 16, 20 C. 16, 32, 20 D. 20, 32, 20printf 冷 * z) ; } A. 20, 20, 20 B.12.若有运算符:>、*二、==、%、sizeof,则它们按优先级(由低至高)的正确排列次序为()A. *二-> ==->>->% -> sizeof B. == -> *二->>->% -> sizeof C. *二-〉 > -〉二二-〉sizeof -> % D. *二-〉 > -〉二二 -〉% -> sizeof13.char s[]二” student”，*(s+2)的值是()A.，u，B. <d,C. “s' D. 't'14.用C语言编写的源程序，必须经过编译、连接和运行才能得到结果。

《编译原理》课程实验报告实验地点实验时间实验名称：第一次使实验实验目的：重温C语言程序设计，重温程序设计从编辑、编译到连接的全过程，理解编译器的重要性。

实验要求（详见实验讲义与实验指导书）：1）键盘输入任意字符串，统计其中数字、字母的个数并输出到终端。

输入：字符串输出：(数字，SUMD);(字母，SUML)其中SUMD和SUML分别为统计出的数字和字母的个数。

2）查找给定文件中的C语言注释行，并输出其内容。

输入：文本文件“test.txt”输出：文件中C语言注释行的内容（注：结果同时输出到文件）提示：注释行以“/* */”或“// ”标示实验内容及关键步骤（算法描述（流程图或伪代码）、代码）1.1、算法描述（1）输入一个字符串（2）使用for循环检测每个字符，判断是否为字母或数字，判断的条件：字母：if(str[i] >= 'A'&&str[i] <= 'Z'|| str[i] >= 'a'&&str[i]<='z'){字母数量++;}数字：if(str[i] >='0'&&str[i]<='9'){ 数字数量++; } （3）输出最后结果1.2、流程图描述是否是否是否开始 输入字符串 循环检测每个字符 当前字符为字母 当前字符为数字 i++ i<字符串长度 字母数量++数字数量++输出结果结束2.1、算法描述（1)读取的模式打开一个txt的一个文件，逐行读入文件的内容（2)检测每行中的每个字符，判断是否为//注释行或为/**/注释行（3)判断条件//注释行：if (buffer[i] == '/'&&buffer[i + 1] == '/'&&op ==false){//当前的字符为’/‘，下个字符为‘/’直接输出注释行内容跳出当行的字符循环}/**/注释行if (op == true){该字符是/**/内的字符，将该字符保存到pstr的字符串中}if (buffer[i] == '/'&&buffer[i + 1] == '*'){以下是/**/注释行的内容memcpy(pstr, p + i, 1);//拷贝当前字符op = true;//设置注释行的类型，当前为/**/的类型}if (buffer[i] == '*'&&buffer[i + 1] == '/'&&op == true){检测到注释行的内容结束memcpy(pstr, p + i+1, 1);//拷贝当前字符continue;}（4)输出结果2.2、算法流程图统计数字和字母数量的结果截图：实验过程中遇到的问题解决办法与实验体会在这次的实验中基本没遇到什么问题，只是c语言有点不熟练了**************************源代码******************************* #include"iostream"#include"string"using namespace std;int main(){while(1){char str[100];cin>>str;int k = 0;int j = 0;for(int i = 0;i < strlen(str);i++){if(str[i] >= 'A'&&str[i] <= 'Z'|| str[i] >= 'a'&&str[i]<='z'){j++;}if(str[i] >='0'&&str[i]<='9'){k++;}}cout<<"数字："<<k<<endl;cout<<"字母："<<j<<endl<<endl;}return 0;}#include"iostream"#include"string"#include"fstream"using namespace std;int main(){char buffer[256];bool op = false; //判断是否为/**/的注释char* pstr = NULL; //记录注释内容pstr = (char *)malloc(1024 * sizeof(char));char* ptempstr = NULL; //记录pstr的首地址ptempstr = (char *)malloc(1024 * sizeof(char));ptempstr = pstr;ifstream fileopen;fileopen.open("d:\\com.txt");cout << "文件内容如下：" << endl;while (!fileopen.eof()){fileopen.getline(buffer, 256, '\n'); //读入一行到控制台char* p; //指向读取文件的buffer缓冲区的首地址p = buffer;for (int i = 0; i<strlen(buffer); i++){//遇到“//”的注释if (buffer[i] == '/'&&buffer[i + 1] == '/'&&op ==false){memset(pstr, 0, 1024);memcpy(pstr, p + i, strlen(buffer) - i);cout << pstr << endl;break;}/**///**///遇到“/**/”的注释if (op == true){memcpy(pstr, p + i, 1);//拷贝当前字符pstr += 1;}if (buffer[i] == '/'&&buffer[i + 1] == '*'){memset(pstr, 0, 1024);ptempstr = pstr;memcpy(pstr, p + i, 1);//拷贝当前字符pstr += 1;op = true;}if (buffer[i] == '*'&&buffer[i + 1] == '/'&&op == true){memcpy(pstr, p + i+1, 1);//拷贝当前字符pstr += 1;cout << ptempstr << endl;//显示注释内容op = false;i++;continue;}}}fileopen.close();return 0;}。

1.系统当前有4个进程P1、P2、P3、P4。

P1处于运行状态，P2、P3和P4均处于就绪状态。

如果进程P1正在执行一条I/O指令，请按照顺序列出此后在操作系统中发生的各项操作。

P1在做I/O，在P1由于I/O阻塞让出CPU；内核调度程序会在内核态根据调度算法找出下一个需要运行的进程，比如P2。

则P1的运行环境被保存，运行环境包括进程内存空间，寄存器状态，栈指针SP，页表，然后P2的运行环境被restore，然后P2运行。

接下来P3 P4都有可能被调度（如果P2的时间片已经用完），在这一过程中如果P1的i/o已经完成，在i/o会有中断发给内核，i/o中断处理程序会被调用告诉操作系统i/o已经完成。

2.试列举两个多线程程序设计的例子，其中一个示例为多线程的性能优于单线程的性能，另一个示例则为多线程的性能劣于单线程的性能。

多线程优于单线程
多优于单：一个用户刚刚在一个800页的文档的第一页上删掉一条语句，接着打算在第600页上修改一个错别字。

当用户键入一条命令通知字处理程序转到第600页时，字处理程序对该文档的前600页重新进行格式处理，以便确定第600页的第一行应该在哪里，此时计算机可能要拖延相当一段时间，才能显示出第600页。

单优于多：执行较小规模的顺序语句，双线程执行一次要比单线程执行两次慢。

(4) 对所有进程，哪一种调度算法的平均等待时间最小？
在一个使用多级反馈队列的系统中，一个只使用CPU的进程的执行时间为40秒。

如果第一个队列时间片为2，每级时间片增加5个时间单元，那么这个作业运行结束前会被中断多少次，结束时处于哪级队列？。

课程编号：COM07017北京理工大学2015—2016学年第二学期2013级计算机科学与技术类编译原理与设计试题A卷班级学号姓名成绩** 注意：各题均必须答在答题纸上。

一．判断题（在答题表中填上“√”或“×”）（10分）1.对任何一个NFA M，不一定都存在一个DFA M' ，使M和M'所识别的字的全体相同。

2.一个DFA M的无关状态（或称之为多余状态、无用状态）是指从DFA M的初态开始，任何输入序列都不能到达的那些状态。

3.词法分析器通常需要超前扫描输入字符以确定每个单词的结束位置。

4.多数程序设计语言的词法规则可用正则文法或正规式进行描述。

5.第10章的PL/0编译程序采用Display表查找外层过程的最新活动记录。

6.若过程P第K次被调用，则P的Display表中就有K+1个元素。

7.在后缀式（逆波兰式）和中缀式中，运算对象排列的顺序一致。

8.语法制导翻译方法可用来产生各种中间代码，但不能用来产生目标代码。

9.所有LR分析器的总控程序都是一样的，只是分析表各有不同。

10.一个素短语除自身外，其子串中没有其他素短语。

二、单项选择题（10分）1.下述关于词法分析器中的对半互补输入缓冲区的描述错误的是【】A)方便输入字符串的超前扫描B)方便字符回退C)可以支持无限长度单词的识别D)缓冲区大小一般设置为磁盘扇区大小的整数倍2.下述关于Lex和Yacc的描述错误的是【】A)Lex和Yacc编译器接受正规式并据此构造相应的有限状态自动机B)Lex编译器采用子集法将NFA转化为DFAC)Lex编译器采用划分法对DFA进行化简D)Yacc编译器生成的是移进归约语法分析器3.无法在局部优化阶段实施的优化技术是【】A)公共子表达式删除B)常量合并C)无用赋值删除D)死代码删除4.解释程序和编译程序的区别在于【】A)是否生成中间代码B)加工的对象不同C)使用的实现技术不同D)是否生成目标程序5.关于编译程序中使用符号表的作用描述错误的是【】A)收集标识符属性信息B)语义检查依据C)代码生成时地址分配依据D)便于移植6.从无冲突的LR(1)项目集规范簇通过合并同心项目集，得到的LALR(1)项目集规范簇中会出现【】冲突A)移进-移进B)移进-归约C)归约-归约D)任何7.就文法的描述能力，有【】A)LALR(1)⊂SLR(1) B)SLR(1)⊂LR(0)C)LALR(1) ⊂LR(1) D)LR(1) ⊂LR(0)8.如果一个正规式所描述的语言是个无限集合，则该正规式一定含有的运算是【】A)连接运算“•”B)或运算“|”C)闭包运算“*”D)括号运算“（）”9.有文法G(S)的属性文法如下所示(语义规则中的×和+分别是常规意义下的算术运算符)：S→E {输出(E.val)}E→E?T {E.val=E1.val×T.val}E→T{E.val= T.val}T→T#num {T.val=T1.val+num.lexval}T→num {T.val=num.lexval}则句子1?2?3#4的语义处理结果是【】A)10 B)34 C)14 D)5410.LR分析法中，分析栈中存放的符号串始终是规范句型的【】A)短语B)活前缀C)项目D)句柄三．填空题（30分）1.第10章的PL/0编译程序采用【①】遍扫描，以【②】分析程序为核心对输入源程序进行解释执行。

本科实验报告实验名称：VHDL语言及集成电路设计实验实验一：带有异步复位端的D触发器一、实验目的（1）熟悉linux操作环境和modelsim软件环境（2）理解时序逻辑和组合逻辑电路的区别（3）理解并行语句和顺序语句（4）用VHDL语言编写一个带有异步复位端的D触发器及其测试文件二、实验原理（1）组合逻辑和时序逻辑组合逻辑电路当前输出的值仅取决于当前的输入，不需要触发器等具有存储能力的逻辑单元，仅仅使用组合逻辑门；时序逻辑电路的当前输出不仅取决于当前的输入，还与以前的输入有关，这类电路中包括寄存器等元件，也包括组合逻辑电路，寄存器通过一个反馈环和组合逻辑模块相连，触发器便是属于时序逻辑电路；（2）并行和顺序代码从本质上讲，VHDL代码是并发执行的。

只有PROCESS，FUNCTION或PROCEDURE 内的代码才是顺序执行的。

当它们作为一个整体时，与其他模块之间又是并发执行的。

以下是3个并发描述语句（stat1,stat2和stat3）的代码，会产生同样的电路结构。

stat1 stat3 stat1stat2 = stat2 = stat3 = 其他排列顺序stat3 stat1 stat2（3）并行语句——进程（PROCESS）1）语法结构：[进程名: ]PROCESS (敏感信号列表)[变量说明语句]…BEGIN…(顺序执行的代码)…END PROCESS [进程名]；2） PROCESS 的特点多进程之间是并行执行的；进程结构内部的所有语句都是顺序执行的；进程中可访问结构体或实体中所定义的信号；进程的启动是由敏感信号列表所标明的信号来触发，也可以用WAIT语句等待一个触发条件的成立。

各进程之间的通信是由信号来传递的。

（4）带有异步复位端的D触发器三、实验代码LIBRARY IEEE;USE IEEE.STD_LOGIC_1164.ALL;ENTITY dff ISPORT(d,clk,rst:IN STD_LOGIC;q:OUT STD_LOGIC);END dff;定义entity dffARCHITECTURE behavior OF dff IS BEGINPROCESS(rst,clk)BEGINIF(rst='1') THENq<='0';如果复位信号有效，q为0ELSIF(clk'EVENT AND clk='1') THEN q<=d;上升沿触发且，q<=dEND IF;END PROCESS;结束进程end ARCHITECTURE behavior;测试文件：library IEEE;use ieee.std_logic_1164.all;entity dff_tb isend dff_tb;architecture tb_behavior of dff_tb is component dffport(d,rst,clk: in std_logic;q: out std_logic);end component;constant clk_period:time:=50 ns;signal d,clk,q,rst:std_logic;begindut:dff port map(d=>d,clk=>clk,rst=>rst,q=>q); clk_gen:process beginclk<='0';wait for clk_period/2; clk<='1';wait for clk_period/2; end process;d_gen:processbeginwait for 100 ns;d<='1';wait for 100 ns;d<='0';end process;rst_gen:processbeginrst<='1';wait for 150 ns;rst<='0';wait for 500 ns;rst<='1';wait for 150 ns; wait;end process;end tb_behavior;四、实验结果五、实验心得第一次使用此软件，略有陌生，耗费时间稍久，因为之前用过的quartusii9.0不必使用tb文件，所以第一次实验刚开始并没有明白tb文件的用途，上网查找资料之后才明白过来，不过好在程序简单，顺利完成实验。

H1：计算通用产品代码(UPC)的校验位（选作）成绩: 5 / 折扣: 0.8背景许多年来，货物生产商都会把超市售卖的每件商品上放置一个条码。

这种被称为通用产品代码（Universal Product Code，缩写UPC）的条码可以识别生产商和产品。

超市可以通过扫描产品上的条码来确定支付此项商品的费用。

每一个条码由十二位数字构成，通常这些数字会显示在条码下面。

例如，包装为26盎司的Morton牌碘化盐所用条码下的数字是：0 24600 01003 0第一个数字表示商品的种类（0表示大部分的食品杂货，2表示需要称量的货品，3表示药品或和健康相关的商品，而5表示优惠券）。

接下来的一组五位数字用来识别生产商。

而第二组五位数字则用来区分产品类型（其中包括包装尺寸）。

最后一位数字是“校验位”，它可以帮助鉴别先前数字中的错误。

如果条码扫描出现错误，那么前十一位数字和最后一位数字可能会不一致，而超市扫描机也会拒绝整个条码。

下面是一种计算校验位的方法：首先把第一位、第三位、第五位、第七位、第九位和第十一位数字相加。

然后把第二位、第四位、第六位、第八位和第十位数字相加。

接着把第一次加法结果乘以3后再加上第二次加法的结果。

随后，再把上述结果减去1。

减法后的结果除以10取余数。

最后，用9减去上一步骤中得到的余数。

现在以Morton碘盐为例，第一组数字的加法是0+4+0+0+0+3=7，而第二组数字的加法是2+6+0+1+0=9。

把第一组加法值乘以3后再加上第二组加法值得到的结果是30。

再减去1，结果变为29。

再把这个值除以10取余数为9。

9在减去余数结果9，最终值为0。

输入每次输入三行数据，第一行是UPC的第一位数字，第二行是UPC的第一组五位数字，第三行是UPC的第二组五位数字。

输出UPC的校验位提示本题有隐藏测试用例。

如果想多找不同的实例验证你的算法，可以拿身边书或食品背后的条码测试一下。

1.#include<stdio.h>2.main()3.{4.int a,b,c;5.int b1,b2,b3,b4,b5;6.int c1,c2,c3,c4,c5;7.int d1,d2,d3,d4;8.scanf("%d\n%d\n%d",&a,&b,&c);9.b1=b/10000,b2=(b/1000)%10,b3=(b/100)%10,b4=(b/10)%10,b5=b%10;10.c1=c/10000,c2=(c/1000)%10,c3=(c/100)%10,c4=(c/10)%10,c5=c%10;11.d1=a+b2+b4+c1+c3+c5,d2=b1+b3+b5+c2+c4,d3=(3*d1+d2-1)%10,d4=9-d3;12.printf("%d\n",d4);13.}H2：数制转换（选作）成绩: 5 / 折扣: 0.8我们通常使用的都是十进制的数字，但其实在生活中也经常会使用其它进制。

课程编号：COM07017北京理工大学2016—2017学年第二学期计算机科学与技术类《编译原理与设计》试卷(2017.06)班级学号姓名成绩** 注意：各题均必须答在试卷上，书写不下可以写在试卷背面。

一．判断题（15分）在下面答题表中填上“√”或“×”。

1.符号串的前缀一定是此符号串的子串。

2.设正规式r对应的正规集合中有m个元素、正规式s对应的正规集合中有n个元素，则正规式rs对应的正规集合中有m×n个元素。

3.NFA的确定化是为了减少有限状态机的状态数。

4.DFA识别的语言一定是一个正规集。

5.一个LR(1)的项目集可以对多个句型的活前缀有效。

6.变量P在点d是活跃的是指P在点d被引用。

7.程序控制流图是无环路有向图。

8.若文法规则存在P P'a，则FIRST(P') = FIRST(P)。

9.C语言的符号表是在可执行程序运行过程中动态维护的。

10.实施循环不变代码外提之前需要进行活跃变量分析。

二、单项选择题 (在下面答题表中填上答案) （20分）1. 编译过程处理的遍数多的优点不包括（）A）编译程序逻辑结构清晰B）减少对主存容量的要求；C）优化准备充分D）便于移植2. 有G(S)={{S, T, F, X}, {a, b}, S, {S→XSX | T T→aFb | bFa F→XFX | X | εX→a | b}}，则下列符号串中不是该文法的句子的是（）A）babb B）aaaab C）aba D）bbbaa3. 不是文法的表示方法的是（）A）BNF B）语法树C）EBNF D）语法图4. 根据N. Chomsky分类法，则下列说法错误的是（）A）正则语言可以用上下文无关文法表示；B）短语文法语言可由图灵机识别；C）线性有界自动机识别的语言可以用上下文无关文法表示；D）下推自动机识别的语言可以用上下文无关文法表示。

5. 下列文法中，（）是算符优先文法。