精华内容
下载资源
问答
  • 之前的传错了 云南大学编译原理-实现代码优化器
  • 代码生成的主要任务 指令选择 选择适当的__目标机指令__来实现__中间表示(IR)__语句 例: 三地址语句:x = y+z 目标代码 LD R0 , y:把的值加载到寄存器中 AD R0 , R0 , z:z加到上 R0 上 ST , x, R0:把 R0的值...

    代码生成器的主要任务

    一、指令选择

    • 选择适当的目标机指令来实现中间表示(IR)语句,
    • 例如:三地址语句 x = y + z
      目标代码:
      
      LD R0, y      /* 把y的值加载到寄存器R0中*/
      ADD R0, R0, z /* z加到R0上*/
      ST x, R0      /* 把R0的值保存到x中*/
      
    • 如上,直接进行生成,会产生一些冗余指令。目标代码需要进一步优化。

    二、寄存器分配和指派:

    • 把哪个值放在哪个寄存器中

    三、指令排序:

    • 按照什么顺序来安排指令的执行

    一个简单的目标机模型

    三地址机器模型:

    • 加载、保存、运算、跳转等操作
    • 内存按字节寻址
    • n个通用寄存器R0,R1,,Rn1R_0, R_1, …, R_{n-1}
    • 假设所有的运算分量都是整数
    • 指令之间可能有一个标号

    目标机器的主要指令

    • 加载指令 LD dst, addr

      • LD r, x
      • LD r1, r2
    • 保存指令 ST x, r

    • 运算指令 OP dst, src1, src2

    • 无条件跳转指令 BR L

    • 条件跳转指令 Bcond r, L

      • 例: BLTZ r, L

    寻址模式

    • 变量名a

      • 例如:LD R1, a,即R1 = contents(a),将地址 a 中的内容放到寄存器 R1
    • a(r),a是一个变量,r是一个寄存器

      • 例如:LD R1, a(R2),即R1 = contents(a + contents(R2))
    • c(r),c是一个整数

      • 例如:LD R1, 100(R2),即R1 = contents(contents(R2) + 100),表示寄存器 R2 中存放的地址,加上整数c,其表示的地址所存放的内容。
    • ∗r,在寄存器r的内容所表示的位置上存放的内存位置

      • 例如:LD R1, *R2,即R1 = contents(contents(contents(R2))),这是间接寻址模式
    • ∗c(r),在寄存器r中内容加上c后所表示的位置上存放的内存位置

      • 例如:LD R1, *100(R2),即R1 = contents(contents(contents(R2) + 100))
    • KaTeX parse error: Expected ‘EOF’, got ‘#’ at position 1: #̲c,

      • 例如LD R1, #100,即R1 = 100。

    指令选择

    运算语句的目标代码

    • 三地址语句:x = y - z

    • 目标代码:

      LD R1 , y        // R1 = y
      LD R2 , z        // R2 = z
      SUB R1 , R1 , R2 // R1 = R1 - R2
      ST x , R1        // x = R1
      
    • 尽可能避免使用上面的全部四个指令,如果:

      • 所需的运算分量已经在寄存器中了
      • 运算结果不需要存放回内存

    数组寻址语句的目标代码

    • 三地址语句:b = a[ i ](a是一个实数数组,每个实数占8个字节)
      • 目标代码:
      LD R1 , i      // R1 = i
      MUL R1 , R1, 8 // R1=R1 * 8
      LD R2 , a(R1)  // R2=contents ( a + contents(R1) )
      ST b , R2      // b = R2
      
    • 三地址语句:a [ j ] = c(a是一个实数数组,每个实数占8个字节)
      • 目标代码:
      LD R1 , c       // R1 = c
      LD R2 , j       // R2 = j
      MUL R2 , R2 , 8 //R2 = R2 * 8
      ST a(R2) , R1   // contents(a+contents(R2))=R1
      

    指针存取语句的目标代码

    • 三地址语句:x = *p
      • 目标代码:
      LD R1, p      // R1 = p
      LD R2, 0 (R1) // R2 = contents ( 0 + contents (R1) )
      ST x , R2     // x = R2
      
    • 三地址语句:*p = y
      • 目标代码:
      LD R1 , p    // R1 = p
      LD R2 , y    // R2 = y
      ST 0(R1), R2 //contents ( 0 + contents ( R1 ) ) = R2
      

    条件跳转语句的目标代码

    • 三地址语句:if x < y goto L
      • 目标代码:
      LD R1 , x        // R1 = x
      LD R2 , y        // R2 = y
      SUB R1 , R1 , R2 // R1=R1 - R2
      BLTZ R1 , M      // if R1 < 0 jump to M
      
      • M是标号为L的三地址指令所产生的目标代码中的第一个指令的标号。

    过程调用和返回的目标代码
    静态区存储分配

    • 方法调用
      • 三地址语句:call callee
      • 目标代码
      ST callee.staticArea, #here + 20 //即callee的活动记录在静态区中的起始位置
      BR callee.codeArea,  //即calle的目标代码在代码区中的起始位置
      
    • 方法返回
      • 三地址语句:return
      • 目标代码
      BR * callee.staticArea // 间址,返回地址在 callee 栈帧底部
      

    栈式存储分配

    • 方法调用
      • 三地址语句:call callee
      • 目标代码
      ADD SP, SP, #caller.recordsize 
      ST 0(SP), #here+16  // 把返回地址压到被调过程的栈帧底部
      BR callee. code Area
      
    • 方法返回
      • 三地址语句:return
      • 目标代码
      	被调用过程:BR* 0(SP)
      	调用过程:SUB SP, SP, #caller.recordsixe
      

    寄存器的选择

    三地址语句的目标代码生成

    对每个形如x = y op z的三地址指令I,执行如下动作:

    • 调用函数 getreg(I)来为x、y、z选择寄存器,把这些寄存器称为RxRyRzR_x R_y R_z
    • 如果RyR_y 中存放的不是y ,则生成指令“LD    Ry ,    y′ ′”。y′ 是存放y的内存位置之一
    • 类似的,如果Rz中存放的不是z,生成指令“LD    Rz ,   z ′ ”
    • 生成目标指令“OP    Rx ,    Ry ,    Rz ”

    寄存器描述符和地址描述符

    寄存器描述符(register descriptor):

    • 记录每个寄存器当前存放的是哪些变量的值

    地址描述符(address descriptor):

    • 记录运行时每个名字的当前值存放在哪个或哪些位置
    • 该位置可能是寄存器、栈单元、内存地址或者是它们的某个集合
    • 这些信息可以存放在该变量名对应的符号表条目中

    基本块的收尾处理

    对于一个在基本块的出口处可能活跃的变量x

    • 如果它的地址描述符表明它的值没有存放在x的内存位置上,则生成指令“ST x, R” ( R是在基本块结尾处存放x值的寄存器)

    管理寄存器和地址描述符

    对于指令LDR, x":

    • 修改R的寄存器描述符,使之只包含x
    • 修改x的地址描述符,把R作为新增位置加入到x的位置集合中
    • 从任何不同于x的地址描述符中删除R

    对于指令"OP Rx, Ry ,Rz,":

    • 修改Rx的寄存器描述符,使之只跑含x
    • 从任何不同于Rx的寄存器描述符中删除x
    • 修改x的地址描述符,使之只包含位置Rx
    • 从任何不同于x的地址描述符中删除Rx

    对于指令“ST x, R”:

    • 修改x的地址描述符,使之包含自己的内存位置

    对于复制语句x=y,如果需要生成加载指令"LD Ry, y’"则:

    • 修改Ry的寄存器描述符,使之只包含y
    • 修改y的地址描述符,把Ry作为新增位置加入到y的位置集合中
    • 从任何不同于y的变量的地址描述符中删除Ry
    • 修改Ry的寄存器描述符,使之也包含x
    • 修改x的地址描述符,使之只包含Ry

    窥孔优化

    • 窥孔(peephole)是程序上的一个小的滑动窗口

    • 窥孔优化是指在优化的时候,检查目标指令的一个滑动窗口(即窥孔) ,并且只要有可能就在窥孔内用更快或更短的指令来替换窗口中的指令序列。

    • 也可以在中间代码生成之后直接应用窥孔优化来提高中间表示形式的质量。

    具有窥孔优化特点的程序变换的例子

    • 冗余指令删除
      • 例如:消除冗余的加载和保存指令
      • 例如:消除不可达代码,一个紧跟在无条件跳转之后的不带标号的指令可以被删除。
    • 控制流优化
      • 在代码中出现跳转到跳转指令的指令时,某些条件下可以使用一个跳转指令来代替。
      • 如果不再有跳转到L1的指令,并且语句L1: goto L2之前是一个无条件跳转指令,则可以删除该语句。
    • 代数优化
      • 代数恒等式:消除窥孔中类似于x=x+0或x=x*1的运算指令。
      • 强度削弱:
        对于乘数(除数)是2的幂的定点数乘法(除法) ,用移位运算实现代价比较低;
        除数为常量的浮点数除法可以通过乘数为该常量倒数的乘法来求近似值。
    • 机器特有指令的使用
      • 充分利用目标系统的某些高效的特殊指令来提高代码效率。
      • 例如:INC指令可以用来替代加1的操作。
    展开全文
  • 一、题目的理解和说明 ...其过程分为词法分析、语法分析、语义分析中间代码生成、中间代码优化、代码生成等五个阶段。而本次实验所解决的问题是编译程序的第一个阶段–词法分析。 实验要求实现一个可...

    一、题目的理解和说明

    编译原理这门课是计算机专业的核心课程之一,是一门研究软件是什么,为什么可以运行,以及怎么运行的学科。编译系统的改进将会直接对其上层的应用程序的执行效率,执行原理产生深刻的影响。编译原理的目的是将源语言翻译成目标语言。其过程分为词法分析、语法分析、语义分析中间代码生成、中间代码优化、代码生成等五个阶段。而本次实验所解决的问题是编译程序的第一个阶段–词法分析。

    实验要求实现一个可以分析一门编程语言的语法分析器。我以c/c++语言的语法为例,采用c/c++进行编程实现一个可以对c/c++语言进行词法分析的分析器。

    该词法分析器的目标为:处理c语言源程序,过滤掉无用符号,判断源程序中单词的合法性,并分解出正确的单词,以二元组形式存放在文件中。

    词法分析器所做的工作主要是对源程序进行编译预处理(去除注释、无用的回车换行找到包含的文件等)之后,对整个源程序进行分解,分解成一个个单词,这些单词有且只有五类,分别是标识符、保留字、常数、运算符、界符。

    词法分析面向的对象是单个的字符,目的是把它们组成有效的单词(字符串);而语法的分析则是利用词法分析的结果作为输入来分析是否符合语法规则并且进行语法制导下的语义分析,最后产生四元组(中间代码),进行优化(可有可无)之后最终生成目标代码。因此词法分析是整个编译程序的基础,如果词法分析做不好,那么会严重英雄后续编译阶段的效果。二

    二、程序功能和框架

    1. 识别单词的类

    总共需要识别的单词分为五类:标识符、保留字、常数、运算符、界符。为了能更大限度的处理c语言的各种语句,因此我对这五类单词定义为:
    第一类:标识符 letter(letter | digit)* 无穷集
    第二类:常数 (digit)+ 无穷集
    第三类:保留字(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

    第四类:界符 ‘/’、‘//’、 () { } [ ] " " ’ 等
    第五类:运算符 <、<=、>、>=、=、+、-、
    、/、^、等
    然后对所有可数符号进行编码:
    <$,0>
    <auto,1>

    <while,32><+,33><-,34><*,35></,36><<,37><<=,38><>,39><>=,40><=,41>
    <==,42><!=,43><;,44><(,45><),46><^,47><,48><",49><’,50><#,51><&,52>
    <&&,53><|,54><||,55><%,56><~,57><<<,58>左移<>>,59>右移<[,60>
    <],61><{,62><},63><,64><.,65><?,66><:,67><!,68>"[","]","{","}"
    <常数99 ,数值><标识符100 ,标识符指针>

    上述二元组中左边是单词的符号,右边为其种别码,其中常数和标识符有点特别,因为是无穷集合,因此常数用自身来表示,种别码为99,标识符用标识符符号表的指针表示(当然也可用自身显示,比较容易观察),种别码100。根据上述约定,一旦见到了种别码syn=63,就唯一确定了‘}’这个单词。

    2.程序框架设计

    确定好这些单词种类后,然后程序需要实现以下几个功能函数:
    保留字识别函数:int SearchRWord(char RW[][20],char s[])
    字母判别函数:bool IsLetter(char letter)
    数字判别函数:bool IsDigit(char digit)
    预处理程序:void PreProcessing(char r[], int pProject)
    扫描器(算法核心):void Scanner(int &syn, char resourceProject[], char token[], int &pProject)

    上述函数中,最核心的在于扫描器。扫描器的实现主要依据于DFA理论。旨在实现对读入且经过预处理后的字符流中逐个字符进行扫描判别,然后以实现的有限自动机算法逐个识别以空格隔开的单词,并通过查找其相关二元组序列:(自身值,种别码)来达成识别单词种类的目的。

    程序的基本处理流程描述为:
    (1)词法分析程序打开源文件,读取文件内容,直至遇上’$’文件结束符,然后读取结束。
    (2)对读取的文件进行预处理,从头到尾进行扫描,去除//和/* */的内容,以及一些无用的、影响程序执行的符号如换行符、回车符、制表符等。但是千万注意不要在这个时候去除空格,因为空格在词法分析中有用,比如说int i=3;这个语句,如果去除空格就变成了“inti=3”,这样就失去了程序的本意,因此不能在这个时候去除空格。
    (3)选下面就要对源文件从头到尾进行扫描了,从头开始扫描,这个时候扫描程序首先要询问当前的字符是不是空格,若是空格,则继续扫描下一个字符,直至不是空格,然后询问这个字符是不是字母,若是则进行标识符和保留字的识别;若这个字符为数字,则进行数字的判断。否则,依次对这个字符可能的情况进行判断,若是将所有可能都走了一遍还是没有知道它是谁,则认定为错误符号,输出该错误符号,然后结束。每次成功识别了一个单词后,单词都会存在token[ ]中。然后确定这个单词的种别码,最后进行下一个单词的识别。这就是扫描程序进行的工作,可以说这个程序彻底实现了确定有限自动机的某些功能,比如说识别标识符,识别数字等。为了简单起见,这里的数字只是整数。
    (4)主控程序主要负责对每次识别的种别码syn进行判断,对于不同的单词种别做出不同的反应,如对于标识符则将其插入标识符表中。对于保留字则输出该保留字的种别码和助记符,等等吧。直至遇到syn=0;程序结束。

    三、设计说明

    1.变量存储

    在报告的第二部分,我介绍了单词的五种种类:标识符、保留字、常数、运算符、界符。
    在程序实现中,我设置以下数据结构分别存储上述五种单词种类:

    /*******保留字表*******/
    static char RWord[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 OandD[36][10] = {	
    "+", "-", "*", "/", "<", "<=",	
    ">", ">=", "=", "==","!=", ";",	
    "(", ")", "^", ",", "\"", "\'",	
    "#", "&","&&", "|", "||", "%",	
    "~", "<<", ">>", "[", "]", "{",	
    "}", "\\", ".", "\?", ":", "!" };
    /*******界符与运算符表*******/
    /*******标识符表*******/
    static char IDtable[1000][50] = { "" };//初始为空
    /*******标识符表*******/

    2. 基本函数的实现

    /*******识别保留字*******/
    int SearchRWord(char RW[][20],char s[]) {
     for (int i = 0;i<32;i++) {
      if (strcmp(RW[i], s) == 0) {
       //所识别的单词和保留字表中;
       //存储的保留字比较;
       //正确则返回其种别码;
       return i + 1;
      }
     }
     //不匹配则返回-1
     //即:该单词可能是标识符或者错别字
     return -1;
    }
    /*******识别保留字*******/
    /*******字母判别*******/
    bool IsLetter(char letter){
     //C/c++语言中允许下划线也为标识符的一部分可以放在首部或其他地方
     if (letter >= 'a'&&letter <= 'z' || letter >= 'A'&&
     letter <= 'Z' || letter == '_')
      return true;
     else
      return false;
    }
    /*******字母判别*******/
    /*******数字判别*******/
    bool IsDigit(char digit){
     if (digit >= '0'&&digit <= '9')
      return true;
     else
      return false;
    }
    /*******数字判别*******/
    /*******预处理程序,去除错误字符和注释*******/
    void PreProcessing(char r[], int pProject){
     char tempString[10000];
     int count = 0;
     for (int i = 0; i <= pProject; i++){
      if (r[i] == '/'&&r[i + 1] == '/'){
       //若为单行注释“//”,则去除注释后面的东西,直至遇到回车换行
       while (r[i] != '\n'){
        i++;//向后扫描
       }
      }
      if (r[i] == '/'&&r[i + 1] == '*'){
       //若为多行注释“/*......*/”则去除该内容
       i += 2;
       while (r[i] != '*' || r[i + 1] != '/'){
        i++;//继续扫描
        if (r[i] == '$'){
         printf("注释出错,没有找到 */,程序结束!!!\n");
         exit(0);
        }
       }
       i += 2;//跨过“*/”
      }
      if (r[i] != '\n'&&r[i] != '\t'&&r[i] != '\v'&&r[i] != '\r'){
       //若出现无用字符,则过滤;否则加载
       tempString[count++] = r[i];
      }
     }
     tempString[count] = '\0';
     strcpy(r, tempString);//产生净化之后的源程序,将处理后的源程序字符串重新返回
    }
    /*******预处理程序,去除错误字符和注释*******/

    预处理的过程需要实现对输入的字符流进行筛选,把注释、换行符、无效字符、错误字符等进行净化删除得到只有空格的程序字符流。注意:空格是区别五类单词的重要分解符号,因此不可以净化。

    3.扫描器的实现

    扫描器作为词法分析的核心函数,其主要功能是实现净化后的字符流中每个单词的分类,并生成单词的对应二元组写到文件中。主要理论是使用DFA理论进行构建。

    /*******分析模块,词法分析器的核心*******/
    //该模块主要的原理支撑是DFA的状态转换图的设计
    void Scanner(int &syn, char resourceProject[], char token[], int &pProject){
     int i, count = 0;//count用来做token[]的指示器,收集有用字符
     char ch;//作为判断使用
     ch = resourceProject[pProject];
     while (ch == ' '){//过滤空格,防止程序因识别不了空格而结束
      pProject++;
      ch = resourceProject[pProject];
     }
     for (i = 0; i < 20; i++){//每次收集前先清零
      token[i] = '\0';
     }
     if (IsLetter(resourceProject[pProject])){//开头为字母
      token[count++] = resourceProject[pProject];//收集
      pProject++;//下移
      while (IsLetter(resourceProject[pProject]) || IsDigit(resourceProject[pProject])){//后跟字母或数字
       token[count++] = resourceProject[pProject];//收集
       pProject++;//下移
      }//多读了一个字符既是下次将要开始的指针位置
      token[count] = '\0';
      syn = SearchRWord(RWord, token);//查表找到种别码
      if (syn == -1){//若不是保留字则是标识符
       syn = 100;//标识符种别码
      }
      return;
     }
     else if (IsDigit(resourceProject[pProject])){//首字符为数字
      while (IsDigit(resourceProject[pProject])){//后跟数字
       token[count++] = resourceProject[pProject];//收集
       pProject++;
      }//多读了一个字符既是下次将要开始的指针位置
      token[count] = '\0';
      syn = 99;//常数种别码
     }
     else if (ch == '+' || ch == '-' || ch == '*' || ch == '/' || ch == ';' || ch == '(' || ch == ')' || ch == '^'
      || ch == ',' || ch == '\"' || ch == '\'' || ch == '~' || ch == '#' || ch == '%' || ch == '['
      || ch == ']' || ch == '{' || ch == '}' || ch == '\\' || ch == '.' || ch == '\?' || ch == ':'){
      //若为运算符或者界符,查表得到结果
      token[0] = resourceProject[pProject];
      token[1] = '\0';//形成单字符串
      for (i = 0; i < 36; i++)
      {//查运算符界符表
       if (strcmp(token, OandD[i]) == 0){
        syn = 33 + i;//获得种别码,使用了一点技巧,使之呈线性映射
        break;//查到即推出
       }
      }
      pProject++;//指针下移,为下一扫描做准备
      return;
     }
     else  if (resourceProject[pProject] == '<'){//<,<=,<<
      pProject++;//后移,超前搜索
      if (resourceProject[pProject] == '='){
       syn = 38;
      }
      else if (resourceProject[pProject] == '<'){//左移
       pProject--;
       syn = 58;
      }
      else{
       pProject--;
       syn = 37;
      }
      pProject++;//指针下移
      return;
     }
     else  if (resourceProject[pProject] == '>'){//>,>=,>>
      pProject++;
      if (resourceProject[pProject] == '=')
       syn = 40;
      else if (resourceProject[pProject] == '>')
       syn = 59;
      else{
       pProject--;
       syn = 39;
      }
      pProject++;
      return;
     }
     else  if (resourceProject[pProject] == '='){//=.==
      pProject++;
      if (resourceProject[pProject] == '=')
       syn = 42;
      else{
       pProject--;
       syn = 41;
      }
      pProject++;
      return;
     }
     else  if (resourceProject[pProject] == '!'){//!,!=
      pProject++;
      if (resourceProject[pProject] == '=')
       syn = 43;
      else{
       syn = 68;
       pProject--;
      }
      pProject++;
      return;
     }
     else  if (resourceProject[pProject] == '&'){//&,&&
      pProject++;
      if (resourceProject[pProject] == '&')
       syn = 53;
      else{
       pProject--;
       syn = 52;
      }
      pProject++;
      return;
     }
     else  if (resourceProject[pProject] == '|'){//|,||
     pProject++;
     if (resourceProject[pProject] == '|')
      syn = 55;
     else{
      pProject--;
      syn = 54;
     }
     pProject++;
     return;
     }
     else  if (resourceProject[pProject] == '$')//结束符
      syn = 0;//种别码为0
     else{//不能被以上词法分析识别,则出错。
      printf("error:there is no exist %c \n", ch);
      exit(0);
     }
    }
    /*******分析模块,词法分析器的核心*******/

    其主要处理流程为:首先从头开始扫描,这个时候扫描程序首先要询问当前的字符是不是空格,若是空格,则继续扫描下一个字符,直至不是空格,然后询问这个字符是不是字母,若是则进行标识符和保留字的识别;若这个字符为数字,则进行数字的判断。否则,依次对这个字符可能的情况进行判断,若是将所有可能都走了一遍还是没有知道它是谁,则认定为错误符号,输出该错误符号,然后结束。每次成功识别了一个单词后,单词都会存在token[ ]中。然后确定这个单词的种别码,最后进行下一个单词的识别。这就是扫描程序进行的工作,可以说这个程序彻底实现了确定有限自动机的某些功能,比如说识别标识符,识别数字等。为了简单起见,这里的数字只是整数。

    4.主函数的操作

    主函数中主要是对必要变量的初始化操作以及对文件的读写操作。设置resourceProject变量存储从txt文本读入的字符流,为了方便起见,我只设置读入的字符流最大值为10000个char类型的字符。设置token变量为了存储每次识别的单词以便于找到其相对应种别码。syn是对当前单词种别码的保存,我设置’txtsyn0’为读入的txt文本的扫描终点标识符,其syn值为0,当读入’’意味着扫描的字符流到达终点,即当syn==0时,退出扫描程序,扫描结束,词法分析结束。pProject变量是源程序指针,其始终指向当前识别的字符位置。主函数操作流程为:先打开预设定的txt文本读入其中全部字符到resourceProject变量中,然后调用预处理程序得到净化后的字符流,覆盖存储到resourceProject变量中。然后调用扫描器识别各个单词,此时初始时syn=-1,pProject=0。处理完后把处理结果存储到一个txt文件中并输出即可。

    int main(){
     //打开一个文件,读取其中的源程序
     char resourceProject[10000];
     char token[20] = { 0 };
     int syn = -1, i;//初始化
     int pProject = 0;//源程序指针
     FILE *fp, *fp1;
     if ((fp = fopen("F:\\大三下课程\\编译原理(必修)\\词法分析器\\zyr_rc.txt", "r")) == NULL){//打开源程序
      cout << "can't open this file";
      exit(0);
     }
     resourceProject[pProject] = fgetc(fp);
     while (resourceProject[pProject] != '$'){//将源程序读入resourceProject[]数组
      pProject++;
      resourceProject[pProject] = fgetc(fp);
     }
     resourceProject[++pProject] = '\0';
     fclose(fp);
     cout << endl << "源程序为:" << endl;
     cout << resourceProject << endl;
     //对源程序进行过滤
     PreProcessing(resourceProject, pProject);
     cout << endl << "过滤之后的程序:" << endl;
     cout << resourceProject << endl;
     pProject = 0;//从头开始读
     if ((fp1 = fopen("F:\\大三下课程\\编译原理(必修)\\词法分析器\\zyr_compile.txt", "w+")) == NULL){//打开源程序
      cout << "can't open this file";
      exit(0);
     }//F:\\大三下课程\\编译原理(必修)\\词法分析器\\zyr_compile.txt
     while (syn != 0){
      //启动扫描
      Scanner(syn, resourceProject, token, pProject);
      if (syn == 100){//标识符
       for (i = 0; i < 1000; i++){//插入标识符表中
        if (strcmp(IDtable[i], token) == 0)//已在表中
         break;  
        if (strcmp(IDtable[i], "") == 0){//查找空间
         strcpy(IDtable[i], token);
         break;
        }
       }//F:\大三下课程\编译原理(必修)\词法分析器\zyr_rc.txt
       printf("(标识符  ,%s)\n", token);
       fprintf(fp1, "(标识符   ,%s)\n", token);
      }
      else if (syn >= 1 && syn <= 32){//保留字
       printf("(%s   ,  --)\n", RWord[syn - 1]);
       fprintf(fp1, "(%s   ,  --)\n", RWord[syn - 1]);
      }
      else if (syn == 99){//const 常数
       printf("(常数   ,   %s)\n", token);
       fprintf(fp1, "(常数   ,   %s)\n", token);
      }
      else if (syn >= 33 && syn <= 68){
       printf("(%s   ,   --)\n", OandD[syn - 33]);
       fprintf(fp1, "(%s   ,   --)\n", OandD[syn - 33]);
      }
     }
     for (i = 0; i < 100; i++){//插入标识符表中
      if (strcmp(IDtable[i],"")==0)
       break;
      printf("第%d个标识符:  %s\n", i + 1, IDtable[i]);
      fprintf(fp1, "第%d个标识符:  %s\n", i + 1, IDtable[i]);
     }
     fclose(fp1);
     return 0;
    }

    四、测试数据与运行结果

    测试内容:
    文件路径及其文件名:F:\\大三下课程\\编译原理(必修)\\词法分析器\\zyr_rc.txt
    文件内容:

    int main(){
     //打开一个文件,读取其中的源程序
     char resourceProject[10000];
     char token[20] = { 0 };
     int syn = -1, i;//初始化
     int pProject = 0;//源程序指针
     FILE *fp, *fp1;
     if ((fp = fopen("F:\\大三下课程\\编译原理(必修)\\词法分析器\\zyr_rc.txt", "r")) == NULL){//打开源程序
      cout << "can't open this file";
      exit(0);
     }
     resourceProject[pProject] = fgetc(fp);
     while (resourceProject[pProject] != '$'){//将源程序读入resourceProject[]数组
      pProject++;
      resourceProject[pProject] = fgetc(fp);
     }
     resourceProject[++pProject] = '\0';
     fclose(fp);
     cout << endl << "源程序为:" << endl;
     cout << resourceProject << endl;
     //对源程序进行过滤
     PreProcessing(resourceProject, pProject);
     cout << endl << "过滤之后的程序:" << endl;
     cout << resourceProject << endl;
     pProject = 0;//从头开始读
     if ((fp1 = fopen("F:\\大三下课程\\编译原理(必修)\\词法分析器\\zyr_compile.txt", "w+")) == NULL){//打开源程序
      cout << "can't open this file";
      exit(0);
     }
     $
     

    输出结果存储文件路径及其文件名:F:\\大三下课程\\编译原理(必修)\\词法分析器\\zyr_compile.txt
    运行结果为:
    (int , --)
    (标识符 ,main)
    (( , --)
    () , --)
    ({ , --)
    (char , --)
    (标识符 ,resourceProject)
    ([ , --)
    (常数 , 10000)
    (] , --)
    (; , --)
    (char , --)
    (标识符 ,token)
    ([ , --)
    (常数 , 20)
    (] , --)
    (= , --)
    ({ , --)
    (常数 , 0)
    (} , --)
    (; , --)
    (int , --)
    (标识符 ,syn)
    (= , --)
    (- , --)
    (常数 , 1)
    (, , --)
    (标识符 ,i)
    (; , --)
    (int , --)
    (标识符 ,pProject)
    (= , --)
    (常数 , 0)
    (; , --)
    (标识符 ,FILE)
    (* , --)
    (标识符 ,fp)
    (, , --)
    (* , --)
    (标识符 ,fp1)
    (; , --)
    (if , --)
    (( , --)
    (( , --)
    (标识符 ,fp)
    (= , --)
    (标识符 ,fopen)
    (( , --)
    (" , --)
    (标识符 ,D)
    (: , --)
    (\ , --)
    (\ , --)
    (标识符 ,zyr_rc)
    (. , --)
    (标识符 ,txt)
    (" , --)
    (, , --)
    (" , --)
    (标识符 ,r)
    (" , --)
    () , --)
    () , --)
    (== , --)
    (标识符 ,NULL)
    () , --)
    ({ , --)
    (标识符 ,cout)
    (<< , --)
    (< , --)
    (" , --)
    (标识符 ,can)
    (’ , --)
    (标识符 ,t)
    (标识符 ,open)
    (标识符 ,this)
    (标识符 ,file)
    (" , --)
    (; , --)
    (标识符 ,exit)
    (( , --)
    (常数 , 0)
    () , --)
    (; , --)
    (} , --)
    (标识符 ,resourceProject)
    ([ , --)
    (标识符 ,pProject)
    (] , --)
    (= , --)
    (标识符 ,fgetc)
    (( , --)
    (标识符 ,fp)
    () , --)
    (; , --)
    (while , --)
    (( , --)
    (标识符 ,resourceProject)
    ([ , --)
    (标识符 ,pProject)
    (] , --)
    (!= , --)
    (’ , --)
    第1个标识符: main
    第2个标识符: resourceProject
    第3个标识符: token
    第4个标识符: syn
    第5个标识符: i
    第6个标识符: pProject
    第7个标识符: FILE
    第8个标识符: fp
    第9个标识符: fp1
    第10个标识符: fopen
    第11个标识符: D
    第12个标识符: zyr_rc
    第13个标识符: txt
    第14个标识符: r
    第15个标识符: NULL
    第16个标识符: cout
    第17个标识符: can
    第18个标识符: t
    第19个标识符: open
    第20个标识符: this
    第21个标识符: file
    第22个标识符: exit
    第23个标识符: fgetc

    五、总结

    这次的实验,算法部分并不难,只要对DFA有一定熟练的掌握,扫描器模块很好写。比较麻烦的是五种类型的字符个数越多程序就越长。但为了能识别大部分程序,我依然选用了比较大的子集,下了一定的功夫,最终这个词法分析器的处理能力还是可以处理大多数c/c++程序的。同时加深了我对字符的认识。程序的可读性还算不错。我的程序没有实现的是对所有复合运算的分离,但原理是相同的,比如“+=“,只需在”+“的逻辑之后向前扫描就行了,因此就没有再加上了。感受最深的是学习编译原理必须要做实验,写程序,这样才会提高自己的动手能力,加深自己对难点的理解,对于以后的求first{},follow{},fisrtVT{},lastVT{}更是应该如此。基于此次实验,让我对编译程序有了基础性的认识,对后面的语法分析的实验也有了一定想法。为之后更好的学习和实践做了充分准备。

    展开全文
  • 编译原理实现

    2014-06-27 00:09:35
    8.9.1 代码优化的主要来源 358 8.9.2 优化分类 360 8.9.3 优化的数据结构和实现技术 362 8.10 TINY代码生成的简单优化 366 8.10.1 将临时变量放入寄存器 366 8.10.2 在寄存器中保存变量 367 8.10.3 优化测试表达式...
  • 编译原理-9-代码生成

    2020-02-29 21:57:23
    1 代码生成的主要任务 2 一个简单的目标机模型 3 指令选择 4 寄存器的选择 5 寄存器选择函数getReg的设计 6 窥孔优化 1 代码生成的主要任务 (1)指令选择 选择适当的目标机指令来实现中间表示(IR)语句...

    目录

    1 代码生成器的主要任务

    2 一个简单的目标机模型

    3 指令选择

    4 寄存器的选择

    5 寄存器选择函数getReg的设计

    6 窥孔优化


    1 代码生成器的主要任务

    (1)指令选择

             选择适当的目标机指令来实现中间表示(IR)语句

    (2)寄存器分配和指派
             把哪个值放在哪个寄存器中
    (3)指令排序
             按照什么顺序来安排指令的执行

    2 一个简单的目标机模型

    三地址机器模型
        加载、保存、运算、跳转等操作
        内存按字节寻址
        n个通用寄存器R0, R1, …, Rn-1
        假设所有的运算分量都是整数
        ​​​​​​​指令之间可能有一个标号

    3 指令选择

    指令选择:为中间表示语句选择合适的目标指令序列

    4 寄存器的选择

    (1)三地址语句的目标代码生成
    (2)寄存器描述符和地址描述符
    (3)基本块的收尾处理
    对于一个在基本块的出口处可能活跃的变量x , 如果它的地址描述符表明它的值没有存放在x的内存位置上,则生成指令“ST x, R(R是在基本块结尾处存放 x的寄存器 )
    (4)管理寄存器和地址描述符

    5 寄存器选择函数getReg的设计

    6 窥孔优化

    窥孔(peephole)是程序上的一个小的滑动窗口
    窥孔优化是指在优化的时候,检查目标指令的一个滑动窗口(即窥孔) ,并且只要有可能就在窥孔内用更快或更短的指令来替换窗口中的指令序列
    也可以在中间代码生成之后直接应用窥孔优化来提高中间表示形式的质量
    展开全文
  • 1. 巩固对词法分析的基本功能和原理的认识。 2. 能够应用自动机的知识进行词法分析。 3. 理解并处理词法分析中的异常和错误。 实验要求 1.掌握词法分析的基本功能,并将其实现。 2.词法分析程序应具有较好的可...

    实验目的
    1. 巩固对词法分析的基本功能和原理的认识。
    2. 能够应用自动机的知识进行词法分析。
    3. 理解并处理词法分析中的异常和错误。
    实验要求
    1.掌握词法分析的基本功能,并将其实现。
    2.词法分析程序应具有较好的可扩展性,应清晰明确。
    3.除对相关问题的全面考虑外,还需对局部作一些优化考虑(如符号表)。
    实验内容
    对一段类高级语言代码进行词法分析,并输出词法分析的结果。

    废话不多说 看看代码吧
    部分识别用的是正则表达式,如有什么疑问或问题,欢迎讨论:

    'use static';
    /*jshint esversion: 6 */
    var fs = require('fs');
    var write = fs.writeFileSync;
    const FILE_PATH = "output.txt";
    var data = fs.readFileSync('data.txt').toString().trim().split('\r\n').join('');
    var keyWord = [ "begin","if","then","while","do","end","int","main",
                       "else","float","double","return"]; //关键字数组
    var symbol = ['(',')','=', '>=','<=','<','>',':=','+','-','*','/',',',';'];
    var isDigit = /[0-9]/;  //判断数字
    var isLetter = /[a-zA-Z]/; //判断字母
    var notation = /^\/\*.*\*\//g;  //识别注释 
    var notation1 = /\/\*/;  //注释开头
    var notation2 = /\*\//; //注释结尾
    var result = '';
    var num;
    if(notation.test(data)) {
        data = data.replace(notation, '');
    }
    if(notation1.test(data) || notation2.test(data)) {
        write(FILE_PATH, "error");
        return;
    }
    var str = '';
    for(let i=0;i<data.length;i++) {
        if(data[i] === ' ') {
            continue;
        }
        if(isLetter.test(data[i])) {
            str += data[i++];
            while(isDigit.test(data[i]) || isLetter.test(data[i])) {
                str += data[i++];
            }
            num = keyWord.indexOf(str);
            if(num !== -1) {
                result += num.toString() + '::' + str + ']';
            } else {
                result += '[' + '25::' + str + ']';  //变量的种别码为25
            }
            i--;
        }else if(isDigit.test(data[i])) {
            str += data[i++];
            while(isDigit.test(data[i])) {
                str += data[i++];
            }
            result += '[' + '26::' + str + ']';//常数的种别码为26
            i--;
        } else {
            try {
                num = symbol.indexOf(data[i]+data[i+1]);
                if(num !== -1) {
                    result += '[' + num.toString() + '::' + data[i]+data[i+1] + ']';
                    i += 2;
                } else {
                    num = symbol.indexOf(data[i]);
                    if(num !== -1) {
                        result += '[' + num.toString() + '::' + data[i] + ']';
                        if(data[i] === ';') {
                            result += '\n';
                        }
                    } else {
                        result += '[-1::error]';
                    }
                }
            } catch(e) {
                num = symbol.indexOf(data[i]);
                if(num !== -1) {
                    result += '[' + num.toString() + '::' + data[i] + ']';
                    if(data[i] === ';') {
                        result += '\n';
                    }
                } else {
                    result += '[-1::error]';
                }
            }
        }
        str = '';
    }
    write(FILE_PATH, result);
    
    
    展开全文
  • A 便于目标代码优化 B 便于存储空间的组织 C 便于目标代码的移植 D 便于编译程序的移植 逆波兰表示法表示表达式时无须使用括号。正确 四元式之间的联系是通过(B)实现的。 A 指示 B 临时变量 C 符号...
  • javac编译原理简介

    2021-03-26 08:48:42
    javac这种将源代码转化为字节码的过程在编译原理上属于前端编译,不涉及相关代码的生成和优化。 JDK中的javac本身是用Java语言编写的,在某种意义上实现javac语言自举。javac没有使用类似的YACC和Lex这样的生成...
  • 编译原理章节整理

    2020-07-15 16:15:45
    bjfu编译原理复习资料整理,仅供参考 编译原理章节整理 第一章 判断: 编译器生成的目标程序都是可执行...(错误,中间代码生成和代码优化并不是必不可少的) 6. 许多编译程序在识别出语法单位后并不真正构造语.
  • 通过获取对象内部的监视实现,使用了 monitorenter 和 monitorexit 指令,这两条指令在编译字节码时分别插入同步代码块的开始和结束位置(查看字节码可以使用 JDK 的 javap 命令,也可以使用 idea 的插件 ...
  • 编译原理实验源码.zip

    2020-12-07 21:15:23
    华中科技大学编译原理实验源码一到四,运行makefile文件即可,不过电脑应该先安装c编译器。 实验一:词法语法分析的设计与实现; 实验二:符号表管和语义检查; 实验三:中间代码生成和优化; 实验四:目标代码...
  • 编译原理全套

    2011-12-03 11:17:21
    *第9章 代码优化 9.1 优化的主要种类 9.1.1 代码改进变换的标准 9.1.2 公共子表达式删除 9.1.3 复写传播 9.1.4 死代码删除 9.1.5 代码外提 9.1.6 强度削弱和归纳变量删除 9.1.7 优化编译器的组织 9.2 流图中...
  • 8.9.1 代码优化的主要来源 358 8.9.2 优化分类 360 8.9.3 优化的数据结构和实现技术 362 8.10 TINY代码生成的简单优化 366 8.10.1 将临时变量放入寄存器 366 8.10.2 在寄存器中保存变量 367 8.10.3 优化测试表达式...
  • 一、背景对于Java来说我们知道,Java代码首先会编译成Java字节码,字节码被类加载加载到JVM里,JVM执行字节码,最终需要转化为汇编指令在CPU上进行执行。Java中所使用的并发机制依赖于JVM的实现和CPU的指令。下边...
  • c编译器ucc 编译原理

    2011-03-30 20:33:54
    “上了一学期的编译原理,但是对于如何去实现一个真正的编译器仍然觉得困惑; 学习了一些好的优化算法或者自己有些好的想法,想在gcc上实践一下,但发现gcc 实在太大了,有点无从下手。 如果你曾经有过上面这些感受,...
  • 编译原理电子书

    2007-08-07 16:42:16
    简单的目标机器 346 8.7.1 Tiny Machine的基本结构 347 8.7.2 TM...代码优化的主要来源 358 8.9.2 优化分类 360 8.9.3 优化的数据结构和实现技术 362 8.10 TINY代码生成的简单优化 366 8.10.1 将...
  • 编译原理中文版

    2014-12-01 09:14:48
    8.9.1 代码优化的主要来源 358 8.9.2 优化分类 360 8.9.3 优化的数据结构和实现技术 362 8.10 TINY代码生成的简单优化 366 8.10.1 将临时变量放入寄存器 366 8.10.2 在寄存器中保存变量 367 8.10.3 优化测试表达式...
  • 内容包括语言和文法、词法分析、语法分析、语法制导翻译、中间代码生成、存储管理、代码优化和目标代码生成。 编译原理是计算机专业设置的一门重要的专业课程。虽然只有少数人从事编译方面的工作,但是这门课在理论...
  • 有问题联系我 整合、完善已完成的编译程序各阶段相关内容,并能可视化演示。 (2)深入研究编译相关算法,从下列几个算法中至少选择其中一个实现(如果语法分析程序中...可以选择实现解释,也可以选择生成汇编代码
  •   通常的ORM实现基于配置或注释,由反射或Emit生成相应的Sql语句,然后将Sql发送给数据库解析Sql字符串生成AST再交给优化器处理后执行,返回的数据再经由反射或Emit转换为相应的实体实例。作者认为上述方式主要...
  • 编译原理--编译器

    2020-04-29 14:27:03
    实现这个功能要经历什么步骤呢? 理解源代码:词法分析,语法分析,语义分析 转化为等价的目标代码:中间代码生成,目标代码生成 优化优化方法 编译器的结构: 每个阶段源程序从一种表示转换成另一种表示。 ...
  • 编译原理及实践

    2012-04-25 23:12:05
    8.9.1 代码优化的主要来源 358 8.9.2 优化分类 360 8.9.3 优化的数据结构和实现技术 362 8.10 TINY代码生成的简单优化 366 8.10.1 将临时变量放入寄存器 366 8.10.2 在寄存器中保存变量 367 8.10.3 优化测试表达式...
  • 编译原理课程设计

    2008-08-05 16:25:27
    1 2.2设计内容及要求: 1 2.2.1 设计符号表 1 2.2.2 设计词法分析器 1 2.2.3 语法分析与中间代码产生器 2 2.2.4 优化器(选做) 2 2.2.5目标代码生成器(选做) 2 2.2.6 测试范例:...
  • 什么是程序的执行? 输入程序输出 ...中间代码更容易被翻译成目标程序、优化空间更大 中间语言的存在更利于编译器的实现 让虚拟机处理复杂的执行环境(跨平台) 代表: java 即时编译器(Just-in-time compil
  • 编译原理 合工大17级 课件 李宏芒老师的课件 包含以下章节 第一章 引论  1.1 什么叫编译程序  1.2 编译过程概述  1.3 编译程序的结构  1.4 编译程序与程序设计环境  1.5 编译程序的生成 第二章 高级语言及其...
  • vue模板编译 模板编译的概念 ...遍历AST标记静态节点 优化器完成 使用AST生成渲染函数 代码生成器完成 备注:AST即抽象语法树,是用于描述一个节点信息的JavaScript对象 整体pipeline:模板->解析器->
  • 编译原理--龙书

    2013-10-11 17:09:34
    8.9.1 代码优化的主要来源 358 8.9.2 优化分类 360 8.9.3 优化的数据结构和实现技术 362 8.10 TINY代码生成的简单优化 366 8.10.1 将临时变量放入寄存器 366 8.10.2 在寄存器中保存变量 367 8.10.3 优化测试...
  • 19.1 什么是代码优化 194 19.2 基本块及流图 199 19.3 单元测试 202 二十、代码优化_2 203 20.1 基本块的DAG表示及其作用 203 二十一、重要知识点 213 1. 考试内容及分数分布 213 2. 名词解释 214 3. 简答题 215 4. ...

空空如也

空空如也

1 2 3 4 5 ... 16
收藏数 304
精华内容 121
关键字:

编译原理实现实现代码优化器