精华内容
下载资源
问答
  • 中间代码生成器
    千次阅读 多人点赞
    2020-02-17 11:29:05

    1.词法分析

    词法分析的过程中,源代码程序被输入到了一个叫做扫描器的东西中,扫描器的任务就是进行词法分析。他应用了一种叫做有限状态机的算法把源代码分割成一个一个的记号,举例比如array[index] = (index + 4) * (2 + 3)这行代码,经过扫描就会变成如下的一个个记号:

    记号类型
    array标识符
    [左方括号
    index标识符
    ]右方括号
    =赋值
    (左圆括号
    index标识符
    +加号
    4数字
    )左圆括号
    *乘号
    (左圆括号
    2数字
    +加号
    3数字
    )右圆括号

    以上的这些记号一般有以下几类:关键字标识符字面量(数字、字符串等)和特殊符号

    单词类型种别种别码
    关键字if、else、for……一词一码
    标识符变量名、数组名……多词一码
    常量整型、浮点型、字符……一型一码
    运算符算术(+ - * / %)、关系(> < =)、逻辑(& | ~)一词一码
    界限符; ( ) [ ] { }一词一码

    在识别这些标志的同时,扫描器也同时把标识符存放到了符号表,将数字、字符串常量存放到文字表,以备后续步骤使用。对于C语言的预处理,他的宏替换和文件包含等工作不交给编译器范围而是交给独立的预处理器处理。

    2.语法分析

    语法分析则由分析器去扫描扫描器产生的那些记号去进行语法分析,产生语法树,整个过程采用了上下文无关语法的分析手段,由语法分析树生成的树是以表达式为节点的树,如下所示:
    在这里插入图片描述
    这个数的左分支是array[index]右分支是(index + 4) * (2 + 3)左分支和右分支又可以再拆开,形成语法树
    通过语法树我们可以看到很多运算符号的优先级和含义也被确定了下来。对于有多重含义的符号,比如*可以做乘法,也可以作为指针,语法分析阶段,要去确定他们的含义来进行区分,出现了不合法的表示方式,则会抛出语法错误。

    3.语义分析

    语义分析由语义分析器来完成,语法分析器仅完成了语法的对错,他并不去关心代码实现的含义,在C语言中两个指针相乘是没有意义的,但是在语法层面确是合法的。编译器能分析的语义是静态语义,即编译期可以确定的语义,相反,动态语义则是在运行的时候才确定的语义。

    静态语义包括声明类型和类型的匹配、转换。比如当一个浮点数赋值给整型的时候,隐藏了一个过程,就是浮点型到整型转换的过程。但是将浮点数赋值给指针的时候,在语法层面可以,但是语义阶段,会发现,类型不匹配则会报错。
    经过语义分析后,整个语法数表达式都被标志了类型,如下:
    在这里插入图片描述
    该表达式中基本所有的类型都是整型,并不需要做类型转换,有些需要做转换的会在语法树上插入转换节点

    4.z中间语言生成

    目前的编译器都会有很多优化,在源代码中就会有一些优化过程,比如以上的(2+6)就会在编译的时候进行优化,优化后就直接变成了一个数字5
    在这里插入图片描述
    其实直接在语法树上边做优化比较困难,所以源代码优化器往往把整个语法树转换成中间代码,跟目标机器和运行环境无关,他不包含数据的尺寸、变量地址和寄存器的名字。常见的中间代码有三地址码P-代码等。比如x = y op z,该三地址码表示将变量y和z进行op操作后赋值给x,比如x = y + z;一下是常用的三地址表示方式

    指令类型指令形式
    赋值操作x = y op z 、 x = op y
    复制指令x = y
    条件跳转if x op y goto z
    非条件跳转goto z
    参数传递param z
    过程调用call p, n
    过程返回return x
    数组引用x = y[ i ]
    数组赋值y[ i ] = x
    地址以及指针操作x = &y 、x = *y 、*x = y

    我们把上述的例子的语法树翻译成三地址码如下

    t1 = 2 + 3
    t2 = index + 4
    t3 = t1 * t2
    array[index] = t3
    

    在三地址码基础上进行优化,会把2+3的结果计算出来,得到t1 = 5然后把t1换成5。这样三地址码就变成了如下

    t2 = index + 4
    t2 = t2 * 8
    array[index] = t2
    

    中间代码把编译器分成了前端和后端(此前后端非彼前后端),前端负责生成与机器无挂的中间代码,后端则是将中间代码变成目标代码。这样对于一些跨平台的编译器而言,可以针对不同平台使用同一个前端,然后对应不同机器开发不同后端。

    参考资料《编译原理》、《程序员的自我修养(链接、装载与库)》

    更多相关内容
  • 实验五_用语法制导方式生成中间代码生成器参照.pdf
  • ICM-CD:中间代码生成器

    2021-05-02 21:48:32
    光盘 中间代码生成器此系统将高级程序转换为机器可理解的三个地址代码。 该项目主要侧重于学习编译器中间代码生成器阶段。 GUI是使用Java swing开发的。
  • 包括词法分析器、lr(k)语法分析器、递归下降语法分析器、中间代码生成器以及对应的实验报告。中间代码生成器是在词法分析器和语法分析器的基础上做的。写的很乱仅供参考。
  • 中间代码生成器

    2013-06-13 22:36:45
    非常棒的资源,其中包括了逆波兰表达式和三元组的表示,做实验非常实用
  • 中间代码生成实验报告.doc
  • 编译原理课程词法分析,语法分析(递归实现),中间代码生成
  • 编译原理中间代码生成器实现C++编译原理中间代码生成器实现C++
  • 中间代码生成器的设计c++

    热门讨论 2009-01-02 13:03:04
    中间代码生成器的设计,用c++设计。 实验目的 熟悉算术表达式的语法分析与中间代码生成原理。 实验内容 (1) 设计语法制导翻译生成表达式的四元式的算法; (2) 编写代码并上机调试运行通过。 输入——算术表达式 ...
  • #include #include #include #include using namespace std; #define dd(x) cout #define de(x) cout //词法分析双向链表(存已识别的词单元(endSign)) typedef struct WordAnalysisList ... struct WordAnalysisList *...
  • (1) 设计语法制导翻译生成表达式的四元式的算法; (2) 编写代码并上机调试运行通过。 ·输入——算术表达式 ·输出——语法分析结果 相应的四元式序列 (3) 本实验已给出递归子程序法的四元式属性翻译文法的设计,...
  • 编译原理实验七:中间代码生成器

    万次阅读 2019-04-13 12:08:02
    实现一门语言的中间代码生成器(4小时) 实验目的 通过本次实验,加深对中间代码生成的理解,学会编制中间代码生成器。 实验任务 用C、JAVA或其他语言编写一门语言的中间代码生成器,所选实现语言应与之前语言...

    实现一门语言的中间代码生成器(4小时)

     

    实验目的

    通过本次实验,加深对中间代码生成的理解,学会编制中间代码生成器。

    实验任务

    用C、JAVA或其他语言编写一门语言的中间代码生成器,所选实现语言应与之前语言保持一致。

    实验内容

    1. 实现中间代码生成器,可以将任一源语言(源语言尽量与前期实验中的源语言保持一致)转化成三地址码(或其他中间表示形式)。
    2. 准备2~3个测试用例,测试你的程序,并解释生成的中间代码。

     

    源代码下载和说明

    链接:https://pan.baidu.com/s/1Ogf4447oPMrxHVJE8_hwmg

    密码:fc7f

    运行方法:同实验一TINY编译器(这其实就是实验一的工程)

     

    说明:实验七中间代码生成器直接使用了TINY语言。在2018-2019年秋季学期,湖南大学编译原理课首次将本实验变为必做(之前是选做,但由于难度太大,基本没有学长学姐写),故本实验采用已有的代码。

     

    实验知识点讲解和函数源代码分析

     

    1、中间代码生成的任务

     

    中间代码生成属于编译器前端结构的最后一部分,首先,编译器前端读入代码,对代码进行词法分析,构建出符号序列,再将符号序列传入语法分析,构造出语法树;接下来的语义分析则是一个静态检查的过程,它判断上下文的各个结点是否符合语法规则,并报错,生成符号表,而接下来的中间代码生成则也是对于语法树进行操作,传入一棵语法树,从根结点,根据该节点的词法属性,分析词法结点之间的逻辑,翻译成合适的中间表示。

    在TINY语言中,需要将NO_CODE标记位设置为真,这样就能够输出中间代码的生成结果。

    2、实现TINY语言的中间代码生成器

     

    本次实验要求实现一个中间代码生成器,则我们采用的方法是增量编程,在之前所构造好的TINY前期组件基础之上,构建中间代码的生成部分。

     

    2.1 TINY语言的中间代码生成结果——TM CODE

     

    TINY语言可以被翻译为一个适用于TM虚拟机环境的代码表示:TM CODE。TM CODE其实是类似于汇编指令的程序语言,但是何其不同的地方在于,TM CODE可以在为TINY语言所构建的虚拟机中运行,它模拟了汇编代码中的一些特性,比如说寄存器操作,它在CODE.H头文件中定义了几个寄存器的值(地址),使得这样的一种基于寄存器操作的类汇编语言能够执行。

    T机的模拟程序直接从一个文件中读取汇编代码并执行它,因此应避免将由汇编语言翻译为机器代码的过程复杂化。但是,这个模拟程序并非是一个真正的汇编程序,它没有符号地址或标号。因此,TINY编译器必须仍然计算跳转的绝对地址。此外为了避免与外部的输入/输出例程连接的复杂性,TM机有内部整型的I/O设备;在模拟时,它们都对标准设备读写。

    下图展示了TM CODE的详细定义:

    我们注意到装入操作中有3个地址模式并且是由不同的指令给出的:LDC是“装入常量”,LD是“由存储器装入”,而LDA是“装入地址”。另外,该地址通常必须给成“寄存器+偏差”值。例如“10(1)”(上面代码的第2条指令),它代表在将偏差10加到寄存器1的内容中计算该地址。(因为在前面的指令中,0已被装入到寄存器1中,这实际是指绝对位置10)。我们还看到算术指令MUL和ADD可以是“三元”指令且只有寄存器操作数,其中可以单独确定结果的目标寄存器。

     

    2.2 MAIN函数调用入口及文件预处理

     

    如图代码展示了MAIN函数的文件预处理和中间代码生成的调用入口:

    第一步是文件的预处理。

    strcspn函数的作用是,在pgm字符串中查找到第一个“.”,并返回它之前的所有字符作为子串,这样做的目的在于,我们传入给编译器的文件是一个文件,我们中间代码的输出结果也需要保存在一个文件中,输出文件在这里这样做,是为了保持和输入文件同名。

    strncpy函数的作用是拷贝字符串,这里用于将strcspn提取的文件名存入字符串供输出文件使用。

    接下来程序使用提取的文件名创建了一个.TM文件,作为中间代码的输出,并打开它,赋予其“w”写的权限,并执行中间代码生成的后续操作。

    【这里大家注意一下,运行完程序之后,文件夹里面会出现一个.TM结尾的文件,用记事本打开,就是其生成的TM CODE,也就是运行结果】

    第二步就是中间代码生成,它调用了codeGen函数,传入了语法树根结点以及需要写入的文件,进行后续操作,下面代码所展示的是该函数:

    这个代码主要是调用了emitRM,emitComment函数插入了TM虚拟机的初始化指令,其中这些函数传入的都是mp、ac等定义好的寄存器,这个在code.H中有详细定义:

    TM虚拟机不是一开始就能运行中间代码的,需要一些初始化的条件,在插入完这些指令之后,就会到达一个正式的cGen的代码生成过程,待到cGen函数执行完毕,继续需要插入一条停机指令HALT代表代码执行完毕。

     

    2.3 代码生成的具体过程

     

    下图展示的是cGen函数的代码:

    可以看到,传入的语法树在一边遍历的同时,检查结点的类型,TINY语言中分为两种语句结点,一种是带有关键字的保留语句,一种是表达式,比如赋值或者是算式(总之,不带有保留关键字),这两种情况分开考虑。

     

    1、getStmt——分析含有保留关键字语句的函数

    该函数的作用主要是处理TINY语言中所包含的五个关键字——if,repeat,assign,read,write。

    这里以if作为一个例子来分析说明这个函数需要做的工作:if结点包括三个子结点,if本身的判断表达式、then、以及else(通常,else可以被省略)。我们对于每个if的子结点递归分析(因为if的子结点可能也会是一个表达式,比如if的条件判断,这样的话就需要对它进行递归分析)。

    用savedLoc变量记录递归的返回位置,待分析完这一条路径之后,就可以找到函数在哪里被调用了,在调用的过程中,由于各个节点都需要递归地访问,因此这里在处理下一个节点的时候,使用了emitSkip这个函数,用于跳过并保存当前点的位置,以便于函数最后的返回工作。【这个地方,也叫作回填】

    其他的处理也是类似的,比如在repeat语句里面,repeat包含的是两个结点,一个是repeat它本身,第二个是与之对应的until条件,同if一样,分为两块进行分别的一个递归处理。

    其他三个关键字分别是assign,read,write。这三个的处理比较简单,因为他们的语句结构决定了他们只有一个子结点,因此,直接处理子结点就可以了。

    如何处理子结点呢?

    如图所示,我们获取了结点的类型,也能够获取结点的逻辑关系,此时,只要调用刚刚提到的函数emit,就可以将这条指令写到输出文件中,使得最后的TM虚拟机能够执行完成。

     

    2、getExp——处理表达式

     

    处理表达式结点的逻辑比较简单,如果表达式的结点类型是ID或者数字,那么直接使用LD命令加载它即可。

    如果结点是一个运算符,那么据我们所知,运算符是由子结点构成的,它的子结点就是运算的两个数字,或者是ID字符。我们需要使用LD命令将子结点里面的具体数字或字符读取出来,再根据运算符的类型构造相应的TM code命令。

    下图展示的是小于和等于的命令TM code:

    运行结果

     

    输入数据:(文件名:SAMPLE.TNY)

    { Sample program
      in TINY language -
      computes factorial
    }
    read x; { input an integer }
    if 0 < x then { don't compute if x <= 0 }
      fact := 1;
      repeat
        fact := fact * x;
        x := x - 1
      until x = 0;
      write fact  { output factorial of x }
    end

    输出:(文件名:SAMPLE.TM)

    * Standard prelude:
      0:     LD  6,0(0) 	load maxaddress from location 0
      1:     ST  0,0(0) 	clear location 0
    * End of standard prelude.
      2:     IN  0,0,0 	read integer value
      3:     ST  0,0(5) 	read: store value
    * -> if
    * -> Op
    * -> Const
      4:    LDC  0,0(0) 	load const
    * <- Const
      5:     ST  0,0(6) 	op: push left
    * -> Id
      6:     LD  0,0(5) 	load id value
    * <- Id
      7:     LD  1,0(6) 	op: load left
      8:    SUB  0,1,0 	op <
      9:    JLT  0,2(7) 	br if true
     10:    LDC  0,0(0) 	false case
     11:    LDA  7,1(7) 	unconditional jmp
     12:    LDC  0,1(0) 	true case
    * <- Op
    * if: jump to else belongs here
    * -> assign
    * -> Const
     14:    LDC  0,1(0) 	load const
    * <- Const
     15:     ST  0,1(5) 	assign: store value
    * <- assign
    * -> repeat
    * repeat: jump after body comes back here
    * -> assign
    * -> Op
    * -> Id
     16:     LD  0,1(5) 	load id value
    * <- Id
     17:     ST  0,0(6) 	op: push left
    * -> Id
     18:     LD  0,0(5) 	load id value
    * <- Id
     19:     LD  1,0(6) 	op: load left
     20:    MUL  0,1,0 	op *
    * <- Op
     21:     ST  0,1(5) 	assign: store value
    * <- assign
    * -> assign
    * -> Op
    * -> Id
     22:     LD  0,0(5) 	load id value
    * <- Id
     23:     ST  0,0(6) 	op: push left
    * -> Const
     24:    LDC  0,1(0) 	load const

     

    展开全文
  • 编译方法实验报告(中间代码生成器).pdf
  • 中间代码生成器设计

    2008-04-22 19:43:47
    编辑原理的中间代码生成器设计C语言版
  • 编译方法实验报告(中间代码生成器的设计).pdf
  • 实验五_用语法制导方式生成中间代码生成器[收集].pdf
  • 解析器然后从上面,我们做了一个解析器,输出是一个点格式的输入程序的解析树(可以使用graphviz渲染)中间代码生成器在这里,我们为源语言 JAVA 编写了一个中间代码生成器(在 Ass3 文件夹中)。 它的输出是三个...
  • 编译原理实验,扫描器设计,中间代码生成器设计
  • 华南理工大学SE编译原理实验4 - 中间代码生成
  • 中间代码生成器的文法采用的是递归子程序属性文法。
  • 编译原理 中间代码生成器设计 ~~~~~~~~~~~~~~~~~~~~~~~~~
  • 一个简单的编辑 编译原理课设 对简单的程序进行语义分析并将中间代码生成
  • 两次编译方法的实验,实验一要求实现一个扫描器,实验二要求实现一个中间代码生成器,其中实验二使用了递归子程序和LL1方法实现,代码为自己编写,希望能给您带来帮助
  • 中间代码生成器-5-编译原理

    千次阅读 2013-08-26 12:56:00
    中间代码生成器  一、实验目的 掌握中间代码生成器的构造原理和编程方法。   二、实验内容 用自顶向下方法或Yacc进行语法分析的基础上,编写一个中间代码生成程序。(见教材附录 A.1,p394) program → ...

                              中间代码生成器 

    一、实验目的

    掌握中间代码生成器的构造原理和编程方法。

     

    二、实验内容

    用自顶向下方法或Yacc进行语法分析的基础上,编写一个中间代码生成程序。见教材附录 A.1p394

    program      → block

    block     →   { decls stmts }

    decls  →   decls decl | e

    decl   →   type id ;

    type   →   type [num]   //数组可以不做

     | basic        //四种基本数据类型 int | float | char | bool

    stmts     → stmts stmt | e

           stmt       →   id= expr ;

                            |      if ( bool ) stmt

                                |      if ( bool) stmt else stmt

    |      while (bool) stmt

    |      do stmt while (bool ) ;

    |      break ;    //break可以不做

    |      block

    bool        →  bool || join  |  join

    join     →   join  && equality | equality

    equality  →  equality == rel  |  equality != rel  |  rel

    rel      →  expr < expr

    |    expr <= expr

    |     expr > expr

    |     expr >= expr

    |     expr

    expr      → expr + term

    |     expr - term

    |     term

    term      → term * unary

     |   term / unary

    |     unary

          unary  →  !unary  |  - unary  |  factor

    factor     → ( expr ) | id| num 

     

    三、实验要求

    1.个人完成,提交实验报告。

    2.实验的结果为:生成中间代码 (三地址码)

    {

    a=10;

    x = b - c;

    y = a * x;

    z = x * d;

    abcd = a + x +y;

    if(a>10)

    a=a+1;

    a=a+2;

    }

        实验结果生成的代码片段

        0:  a =  10

        1:  t0 = b - c

        2:  x =  t0

        3:  t1 = a * x

        4:  y =  t1

        5:  t2 = x * d

        6:  z =  t2

        7:  t3 = a + x

        8:  t4 = t3 + y

        9:  abcd =  t4

       10:  if a > 10 goto 12

       11:  goto 14

       12:  t5 = a + 1

       13:  a =  t5

       14:  t6 = a + 2

       15:  a =  t6

    个人对于本次中间代码生成器-编译实验的心得:

    View Code
           #define YYSTYPE node:定义符号栈属性结点类型
    
    typedef struct node
    
    {
    
          instrlist *truelist, *falselist, *nextlist;//相当于有一个 正确链表与 错误链表 每个链表结点都有个值
    
           char addr[256];//    地址字段       存放具体结点的内容比如 a 8 10 等
    
           char lexeme[256];//字符串指端
    
           char oper[3];//操作符字段           具体存放操作符对应的字符串
    
           int instr; //是否要回填指示          具体内容是行号
    
    }node;
    
    int main()
    
    {
    
           list = newcodelist();
    
    //申请一个内存空间给list
    
    // int linecnt, capacity;   行数  与  最大行数
    
    // int temp_index;         
    
    // char **code;                     总代码
    
           freopen("test.in", "rt+", stdin);
    
           freopen("test.out", "wt+", stdout);
    
    //打开文件
    
           yyparse();
    
           print(list);
    
           fclose(stdin);
    
    //关闭文件
    
           fclose(stdout);
    
    //关闭文件
    
           return 0;
    
    }
    
    int gen_if(codelist *dst, node left, char* op, node right)
    
    {
    
           sprintf(tmp, "if %s %s %s goto", left.addr, op, right.addr);//第一个字符串 操作符 第二个字符串
    
           Gen(dst, tmp);       //将tmp的内容存放到 总字符串                list的code字段当中
    
           return 0;
    
    }    
    
    int Gen(codelist *dst, char *str)  //输入 第一个参数为 list  第二个参数是 总字符串 tmp[1024]
    
           {                             //目标是   将tmp的内容存放到 总字符串           list的code字段当中
    
     
    
                  if (dst->linecnt >= dst->capacity)
    
                  {
    
                         dst->capacity += 1024;
    
                         dst->code = (char**)realloc(dst->code, sizeof(char*)*dst->capacity);
    
                         if (dst->code == NULL)
    
                         {
    
                                printf("short of memeory\n");
    
                                return 0;
    
                         }
    
                  }
    
                  dst->code[dst->linecnt] = (char*)malloc(strlen(str)+20);     //申请一个内存空间存放中间字符串
    
                  strcpy(dst->code[dst->linecnt], str);                    //字符串复制
    
                  dst->linecnt++;                                  //行号加1
    
                  return 0;
    
           }
    
           int backpatch(codelist *dst, instrlist *list, int instrno)     //总代码 dst  错误列表list   错误的指向行数
    
           {
    
                  if (list!=NULL)                                          //如果错误的列表不为空
    
                  {
    
                         listele *p=list->first;     
    
                         char tmp[20];
    
                 
    
                         sprintf(tmp, " %d", instrno);                     取出一个
    
                         while (p!=NULL)
    
                         {
    
                                if (p->instrno<dst->linecnt)
    
                                       strcat(dst->code[p->instrno], tmp);   //错误列表:1 2 3 4  假设都指向instrno=6 那么将6转化为字符串tmp
    
                                                                          //再添加到每个字符串的末尾
    
                                p=p->next;
    
                         }
    
                  }
    
                  return 0;
    
           }
    
    // int linecnt, capacity; 行数  与  最大行数
    
    // int temp_index;       
    
    // char **code;     


    重点是对课上的回填技术,还有

    栈中的可能属性类别也就是node结点的属性种类,还有的是全局变量list使用的结点除了行号,最大行号,还有就是三地址码存放的chor **类型的code。

    jia.l

    View Code
    %{
        #include "jia.tab.h"
    %}
    delim        [ \t\n\r]
    ws        {delim}+
    letter        [A-Za-z]
    digit        [0-9]
    id        {letter}({letter}|{digit})*
    integer        {digit}+
    exponent    E[+-]?{integer}
    number        {integer}{exponent}?
    real        integer(\.integer)?{exponent}?
    %option noyywrap
    %%
    if    { return( IF ); }
    else     { return( ELSE ); }
    while    { return( WHILE ); }
    do    { return( DO ); }
    for    { return( FOR ); }
    switch    { return( SWITCH ); }
    case    { return( CASE ); }
    default    { return( DEFAULT ); }
    break    { return( BREAK ); }
    true    { return( TRUE ); }
    false    { return( FALSE ); }
    int    { return( INT ); }
    long    { return( LONG ); }
    char    { return( CHAR ); }
    bool    { return( BOOL ); }
    float    { return( FLOAT ); }
    double    { return( DOUBLE ); }
    "&&"    { return( AND ); }
    "||"    { return( OR ); }
    "!"    { return( '!'); }
    "<"|"<="|">"|">="|"!="|"=="    { filloperator(&yylval, yytext); return( REL); }
    "++"    { return( INC ); }
    "--"    { return( DEC ); }
    "+"    { return( '+' ); }
    "-"    { return( '-' ); }
    "*"    { return( '*' ); }
    "/"    { return( '/' ); }
    "="    { return( '=' ); }
    "{"    { return( '{' ); }
    "}"    { return( '}' ); }
    "["    { return( '[' ); }
    "]"    { return( ']' ); }
    "("    { return( '(' ); }
    ")"    { return( ')' ); }
    
    ";"    { return( ';' ); }
    {ws}    { }
    {id}    { filllexeme(&yylval, yytext); return( ID ); }
    {number}    { filllexeme(&yylval, yytext); return( NUMBER ); }
    {real}        { filllexeme(&yylval, yytext); return( REAL ); }
    %%

    jia.y

    View Code
    %{
        #include "xu.h"
        #define YYSTYPE node
        #include "jia.tab.h"
    
        int yyerror();
        int yyerror(char* msg);
        extern int yylex();
        
        codelist* list;
    %}
    %token BASIC NUMBER REAL ID TRUE FALSE
    %token INT LONG CHAR BOOL FLOAT DOUBLE
    %token REL
    %token IF ELSE WHILE DO BREAK FOR SWITCH CASE DEFAULT 
    %token OR AND
    %left OR
    %left AND
    %right '!'
    %left '+' '-'
    %left '*' '/'
    %right UMINUS
    %right INC DEC
    %%
    
    program : block         {  }
        ;
    
    block     : '{' decls statementlist '}' { }
        ;
    
    decls    : decls decl        {  }
        |            {  }
        ;
    
    decl    : type ID ';'        {  }
        ;
    
    type    : type '[' NUMBER ']'    {  }
        | BASIC            {  }
        ;
    
    statementlist    :
             statementlist M statement    { backpatch(list, $1.nextlist, $2.instr);
                              $$.nextlist = $3.nextlist; }
            | statement            { $$.nextlist = $1.nextlist; }
            ;
    
    statement    :
         IF '(' boolean ')' M statement ELSE N M statement    { backpatch(list, $3.truelist, $5.instr);
                                      backpatch(list, $3.falselist, $9.instr);
                                      $6.nextlist = merge($6.nextlist, $8.nextlist);
                                      $$.nextlist = merge($6.nextlist, $10.nextlist); } 
            | IF '(' boolean ')' M statement        { backpatch(list, $3.truelist, $5.instr);
                                  $$.nextlist = merge($3.falselist, $6.nextlist); }
        | WHILE M '(' boolean ')' M statement    { backpatch(list, $7.nextlist, $2.instr);
                              backpatch(list, $4.truelist, $6.instr);
                              $$.nextlist = $4.falselist;
                              gen_goto(list, $2.instr); }
        | DO M statement M WHILE '(' boolean ')' M ';'    { backpatch(list, $3.nextlist, $4.instr);
                                    backpatch(list, $7.truelist, $9.instr);
                                  $$.nextlist = $7.falselist;
                                   gen_goto(list, $2.instr); }
        | FOR '(' assignment ';' M boolean ';' M assignment ')' N M statement { backpatch(list, $6.truelist, $12.instr);
                                            backpatch(list, $11.nextlist, $5.instr);
                                            backpatch(list, $13.nextlist, $8.instr);
                                            $$.nextlist = $6.falselist;
                                            gen_goto(list, $8.instr); }
        | BREAK ';'                {  }
        | '{' statementlist '}'                { $$.nextlist = $2.nextlist; } 
        | assignment ';'        { $$.nextlist = NULL; }
        ;
    
    assignment    : ID '=' boolean          { copyaddr(&$1, $1.lexeme); gen_assignment(list, $1, $3); }
        ;
    
    loc    : loc '[' boolean ']'    {  }
        | ID            { copyaddr(&$$, $1.lexeme); }
        ;
    
    boolean    : boolean OR M boolean    { backpatch(list, $1.falselist, $3.instr);
                      $$.truelist = merge($1.truelist, $4.truelist);
                      $$.falselist = $4.falselist; }
        | boolean AND M boolean    { backpatch(list, $1.truelist, $3.instr);
                      $$.truelist = $4.truelist;
                      $$.falselist = merge($1.falselist, $4.falselist); }
        | '!' boolean        { $$.truelist = $1.falselist;
                      $$.falselist = $1.truelist; }
        | '(' boolean ')'        { $$.truelist = $1.truelist; 
                      $$.falselist = $1.falselist; }
        | expression REL expression        { $$.truelist = new_instrlist(nextinstr(list));
                              $$.falselist = new_instrlist(nextinstr(list)+1);
                              gen_if(list, $1, $2.oper, $3);
                              gen_goto_blank(list); }
        | TRUE            { copyaddr(&$$, "TRUE");
                      gen_goto_blank(list); }
        | FALSE                { copyaddr(&$$, "FALSE");
                          gen_goto_blank(list); }
        | expression        { copyaddr_fromnode(&$$, $1); }
        ;
    
    M    :         { $$.instr = nextinstr(list); }
        ;
    
    N    :            { $$.nextlist = new_instrlist(nextinstr(list));
                      gen_goto_blank(list); }
        ;
    
    expression    : expression '+' expression        { new_temp(&$$, get_temp_index(list)); gen_3addr(list, $$, $1, "+", $3); }
        | expression '-' expression        { new_temp(&$$, get_temp_index(list)); gen_3addr(list, $$, $1, "-", $3); }
        | expression '*' expression            { new_temp(&$$, get_temp_index(list)); gen_3addr(list, $$, $1, "*", $3); }
        | expression '/' expression        { new_temp(&$$, get_temp_index(list)); gen_3addr(list, $$, $1, "/", $3); }
        | '-' expression %prec UMINUS            { new_temp(&$$, get_temp_index(list)); gen_2addr(list, $$, "-", $2); }
        | loc            { copyaddr_fromnode(&$$, $1); }
        | NUMBER            { copyaddr(&$$, $1.lexeme); }
        | REAL            { copyaddr(&$$, $1.lexeme); }
        ;
    
    %%
    
    
    int yyerror(char* msg)
    {
        printf("\nERROR with message: %s\n", msg);
        return 0;
    }
    
    
    int main()
    {
        list = newcodelist();
    //申请一个内存空间给list 
    // int linecnt, capacity;
    // int temp_index;
    // char **code;
        freopen("test.in", "rt+", stdin);
        freopen("test.out", "wt+", stdout);
    //打开文件
        yyparse();
        print(list);
        fclose(stdin);
    //关闭文件
        fclose(stdout);
    //关闭文件
        return 0;
    }

    xu.h

    View Code
    #ifndef CP_H
    #define CP_H
    
    #include <stdio.h>
    #include <string.h>
    #include <malloc.h>
    
    typedef struct listele
    {
        int instrno;
        struct listele *next;
    }listele;
    
        listele* new_listele(int no)
        {
            listele* p = (listele*)malloc(sizeof(listele));
            p->instrno = no;
            p->next = NULL;
            return p;
        }
    
    
    typedef struct instrlist
    {
        listele *first,*last;
    }instrlist;
    
        instrlist* new_instrlist(int instrno)
        {
            instrlist* p = (instrlist*)malloc(sizeof(instrlist));
            p->first = p->last = new_listele(instrno);
            return p;
        }
    
        instrlist* merge(instrlist *list1, instrlist *list2)
        {
            instrlist *p;
            if (list1 == NULL) p = list2;
            else
            {
                if (list2!=NULL)
                {
                    if (list1->last == NULL)
                    {
                        list1->first = list2->first;
                        list1->last =list2->last;
                    }else list1->last->next = list2->first;
                    list2->first = list2->last = NULL;
                    free(list2);
                }
                p = list1;
            }
            return p;
        }
    
    typedef struct node
    {
         instrlist *truelist, *falselist, *nextlist;
        char addr[256];
        char lexeme[256];
        char oper[3];
        int instr;
    }node;
    
        int filloperator(node *dst, char *src)
        {
            strcpy(dst->oper, src);
            return 0;
        }    
        int filllexeme(node *dst, char *yytext)
        {
            strcpy(dst->lexeme, yytext);
            return 0;
        }
        int copyaddr(node *dst, char *src)
        {
            strcpy(dst->addr, src);
            return 0;
        }
        int new_temp(node *dst, int index)
        {
            sprintf(dst->addr, "t%d", index);
            return 0;
        }
        int copyaddr_fromnode(node *dst, node src)
        {
            strcpy(dst->addr, src.addr);
            return 0;
        }
    
    typedef struct codelist
    {
          int linecnt, capacity;
        int temp_index;
        char **code;
    }codelist;
    
          codelist* newcodelist()
        {
            codelist* p = (codelist*)malloc(sizeof(codelist));
            p->linecnt = 0;
            p->capacity = 1024;
            p->temp_index = 0;
            p->code = (char**)malloc(sizeof(char*)*1024);
            return p;
        }
    
        int get_temp_index(codelist* dst)
        {
            return dst->temp_index++;
        }
    
        int nextinstr(codelist *dst) { return dst->linecnt; }
        
          int Gen(codelist *dst, char *str)
        {
    
            if (dst->linecnt >= dst->capacity)
            {
                dst->capacity += 1024;
                dst->code = (char**)realloc(dst->code, sizeof(char*)*dst->capacity);
                if (dst->code == NULL)
                {
                    printf("short of memeory\n");
                    return 0;
                }
            }
            dst->code[dst->linecnt] = (char*)malloc(strlen(str)+20);
            strcpy(dst->code[dst->linecnt], str);
            dst->linecnt++;
            return 0;
        }
    
        char tmp[1024];
    
        int gen_goto_blank(codelist *dst)
        {
            sprintf(tmp, "goto");
            Gen(dst, tmp);
            return 0;
        }
    
        int gen_goto(codelist *dst, int instrno)
        {
            sprintf(tmp, "goto %d", instrno);
            Gen(dst, tmp);
            return 0;
        }
    
        int gen_if(codelist *dst, node left, char* op, node right)
        {
            sprintf(tmp, "if %s %s %s goto", left.addr, op, right.addr);
            Gen(dst, tmp);
            return 0;
        }
    
        int gen_1addr(codelist *dst, node left, char* op)
        {
            sprintf(tmp, "%s %s", left.addr, op);
            Gen(dst, tmp);
            return 0;
        }
    
        int gen_2addr(codelist *dst, node left, char* op, node right)
        {
            sprintf(tmp, "%s = %s %s", left.addr, op, right.addr);
            Gen(dst, tmp);
            return 0;
        }
    
        int gen_3addr(codelist *dst, node left, node op1, char* op, node op2)
        {
            sprintf(tmp, "%s = %s %s %s", left.addr, op1.addr, op, op2.addr);
            Gen(dst, tmp);
            return 0;
        }
    
        int gen_assignment(codelist *dst, node left, node right)
        {
            gen_2addr(dst, left, "", right);
            return 0;
        }
    
        int backpatch(codelist *dst, instrlist *list, int instrno)
        {
            if (list!=NULL)
            {
                listele *p=list->first;
                char tmp[20];
            
                sprintf(tmp, " %d", instrno);
                while (p!=NULL)
                {
                    if (p->instrno<dst->linecnt)
                        strcat(dst->code[p->instrno], tmp);
                    p=p->next;
                }
            }
            return 0;
        }
    
        int print(codelist* dst)
        {
            int i;
            
            for (i=0; i < dst->linecnt; i++)
                printf("%5d:  %s\n", i, dst->code[i]);
            return 0;
        }
    
    #endif

    test.in

    View Code
    {
    
    a=10;
    x = b - c;
    y = a * x;
    z = x * d;
    abcd = a + x +y;
    if(a>10)
    a=a+1;
    a=a+2;
    while(a>0)
    a=a-1;
    b=b+1;
    }

     最终老师给的代码暂未公开

    课件

    展开全文
  • 表达式中间代码生成 二、实验目的 熟悉算术表达式的语法分析与中间代码生成原理。 三、实验内容 1. 构造算术表达式的四元式翻译文法 2. 设计算术表达式的递归下降子程序分析算法 3. 设计算术表达的四元式生成算法...
  • 能对下列表达式进行解析,生成正确的中间代码。 (q+(s+d)-r) 3-((wang+1.2)+(li-3.4)) (e-d)*(a+b) ((((li+gao)))) a1+b2*(((t*(q+w))-po)/gi)

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 309,750
精华内容 123,900
关键字:

中间代码生成器