精华内容
下载资源
问答
  • 2018-10-19 20:09:10

     

    进程在内存中的大概分布情况
    进程都需要占用一定内存,被占用的内存有些是事先静态分配和统一回收的,有些是按需动态分配和及时回收的。一般分为5种不同的内存数据段:

    1.  代码段:用来存放可执行文件完整的操作指令(机器码)和只读数据,为了防止代码段被非法修改,代码段的特点是只读不写的。如果一个程序有多个运行实体,则这些实体共享同一个代码段。
    2.  数据段:用来存放可执行文件中已经初始化了的全局变量,也就是在程序中静态分配的变量和全局变量。数据段在编译时分配。注意:数据段中的变量既占程序运行时的内存空间,也占程序文件的储存空间。    
    3.  BSS段:用来存放可执行文件中未初始化的全局变量,在内存中全部置零。注意:BSS段中的变量只占用程序运行时的内存空间,而不占用程序文件的储存空间。
    4.  堆(heap):用来存放进程中被动态分配的内存段,大小不固定,动态扩张。当进程使用new或malloc申请变量内存时候,这些变量就会被分配到堆上,当使用delete或free释放内存时,堆上相应的内存会被释放。如果没有主动释放,操作系统会在程序结束后自动回收。
    5.  栈(stack): 用来存放程序临时创建的局部变量,也就是在函数体中定义的变量。此外还包括在函数调用时,函数的参数以及函数的返回值,这些内存是由系统自动分配和释放的。栈的特点是先进后出,向栈中添加数据(压栈),会将数据放置在栈顶,从栈中取出数据,会从栈顶部移出一个数据(弹栈)。所以栈在保存和恢复调用现场方面特别方便。    

     

    堆和栈的区别
    分配管理方式上:堆是动态分配,空间的分配和释放由程序员控制;栈由编译器自动管理。
    产生碎片上:对堆来说,频繁的new/delete或者malloc/free势必会造成内存空间的不连续,造成大量的碎片,使程序效率降低。对栈而言,则不存在碎片问题,因为栈是先进后出的队列,永远不可能有一个内存块从栈中间弹出。
    生长方向不同:堆是向着内存地址增加的方向增长的,从内存的低地址向高地址方向增长。栈的生长方向与之相反,是向着内存地址减小的方向增长,由内存的高地址向低地址方向增长。

     

    进程间通信方式(IPC,Inter-Process Communication)
    不同进程间的用户空间是相互独立的,一般不能相互访问。进程间通信是指在不同进程之间传播或交换信息,比较常见的进程间通信的场景是父子进程间的通信,共享数据,通知事件等。
    1. 管道
    也称为无名管道或匿名管道,使用pipe()创建。
    管道上的数据只能在一个方向上流动,具有固定的读端和写端。
    只能用于具有亲缘关系的进程之间的通信(也是父子进程或者兄弟进程之间)。
    管道可以看作是一种特殊的文件,但不属于任何文件系统,只存在于内存中。
    2. FIFO
    也称为命名管道,是一种文件类型。使用mkfifo创建。
    可以在无关的进程之间交换数据,与无名管道不同。
    FIFO有路径名与之相关联,它以一种特殊设备文件形式存在于文件系统中。
    3. 消息队列
    消息队列是消息的链表,存放在内核中。一个消息队列由一个标识符(即队列ID)来标识。
    消息队列独立于发送与接收进程。进程终止时,消息队列及其内容并不会被删除。
    消息队列是面向记录的,其中的消息具有特定的格式以及特定的优先级。
    消息队列可以实现消息的随机查询,消息不一定要以先进先出的次序读取,也可以按消息的类型读取。
    4. 信号量
    信号量是一个计数器,用于实现进程间的互斥与同步,而不是用于存储进程间通信数据,若要在进程间传递数据需要结合共享内存。
    信号量基于操作系统的 PV 操作,程序对信号量的操作都是原子操作(不可被中断的一个或一系列操作)。
    一个进程对信号量成功执行来P操作,就得到了信号量,可以进入临界区,另外一个进程试图执行P操作时,会被挂起,直到拥有信号量的进程离开并执行V操作释放信号量。
    5. 共享内存
    共享内存(Shared Memory),指两个或多个进程共享一个给定的存储区。不同进程之间共享的内存通常安排为同一段物理内存。进程可以将同一段共享内存映射到它们自己的地址空间中,所有进程都可以访问共享内存中的地址。
    共享内存是最快的一种进程间通信方式,因为进程是直接对内存进行存取。
    因为多个进程可以同时操作,所以需要额外的同步控制,如互斥锁或信号量。
    信号量+共享内存通常结合在一起使用,信号量用来同步对共享内存的访问。

     

    进程5种通信(IPC)方式比较
    管道:速度慢,容量有限,只有父子或兄弟进程能通讯
    FIFO:任何进程间都能通讯,但速度慢
    消息队列:容量受到系统限制,且要注意第一次读的时候,要考虑上一次没有读完数据的问题
    信号量:不能传递复杂消息,只能用来同步控制,相当于是一个信号灯
    共享内存:能够很容易控制容量,速度快,但要保持同步,一般需借助于信号量或互斥锁,比如一个进程在写的时候,另一个进程要注意读写的问题,相当于线程中的线程安全。

     

    信号量与互斥锁区别
    信号量用在多进程(或线程)多任务同步上的,拥有信号量的一个进程在执行动作的时候,别的进程必须等待。
    互斥锁是用在多线程(多进程中不存在互斥锁)多任务互斥上的,拥有互斥锁的一个线程在访问某一资源时候,别的线程就无法访问。
    信号量重点在执行顺序的流程控制上,而不一定是锁住某一个资源,而互斥锁重点在于霸占某一资源上,自己在使用,别人就不能使用。

     

    Ctrl+C、Ctrl+Z、Ctrl+D
    ctrl-c 发送信号给前台进程组中的所有进程,终止正在运行的程序。
    ctrl-z 发送信号给前台进程组中的所有进程,把当前程序挂起,暂停执行。想继续执行的时候输入fg回车即可复活当前进程。
    Ctrl+D :发送一个 exit 的信号,退出当前的用户或者是客户端。

     

    同一进程中的线程间哪些资源共享,哪些独有
    共享的资源:
    a. 堆  由于堆是在进程空间中开辟出来的,所以它是理所当然地被共享的;因此new出来的都是共享的
    b. 全局变量 它是与具体某一函数无关的,所以也与特定线程无关;因此也是共享的
    c. 静态变量 虽然对于局部变量来说,它在代码中是“放”在某一函数中的,但是其存放位置和全局变量一样,存于堆中开辟的.bss和.data段,是共享的
    d. 文件等公用资源  这个是共享的,使用这些公共资源的线程必须同步。

    独有的资源:
    a. 线程ID 每个线程都有自己唯一的线程ID。
    b. 寄存器组的值 由于线程间是并发运行的,每个线程有自己不同的运行线索,当从一个线程切换到另一个线程上时,必须将原有的线程的寄存器集合的状态保存,以便将来该线程在被重新切换到时能得以恢复。
    c. 线程的栈 栈是保证线程独立运行所必须的。线程函数可以调用函数,而被调用函数中又是可以层层嵌套的,所以线程必须拥有自己的函数栈,使得函数调用可以正常执行,不受其他线程的影响。
    d. 错误返回码 由于同一个进程中有很多个线程在同时运行,可能某个线程进行系统调用 后设置了errno值,而在该线程还没有处理这个错误,另外一个线程就在此时被调度器投入运行,这样错误值就有可能被修改。    所以,不同的线程应该拥有自己的错误返回码变量。
    e. 线程的优先级 由于线程需要像进程那样能够被调度,那么就必须要有可供调度使用的参数,这个参数就是线程的优先级。

     

    线程4种同步机制
    临界区:临界区是一段独占对某些共享资源访问的代码,在任意时刻只允许一个线程对共享资源进行访问。通过对多线程的串行化来访问公共资源或一段代码。
    互斥量:功能上跟临界区类似,采用互斥对象机制,只有拥有互斥对象的线程才有访问公共资源的权限。不过可用于不同进程间的线程同步。
    事件: 通过通知操作的方式来保持线程的同步,还可以方便实现对多个线程的优先级比较的操作
    信号量:信号量用于限制对临界资源的访问数量,允许多个线程在同一时刻访问同一资源,但是需要限制在同一时刻访问此资源的最大线程数目,保证了消费数量不会大于生产数量。
    临界区(Critical Section)、互斥对象(Mutex):主要用于互斥控制;都具有拥有权的控制方法,只有拥有该对象的线程才能执行任务,所以拥有,执行完任务后一定要释放该对象。
    信号量(Semaphore)、事件对象(Event):事件对象是以通知的方式进行控制,主要用于同步控制!

     

    同步和互斥
    同步:异步环境下的一组并发进程因制约关系而互相发送消息而进行互相合作、互相等待,使得各进程按一定的顺序执行的过程称为进程间的同步。
    互斥:一组并发进程中的一个或多个程序段,因共享某一公有资源而导致它们必须以一个不允许交叉执行的单位执行。也就是说,不允许两个以上的共享该资源的并发进程同时进入临界区。
    互斥具有唯一性和排它性,但互斥并不限制任务的运行顺序,即任务是无序的。而同步的任务之间则有逻辑顺序关系。

     

    C语言的编译过程
    1. 预处理:读取C源程序,对其中的伪指令进行处理。预处理主要是要处理“#”,将#include包含的头文件插入到hell.c当中;将#define定义的宏进行替换,同时将代码中没用的注释部分删除,还要添加行号和文件标识,以便错误显示和调试。 生成 .i 文件。
    2. 编译:将预处理完的文件进行一系列词法分析、语法分析、语义分析及优化后,产生相应的汇编代码文件。生成 .s 文件。
    3. 汇编: 将编译完的汇编代码文件按照“汇编指令和机器指令的对照表”翻译成机器指令(机器指令是CPU能直接识别并执行的指令,它的表现形式是二进制编码。机器指令通常由操作码和操作数两部分组成,操作码指出该指令所要完成的操作,即指令的功能,操作数指出参与运算的对象,以及运算结果所存放的位置等)。生成 .o 文件。
    4. 链接:通过链接器将一个个目标文件(或许还会有库文件)链接在一起生成一个完整的可执行程序。 生成 .exe 文件。
    功能上的5个阶段是:词法分析、语法分析、语义分析和中间代码的产生、代码优化、目标代码生成

     


    语法树
    语法树是句子结构的图形表示,它代表了句子的推导过程,有利于理解句子语法结构的层次。
    简单说,语法树就是按照某一规则(文法)进行推导时所形成的树(图形表示)。一棵语法树包括了一个句型的所有可能的推导过程。

     

    文法
    文法是描述语言的语法结构的形式规则(即语法规则),是定义由符号到一个有含义的句子的规则和协议。上下文无关文法就是文法的一种,指当前语法单位是上下文无关的,不用去关心在它上边或下边的语法单位。编译原理中的文法指的就是上下文无关文法。
    对于一个文法,如果它的某些句子对应两棵不同的语法树,这个文法就属于“二义性文法”,应尽量避免,如在句子中设置优先级、添加隔离等,但是不存在判断句子是否具有二义性的方法。

     

    词法分析
    词法分析是编译的第一阶段。词法分析器的主要任务是读入源程序的输入字符,将它们组成词素,生成并输出一个词法单元序列,这个词法单元序列被输出到语法分析器进行语法分析。
    另外,由于词法分析器在编译器中负责读取源程序,因此除了识别词素之外,它还会完成一些其他任务,比如过滤掉源程序中的注释和空白,添加行号和文件标识,以便错误显示和调试。总而言之,词法分析器的作用如下:
    1. 读入源程序的输入字符,将它们组成词素,生成并输出一个词法单元序列;
    2. 过滤掉源程序中的注释和空白;
    3. 将编译器生成的错误消息与源程序的位置关联起来(添加行号和文件标识)。

     

    语法分析
    语法分析是编译过程的一个逻辑阶段。语法分析的任务是在词法分析的基础上将单词序列组合成各类语法短语,如“程序”,“语句”,“表达式”等等.语法分析程序判断源程序在结构上是否正确.源程序的结构由上下文无关文法描述。完成语法分析任务的程序称为语法分析器。
    语法分析器会构造一棵语法分析树,并把它传递给编译器的其他部分进一步处理,在构建语法分析树的过程中,就验证了这个词素序列是否符合源语言的文法。
    语法分析方法分为自上而下语法分析方法和自下而上语法分析方法。

     

    语义分析
    语义分析是编译过程的一个逻辑阶段. 语义分析的任务是对结构上正确的源程序进行上下文有关性质的审查, 进行类型审查。语义分析是审查源程序有无语义错误,为代码生成阶段收集类型信息。比如语义分析的一个工作是进行类型审查,审查每个算符是否具有语言规范允许的运算对象,当不符合语言规范时,编译程序应报告错误。
    编译程序最实质性的工作;第一次对源程序的语义作出解释,引起源程序质的变化。

     

    代码优化
    编译原理出于代码编译的模块化组装和提高目标代码运行效率、时间效率(减少运行时间)、空间效率(减少内存容量)的考虑,一般会在语义分析的阶段生成平台无关的中间代码,经过中间代码级的代码优化,而后作为输入进入代码生成阶段,产生最终运行机器平台上的目标代码,再经过一次目标代码级别的代码优化(一般和具体机器的硬件结构高度耦合,复杂且不通用)。编译原理中的代码优化主要针对的是中间代码级的代码优化。
    常见的代码优化手段:
    删除多余运算、循环中不变的代码提到循环外边、运算强度削弱(本质是把强度大的运算换算成强度小的运算,例如将乘法换成加法运算)、变换循环控制条件、合并已知量、删除无用赋值等。

    更多相关内容
  • 编译原理实验报告——语法分析的设计与实现,大学优秀等级 1.实验目的及要求 (1)定义目标语言的语法规则。如: 文法G(E): ① E→E+T ② E→T ③ T→T*F ④ T→F ⑤ F→(E) ⑥ F→i (2)求解某种语法分析法...
  • 通过设计、编制、调试一个具体的词法分析程序,加深对词法分析原理的理解,并掌握在对程序设计语言源程序进行扫描过程中将其分解为各类单词的词法分析方法。
  • 东北大学2022年编译原理实验课——词法分析——简单扫描设计: 【问题描述】 熟悉并实现一个简单的扫描,设计扫描的自动机;设计翻译、生成Token的算法;编写代码并上机调试运行通过。 要求扫描可识别的单词...
  • 设计、编制并调试一个自定义语言C--的词法分析程序,加深对词法分析原理的理解。 不知道现在的实验还是不是这个
  • 本文主要讲解Android虚拟机动态调试背后涉及到的技术原理,除了JDWP协议细节,还包括任意位置断点、堆栈输出、变量值获取等基础调试功能的具体实现。另外本文提供了一款新的android动态调试工具——AVMDBG,提供调试...
  • 根据课本的LR分析模型和LR分析算法,完成LR分析。对要求中的错误信息提示,指的是对应分析表中的空白处,每一个空白的地方都应该有对应的错误情况,因而有相应的错误信息。注意这里的语法分析,是在词法分析的基础...
  • 通过完成预测分析法的语法分析程序,了解预测分析法和递归子程序法的区别和联系。使了解语法分析的功能,掌握语法分析程序设计的原理和构造方法,训练掌握开发应用程序的基本方法。
  • 根据某一文法编制调试 LL (1 )分析程序, 以便对任意输入的符号串进行分析。 2. 构造预测分析表,并利用分析表和一个栈来实现对上述程序设计语言的分析程序。 3.分析法的功能是利用 LL(1)控制程序根据显示栈...
  • 编译原理 扫描 (1) 设计扫描的有限自动机(识别); (2) 设计翻译、生成Token的算法(翻译); (3) 编写代码并上机调试运行通过。 •输入——源程序文件或源程序字符串; •输出——相应的Token序列; 关键...
  • 编译原理实验--词法分析 实验内容:通过设计、编制、调试一个具体的词法分析程序,加深对词法分析原理的理解,并掌握在对程序设计语言源程序进行扫描过程中将其分解为各类单词的词法分析方法。 基本要求:设计出给定...
  • 编译原理源码分享(HUST)
  • 编译原理词法分析调试成功版) c语言编写 想下赶紧
  • 数学与软件科学学院 实验报告 学 期 2015 至 2016 第 2 学期 2016 年 3 月 21 日 课程名称 编译原理 专 业 信息与计算科学 2013 级 5 班 实验编号 2 实验名称 递归下降分析 指导教师 王开端 姓 名 李丹 学 号 ...
  • 编译原理-扫描

    2012-12-12 16:53:33
    (1) 设计扫描的有限自动机(识别); (2) 设计翻译、生成Token...(3) 编写代码并上机调试运行通过。 •输入——源程序文件或源程序字符串; •输出——相应的Token序列; 关键字表和界符表; 符号表和常数表;
  • 1. 了解 LL(1)语法分析是如何根据语法规则逐一分析词法分析所得到的单词,检查语法错误,即掌握语法分析过程。 2. 掌握LL(1)文法判别调剂和 LL(1)语法分析的设计与调试
  • 学生在学习《编译原理》课程设计中,结合各章节的构造编译程序的基本理论,总共用一周的时间完成课程设计。要求用C或C++语言描述及上机调试,实现五个题目中任意一个,是学生将理论与实际应用结合其,起来,受到软件...
  • 编译原理-简单计算器

    2014-08-31 20:04:36
    编译原理-简单计算器:实现词法分析,和语法分析:实现正整数与浮点数的 + - * / () 之前大学的时候,编译原理课程有一个做计算器的任务,当时没有做,只顾做一个漂亮计算器界面。趁这周末有空,就把计算器编译...
  • 编译原理 词法分析

    热门讨论 2010-05-05 22:51:50
    通过设计编制调试一个具体的词法分析程序,加深对词法分析原理的理解。并掌握在对程序设计语言源程序进行扫描过程中将其分解为各类单词的词法分析方法。 编制一个读单词过程,从输入的源程序中,识别出各个具有独立...
  • 用C语言编写的词法分析,内部含有完成的程序源代码,拷贝出来即可使用。还有报告设计文档,供大家参考一下。
  • 编译原理:语法分析

    万次阅读 多人点赞 2019-04-29 17:01:40
    通过设计、编制、调试一个典型的语法分析程序(任选有代表性的语法分析方法,如LL(1)、递归下降分析法、LR、算符优先分析法)等,作为编制语法分析程序的依据,对词法分析所提供的单词序列进行语法检测和结构分析...

    语法分析程序



    一、作业目的和要求

    通过设计、编制、调试一个典型的语法分析程序(任选有代表性的语法分析方法,如LL(1)、递归下降分析法、LR、算符优先分析法)等,作为编制语法分析程序的依据,对词法分析器所提供的单词序列进行语法检测和结构分析,实现并进一步掌握常用的语法分析方法。


    二、作业内容

    选择对各种常见高级程序设计语言都较为通用的语法结构作为分析对象(例如表达式、if、while、for等等),给出其文法规则描述(注意,文法规则的描述要符合所选分析方法的要求,比如用LL(1)分析法,文法必须是LL(1)文法),设计并实现一个完整的语法分析程序。

    • 输入:源程序以文件的形式输入。
    • 输出:对于输入的源程序,如果输入源程序是给定文法定义的合法程序,则输出”success”,如果不是,即输入源程序有错误,则输出“Error”,并且尽可能指出出错位置和原因。

    三、作业要求

    1、说明语法分析的源语言是什么?
    能分析的语法成分有哪些(比如if、while、表达式、switch等等)。
    给出每个语法规则的文法描述。(可以自定义语法成分,设计合理的语法规则。)

    运用的Java语言写成的语法分析程序,
    语法成分包括:if选择结构,while循环结构,for循环结构。

    2、说明选择的语法分析方法是哪种?描述总体设计思路和主要的流程图。

    语法分析的方法是LL(1)文法。

    • 设计思路:

    • 1.构造单个文法符号X的first集:
      如果X为终结符,First(X)=X;
      如果X->ε是产生式,把ε加入First(X);
      如果X是非终结符,如X->YZW。从左往右扫描产生式右部,把First(Y)加入First(X); 如果First(Y)不包含ε,表示Y不可为空,便不再往后处理;如果First(Y)包含ε,表示Y可为空,则处理Z,依次类推。
      构造文法符号串的first集,如:X->YZW;求YZW的first集
      从左往右扫描该式,加入其非空first集:把First(Y)加入First(YZW)
      若包含空串,处理下一个符号:如果First(Y)包含空串,便处理Z;不包含就退出;处理到尾部,即所有符号的first集都包含空串 把空串加入First(YZW)。

    • 2.在计算First(X)集之后的基础上:
      (1)$属于FOLLOW(S),S是开始符;
      (2)查找输入的所有产生式,确定X后紧跟的终结符;
      (3)如果存在A->αBβ,(α、β是任意文法符号串,A、B为非终结符),把first(β)的非空符号加入follow(B);
      (4)如果存在A->αB或A->αBβ 但first(β)包含空,把follow(A)加入follow(B)。

    • 3.构造预测分析表:
      对于每个产生式A->α,first(α)中的终结符a,把A->α加入M[A,a]。
      如果空串在first(α)中,说明可为空,找它的follow集,对于follow(A)中的终结符b,把A->α加入M[A,b];
      如果空串在first(α)中,且 “$”也在follow(A)中,说明A后可以接终结符,故把A->α加入M[A,$]中。

    • 4.执行分析:
      输入一个串,文法G的预测分析表,输出推导过程:
      $ 和 开始符S入栈,栈顶符号X,index指向分析串的待分析符号a。
      栈非空执行以下循环:
      如果X==a,表示匹配,符号栈弹出一个,index++指向下一个符号;
      否则,如果X是终结符,出错;
      否则,如果查表为error,出错;
      否则,查表正确,弹出栈顶符号,把其右部各个符号进栈,令X为栈顶符号。

    • 流程图:
      在这里插入图片描述
      在这里插入图片描述

    3、编程实现,程序中编写的各种函数,需要给出注释,说明函数的作用。
    通过实现接口中的方法来完成语法分析的功能。

    package Try;
    
    interface MyAnalyseFun {
        void Init();//初始化
        void getVnVt();//获取非终结符和终结符的集合
        void getFirst(Character c);//first集
        void getFirst(String s);//任意字符的first集
        void getFollow(char c);//follow集
        void createTable();//构造表
        void analyzeLL();//LL(1)分析过程
        String find(char X, char a);//查找
        void insert(char X, char a,String s);//插入
        void displayLL();//输出分析过程
        void ouput();//其他输出信息
    }
    

        package Try;
        
        import java.io.*;
        import java.util.*;
        
        public class MyAnalyse implements MyAnalyseFun{
            /**
             * 几个比较重要的参数
             * @param MyfirstSet 终结符的first集合
             * @param MyfirstSetX 任意符号的first集合
             * @param start 文法的开始符
             * @param MyfollowSet follow集
             * @param VnSet 终结符的集合
             * @param VtSet 终结符的集合
             * @param inputStrings 文法拓展的输入
             * @param outputSet 输出的集合
             * @param table 分析表
             * @param MyAnaStatck 分析栈
             * @param strInput 需要使用预测分析器的输入串
             * @param MyAction 分析动作
             * @param Index 分析的索引值
             */
            //从文件中读入时后台无法识别空串ε,因此用符号&代替空串ε
    
        //first集是终结符的first集
        protected HashMap<Character, HashSet<Character>> MyfirstSet = new HashMap<>();
        //firstX集是指任意符号串的first集
        protected HashMap<String, HashSet<Character>> MyfirstSetX = new HashMap<>();
        //文法的开始符
        protected Character start = 'S';
        //follow集
        protected HashMap<Character, HashSet<Character>> MyfollowSet = new HashMap<>();
    
        //存储非终结符的结合
        protected HashSet<Character> VnSet = new HashSet<>();
        //存储终结符的结合
        protected HashSet<Character> VtSet = new HashSet<>();
        protected HashMap<Character, ArrayList<String>> outputSet = new HashMap<>();
        //输入文法
        //S->a|^|(T)
        //T->SU
        //U->,SU|&
    //    protected String [] inputStrings = {   "S->a",
    //                                        "S->^",
    //                                        "S->(T)",
    //                                        "T->SU",
    //                                        "U->,SU",
    //                                        //"U->ε",
    //                                        "U->&"   };
        //定义分析表
        protected String [][] table;
        //分析栈
        protected Stack<Character> MyAnaStatck = new Stack<>();
        //定义要分析的输入串
        protected String strInput = "(a,a)$";
        //对动作的初始化
        protected String MyAction = "";
        int Index = 0;
    
        //从文件中读入
        protected String[] inputStrings = getSource();
    
        protected MyAnalyse() {
        }
    
        public static void main(String[] args){
            MyAnalyse test = new MyAnalyse();
    
            test.getVnVt();
            test.Init();
            test.createTable();
            test.analyzeLL();
            test.ouput();
            
        }
    
        //从文件中读入文法的方法
        public  static  String[] getSource(){
            StringBuffer temp = new StringBuffer();
            FileInputStream fis= null;
            try {
                fis = new FileInputStream("E:\\readin.txt");
                byte[] buff=new byte[1024];
                int len=0;
                while((len=fis.read(buff))!=-1){
                    temp.append(new String(buff,0,len));
                }
            } catch (Exception e) {
                e.printStackTrace();
            } finally {
                try {
                    fis.close();
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return temp.toString().split("\n");
        }
    
        //初始化
        @Override
        public void Init() {
            for (String s1 : inputStrings) {
                //"S->a",
                //"S->^",
                //"S->(T)",
                //"T->SU",
                //"U->,SU",
                //"U->&"
                String[] str = s1.split("->");//通过符号“->”分隔每行的文法
                char c = str[0].charAt(0);//取得左边的非终结符
                ArrayList<String> list = outputSet.containsKey(c) ? outputSet.get(c) : new ArrayList<>();
                list.add(str[1]);//添加文法右边的内容到集合中
                outputSet.put(c, list);
            }
            //求非终结符的first集
            for (Character c1 : VnSet)
                getFirst(c1);
    
            for (Character c2 : VnSet) {
                ArrayList<String> l = outputSet.get(c2);
                for (String s2 : l)
                    getFirst(s2);
            }
            //求出follow集
            getFollow(start);
            for (Character c3 : VnSet) {
                getFollow(c3);
            }
        }
    
        @Override
        public void getVnVt() {//取出终结符和非终结符的集合
            for (String s3 : inputStrings) {
                String[] str = s3.split("->");
                VnSet.add(str[0].charAt(0));
            }
            for (String s4 : inputStrings) {
                String[] str = s4.split("->");
                String right = str[1];
                for (int i = 0; i < right.length(); i++)
                    if (!VnSet.contains(right.charAt(i)))
                        VtSet.add(right.charAt(i));
            }
        }
    
        @Override
        public void getFirst(Character c) {
            ArrayList<String> list = outputSet.get(c);
            HashSet<Character> set = MyfirstSet.containsKey(c) ? MyfirstSet.get(c) : new HashSet<Character>();
            // c为终结符 直接添加
            if (VtSet.contains(c)) {
                set.add(c);
                MyfirstSet.put(c, set);
                return;
            }
            // c为非终结符 处理其每条产生式
            for (String s5 : list) {
                // c 推出空串 直接添加
                if (s5 == Character.toString('&')) {
                    set.add('&');
                }
                // X -> Y1Y2Y3… 情况
                else {
                    // 从左往右扫描生成式右部
                    int i = 0;
                    while (i < s5.length()) {
                        char tn = s5.charAt(i);
                        //先处理防止未初始化
                        getFirst(tn);
                        HashSet<Character> tvSet = MyfirstSet.get(tn);
                        // 将其first集加入左部
                        for (Character tmp : tvSet)
                            set.add(tmp);
                        // 若包含空串 处理下一个符号
                        if (tvSet.contains('&'))
                            i++;
                            // 否则退出 处理下一个产生式
                        else
                            break;
                    }
                }
            }
            MyfirstSet.put(c, set);
        }
    
        @Override
        public void getFirst(String s) {
            HashSet<Character> set = (MyfirstSetX.containsKey(s))? MyfirstSetX.get(s) : new HashSet<Character>();
            // 从左往右扫描该式
            int i = 0;
            while (i < s.length()) {
                char tn = s.charAt(i);
                HashSet<Character> tvSet = MyfirstSet.get(tn);
                // 将其非空 first集加入左部
                for (Character tmp : tvSet)
                    if(tmp != '&')
                        set.add(tmp);
                // 若包含空串 处理下一个符号
                if (tvSet.contains('&'))
                    i++;
                    // 否则结束
                else
                    break;
                // 到了尾部 即所有符号的first集都包含空串 把空串加入
                if (i == s.length()) {
                    set.add('&');
                }
            }
            MyfirstSetX.put(s, set);
        }
    
        @Override
        public void getFollow(char ch) {
            ArrayList<String> list = outputSet.get(ch);
            HashSet<Character> setA = MyfollowSet.containsKey(ch) ? MyfollowSet.get(ch) : new HashSet<Character>();
            //如果是开始符 添加 $
            if (ch == start) {
                setA.add('$');
            }
            //查找输入的所有产生式,确定c的后跟 终结符
            for (Character cha : VnSet) {
                ArrayList<String> l = outputSet.get(cha);
                for (String s : l)
                    for (int i = 0; i < s.length(); i++)
                        if (s.charAt(i) == ch && i + 1 < s.length() && VtSet.contains(s.charAt(i + 1)))
                            setA.add(s.charAt(i + 1));
            }
            MyfollowSet.put(ch, setA);
            //处理c的每一条产生式
            for (String s : list) {
                int i = s.length() - 1;
                while (i >= 0 ) {
                    char tn = s.charAt(i);
                    //只处理非终结符
                    if(VnSet.contains(tn)){
                        // 都按 A->αB&  形式处理
                        //若&不存在   followA 加入 followB
                        //若&存在,把&的非空first集  加入followB
                        //若&存在  且 first(&)包含空串   followA 加入 followB
    
                        //若&存在
                        if (s.length() - i - 1 > 0) {
                            String right = s.substring(i + 1);
                            //非空first集 加入 followB
                            HashSet<Character> setF = null;
                            if( right.length() == 1 && MyfirstSet.containsKey(right.charAt(0))) {
                                setF = MyfirstSet.get(right.charAt(0));
                            }
                            else{
                                if(!MyfirstSetX.containsKey(right)){
                                    HashSet<Character> set = new HashSet<Character>();
                                    MyfirstSetX.put(right, set);
                                }
                                setF = MyfirstSetX.get(right);
                            }
                            HashSet<Character> setX = MyfollowSet.containsKey(tn) ? MyfollowSet.get(tn) : new HashSet<Character>();
                            for (Character cha : setF) {
                                if (cha != '&') {
                                    setX.add(cha);
                                }
                            }
                            MyfollowSet.put(tn, setX);
    
                            // 若first(&)包含&   followA 加入 followB
                            if(setF.contains('&')){
                                if(tn != ch){
                                    HashSet<Character> setB = MyfollowSet.containsKey(tn) ? MyfollowSet.get(tn) : new HashSet<Character>();
                                    for (Character cha : setA) {
                                        setB.add(cha);
                                    }
                                    MyfollowSet.put(tn, setB);
                                }
                            }
                        }
                        //若&不存在   followA 加入 followB
                        else{
                            // A和B相同不添加
                            if(tn != ch){
                                HashSet<Character> setB = MyfollowSet.containsKey(tn) ? MyfollowSet.get(tn) : new HashSet<Character>();
                                for (Character cha : setA)
                                    setB.add(cha);
                                MyfollowSet.put(tn, setB);
                            }
                        }
                        i--;
                    }
                    //如果是终结符往前扫描  如 A->aaaBCDaaaa  此时&为 CDaaaa
                    else i--;
                }
            }
        }
    
        @Override
        public void createTable() {//构造预测分析表的格式
            //终结符数组
            Object[] VtArray = VtSet.toArray();
            //非终结符数组
            Object[] VnArray = VnSet.toArray();
            // 预测分析表初始化
            table = new String[VnArray.length + 1][VtArray.length + 1];
            table[0][0] = "Vn/Vt";
            //初始化首行首列
            for (int i = 0; i < VtArray.length; i++)
                table[0][i + 1] = (VtArray[i].toString().charAt(0) == '&') ? "$" : VtArray[i].toString();
            for (int i = 0; i < VnArray.length; i++)
                table[i + 1][0] = VnArray[i] + "";
            //全部置error
            for (int i = 0; i < VnArray.length; i++)
                for (int j = 0; j < VtArray.length; j++)
                    table[i + 1][j + 1] = "error";
    
            //插入生成式
            for (char A : VnSet) {
                ArrayList<String> l = outputSet.get(A);
                for(String s : l){
                    HashSet<Character> set = MyfirstSetX.get(s);
                    for (char a : set)
                        insert(A, a, s);
                    if(set.contains('&'))  {//如果包含&
                        HashSet<Character> setFollow = MyfollowSet.get(A);
                        if(setFollow.contains('$'))//判断follow集中是否包含$
                            insert(A, '$', s);
                        for (char b : setFollow)
                            insert(A, b, s);
                    }
                }
            }
        }
    
        @Override
        public void analyzeLL() {
            System.out.println("-------------------1.LL分析过程-------------------");
            System.out.println("|               分析栈        输入串     动作|  ");
            MyAnaStatck.push('$');
            MyAnaStatck.push('S');
            displayLL();//调用分析过程方法
            char X = MyAnaStatck.peek();
            while (X != '$') {
                char a = strInput.charAt(Index);
                if (X == a) {
                    MyAction = "match " + MyAnaStatck.peek();
                    MyAnaStatck.pop();
                    Index++;
                } else if (VtSet.contains(X))
                    return;
                else if (find(X, a).equals("error"))
                    return;
                else if (find(X, a).equals("&")) {
                    MyAnaStatck.pop();
                    MyAction = X + "->&";
                } else {
                    String str = find(X, a);
                    if (str != "") {
                        MyAction = X + "->" + str;
                        MyAnaStatck.pop();
                        int len = str.length();
                        for (int i = len - 1; i >= 0; i--)
                            MyAnaStatck.push(str.charAt(i));
                    } else {
                        System.out.println("error at '" + strInput.charAt(Index) + " in " + Index);
                        return;
                    }
                }
                X = MyAnaStatck.peek();
                displayLL();
            }
            System.out.println("LL(1)文法分析成功!");
            System.out.println("-------------------LL分析过程-------------------");
        }
    
        @Override
        public String find(char X, char a) {
            for (int i = 0; i < VnSet.size() + 1; i++) {
                if (table[i][0].charAt(0) == X)
                    for (int j = 0; j < VtSet.size() + 1; j++) {
                        if (table[0][j].charAt(0) == a)
                            return table[i][j];
                    }
            }
            return "";
        }
    
        @Override
        public void insert(char X, char a, String s) {//插入
            if(a == '&')
                a = '$';
            for (int i = 0; i < VnSet.size() + 1; i++) {
                if (table[i][0].charAt(0) == X)
                    for (int j = 0; j < VtSet.size() + 1; j++) {
                        if (table[0][j].charAt(0) == a){
                            table[i][j] = s;
                            return;
                        }
                    }
            }
        }
    
        @Override
        public void displayLL() {// 对输入串(a,a)$ 输出 LL(1)分析过程
            Stack<Character> s = MyAnaStatck;
            System.out.printf("%23s", s );//输出第一列:分析栈
            System.out.printf("%13s", strInput.substring(Index));//输出第二列:输入串
            System.out.printf("%10s", MyAction);//输出第三列:动作
            System.out.println();
        }
    
        @Override
        public void ouput() {
            // 输出终结符的first集
            System.out.println("-------------------2.first集-------------------");
            for (Character c : VnSet) {
                HashSet<Character> set = MyfirstSet.get(c);
                System.out.printf("%10s",c + "  ->   ");
                for (Character cha : set)
                    System.out.print(cha+" ");
                System.out.println();
            }
            System.out.println("-------------------first集-------------------");
            // 输出任意符号串的first集
            System.out.println("-------------------firstX集-------------------");
            Set<String> setStr =  MyfirstSetX.keySet();
            for (String s : setStr) {
                HashSet<Character> set = MyfirstSetX.get(s);
                System.out.printf("%10s",s + "  ->   ");
                for (Character cha : set)
                    System.out.print(cha+" ");
                System.out.println();
            }
            System.out.println("-------------------firstX集-------------------");
            // 输出follow集
            System.out.println("-------------------3.follow集-------------------");
    
            for (Character c : VnSet) {
                HashSet<Character> set = MyfollowSet.get(c);
                System.out.print("Follow " + c + " : ");
                for (Character cha : set)
                    System.out.print(cha+" ");
                System.out.println();
            }
            System.out.println("-------------------follow集-------------------");
            //构造LL1文法预测分析表
            System.out.println("-------------------4.LL1预测分析表-------------------");
    
            for (int i = 0; i < VnSet.size() + 1; i++) {
                for (int j = 0; j < VtSet.size() + 1; j++) {
                    System.out.printf("%8s", table[i][j] + " ");
                }
                System.out.println();
            }
            System.out.println("-------------------LL1预测分析表-------------------");
        }
    }
    

    四、结果分析

    1、输入正确的源程序截图:
    将符号ε替换为&
    在这里插入图片描述

    输出结果截图:
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    2、输入错误的源程序截图:
    输入错误文法
    在这里插入图片描述
    输出结果截图:
    在这里插入图片描述
    3、总结(自己的心得体会、你编写的语法分析程序的优缺点)
    S->a|^|(T)
    T->SU
    U->,SU|ε

    • 优点:文法分析过程比较详细,任务整个完成过程是充实的,这个实验报告相当于对编译原理理论课的一次实践尝试,能收获很多课堂上面学不到的知识,同时也能巩固老师所教授的知识。

    • 缺点:在写程序的时候,卡在了空串那个点。最开始尝试直接在程序中定义文法时,ε能在程序中分析成功。后来在用读入文件的方式定义文法时,控制台出现乱码,这个点解决起来花了一点时间,最后决定将符号ε替换为&,程序才能运行成功。

    展开全文
  • 通过设计编制调试一个具体的词法分析程序,加深对词法分析原理的理解。并掌握在对程序设计语言源程序进行扫描过程中将其分解为各类单词的词法分析方法。 编制一个读单词过程,从输入的源程序中,识别出各个具有独立...
  • 编译原理 C 语言词法分析 一实验题目 编制并调试 C 词法分析程序 a.txt 源代码 : ?main) { int sum=0 ,it=1;/* Variable declaration*/ if (sum==1) it++; else it=it+2; }? 设计其词法分析程序 能识别出所有的...
  • 编译原理上机实验

    2017-10-22 09:43:48
    通过设计、编制、调试一个具体的词法分析程序,加深对词法分析内部工作原理的理解,并掌握在对程序设计语言源程序进行扫描过程中将其分解为各类单词的词法分析方法。从输入的源程序中,识别出具有独立意义的各个...
  • 东北大学2022编译原理实验课——递归下降分析简单算术表达式(C++) 【问题描述】 1.设计简单算数表达式语法分析算法;(用递归下降分析来实现) 2.编写代码并上机调试运行通过。 【输入形式】 简单算数表达式 ...
  • 编译原理——词法分析实验

    万次阅读 多人点赞 2019-05-21 11:56:19
    对于如下文法所定义的语言子集,试编写并上机调试一个词法分析程序: <程序>→PROGRAM <标识符>;<分程序>. <分程序>→<变量说明>BEGIN<语句表>END <变量说明>→VAR<...
    • 实验目的

    1. 掌握词法分析器的功能。
    2. 掌握词法分析器的实现。
    • 实验内容及要求

    对于如下文法所定义的语言子集,试编写并上机调试一个词法分析程序:

    <程序>→PROGRAM <标识符>;<分程序>.

    <分程序>→<变量说明>BEGIN<语句表>END

    <变量说明>→VAR<变量表>:<类型>;| <空>

    <变量表>→<变量表>,<变量> | <变量>

    <类型>→INTEGER

    <语句表>→<语句表>;<语句> | <语句>

    <语句>→<赋值语句> | <条件语句> | <WHILE语句> | <复合语句> | <过程定义>

    <赋值语句>→<变量>:=<算术表达式>

    <条件语句>→IF<关系表达式>THEN<语句>ELSE<语句>

    <WHILE语句>→WHILE<关系表达式>DO<语句>

    <复合语句>→BEGIN<语句表>END

    <过程定义>→PROCEDURE<标识符><参数表>;

    BEGIN<语句表>END

    <参数表>→(<标识符表>)| <空>

    <标识符表>→<标识符表>,<标识符> | <标识符>

    <算术表达式>→<算术表达式>+<项> | <项>

    <项>→<项>*<初等量> | <初等量>

    <初等量>→(<算术表达式>)| <变量> | <无符号数>

    <关系表达式>→<算术表达式><关系符><算术表达式>

    <变量>→<标识符>

    <标识符>→<标识符><字母> | <标识符><数学> | <字母>

    <无符号数>→<无符号数><数字> | <数字>

    <关系符>→= | < | <= | > | >= | <>

    <字母>→A | B | C | ··· | X | Y | Z

    <数字>→0 | 1 | 2 | ··· | 8 | 9

    <空>→

    要求和提示:

    (1)单词的分类。

    可将所有标识符归为一类;将常数归为另一类;保留字和分隔符则采取一词 一类。

    (2)符号表的建立。

    可事先建立一保留字表,以备在识别保留字时进行查询。变量名表及常数表 则在词法分析过程中建立。

    (3)单词串的输出形式。

    所输出的每一单词,均按形如(CLASS,VALUE)的二元式编码。对于变量标 识符和常数,CLASS字段为相应的类别码,VALUE字段则是该标识符、常数 在其符号表中登记项的序号(要求在变量名表登记项中存放该标识符的字符 串,其最大长度为四个字符;常数表登记项中则存放该整数的二进制形式)。 对于保留字和分隔号,由于采用一词一类的编码方式,所以仅需在二元式的 CLASS字段上放置相应的单词的类别码,VALUE字段则为“空”。不过,为便 于查看由词法分析程序所输出的单词串,也可以在CLASS字段上直接放置单 词符号串本身。

    • 单词分类表

    以下为单词分类表(单词符号,种别编码):

    单词符号

    种别编码

    单词符号

    种别编码

    auto

    1

    void

    30

    break

    2

    volatile

    31

    case

    3

    while

    32

    char

    4

    标识符

    33

    const

    5

    常型整量

    34

    continue

    6

    +

    35

    default

    7

    -

    36

    do

    8

    *

    37

    double

    9

    /

    38

    else

    10

    <

    39

    enum

    11

    <=

    40

    extern

    12

    >

    41

    float

    13

    >=

    42

    for

    14

    =

    43

    goto

    15

    ==

    44

    if

    16

    <>

    45

    int

    17

    ;

    46

    long

    18

    (

    47

    register

    19

    )

    48

    return

    20

    ^

    49

    short

    21

    ,

    50

    signed

    22

    #

    51

    sizeof

    23

    %

    52

    static

    24

    [

    53

    struct

    25

    ]

    54

    switch

    26

    {

    55

    typedef

    27

    }

    56

    union

    28

    .

    57

    unsigned

    29

    //

    58

    • 单词状态图

    • 算法描述

    1.首先,我将单词类别总分为六大类:

        1:标识符

        2:数字

        3:算数运算符 + - * \

        4:关系运算符 <、<=、>、>=、<>、=、==

        5:保留字(32)

              auto      break    case    char   const      continue

              default    do      double   else   enum      extern

              float      for      goto    if      int        long

              register    return   short    signed  sizeof     static

              struct      switch  typedef  union   unsigned  void

               volatile    while

        6:界符 ;、(、)、^、,、#、%、[、]、{、}、.、\\

    2.每种单词类别的识别及判断方法如下:

    首先从文件中读一个字符,赋值给ch,

        如果ch为空格,则文件扫描列序号加一;

        如果ch为回车,则文件扫描行序号加一;

    其它情况如下:

    (1)如果ch为字母或下划线,继续扫描,直到ch不是数字、字母或下划 线,则开始判断单词类型:

              查找关键字表,若找到匹配项,则为关键字;

              否则为标识符,查找标识符表,若没有找到匹配项,则添加到标识符表中。(动态生成标识符表)

              如果ch为数字,继续扫描,直到ch不是数字,则开始判断单词类型: 若数字在合法范围内,则为数字,查找标识符表,若没有找到             匹配项,则添加到数字表中;(动态生成数字表)

               否则为非法单词。

    (2)如果ch是加减乘,一定是算数运算符。

    (3)如果ch为;、(、)、^、,、#、%、[、]、{、}、.,则一定是界符。

    (4)如果ch为<,则继续扫描下一个:

              若下一个为=,则为<=;

               若下一个为>,则为<>;

               否则,为<。

    (5)如果ch为>,则继续扫描下一个:

              若下一个为=,则为>=;

              否则,为>。

    (6)如果ch为/,则继续扫描下一个:

              若下一个为/,则为注释,这一行剩下的全被注释了;

              否则,则为/。

    3.出错处理:

    我使用了两个全局变量:line,col,分别用于定位文件中扫描的位置信息,当发现当前字符为非法字符时,输出报错信息,并输出非法字符在文件中的所在位置信息。

    4.输出显示:

    将所输出的每一单词,均按形如(CLASS,VALUE)的二元式编码。对于变量标识符和常数,CLASS字段为相应的类别码,VALUE字段则是该标识符、常数在其符号表中登记项的序号。对于保留字和分隔号,由于采用一词一类的编码方式,为便于查看由词法分析程序所输出的单词串,所以在CLASS字段上直接放置单词符号串本身,VALUE字段则为“空”。使用分支结构,根据判断结果,从而进行相应输出显示。

    • 程序结构

    1.变量常量定义:

    对程序所需常量以及全局变量进行定义,其中包含:

    (1)全局变量:

    int seekresult:fseek的时候用来接着的;

    string word="":字符串,当前词;

    char ch:每次读进来的一个字符;

    int num=0:每个单词中当前字符的位置;

    int line=1:行数;

    int col=1:列数;

    bool flag:文件是否结束扫描;

    int type;:单词的类型;

    char IDentifierTable[1000][40]:标识符表;

    char DigitBTable[1000][40]常数表等。

    (2)常量:

    static char ReserveWord[32][20]:保留字表;

    static char SuanshuOperator[4][4]:算术运算符表;

    static char GuanxiOperator[7][4]:逻辑运算符表;

    static char Jiefu[36][4]:界符表。

    2.主要函数:

    (1)bool Isletter(char x)函数:判断字符x是否为字母;

    (2)bool IsDigit(char x)函数:判断字符x是否为数字;

    (3)bool IsJiefu(char x)函数:判断字符x是否为界符;

    (4)bool IsSuanshuyunsuanfu(char x) 函数:判断字符x是否为算数运算符;

    (5)bool IsGuanxiyunsuanfu(char x)函数:判断字符x是否为关系运算符;

    (6)int Scanner(FILE *fp)函数:其主要功能为从文件里读一个单词,调用基础函数进行单词类别,。

    (7)int main()函数:程序入口,进行文件扫描,并调用Scanner(FILE *fp)函数对单词进行判断,输出分析结果。

    • 运行结果

    1.待分析文件code.txt:

    2.运行结果:

                 

    3.文件目录:

    4.常数表:

    5.标识符表:

     

    • 调试情况

    在此次实验中,遇到的问题还是比较多的,主要分为以下几种:

    1.读文件和写文件操作:

    由于待分析内容存储在文本文件中,所以文件的读取是必不可少的操作;而单词分析时需要动态生成标识符表和常数表,故需要追写文件。一开始由于语言功底不太扎实,实现的不太顺利,但是在上网查找了解决方案以后,问题就迎刃而解了。

    2.各种单词类别的识别和判断以及出错处理:

    这是词法分析器的核心也是难点,这部分必须逻辑十分清晰才可以实现,一开始虽然听懂了课堂上的内容,但是理解的还是不够深刻,感觉自己已经将单词类别进行了合理的划分,但是具体实现细节上还是遇到了不少的困难。比如,在一些相似单词的识别上面困惑了一段时间,想到了老师上课所说的“超前搜索”算法,所以我进行了实现,但是发现位置定位是一个需要特别关注的问题,我的解决方案就是:添加两个全局位置变量以及一些局部位置变量,将文件中现在正在扫描的位置以及这个单词第一个字符的位置信息记录下来,然后捋清他们之间的关系以及使用目的,则问题也就解决了,并且也使得报错信息可以包含非法字符在文件中的位置所在。

    3.标识符表和常数表的动态生成:

    关于这个问题的解决,我将它放在了识别的过程当中,就可以做到动态生成,并且添加了文件追写,则可以在文件中查看生成的表信息了。

    4.输出显示:

    这个问题一开始实现的有些困难,当我发现它的重心在于认清每个单词的分类情况,并通过识别结果就可以很好的实现了。

    • 测试文件 code.txt

    int main(void) {
      int min=2, mid=3, max=1, t;
      if (min > mid) {
        t = min;
        min = mid;
        mid = t;
      }
      if (min > max) {
        t = min;
        min = max;
        max = t;
      }
      if (mid > max) {
        t = mid;
        mid = max;
        max = t;
      }
    }
    • 源代码

    #include<iostream>
    #include<fstream>
    #include<cstdio>
    #include<cstring>
    #include<string>
    #include<cstdlib>
    
    using namespace std;
    
    /*
    1:标识符
    2:数字 
    3:算数运算符 + - * 
    4:关系运算符 <=、  >=、  <>、  == =、 <、>
    5:保留字(32)
    auto       break    case     char        const      continue
    default    do       double   else        enum       extern
    float      for      goto     if          int        long
    register   return   short    signed      sizeof     static
    struct     switch   typedef  union       unsigned   void
    volatile    while
    6:界符 
    */
    
    int seekresult;		//fseek的时候用来接着的 
    string word="";		//字符串,当前词 
    char ch;			//每次读进来的一个字符
    int num=0;			//每个单词中当前字符的位置
    int line=1;			//行数
    int col=1;			//列数
    bool flag;			//文件是否结束扫描 
    int type;			//单词的类型
    
    //保留字表
    static char ReserveWord[32][20] = {
        "auto", "break", "case", "char", "const", "continue",
        "default", "do", "double", "else", "enum", "extern",
        "float", "for", "goto", "if", "int", "long",
        "register", "return", "short", "signed", "sizeof", "static",
        "struct", "switch", "typedef", "union", "unsigned", "void",
        "volatile", "while"
    };
    
    //算术运算符表
    static char SuanshuOperator[4][4] = {
        "+", "-", "*", "/"
    };
    //逻辑运算符表 
    static char GuanxiOperator[7][4] = {
        "<", "<=", ">", ">=", "=", "==","<>"
    };
    //界符表(12)
    static char Jiefu[36][4] = {
    	";", "(", ")", "^", ",", "#","%", "[", "]", "{", "}","."
    };
    
    //标识符表
    //string IDentifierTable[1000] = { "" };
    char IDentifierTable[1000][40] = {};
    
    //常数表 
    //int DigitBTable[1000][50] = {};
    char DigitBTable[1000][40] = {};
    
    int Inum=0;
    
    int Dnum=0;
    
    
    //判断是否是:字母
    bool Isletter(char x)
    {
    	if((x>='a'&&x<='z')||(x>='A'&&x<='Z'))
    		return true;
    	else return false;
    }
    
    //判断是否是:数字 
    bool IsDigit(char x)
    {
    	if(x>='0'&&x<='9')
    		return true;
    	else
    		return false;
    }
    
    //判断是否是:界符 
    bool IsJiefu(char x) 
    {
    	int i=0;
    	int temp=0;
    	for(i=0;i<14;i++)
    	{
    		if( x == Jiefu[i][0] )
    		{
    			temp=1;
    			break;
    		 } 
    	}
    	if( temp == 1 )
    		return true;
    	else
    		return false;
    }
    
    //判断是否是 算数运算符:加减乘
    bool IsSuanshuyunsuanfu(char x)
    {
    	if(x=='+'||x=='-'||x=='*')
    		return true;
    	else return false;
    }
    
    //判断是否是 关系运算符:等于(赋值),大于小于(大于等于,小于等于,大于小于) 
    bool IsGuanxiyunsuanfu(char x)
    {
    	if(x=='='||x=='<'||x=='>')
    		return true;
    	else
    		return false;
    } 
    
    //从文件里读一个单词 
    int Scanner(FILE *fp)
    {
    	//先读一个字符,赋值给ch 
        ch=fgetc(fp);
        
        if(feof(fp)){
            flag=0;
    		return 0;
        }
        else if(ch==' ')
        {
            col++;
            return 0;
        }
        else if(ch=='\n')
        {
            line++;
            col=1;
            return 0;
        }
        //如果是字母开头或 '_' 看关键字还是标识符 
        else if( Isletter(ch) || ch=='_' )
        {
            word+=ch;
    		col++;
            while( (ch=fgetc(fp)) && ( Isletter(ch) || IsDigit(ch) || ch=='_'))
            {
                word+=ch;
    			col++;
            }
    		//文件读完,返回true
            if(feof(fp)){
                    flag=0;
    				return 1;
            }
            //检验是否是保留字 
            for(int i=1;i<=32;i++){
                if( word == ReserveWord[i] ){
                	//SEEK_CUR当前位置,fseek函数作用:文件位置指针从当前位置位移一个位置 
                    seekresult=fseek(fp,-1,SEEK_CUR);
                  	//5+i-1:保留字 
    				return 5+i-1;
                }
            }
            for(int Ii=0;Ii<Inum;Ii++)
            {
            	if(Inum!=0 && strcmp(IDentifierTable[Ii],word.c_str())==0)
            	{
            		seekresult=fseek(fp,-1,SEEK_CUR);	
            		//1:标识符 
            		//return 1;
            		return 1000+Ii+1;
    			}
    		}
            strcpy(IDentifierTable[Inum],word.c_str());
        	Inum=Inum+1;
    		//写追加 
    		ofstream Arithmetic_operator;
    		Arithmetic_operator.open("IDentifierTable.txt",ios::app);
    		Arithmetic_operator<<word<<" "<<endl;
        	Arithmetic_operator.close();
        	
    		seekresult=fseek(fp,-1,SEEK_CUR);	
            //1:标识符 
            //return 1;
            return 1000+Inum;
        }
     
        //开始是加减乘,一定是算数运算符3 
        else if(IsSuanshuyunsuanfu(ch))
        {
            word+=ch;
    		col++;
    		//3:算数运算符 
            return 3;
        }
     
        //开始是数字就一定是数字2 
        else if(IsDigit(ch))
        {
            word+=ch;
    		col++;
            while((ch=fgetc(fp)) && IsDigit(ch))
            {
                word+=ch;
    			col++;
            }
            int Di=0;
            for(Di=0;Di<Inum;Di++)
            {
            	if(Dnum!=0 && strcmp(DigitBTable[Di],word.c_str())==0)
            	{
            		seekresult=fseek(fp,-1,SEEK_CUR);	
            		//2:数字 
            		//return 2;
            		return 2000+Di+1;
    			}
    		}
            strcpy(DigitBTable[Dnum],word.c_str());
        	Dnum=Dnum+1;
    		//写追加 
    		ofstream Arithmetic_operator;
    		Arithmetic_operator.open("DigitBTabl.txt",ios::app);
    		Arithmetic_operator<<word<<" "<<endl;
        	Arithmetic_operator.close();
       	
    //        if(feof(fp)){
    //                flag=0;
    //				return 2;
    //        }
    
            seekresult=fseek(fp,-1,SEEK_CUR);
            //2:数字 
            return 2000+Dnum;
        }
     
        //检验界符6 
        else if(IsJiefu(ch))
        {
        	int Ji;
    		for(Ji=0;Ji<12;Ji++)
    		{
    			if( ch == Jiefu[Ji][0] )
    			{
    				break;
    			} 
    		}
            word+=ch;col++;
            //6-1+32+i:界符 
            return (6-1+32+Ji);
        }
     
        //检验关系运算符4 :<=、>=、<>、==、 < 、>
        else if( IsGuanxiyunsuanfu(ch) )
        {
            col++;
            word+=ch;
    		//检验  <> <=
            if(ch=='<')   
            {
                ch=fgetc(fp);
                if(ch=='>' || ch=='=')
                {
                    word+=ch;
                    col++; 
                    return 4;
                }
            }
            //检验  >= ==
            else{
                ch=fgetc(fp);
                if(ch=='=')
                {
                    word+=ch;
                    col++;
                    return 4;
                }
            }
            if(feof(fp)){
                    flag=0;
            }
            seekresult=fseek(fp,-1,SEEK_CUR);
            //3:算数运算符 
            return 3;
        }
     
        //首字符是 / 有可能是除号 也有可能是注释
        else if(ch=='/')
        {
            col++;word+=ch;
            ch=fgetc(fp);
            //这种情况是除号
            if(ch!='*' && ch !='/')
            {
                seekresult=fseek(fp,-1,SEEK_CUR);
                //3:算数运算符 
                return 3;
            }
            //注释符//:这一行剩下的全被注释了
            if(ch=='/')
            {
                word.clear();
                while((ch=fgetc(fp)) && ch!='\n' && !feof(fp) )
                {}
                if(feof(fp)){
                    flag=0;
    				return 0;
                }
                else{
                   seekresult=fseek(fp,-1,SEEK_CUR);
                }
                line++;col=1;
                return 0;
            }
            if(ch=='*')
            {
                bool flag5=1;
                while(flag5)
                {
                    word.clear();
                    ch=fgetc(fp);
                    col++;
                    if(ch=='\n')
    				{
    					line++;
    					col=1;
    				}
                    if(ch!='*')
    					continue;
                    else 
    				{
                        ch=fgetc(fp);
                        col++;if(ch=='\n'){line++;col=1;}
                        if(ch=='/'){
                            flag5=0;
                        }
                        else continue;
                    }
                    if(feof(fp))
    				{
    					flag=0;
    					return 0;
    				}
                }
            }
        }
        else {
            word+=ch;
            col++;
            return -1;
        }
    }
     
    int main()
    {
    	FILE *fp;
        
    	cout<<"open "<<"code.txt"<<endl;
        system("pause");
     
        flag=1;
        
    	//打开源代码文件 
    	
    	//未打开 
        if((fp=fopen("code.txt","r"))==NULL)
        {
            cout<<"Sorry,can't open this file."<<endl;
            flag=0;
        }
        //已打开 
        while(flag==1)
        {
    		//反复调用扫描函数提取单词
            type=Scanner(fp);	
     		
    		//1:标识符
            if(type>1000&&type<2000)
            {
                //cout<<"type:1 identifier      "<<"line "<<line<<" col "<<col-word.length()<<"  "<<word<<endl;
                cout<<"("<<word<<","<<type-1000<<")"<<endl; 
    			if(word.length()>20)
                	cout<<"ERROR Identifier length cannot exceed 20 characters"<<endl;
                word.clear();
            }
    		//2:数字   
            else if(type>2000)
            {
                //cout<<"type:2 positive number "<<"line "<<line<<" col "<<col-word.length()<<"  "<<word<<endl;
                cout<<"("<<word<<","<<(type-2000)<<")"<<endl;
    			if(word[0]=='0')
                	cout<<"ERROR: The first digit cannot be 0!"<<endl;
                word.clear();
            }
    		//3:算数运算符 + - * / 
            else if(type==3)
            {
                //cout<<"type:3 unary_operator  "<<"line "<<line<<" col "<<col-1<<"  "<<word<<endl;
                cout<<"("<<word<<","<<"3"<<")"<<endl;
                word.clear();
            }
            
            //4:关系运算符 <、<=、>、>=、= 、<> 
            else if(type==4)
            {
                //cout<<"type:4 double_operator "<<"line "<<line<<" col "<<col-2<<"  "<<word<<endl;
                cout<<"("<<word<<","<<"4"<<")"<<endl;
    			word.clear();
            }
            //6-1+32 - 6-1+32+11:界符
            else if(type>=37)
            {
                //cout<<"type:5 Separator       "<<"line "<<line<<" col "<<col-1<<"  "<<word<<endl;
            	cout<<"("<<word<<","<<"_"<<")"<<endl;
    			//cout<<"("<<type<<","<<"_"<<")"<<endl;  
    			word.clear();
            }
           //5 - 5-1+32:保留字 
            else if( type>=5 && type<=36)
            {
                //cout<<"type:6 reserved word   "<<"line "<<line<<" col "<<col-word.length()<<"  "<<word<<endl;
                cout<<"("<<word<<","<<"_"<<")"<<endl;
    			//cout<<"("<<type<<","<<"_"<<")"<<endl;  
    			word.clear();
            }
            //非法字符
            else if(type==-1)
            {
               cout<<"Illegal character   "<<"line "<<line<<" col "<<col-1<<"  "<<word<<endl;
               word.clear();
            }
        }
            int a=fclose(fp);
            cout<<"Do you want to close?(Y or N)"<<endl;
            char end;
            while(cin>>end && end!='Y'){
                cout<<"Do you want to close?(Y or N)"<<endl;
            }
        return 0;
    }

    展开全文
  • 数学与软件科学学院 实验报告 学 期 2015 至 2016 第 2 学期 2016年 3月 21 日 课程名称 编译原理 专 业 信息与计算科学 2013 级 5 班 实验编号 2 实验名称 递归下降分析 指导教师 王开端 姓 名 李丹 学 号 ...
  • 编译原理课程实验-LL(1) 语法分析实验: 实验目的:1.了解 LL(1)语法分析是如何根据语法规则逐一分析词法分析所得到的单词,检查语法错误,即掌握语法分析过程;2.掌握LL(1)文法判别调剂和 LL(1)语法分析的设计与...
  • 通过设计调试词法分析程序,实现从源程序中分出各种单词的方法;加深对课堂教学的理解;提高词法分析方法的实践能力

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 91,390
精华内容 36,556
关键字:

编译原理 调试器