编译原理语义分析论文

1、2017届课程大作业编译原理大作业论文学生姓名 迪丽那孜 学 号 所属学院 信息工程学院 专 业 计算机科学与技术 班 级 计算机民17-1班 指导教师 史召峰 教师职称 讲 师 目录摘要11LL(1)文法12处理过程23求LL（1）分析表24.递归下降分析法25.综述35.1. SLR(1)文法35.2. LR(1)文法35.3. LALR(1) 文法35.4概述45.5过程46.语言文法的形式化描述（BNF范式）47.语义规则（属性文法）58.运行环境介绍69.关键算法的流程图及文字解释71、本编译器的总框架72、在语义分析中的主要函数介绍73、产生布尔表达式84、While-do语句的语

2、义分析95、词法、语法和语义分析的衔接910.测试报告（测试用例，测试结果）911.附录13摘要语法分析是编译程序的核心部分，其任务是检查词法分析器输出的单词序列是否构成源语言中的句子，亦即是否符合源语言的语法规则。本文从自上而下和自下而上两种角度论述了几种语法分析方法的优劣和各自试用的文法。关键词编译；语法分析；文法；语法分析概述语法分析的任务是检查词法分析器输出的单词序列是否构成源语言中的句子，亦即是否符合源语言的语法规则。分析方法进行语法分析主要有两种：自顶向下的分析方法和自底向上的分析方法。本文讨论基于以上两种分析方式的五种文法：LL(1)，LR(1)，SLR(1)，LALR(1)以及

3、算符优先文法。这五种文法各有其特点与适用范围，很难确切的说孰优孰劣。1LL(1)文法概述LL(1)语法分析属于自顶向下的语法分析。所谓自顶向下的语法分析，就是对给定的输入单词序列w，试图自顶向下的为其建立一棵语法分析树。或者说从文法德开始符号出发，试图寻找w的一种最左推导。这种分析过程实质上是一种试探过程，而且对文法的限制比较多，可能会导致分析效率极低甚至失败。具体的有预测分析法和递归下降分析法。对文法的限制但是无论哪种方法，在分析过程中都可能会遇到一些共同的问题：1 二义性问题;2 回溯问题;3 左递归引起的无穷推导问题。所以说，自顶向下的语法分析方法并不能处理所有的文法，有时为了适应所选择

4、的分析方法，常常需要对原始文法进行改造，包括如下3步：1消除二义性。这一步只能是人工手动的修改文法。2消除左递归。这一步可以由程序来处理。假设有n个语法变量，那么这一步的时间复杂度是O（ ）。3提取左公因子。这一步也主要有人工手动处理。经过这三步处理后的文法，便可以使用预测分析法或者递归下降分析法来进行语法分析了。2处理过程在接下来的处理中，两种方法都需要进行三步预处理，即：1 求出单个文法符号X和文法符号串的FIRST集；3求LL（1）分析表对于求单个文法符号X的时间复杂度，假设文法符号的个数为n，非终结符个数为m，由于循环的次数与嵌套的层数和计算的顺序有极大的关联，最坏情况要循环O（n）次

5、，为方便计算，再根据实际情况假设每个产生式右部的文法符号个数为10，所以，求单个文法符号X的时间复杂度为O（10*n*m）= O(mn),而对于符号串，假设它包含k个符号，则计算它的时间复杂度为O（mnk），求出了FIR求FOLLOW集，易知求FOLLOW集的时间复杂度也为O（mn）。接下来，还需要求出LL（1）分析表，分析表是一个二维数组MA,a,A是语ST集采能法变量，a是输入符号或#。也可以在O（mn）的时间内求出，两种方法其实都用到了预测LL（1）分析表，只不过使用的方法不太一样。2.1.4 预测分析法对于预测分析法，它采用表驱动的方式来实现，它具有一个输入缓冲区、一个分析栈、一张LL

6、（1）分析表和一个输出流。输入缓冲区中包含待分析的串和结束符#。分析栈用来存放文法符号序列，栈底符号是#。初始时，栈中只有文法开始符号及其下的#。整个分析过程在于从文法开始符号开始，试图构造输入缓冲区中待分析串的最左推导。假设某程序共有符号s个，整个控制程序的时间复杂度为O（s）。4.递归下降分析法而对于递归下降分析法，是指根据各个候选式的结构，为文法的每个语法变量编写一个处理子程序，用来识别该语法变量所代表的语法成分。设有产生式AX1X2X3XkXn，则与A对应的处理子程序遇到的Xk是终结符时直接进行匹配，而遇到Xk是语法变量时就调用与Xk对应的处理子程序。由于产生式中的语法变量可能是递归定

7、义的，所以这种实现方法要求处理子程序可以递归调用。另外，这种分析方法也是寻求输入串的一个推导过程，所以称为递归下降分析法。实际上，上面所说的预测分析法是一种特殊的递归下降分析法，它是通过显示地维护一个状态栈而不是通过隐式的递归来实现的。如果编译程序的实现语言允许进行过程的递归调用，则可以采用一般形式的递归下降分析法。这种方法的主要优点是易于实现。此外，由于分析器和文法的紧密对应性，这种方法还易于保证语法分析器的正确性。其缺点是频繁的递归调用会降低分析器的效率，而且与预测分析法相比，这种分析器的代码规模非常大。尽管如此，递归子程序法仍然是一种有效的语法分析方法，因为在实际应用中，递5.综述总之，

8、自顶向下分析法只能处理上下文无关文法的一些子类，对于文法的限制也比较多，而且其中许多部分必须人工手动完成，比较难以实现自动化，与之相反的是自底向上的LR分析法，基于LR分析法的良好形式和理论基础，人们可以寻求这种方法的进一步自动化，于是就有了Yacc之类的语法分析程序自动生成工具。5.1. SLR(1)文法SLR(1)语法分析属于自底向上的语法分析。自底向上的语法分析的思想就是从输入串出发，反复利用产生式进行归约，如果最后能得到文法的开始符号，则输入串是句子，否则输入串有语法错误。核心是寻找句型中的当前归约对象“句柄”进行归约,用不同的方法寻找句柄，就可获得不同的分析方法。和自顶向下文法类似，

9、每种自底向上文法也是有局限性的。比如LR（0）文法。上下文无关文法不是都能用LR(0)方法进行分析的，也就是说，CFG不总是LR(0)文法。当文法分析过程中会出现归约归约冲突和移进-规约冲突时，此文法就不是LR（0）文法。 下面写一下对几种自底向上文法的比较。LR(1)总体来说，就是从左到右扫描输入符号。最右推导对应的最左归约，超前读入1个符号，以便确定归约用的产生式。 为解决LR（0）中的冲突，SLR分析法引入了每个符号的FOLLOW集，SLR(1)分析方法描述能力强于 LL(1) ，SLR(1)还考虑FOLLOW集中的符号，LL(1) 仅考虑产生式的首符号。SLR(1) 文法是在LR（0）

10、分析表的基础上增加了FOLLOW集，可以解决一部分冲突，但是，SLR文法依然有解决不了的问题。SLR（1）只孤立地考察输入符号是否属于归约项目A.相关联的集合FOLLOW（A），而没有考察符号串所在规范句型的“上下文”。即未考虑规约的有效性，即只考虑了FOLLOW集是否符合规约条件，而没有考虑输入串中后面的字符。5.2. LR(1)文法LR(1)语法分析属于自底向上的语法分析。LR(1)文法可以说比SLR又强大了一些。因为LR（1）在构造状态时就考虑follow集，而不是在规约时考虑。与LR（0）文法类似，识别文法全部活前缀的DFA的每一状态也是用一个LR（1）项目集来表示，为保证分析时，每一

11、步都在栈中得到规范句型的活前缀，应使每一个LR（1）项目集仅由若干个对相应活前缀有效的项目组成。但是文法的强大也会带来一些代价，LR（1）分析表相比起LR（0）和SLR（1）庞大许多，相对来说也会有比较大的运行开销。5.3. LALR(1) 文法LALR(1)语法分析属于自底向上的语法分析。LALR（1）是对LR（1）状态的简化，不同的LR(1)项目闭包可能有相同的LR(0)项目，但后继符可能不同，我们称这种情况为两个闭包同心，将两个同心闭包合并，即是LALR（1）文法。它的显著好处就是减少了状态的数量，缩减了分析表，但是合并后可能带来归约归约冲突。合并那些不会带来冲突的同心的LR(1)闭包/

12、状态，可以得到LALR（1）分析表，反之，如果合并会出现规约-规约冲突，那么不能使用LALR（1）分析法，换句话说，存在合并后规约规约冲突的文法不是LALR（1）文法。分析能力LALR（1）强于SLR（1），因为合并后的后继符仍然是FOLLOW集的子集，弱于LR（1），因为有上述局限性。2.5 算符优先文法5.4概述算符优先分析法是一种简单适用的方法，用这种方法分析程序设计语言中的各类表达式尤为有效。由于这种方法简单直观，它还特别适用于手工方式来实现。所谓算符优先分析就是将句型中的终结符当做算符，然后定义算符之间的某种优先关系，利用这种优先关系来寻找句柄并进行规约，也是一种自下而上的分析方法。

13、5.5过程首先要构造FIRSTOP集合和LASTOP集合，构造过程中分别使用了一个|V|*|T|大小的二维布尔数组来表示某个终结符b是否在B的FIRSTOP集合或LASTOP集合中，又使用了一个栈来帮助计算其他非终结符的这两个集合。算法的时间复杂度主要主产生式的个数有关，设产生式个数为p，则该算法时间复杂度为O（）6.语言文法的形式化描述（BNF范式） 程序开始P-program i;SDn SC;定义语句SDn-SDSDn|nullSD-var int iSDTSDT - null|,iSDT复合语句SC-begin Sn endSn-S;Sn|null单个语句S-SD|SA|SIF|SW|

14、SC赋值语句SA-i:=E算术表达式E-cET|iET|(E)ETET-AE|CE|DE|null;C-+|-|*|/;布尔表达式B-EAEBT|NOT B|(B)BT BT-DB|nullA-|=|=|D-AND|ORif语句SIF-if B then S SELSESELSE-null|else S2while语句SW-while B do S7.语义规则（属性文法）产生式语 义 规 则i:=E Gen(:=, E.PLACE , ，entry(i) EE1+E2 E.PLACE = Newtemp; Gen(+ , E1.PLACE, E2.PLACE , E.PLACE ) EE1*E

15、2 E.PLACE = Newtemp; Gen(* , E1.PLACE, E2.PLACE , E.PLACE ) E E1 E.PLACE = Newtemp; Gen( , E1.PLACE, , E.PLACE ) E (E1) E.PLACE = E1.PLACE Ei E.PLACE = Entry(i) 产生式语 义 规 则Ei E.truelist:=makelist(nextquad); E.falselist:=makelist(nextquad+1); Gen( jnz，entry(i)， ，0 )； Gen( j ， ， ，0 ) Ei1 R i2 E.truelis

16、t:=makelist(nextquad); E.falselist:=makelist(nextquad+1); Gen( jR，entry(i1)，entry(i2)，0 )； Gen( j ， ， ，0 ) E E1 E.truelist:= E1.falselist ; E.falselist:= E1.truelist ; E ( E1 ) E.truelist:= E1.truelist ; E.falselist:= E1.falselist ; M M.quad := nextquad ; EE1ME2 backpatch(E1.truelist, M.quad ); E.tr

17、uelist:=E2.truelist; E.falselist:=merge(E1.falselist,E2. Falselist)EE1ME2 backpatch(E1. falselist, M.quad ); E.truelist:= merge(E1. truelist, E2. truelist); E.falselist:= E2. Falselist EE1ME2backpatch(E1.truelist, M.quad );E.truelist:= E2.truelist;E.falselist:=merge(E1.falselist, E2.Falselist) 产生式语

18、义 规 则Sif E then M S1 backpatch(E.truelist, M.quad );S.nextlist:=merge(E.falselist, S1.nextlist) M M.quad := nextquad ; N N.nextlist:=makelist(nextquad);Gen( j , , , 0 ) Sif E then M1 S1 N else M2 S2 backpatch(E.truelist, M1.quad );backpatch(E.falselist, M2.quad );S.nextlist:=merge(S1.nextlist, N.nex

19、tlist, S2.nextlist) Swhile M1 E do M2 S1 backpatch(S1.nextlist, M1.quad ); Gen( j , , , M1.quad ); backpatch(E.truelist, M2.quad ); S.nextlist:= E.falselist S begin L end S.nextlist:=L.nextlist S A S.nextlist:= makelist() /*空链*/ L S L.nextlist:=S.nextlist LL1； M S backpatch(L1.nextlist, M.quad );L.n

20、extlist:=S.nextlist 8.运行环境介绍运行环境是DEVC+Dev-C+是一个C&C+开发工具，它是一款自由软件，遵守GPL协议。它集合了GCC、MinGW32等众多自由软件，并且可以取得最新版本的各种工具支持，而这一切工作都是来自全球的狂热者所做的工作，并且你拥有对这一切工具自由使用的权利，包括取得源代码等，前提是你也必须遵守GNU协议。Dev-C+每一天都在进步着，因为它是一个自由软件。 Dev-C+是一个非常实用的编程软件，多款著名软件均由它编写而成，它在C的基础上，增强了逻辑性9.关键算法的流程图及文字解释1、本编译器的总框架词法分析词法三元式语法分析语义分析四元式2、

21、在语义分析中的主要函数介绍Backpatch(int list,int quad)代码：void backpatch(int list,int patch) int tmp; while(list) tmp = list; list = RSStmp.jump; RSStmp.jump = patch; 改写目标链中四元式中第四项的值若该值不为0则循环处理该值指向的四元式直到其为零Merge (int list1,int list2)代码：int merge(int list1, int list2) int tmp = list2; if(list2=0)list2 = list1; els

22、e while(RSStmp.jump) tmp = RSStmp.jump; RSStmp.jump = list1; return list2;若list2为0，则返回list1的值若list2不为0则将链list1接到list2末尾，返回list2的值3、产生布尔表达式对第一个表达式规约记录操作符对第二个表达式进行规约根据相应语义动作进行整体规约进行相应的backpatch和merge操作4、While-do语句的语义分析根据词法分析的词法三元式判断while关键字判断While关键字根据布尔表达式规则处理布尔表达式，并产生相应的四元式2布尔表达式规约根据词法分析的词法三元式判断do关键

23、字3判断do关键字对while-do语句中的要执行的语句进行规约并产生四元式4处理要执行的语句while-do语句规约进行backpatch(S1.nextlist, M1.quad ); Gen( j , , , M1.quad ); backpatch(E.truelist, M2.quad ); S.nextlist:= E.falselist5进行整体语句规约5、词法、语法和语义分析的衔接1、词法分析是分析输入代码产生词法三元式的程序。读入代码，并将代码中的单词分解成词法三元式。2、语法分析读入词法三元式，并根据词法三元式对句子进行语法分析。3、语义分析嵌入在语法分析中。根据语法分析中

24、得到的句子类型和语义四元式产生规则，产生四元式10.测试报告（测试用例，测试结果）测试用例输入程序（文件input.txt）：program example;var int j,m,n; begin /*there is a comment*/ j:=6; m:=3; /there is a comment n:=j+m; if n=3 and n10 then j:=j*4; while a=,8)(16,3,8)(12,and,8)(15,n,8)(23,10)(16,10,10)(7,then,10)(15,j,10)(26,:=,10)(15,j,10)(28,*,10)(16,4,1

25、0)(24,;,10)(10,while,11)(15,a,11)(23,=,n,3,106)105(j,-,-,111)106(j,n,10,113)112(j,-,-,115)113(*,j,4,T3)114(:=,T3,-,j)115(j:22, :23,;:24,:25,:=:26,:27, *:28,/:29,.:30,=:32,:33 def isLetter(): global ch if ch=None: return False else: return ch.isalpha()def isDigit(): global ch if ch=None: return False

26、 else: return ch.isdigit()def concat(): global code global ch code = code+chdef getchar(l,i): if len(l)=i or i0: return None else: return lidef getstr():global codeglobal key_wordsglobal lltype = 0state = Nonestr = ;if code=None:str = u(0,+code+,%d)%llelif code in key_words:if(key_wordscode=25):str

27、= error code in line %dn%llstr = str + error code :else:str= u(+key_wordscode+u,+code+,%d)%llelif code.isdigit():str= (16,+code+,%d)%llelse:str= (15,+code+,%d)%llreturn strll = 0flag = ;if _name_=_main_: src = rinput.txt outfile = routput.txt if not os.path.exists(src): print cannot open file,src el

28、se:inputf = open(src,r)outputf = open(outfile,w)annotation = 0ll = 0for line in inputf:ll=ll+1i = 0l = len(line)while i=len(line):breakcode = ch = getchar(line,i)i = i+1if annotation=1:if ch=* and getchar(line,i)!=None and getchar(line,i)=/:str = annotation end in line %dn%lloutputf.write(str)annota

29、tion = 0i=i+1continueif ch=/ and getchar(line,i)!=None and getchar(line,i)=/:outputf.write(line annotation in line %dn%ll)i = i+1breakif ch=None:breakelif ch=/ and getchar(line,i)!=None and getchar(line,i)=*:str = annotation start in line %dn%lloutputf.write(str)i=i+1annotation = 1elif ch= or ch=n o

30、r ch=t:continueelif isLetter():while isLetter() or isDigit():concat()ch = getchar(line,i)i=i+1i=i-1str = getstr()str = str+noutputf.write(str)continueelif isDigit():while isDigit():concat()ch = getchar(line,i)i=i+1i=i-1str = getstr()str = str+noutputf.write(str)continueelif ch in key_words:concat()c

31、h = getchar(line,i)i=i+1if ch!=None and (code+ch) in key_words:concat()str = getstr()str = str+noutputf.write(str)else:i=i-1str = getstr()str = str+noutputf.write(str)else:str = error in line %dn%lloutputf.write(str)outputf.write(error code +ch+n);*资源文件（resource.h）*#ifndef RESOURCE_H_ZEADOM#define R

32、ESOURCE_H_ZEADOM#define $program 1#define $begin 2#define $end 3#define $var 4#define $integer 5#define $if 6#define $then 7#define $else 8#define $do 9#define $while 10#define $int 11#define $and 12#define $or 13#define $not 14#define $flag 15#define $num 16#define $add 17#define $sub 18#define $le

33、ft 19#define $right 20#define $eq 21#define $gt 22#define $lt 23#define $ 24#define $copy 26#define $comma 27#define $mul 28#define $div 29#define $point 30#define $loe 31#define $goe 32#define $ne 33#endif*语义分析头文件（semantic.h）*#ifndef ZEADOM_SEMANTIC_H#define ZEADOM_SEMANTIC_H#include stringusing na

34、mespace std;#includeiostream#include fstream#include sstreamint quad,varT;int Nextquad() return quad+;string NextT() varT+; string temp = T; stringstream ss; ssvarT; temp = temp+ ss.str(); return temp;void semantic_init() varT=0; quad=100;struct siyuanshi string op,par1,par2,result; bool hasop,haspa

35、r1,haspar2,hasresult; bool isjump; int jump; siyuanshi() op = par1 = par2 = result = ; hasop = haspar1 = haspar2 = hasresult = false; jump = 0; isjump=false; void setop(string arg) op = arg; hasop = true; void setpar1(string arg) par1 = arg; haspar1 = true; void setpar2(string arg) par2 = arg; haspa

36、r2 = true; void setresult(string arg) result = arg; hasresult = true; void setjump(int arg) jump = arg; isjump = true; void output(ofstream &s) s (op,; if(haspar1) spar1,; else s-,; if(haspar2) spar2,; else s-,; if(isjump) sjump)endl; else if(hasresult) sresult)endl; else s-)endl; ;siyuanshi RSS1000

37、0;struct Estruct string lexval; Estruct()lexval=;struct Bstruct int truelist; int falselist; Bstruct()truelist=falselist=0;struct Mstruct int quad; Mstruct()quad=0;void backpatch(int list,int patch) int tmp; while(list) tmp = list; list = RSStmp.jump; RSStmp.jump = patch; int merge(int list1, int li

38、st2) int tmp = list2; if(list2=0)list2 = list1; else while(RSStmp.jump) tmp = RSStmp.jump; RSStmp.jump = list1; return list2;void semantic_output() ofstream out(Semantic.out); for(int i=100;iquad;i+) outi; RSSi.output(out); out.close();struct Sstruct int nextlist; Sstruct()nextlist=0;struct Nstruct

39、int nextlist; Nstruct()nextlist=0;#endif*语法和语义分析程序（main.cpp）*#include iostreamusing namespace std;#include string.h#include string#include stdlib.h#include stdio.h#include resource.h#include semantic.h#define deal(s) if(!(s)return false;#define pdeal(s) if(!(s)cout没有找到文件结尾（程序是否未完成？）line; if(!cin)cin.clear();normal = false;return false; while(line0!=() cinline; att=; int i,j=0; int l = line.length(); i=3; if(line2=0&line2=9) type = (line1-0)*10+(line2-0); i=4; else type = line1-0; for(;linei!=,;i+) att