S?OPANYOPGAPS （操作符） S??
'''*' N10?{1,2,...,9}N10|?N10?{0,1,...,9}N10|? N10?{0,1,..,9}N10*N8?{0,1,...,7}N8|? N8?{0,1,..,9}N8 *N16?{0,1,...,7}N16|? N16?{0,1,..,9}N16
ANY?{任意字符}ANY|?GAP?{其他非空白符}
P?.|? E?E|e|? SX?X|x
OP?{操作符}OP|?
4) 实现方案
从上述文法可以很容易想到以GAP来作为间隔提取token，唯有操作符略有差异，由于操作符只有一元和二元操作符，故直接在提取token时遇到一个操作符便直接提取出来并确定其词法属性。在token提取出来后可以就可以根据各种词法属性的特征来判断其词法属性了，如8进制常量首位一定为0，字符常量最左最右端一定有?等。 5) 相关函数
int Analy(char *s)：分析token
void print(char *stack,int &StackNum)：输出stack中内容并清空stack void GetToken(char *s)：从s中提取token，并交给Analy()分析 int init()：将所有变量保存至var[]
2. 语法分析器
1) 文法
语法G[S]定义如下：
<程序> => main()<语句块> <语句块> => {<语句串>}
<语句串> => <语句> | <语句><语句串>
<语句> => <赋值语句> | <条件语句> | <循环语句> <赋值语句> => 标识符=<表达式>;
<条件语句> => if<条件><语句块> | if<条件><语句块>else <语句块> <循环语句> => do <语句块> while <条件>
<条件> => <表达式><关系运算符><表达式> | （<条件>） <表达式> => <项> | <项>+<表达式>| <项>-<表达式> <项> => <因子> | <因子>*<项> | <因子>/<项> <因子> => 变量|常量 2) 实现方案
可以轻松得到G[S]的NFA，然后可以通过递归下降分析法来实现语法分析器。 采用自上而下的递归下降分析法，从文法的开始符号出发，根据文法规则正向推导出给定句子。对文法中的每个非终结符编写一个函数 (或子程序), 每个函数（或子程序）的功能是识别由该非终结符所表示的语法成分。描述语言的文法常常是递
归定义的，因此相应的这组函数（或子程序）必然以相互递归的方式进行调用。
为每个非终结符编制一个递归下降分析函数，每个函数名是相应的非终结符，函数体则是根据规则右部符号串的结构和顺序编写，完成相应非终结符匹配，通过所有子程序的相互调用，完成整个终结符号串的分析。
(1) 当遇到终结符a时，则编写语句
if (当前读来的输入符号==a) 读下一个输入符号； (2) 当遇到非终结符A时，则编写语句调用 A( )； (3) 当遇到规则A→ε 时，则编写语句
if (当前读来的输入符号?FOLLOW(A))
error( )；
3) 相关函数：
int checkitem(int l,int r)：检测从l到r的字符串是否为<项>
int checkexp(int l,int r,char *arg)：检测从l到r的字符串是否为<表达式>
int checkcon(int l,int r,int *trow,int type)：检测从l到r的字符串是否为<条件> int checksen(int l,int type)：检测从l到r的字符串是否为<语句串> int checkblock(int l,int r)：检测从l到r的字符串是否为<语句块> int grammar(int start)：检测从start开始的字符串是否符合语法结构
3. 语义分析器和中间代码生成
1) 语义分析器的作用
语义分析即验证语法结构合法的程序是否真正有意义，若真的有意义则需要生成程序的某种中间代码的形式或直接生成目标代码。
本编译器在完成语义分析后会先生成中间代码（四元组），然后在对四元组进行优化。
2) 实现的理论方法
语义分析的总体思路采用语法制导翻译法，即为每个产生式都配备一个语义动作或语义子程序，在语法分析的过程中每档使用一条产生式进行推导或规约时，就执行相应产生式的语义动作，从而实验语义处理。在语法分析过程中，依随分析的过程，根据每个产生式所对应的语义子程序(或语义规则描述的语义处理的加工动作)进行翻译。
3) 实际处理
以上均为语义分析器的理论处理，实际处理中，由于递归下降法也给每个文法提供了一个函数，因此将语义分析器和中间代码生成都加入语法分析器中。即一边对语法进行分析，一边进行语义分析和中间代码的生成。在所有分析做完后，判断是否有错误，若没有则对中间代码
4) 中间代码的优化
这里对重复子元组进行优化。例如，对于(+,a,c,b)……(+,a,c,d)这一个四元组序列，若在(+,a,c,b)和(+,a,c,d)这两个四元组之间a和c的值没有发生改变，那么显然后面一组的加法运算时多余的，因此后一个四元组会被优化为(=,b,-,d)。
具体实现方法采用线性扫描的方式，借用三重循环来查找符合条件的四元组，时间复杂度为O(N^3)。这里实际上可以采用预处理的方法，首先预处理出两对元组间改变的变量名，然后再通过O(N^2)的扫描和O(1)的判断来实现，这样就将复杂度降为O(N^3)。 5) 相关函数
void gettemp(char *arg)：获取一个新的临时变量
void reltemp()：消除使用完毕的临时变量 void opt_tetrad()：中间代码的优化 void gettetrad(char *s)：中间代码生成
4. 目标代码的生成
本编译器的目标代码为X86汇编源代码，本编译器首先将中间代码转化为对应的目标代码，然后对目标代码进行一定程度的优化
1) 中间代码转化为目标代码
在得到中间代码（四元组）后，可以非常轻松的通过中间代码和目标代码的对应表来的得到对应的目标代码。
对应表如下，其中arg1,arg2,arg3均为变量名，而AX和BX为寄存器。
四元式 (=,arg1,-,arg2) (+,arg1,arg2,arg3) 目标代码 MOV AX,argv1 MOV argv2,AX MOV AX,argv1 MOV BX,argv2 ADD AX,BX MOV arg3,AX MOV AX,argv1 MOV BX,argv2 SUB AX,BX MOV arg3,AX MOV AX,argv1 MOV BX,argv2 IMUL AX,BX MOV arg3,AX MOV AX,argv1 CWD MOV BX,argv2 IDIV BX MOV arg3,AX MOV AX,argv1 MOV BX,argv2 CMP AX,BX J? label MOV AX,argv1 MOV BX,argv2 CMP AX,BX J? label (-,arg1,arg2,arg3) (*,arg1,arg2,arg3) (/,arg1,arg2,arg3) (j?,arg1,arg3,label) (jn?,arg1,arg3,label)
2) 目标代码的优化
首先明确目标代码优化的目的，C语言的翻译机制并不是解释型的翻译，因此我们可以通过增加编译时的时间来尽量减少生成的的目标代码的指令数。本编译器要做的目标代码优化做的工作就是这个内容。
(1) 当前翻译机制下的问题
这样得到的目标代码是非常粗糙的。有如下两个问题： 1 冗余翻译
比如a=b+c;对应的四元组为(+,b,c,k0),(=,k0,-,a)因此其对应翻译为： MOV AX,b MOV BX,c ADD AX,BX MOV k0,AX MOV AX,k0 MOV a,AX
很显然，代码中标红色的部分完全是冗余的，因为k0只是一个临时变量而已，没有其他任意意义，这里完全可以将标红色的这两句代码去掉，实际的执行效果相同。 优化后的代码为： MOV AX,b MOV BX,c ADD AX,BX MOV a,AX
2 无继承性的翻译
比如a=1; b=a;对应的四元组为(=,1,-,a),(=,k0,-,b)。其对应的目标代码为： MOV AX,1 MOV a,AX MOV AX,a MOV b,AX
代码中标红色的部分中MOV AX,a很显然是一个无继承性地的翻译，实际上上次寄存器AX的变更中内部的值就是a对应的值，因此AX的值可以通过继承上次AX中的值来进行下一次的运算，因此MOV AX,a这句话可以去掉，实际的执行效果相同。
优化后的代码为： MOV AX,1 MOV a,AX MOV b,AX
(2) 实现方法
1 冗余翻译
首先在当前的翻译机制下，每个四元组的第一个语句一定是MOV AX,arg1，同时这句话也是这个问题的始作俑者。因此这个问题可以在翻译一个四元组的开始判断当前四元组的arg1是否等于前一个四元组的arg3，且arg1是临时变量来决定是否要输出MOV AX,arg1。
而一个四元组若是最后要输出MOV arg3,AX，则判断当前四元组的arg3是否等于下一个四元组的arg1，且arg3是否为临时变量来决定是否要输出MOV arg3,AX。这样就可以很好的规避冗余翻译的问题 3 无继承的翻译
相关推荐：
loading