基于C语言实现的一个小型编译程序

朱雀 2024-04-07 13:18 77阅读 0赞

## 基于 C 语言实现一个小型编译程序 ##

### 本次课程设计任务 ###

*  实现一个小型编译程序
    
     *  输入:高级语言源程序
     *  输出:四元式程序(必做)
    
        汇编语言程序(选做)
 *  小型编译程序执行分两个阶段：
    
     *  第一阶段，将高级语言源程序翻译成四元式程序；
     *  第二阶段，将四元式程序翻译成汇编语言目标程序。如图 1 所示：

![在这里插入图片描述][0a23ba8edd4c43f8a9f41303ec43c67e.png]

*  本次课程设计要求所有同学完成小型编译程序的第一阶段（**必做**），第二阶段为选做题目（完成加分）。

--------------------

### 示例 ###

*  下例为一个名为 `PAS.DAT` 的高级语言源程序经过 `PAS` 的编译，产生名为 `PAS.MED` 的四元式（中间代码）程序；`PAS.MED` 经过 `COMPILER` 编译生成 `8086/8088` 汇编语言目标程序 `PAS.ASM`。
    
        /*************************************************************/
        /* pas.dat */
        /* 高级语言源程序 */
        /************************************************************/
        while (a>b) do 
            begin
            if m>=n then 
                a:=a+1
            else
                while k=h do 
                    x:=x+2;
        	m:=n+x*(m+y)
            end
            #
            ~
        /*************************************************************/
    
        /*************************************************************/
        /* pas.med */
        /* 高级语言生成的四元式文件 */
        /*************************************************************/
        100 (j>, a, b, 102)
        101 (j, , , 117)
        102 (j>=,m,n, 104)
        103 (j, , , 107)
        104 (+,a, 1, T1)
        105 (:=,T1, ,a)
        106 (j, , , 112)
        107 (j=,k, h, 109)
        108 (j, , ,112)
        109 (+, x,2,T2)
        110 (:=,T2, , x)
        111 (j, , , 107)
        112 (+, m ,y, T3)
        113 (*, x, T3, T4)
        114 (+, n, T4, T5)
        115 (:=,T5, , m)
        116 (j, , , 100)
        117
        /*************************************************************/

![在这里插入图片描述][ebef579049bc488cbd72ed84ba540c1e.png]  
![在这里插入图片描述][063fdd0b11af44e78a2e70ecfc64b33d.png]

--------------------

### **小型编译程序关于高级语言的规定** ###

*  高级语言程序具有四种基本结构：顺序结构﹑选择结构﹑循环结构和过程。为了便于掌握编译的核心内容，突出重点，简化编译程序的结构，同时又涵盖高级语言程序的基本结构，我们选取赋值语句﹑if 语句和 while 语句作为前三种结构的代表，略去了过程结构。实际上，上述三种语句已经基本满足了高级语言的程序设计。因此，我们仅考虑由下面产生式所定义的程序语句：

S→if B then S else S︱while B do S︱begin L end︱A
    L→S;L︱S
    A→i:=E
    B→B∧B︱B∨B︱┐B︱(B)︱i rop i︱i
    E→E+E︱E*E︱(E)︱i

*  其中，各非终结符的含义如下：
    
     *  S —— 语句；
     *  L —— 语句串；
     *  A —— 赋值句；
     *  B —— 布尔表达式；
     *  E —— 算术表达式。
 *  各终结符的含义如下：
    
     *  i —— 整型变量或常数，布尔变量或常数；
     *  rop —— 六种关系运算符的代表；
     *  ; —— 起语句分隔符作用；
     *  := —— 赋值符号；
     *  ┐ —— 逻辑非运算符“not”；
     *  ∧ —— 逻辑与运算符“and”；
     *  ∨ —— 逻辑或运算符“or”；
     *  \+ —— 算术加运算符；
     *  \* —— 算术乘运算符；
     *  ( —— 左括号；
     *  ) —— 右括号。
 *  注意，六种关系运算符分别为
    
        < 小于    <= 小于等于    <> 不等于 
        
          \> 大于    >= 大于等于    = 等于
 *  关于表达式的运算，我们规定由高到低优先顺序为算术运算、关系运算、布尔运算；并且服从左结合规则。算术运算符优先级的顺序依次为 “( )”﹑ “\*”﹑“+”；布尔运算符优先级的顺序依次为 “┐”﹑“∧”﹑“∨”；六个关系运算符优先级相同。
 *  我们规定的程序是由一条语句或由 begin 和 end 嵌套起来的复合语句组成的，并且规定在语句末要加上“\#~”表示程序结束。下面给出的是符合规定的程序
    
    示例：
    
        /*****************************************************/
        begin 
            A:=A+B*C;
        	C:=A+2;
        	while A<C and B<D do
            	while A>B do 
                	if M=N then C:=D
                    else while A<=D do
                        A:=D
        End
        #~

--------------------

### **小型编译程序关于单词的内部定义** ###

*  由于我们规定的程序语句中涉及单词较少，故在词法分析阶段忽略了单词输入错误的检查，而将编译程序的重点放在中间代码生成阶段。词法分析器的功能是输入源程序，输出单词符号。我们规定输出的单词符号格式为如下的二元式：

(单词种别，单词自身的值)

我们对常量、变量、临时变量、保留关键字(if、while、begin、end、else、then、do 等)、关系运算符、逻辑运算符、分号、括号等，规定其内部定义如表 1 所示。

![在这里插入图片描述][e502435d2c304b9aac1fb559418b7ace.png]

> 注：单词自身的值对变量而言是指其在变量表中的位置

--------------------

### **小型编译程序的 LR 分析表** ###

--------------------

#### **1.算术表达式的 LR 分析表** ####

算术表达式文法 G\[E\] 如下：

$E -> E+E︱E*E︱(E)︱i$

将文法 G\[E\]拓广为文法 G′\[E\]：

(0) $S′→E$
    
    		(1) $E→E+E$
    
    		(2) $E→E*E$
    
    		(3) $E→(E)$
    
    		(4) $E→i$

由此得到算术表达式的 SLR(1) 分析表如表 2 所示。

![在这里插入图片描述][33522816fda04229b4806bc0faf063f8.png]

--------------------

#### 2.布尔表达式的 LR 分析表 ####

布尔表达式的文法如下：

$B -> B∧B︱B∨B︱┐B︱i \; rop \; i︱i$

为了便于语法分析时的加工处理，我们将上述文法改写为文法 G\[S\]：

$B → B^AB | B^OB | ┐B | (B)︱i \; rop \; i︱i$
    
    			$B^A → B ∧ $
    
    			$B^O → B∨$

将文法 G\[S\] 拓广为文法 G\[S′\]：

$(0) S′→B$
    
    			$(1) B→i$
    
    			$ (2) B→i \; rop \; i$
    
    			$ (3) B→(B)$
    
    			$ (4) B→not \; B$
    
    			$ (5) A→B \; and$
    
    			$ (6) B→AB$
    
    			$ (7) O→B \; or$
    
    			$ (8) B→OB$

由此得到布尔表达式的 SLR(1)分析表如表 3 所示。

![在这里插入图片描述][fa3121b264974f4da34b40d4a58ee10d.png]

--------------------

#### 3.程序语句的 LR 分析表 ####

程序语句的文法 G\[S\]如下：

$S→if \; e \; then \; S \; else \; S \; | \; while \; e \; do \; S \; | \; begin \; L \; end \; | \; a$
    
    			$L→S;L︱S$

由于在编译程序设计与实现中，我们是将赋值语句与算术表达式归为一类处理的，故在此将赋值语句仅看作为程序语句文法中的一

个终结符 a，将布尔表达式 B 也看作为终结符 e。将文法 G\[S\]拓广为文法 G\[S′\]：

(0) $S′→S$
    
    			(1) $S→if \; e \; then \; S \; else \; S $
    
    			(2) $S→while \; e \; do \; S$
    
    			(3) $S→begin \; L \; end$
    
    			(4) $S→a$
    
    			(5) $L→S$
    
    			(6) $L→S;L$

由此得到程序语句的 SLR(1) 分析表如表 4 所示。

![在这里插入图片描述][bc47b0588d31454da1246a4ea485af64.png]

--------------------

### 小型编译程序执行过程 ###

![在这里插入图片描述][974c8a96b54342cf850ace0605ed8b4e.png]  
![在这里插入图片描述][179ed9ad556e499b9cbf35e2eae3809e.png]  
![在这里插入图片描述][20c92a7a78f54137a1e6d5b895976b87.png]

![在这里插入图片描述][c1df8034a6b84c6083e72ff8c720f7be.png]  
![在这里插入图片描述][c1d77d94b58a47e2b3aed1b1550f24dd.png]

--------------------

## 系统结构图 ##

![在这里插入图片描述][60fa241ee59f4866b2f5cbf018379800.png]

--------------------

## 程序流程图 ##

--------------------

### 主函数 ###

![在这里插入图片描述][5aa8bf322d6046729fffa25ead77e45c.png]

--------------------

### 程序语句分析程序 ###

![在这里插入图片描述][f8febea0a17547d3b21c7ad44fdd4cf9.png]

--------------------

### 语句分析子程序 ###

![在这里插入图片描述][511cca6ce41d48e6b090743eb8d878a5.png]

--------------------

## 词法分析 ##

--------------------

### 准备阶段 ###

![在这里插入图片描述][f6b3a5ec69bc4f52b95e1d72f5446d21.png]

--------------------

### 词法分析阶段 ###

![在这里插入图片描述][b81faff793da4fcbbed569078f81ebce.png]

--------------------

#### 单词内部定义 ####

<table> 
 <thead> 
  <tr> 
   <th align="center">符号</th> 
   <th align="center">种别编码</th> 
   <th align="center">说明</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td align="center">sy__if</td> 
   <td align="center">0</td> 
   <td align="center">保留字 if</td> 
  </tr> 
  <tr> 
   <td align="center">sy_then</td> 
   <td align="center">1</td> 
   <td align="center">保留字 then</td> 
  </tr> 
  <tr> 
   <td align="center">sy_else</td> 
   <td align="center">2</td> 
   <td align="center">保留字 else</td> 
  </tr> 
  <tr> 
   <td align="center">sy_while</td> 
   <td align="center">3</td> 
   <td align="center">保留字 while</td> 
  </tr> 
  <tr> 
   <td align="center">sy_begin</td> 
   <td align="center">4</td> 
   <td align="center">保留字 begin</td> 
  </tr> 
  <tr> 
   <td align="center">sy_do</td> 
   <td align="center">5</td> 
   <td align="center">保留字 do</td> 
  </tr> 
  <tr> 
   <td align="center">sy_end</td> 
   <td align="center">6</td> 
   <td align="center">保留字 end</td> 
  </tr> 
  <tr> 
   <td align="center">a</td> 
   <td align="center">7</td> 
   <td align="center">赋值语句</td> 
  </tr> 
  <tr> 
   <td align="center">semicolon</td> 
   <td align="center">8</td> 
   <td align="center">“:”</td> 
  </tr> 
  <tr> 
   <td align="center">e</td> 
   <td align="center">9</td> 
   <td align="center">布尔表达式</td> 
  </tr> 
  <tr> 
   <td align="center">jinghao</td> 
   <td align="center">10</td> 
   <td align="center">“#”</td> 
  </tr> 
  <tr> 
   <td align="center">S</td> 
   <td align="center">11</td> 
   <td align="center">语句</td> 
  </tr> 
  <tr> 
   <td align="center">L</td> 
   <td align="center">12</td> 
   <td align="center">复合语句</td> 
  </tr> 
  <tr> 
   <td align="center">tempsy</td> 
   <td align="center">15</td> 
   <td align="center">临时变量</td> 
  </tr> 
  <tr> 
   <td align="center">EA</td> 
   <td align="center">18</td> 
   <td align="center">B and(即布尔表达式中“B 且”)</td> 
  </tr> 
  <tr> 
   <td align="center">EO</td> 
   <td align="center">19</td> 
   <td align="center">B or(即布尔表达式中“B 或”)</td> 
  </tr> 
  <tr> 
   <td align="center">plus</td> 
   <td align="center">34</td> 
   <td align="center">“+”</td> 
  </tr> 
  <tr> 
   <td align="center">times</td> 
   <td align="center">36</td> 
   <td align="center">“*”</td> 
  </tr> 
  <tr> 
   <td align="center">becomes</td> 
   <td align="center">38</td> 
   <td align="center">“:=”</td> 
  </tr> 
  <tr> 
   <td align="center">op_and</td> 
   <td align="center">39</td> 
   <td align="center">“and”</td> 
  </tr> 
  <tr> 
   <td align="center">op_or</td> 
   <td align="center">40</td> 
   <td align="center">“or”</td> 
  </tr> 
  <tr> 
   <td align="center">op_not</td> 
   <td align="center">41</td> 
   <td align="center">“not”</td> 
  </tr> 
  <tr> 
   <td align="center">rop</td> 
   <td align="center">42</td> 
   <td align="center">关系运算符</td> 
  </tr> 
  <tr> 
   <td align="center">lparent</td> 
   <td align="center">48</td> 
   <td align="center">“(”</td> 
  </tr> 
  <tr> 
   <td align="center">rparent</td> 
   <td align="center">49</td> 
   <td align="center">“)”</td> 
  </tr> 
  <tr> 
   <td align="center">ident</td> 
   <td align="center">56</td> 
   <td align="center">变量</td> 
  </tr> 
  <tr> 
   <td align="center">intconst</td> 
   <td align="center">57</td> 
   <td align="center">整常量</td> 
  </tr> 
 </tbody> 
</table>

> 变量的子种别编码根据识别的先后顺序由 0 逐渐递增
> 
> 整常量的子种别编码就是整常量本身

*  关系运算符 rop 的子种别编码
    
    <table> 
     <thead> 
      <tr> 
       <th align="center">子种别编码</th> 
       <th align="center">说明</th> 
      </tr> 
     </thead> 
     <tbody> 
      <tr> 
       <td align="center">0</td> 
       <td align="center">&lt;=</td> 
      </tr> 
      <tr> 
       <td align="center">1</td> 
       <td align="center">&lt;</td> 
      </tr> 
      <tr> 
       <td align="center">2</td> 
       <td align="center">&gt;=</td> 
      </tr> 
      <tr> 
       <td align="center">3</td> 
       <td align="center">&gt;</td> 
      </tr> 
      <tr> 
       <td align="center">4</td> 
       <td align="center">&lt;&gt;</td> 
      </tr> 
      <tr> 
       <td align="center">5</td> 
       <td align="center">=</td> 
      </tr> 
     </tbody> 
    </table>

ident | 56 | 变量 |  
| intconst | 57 | 整常量 |

> 变量的子种别编码根据识别的先后顺序由 0 逐渐递增
> 
> 整常量的子种别编码就是整常量本身

[0a23ba8edd4c43f8a9f41303ec43c67e.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/07/994601534502431aaf798b5126dfb779.png
[ebef579049bc488cbd72ed84ba540c1e.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/07/f0dcf48cacbc4618b6e481ad4b1770ec.png
[063fdd0b11af44e78a2e70ecfc64b33d.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/07/71b9bfb56cde4bab8adc9a35f6e649e9.png
[e502435d2c304b9aac1fb559418b7ace.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/07/07be4e3e991e4c89841676680a357ad9.png
[33522816fda04229b4806bc0faf063f8.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/07/7657a98229474350a633fe1967333cb0.png
[fa3121b264974f4da34b40d4a58ee10d.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/07/891750f0c1bb40aa85c234a6b71c28b9.png
[bc47b0588d31454da1246a4ea485af64.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/07/2233dcc0a1bd4977859e95f7624786b2.png
[974c8a96b54342cf850ace0605ed8b4e.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/07/c8d7768d312f4a1db00664f21b6fc2ea.png
[179ed9ad556e499b9cbf35e2eae3809e.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/07/8a4b25b6c1ae47f5983bcfc7e864d8db.png
[20c92a7a78f54137a1e6d5b895976b87.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/07/1af0904036fa461080140887c476c86a.png
[c1df8034a6b84c6083e72ff8c720f7be.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/07/f74f16343dd542c78893345204273754.png
[c1d77d94b58a47e2b3aed1b1550f24dd.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/07/a289a41898774cde9b724d7fc75af3bb.png
[60fa241ee59f4866b2f5cbf018379800.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/07/07471b696da744d1a83c560927767b22.png
[5aa8bf322d6046729fffa25ead77e45c.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/07/447331e8c32b463b9e666bd434f1a10b.png
[f8febea0a17547d3b21c7ad44fdd4cf9.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/07/054566ba8766481196b8c0a03c127126.png
[511cca6ce41d48e6b090743eb8d878a5.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/07/11760edc1f234839852197ec9ff40eb6.png
[f6b3a5ec69bc4f52b95e1d72f5446d21.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/07/4163add70c70414aa1dc952e8fb5c265.png
[b81faff793da4fcbbed569078f81ebce.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/07/97a7ab2c71c54ad697464b500894e7b8.png