形式语言与编译 15 语法制导下的语义翻译过程
语法制导翻译和中间代码生成
语法分析之后进行语义分析。
语义分析包含两项工作：
- 说明语义没有问题
- 生成中间代码 (因此有时候我们把语义分析和中间代码生成等价)
中间代码的表示形式有很多，逆波兰记号、树形表示、三元式、四元式。
这些都是介于单词流 和 目标指令之间的中间产品。
困难：语义分析(中间代码生成)不如词法分析、语法分析有比较成熟的数学工具(形式化工具)。语义分析的数学工具尚未诞生。虽然有属性文法，但是属性文法并不是一个完美的形式系统
解决办法：为每一个产生式配一个 翻译子程序 ，在语法分析的同时执行它。
在语法分析的过程中，每使用一个产生式就会使用一个语义动作，这里的语义动作我们主要使用的是 属性文法。在这样语法分析的过程中会产生中间代码。
我们语义分析的示例主要是使用自底向上的分析方法。但是要知道，自上而下也是可以进行语法制导的语义分析的。
我们并不是有源程序直接得到目标代码，而是在之间用中间代码过渡一下。尽管理论上是可以直接由源程序得到目标代码。
应用属性文法进行语义分析
先运算e，等于0的话，到了y；不等于0的话，到了x；
注意到上面??，\(p ~jump是一个一元运算符；e1~e2~p~jlt，是一个三元运算符；e~p~jez二元运算符\)
且第一个是绝对跳；后两个是条件跳
对后缀表达式做出更改，使得其可以跳转到别的位置;这样原来的后缀表达式是没有的。比如上面的：先判断e是否等于0，如果等于0的话，跳转到p1，否则顺序执行x，执行完之后强制跳转到p2。
用语法制导方式生成后缀表达式(逆波兰式)
逆波兰式比较适用于表达式类，但是其它类型语句效果就不一定好了
语法制导生成 三元式和树
三元式和我们的x86汇编语言很像。
还有另外一种三元式，是对上面的三元式表的一种优化
可以少算一回
树
语法制导产生树
语义方程
四元式
对三元式进行优化，除了三元式原来的三个量，多了每一步计算得出的量，称为中间临时变量，保存临时中间结果。原来的三元式就做不到使用中间变量。四元式也是使用比较多的一种中间表示。
要清楚上面的这些所有中间表示都是语义分析阶段的输出，我们目前的难点就是要通过这些中间表示反推 花括号中的语义方程。看看写入什么语义方程才可以得到上面的各种中间表示。
后面我们使用四元式还是比较多
怎么样通过语法分析得到上面的中间表示，具体地说是四元式
一、先看表达式与赋值语句怎么分析（翻译）？
设计语义动作(语义过程确实也比较难，需要大量practice\看看别人的样例)
一般套路：定义好语义值；再列写四元式
要是属性比较多的话，语义栈中就会是结构体。我们的示例比较简单，属性只有一个，所以并未使用结构体
ENTRY表示查找符号表 entry(i)表达为变量i的存储地址
自底向上归约
归约过程自动产生四元式表
终结符没有语义值；变量才有。所以对终结符只进行进入符号栈操作就行了，相应的语义栈会填入一个占位符。
每次归约的时候实际上都可以产生一个四元式，只不过根据语义动作，语义栈里的变量有的使用原来的语义值，有的gen()使用新的语义值，而我们通常写的时候只把有新变量的语义值写出来。
输入的符号如果是终结符，该符进符号栈，语义栈填充占位符；如果是非终结符，该符进语义栈，符号栈用终结符i占位。
表中有四元式的行，只是在归约过程中使用的是有gen语义动作的产生式。
上例中输入的是一个句型，输出的是一组四元式
对原来的语义方程进行添加语义值E.mode
布尔表达式到四元式的翻译(属于控制语句部分)
研究布尔表达式的目标是研究第二大类——控制语句的一部分工作
布尔式的翻译
真链、假链对应程序为真或者程序为假的情况下跳转
任何布尔表达式都有真转、假转两种去向。
翻译模式的方式：
控制语句的翻译，两种方法：
-
分段的方法
对文法进行修改
-
翻译模式
对文法进行修改，对$or ~and $的产生式，原来产生式中间插入M,
再给后面插入M的产生式
产生四元式的是下面这条emit = gen,标记方式不同
-
扫面完\(E_1\)之后，得到两个四元式 \((1)~(jnz,E_1,\_,?),~~~(2)(j,\_,\_,?)\) ;
-
然后扫描\(then\)，扫描完之后知道了上面？要跳去哪里，进行回填，\((1)~~(jnz,E_1,\_,3)\)这里知道了是跳到第3句上；
-
然后扫描完\(E_2\),得到了\((3)~~(jnz,E_2,\_,?)~~~(4)(j,\_,\_,?)\) 两条
-
然后扫描完\(then\)，扫描完之后知道了\((3)\) 要跳到哪里去，进行回填 ，\((5)~~(jnz,E_2,\_,5)\)
-
然后扫描S，执行\(S\);
-
然后扫描\(else\),得到一个产生式，并可以回填假出口
-
所有扫描完，可能还有没有回填的四元式，这时应该把所有没有回填的四元式成链后，关联到整个语句的开始符号S.chain，进行回填 (等待回填的内容)
扫描完then有语义动作，因此需要归约；扫描完else之后也有语义动作，因此也需要归约
可以说是把原来的if else断开了，如下所示
断开成3部分
改写之后的语义子程序
then扫描完知道回填(真出口)；
else 产生一 个新的四元式（直接跳类型的）+回填（假出口）
else扫描完知道了假出口，并且产生一个可以跳过s2的直接跳转指令，但是这个跳转指令在哪里，又不知道，保留一个链
- 扫描if;
- 扫描a,这是一个条件表达式，有真有假，因此得到了两条四元式\((1)(jnz,a,\_,0)~~~~~(2)(j,\_,\_,0)\)
- 扫描\(then\) ，扫描完它之后，发现可以归约，也就有了语义子程序，知道了真出口的位置 ,回填$(1)(jnz,a,_,3) $
- 扫描if
- 扫描b，这是一个条件表达式，又有两个新的四元式产生\((3)(jnz,b,\_,0)~~~~~~(4)(j,\_,\_,0)\)
- 扫描\(then\),进行归约，下一个四元式编号5，回填\((3)(jnz,b,\_,5)\)
- 扫描\(A:=2\) ,赋值表达式，得到一个四元式\((5)(:=,2,\_,A)\)
- 扫描else,先得到一个新的四元式\((6)(j,\_,\_,0)\),回填\((4)(j,\_,\_,7)\) 7是由于知道下一条四元式知道编号
- 扫描 \(A:=3\) ,得到一条四元式 \((7)(:=,3,\_,A)\)
- 扫描\(Else\),先得到四元式\((8)(j,\_,\_,0)\),再回填\((2)(j,\_,\_,9)\)
- 扫描\(if\)
- 扫描\(c\),这是一个条件表达式，得到两条新的四元式$(9)(jnz,c,_,0),~~~~(10)(j,_,_，0) $
- 扫描\(then\),回填真 ,\((9)(jnz,c,\_,11)\)
- 扫描\(A:=4\) ,得到一条四元式 \((11)(:=,4,\_,A)\)
- 扫描\(else\),先得到一条四元式\((12)(j,\_,\_,0)\),再进行回填\((8)(j,\_,\_6)\)
- 扫描\(A=5\),得到一条四元式 \((13)(=,5,\_,A)\)
发现确实有一些还没回填完毕，这些没有回填的语句观察发现都是指向程序段结束后，也就是(14)，然后通过拉链法，串成一串，序号从小到大，一直指向(14)
- 于是有\((12)回填14 ~~~~~ (10)回填12 ~~~~~~~ (6)回填0(头)\)
while语句实际上就是带有标号的 if语句。
while语句改写如上，旁边就是对应的四元式
- 扫描while 注意保留准备得到的第一个四元式的序号
- 扫描 E,扫描完产生两条四元式 \((1)(jnz,E,\_,?)~~~~~(2)(j,\_,\_,?)\)
- 扫描 \(do\),类似于\(then\)，进行回填真四元式链
- 扫描 \(S代码段\)；
- 扫描 \(;\) 之后必须紧接着进行跳转到标号，产生一条无条件跳转四元式\((p)(j,\_,\_,?)\) \(goto()回去\)
回填序号可以通过流程图看出来
不变部分 CONSPART，编译之前就可以求出来，提前求出来；
可变部分 VARPART, 和具体求取的元素角标有关，运行时求出来
内情向量表是符号表的一部分，如果符号是数组，就会有一个地址栏，里面会是 内情向量表的指针。 扫描过程中找到数组名，发现是数组，进而可以找到内情向量表的地址
内情向量表有 维数、上界、下界、每一维尺寸、类型、C、起始地址等量
可变数组，不会提前建立内情向量表，因为有好多量不知道，无法建立。因此只能申请一块内存，然后就不要管了，在这块内存上动态、自由的发挥！
基地址+变地址
数组变量赋值例子：
先读取数组，然后可以从数组的内情向量表中读取，首地址a,C = 21 ,\(d_2 = 20,m=1\).然后进行数组赋值\(X~:=A[i,j]\)生成四元式序列。
对于这个句子，逐词扫描：
根据题意，计算出C，type。再假设一个a
-
扫描X
-
扫描:=
-
扫描A
-
扫描[
-
扫描I, 这时可以根据产生式归约,但是没有四元式产生
-
扫描,
-
扫描J后，这时可以根据产生式归约，并且产生2条产生式\((1)(*,I,d,T_1) 计算I*d = T_1~~~~~~(2)(+,T_1,J,T_2)计算T_1+J=T_2\)
计算不变部分，当类型是非1字节类型时，会产生3条产生式
-
扫描], 这时可以根据产生式进行归约，并且得到一条产生式\((3)(-,a,C,T_3)\) 得到不变部分
-
然后不用扫描，但是需要两条产生式\((4)(=[],T_3[T_2],\_,T_4)结合不变和可变部分 进行赋值~~~~~(5)(：=，T_4,\_,X)再次进行赋值\)
\(-C = -l_1d_2-l_2,固定部分，我们只需要算i_1d_2+i_2\)
原文：https://www.cnblogs.com/fennleo/p/13363032.html