级编译原理期末复习.ppt

07级编译原理期末复习,一、概念,编译器；词法分析器；语法分析器；LEX；YACC； 代码生成器；编译系统； 单词（token）；属性（attribute）；符号表； 上下文无关文法（CFG）；语言；字符串；正则表达式；前缀；后缀；子串； 语法产生式；终结符；非终结符； 重写规则； 属性文法；继承属性；综合属性；语义规则；语义动作； 自顶向下分析（top-down）；自底向上分析（bottom-up）； DFA；NFA；LL；算符优先算法；SLR；LR；LALR； 状态转换表；语法分析表； 回溯；消除左递规；提取左因式；右递规； 最左推导；最右推导；规约；句型；句子（sentence）；句柄（handle）；语法树； 移进-规约冲突；规约-规约冲突； 栈帧；栈指针；活动记录/帧；存储分配策略；函数参数传递； LR(0)项目集；LR(1)项目集；同心集； 中缀表示；后缀表示；前缀表示；三地址表示；RTL；,二、几个重要的关系,正则表达式语言； 语法语言； 正则表达式语法； LLSLRLRLALR； 中缀表示前、后缀表示； 最右推导句柄； 最左、最右推导语法分析；,三、算法,消除左递归和提取左公共因子； Thompson构造法； 子集构造法； 正则表达式直接构造DFA； 构造FIRST集合； 构造FOLLOW集合； 构造LL(1)语法分析表； 构造LR(0)项目集； 构造SLR(1)语法分析表； 构造LR(1)项目集； 构造LR(1)/LALR(1)语法分析表； 构造属性文法（左递规，右递规，运算表达式，类型声明）； 构造语法制导翻译的语义动（包括自顶向下和自底向上）； 三地址表示的代码生成； 汇编表示的代码生成；,将下列中缀式改写为逆波兰式。 (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,构造识别如下正规语言的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,下列文法是否为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 type -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,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=, 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(integer) end else if lookahead=real then begin match(real); return(real) end else error end,下面文法产生的表达式是对整型和实型常数应用算符+形成的。当两个整数相加时,结果为整数，否则为实数。 E TR R + TR| Tnum.num | num a)给出语法制导定义确定每个子表达式的类型。 b) 把表达式翻译成前缀形式，并且决定类型