《07级编译原理期末复习.ppt》由会员分享，可在线阅读，更多相关《07级编译原理期末复习.ppt（33页珍藏版）》请在三一文库上搜索。
1、07级编译原理期末复习,一、概念,编译器；词法分析器；语法分析器；LEX；YACC； 代码生成器；编译系统； 单词（token）；属性（attribute）；符号表； 上下文无关文法（CFG）；语言；字符串；正则表达式；前缀；后缀；子串； 语法产生式；终结符；非终结符； 重写规则； 属性文法；继承属性；综合属性；语义规则；语义动作； 自顶向下分析（top-down）；自底向上分析（bottom-up）； DFA；NFA；LL；算符优先算法；SLR；LR；LALR； 状态转换表；语法分析表； 回溯；消除左递规；提取左因式；右递规； 最左推导；最右推导；规约；句型；句子（sentence）；句柄（
2、handle）；语法树； 移进-规约冲突；规约-规约冲突； 栈帧；栈指针；活动记录/帧；存储分配策略；函数参数传递； LR(0)项目集；LR(1)项目集；同心集； 中缀表示；后缀表示；前缀表示；三地址表示；RTL；,二、几个重要的关系,正则表达式语言； 语法语言； 正则表达式语法； LLSLRLRLALR； 中缀表示前、后缀表示； 最右推导句柄； 最左、最右推导语法分析；,三、算法,消除左递归和提取左公共因子； Thompson构造法； 子集构造法； 正则表达式直接构造DFA； 构造FIRST集合； 构造FOLLOW集合； 构造LL(1)语法分析表； 构造LR(0)项目集； 构造SLR(1)语
3、法分析表； 构造LR(1)项目集； 构造LR(1)/LALR(1)语法分析表； 构造属性文法（左递规，右递规，运算表达式，类型声明）； 构造语法制导翻译的语义动（包括自顶向下和自底向上）； 三地址表示的代码生成； 汇编表示的代码生成；,http:/ (1) -A*(B+C)(D-E) (2) (a*d+c)/d+e)*f+g (3) a+x4(Cd*3) (4) abc+d*ef,RECURSIVE,消除下列文法的左递归性。 （1）SSA SA ASB AB A(S) A( ) BS B (2) SAS Sb ASA Aa (3) S(T) Sa S TS TT,S,RE/LL,构造识别如下正
4、规语言的DFA： 01(0|1) *1 对于如下的文法，topdown语法分析。 Pbegin d; X end Xd;X XsY Y;sY Y,LL,验证下列文法是否为LL(1)文法。 (1)SABSCDa AabAc BdECeC CDfD DfEdE E (2) SaABbCDS AASdA BSAcBeC BCSf CCgC DaBDD,SLR,对于下列的文法，试分别构造它们的LR(0)项目集规范族及识别全部活前缀的DFA。 (1)SaSb SaSc Sab (2) ScA SccB AcA Aa BccB Bb (3) SaSSb SaSSS Sc (4)SA AAb Aa,SLR,
5、下列文法是否为SLR(1)文法?若是，构造相应的SLR(1)分析表，若不是，则阐明其理由。 (1) SSab SbR RS Ra (2)SaSAB SBA AaA AB Bb (3)SaSb SbSa Sab (4)SaA SbB AcAd A BcBdd B,LR/LALR,对于文法GS: SA ABA A BaB Bb (1) 构造LR(1)分析表； (2) 给出用LR(1)分析表对输入符号串abab的分析过程。,AR,下面文法给出是Pascal说明的文法，写出变量类型的一个属性文法。 decl -var-list: type var-list - var-list, id | id ty
6、pe -int | float,var-list2.in=var-list1.dtype var-list2.dtype=var-list2.in id.in=var-list1.dtype id.in = var-list.dtype,var-list2.dtype=var-list1.dtype id.dtype=var-list1.dtype,id.dtype = var-list.dtype,请按语法制导的定义，将后缀表达式翻译成中缀表达式。注意，不允许出现冗余括号，后续表达式的文法如下： E-EE+ E-EE* E-id,语法制导定义,假设变量的说明是由下列文法生成的： Di L L
7、,i L | :T Tinteger | real 1）建立一个语法制导定义，把每一个标志符的类型加在符号表中 2）为1）构造一个预翻译程序,1)type为综合属性，代表类型属性， 函数addtype实现向符号表中i对应项填类型信息。 语法制导定义,b) 采用递归下降分析法编写预翻译程序： Procedure D; begin if lookahead=id then begin match(id); D.type=L; addtype(id.entry,D.type) end else error end Function L: DataType; begin if lookahead=,
8、then begin match(,); if lookahead=id then begin match(id); L.Type=L; addtype(id.entry,L.type); return(L.type) end else error end,else if lookahead=: then begin match(:); L.Type=T; return(L.Type) end else error end Function T: DataType; begin if lookahead=integer then begin match(integer); return(int
9、eger) end else if lookahead=real then begin match(real); return(real) end else error end,下面文法产生的表达式是对整型和实型常数应用算符+形成的。当两个整数相加时,结果为整数，否则为实数。 E TR R + TR| Tnum.num | num a)给出语法制导定义确定每个子表达式的类型。 b) 把表达式翻译成前缀形式，并且决定类型。试用一元运算符inttoreal把整型值转换为相等的实型值，以使得前缀表达式中两个运算对象是同类型的。,a)设type是综合属性，代表各非终结符的“类型”属性 设in是继承属性， 翻译方案,b) 设属性s和i用于传递属性type，属性t和j用于传递属性val。 翻译方案,