级编译原理期末复习.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)语法分析表； 构造属性文法（左递规，右递规，运算表达式，类型声明）； 构造语法制导翻译的语义动（包括自顶向下和自底向上）； 三地址表示的代码生成； 汇编表示的代码生成； /jp2005/20/kcwz/stk /khxt/No5.htm# 将下列中缀式改写为逆波兰式。 (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 文法规则语义规则 declvar-list: typevar-list.dtype=type.dtype var-list1var-list2, id var-listid typeintegertype.dtype = integer typerealtype.dtype = real 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 语法制导定义 产产生式 语义规则语义规则 S-E print E.code E-E1E2+ E.code=E1.code|+|E2.code; E.op=+ E-E1E2* IF E1.op=+ AND E2.op=+ THEN E.code=“(“|E1.code|)|*|(|E2.code|); ELSE IF E1.op=+THEN E.code=“(“|E1.code|)|*|E2.code; ELSE IF E2.op=+THEN E.code=E1.code|*|(|E2.code|); ELSE E.code=E1.code|*|E2.code|; E一id E.code:=id.lexeme; 假设变量的说明是由下列文法生成的： Di L L,i L | :T Tinteger | real 1）建立一个语法制导定义，把每一个标志 符的类型加在符号表中 2）为1）构造一个预翻译程序 1)type为综合属性，代表类型属性， 函数addtype实现向符号表中i对应项填类型信息。 语法制导定义 产产生式 语义动语义动 作 Di L D.Type:=L.Type addtype(i.entry, D.type) L,i L1 L.Type:=L1.Type addtype(i.entry, L.type) L:T L.type:=T.type Tinteger T.type:=integer Treal T.type:=real 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) 把表达式翻译成前缀形式，并且决定类型。试 用一元运算符inttoreal把整型值转换为相等的实 型值，以使得前缀表达式中两个运算对象是同类 型的。 a)设type是综合属性，代表各非终结符的“类型”属性 设in是继承属性， 翻译方案 产产生式 语义规则语义规则 ET R R.in:=T.type E.Type:=R.s R+ T R1 IF (R.in=integer) and (T.type=integer) THEN R1.in:=integer ELSE R1.in :=real R.s:=R1.s R R.s:=R.in Tnum.num T.type:=real Tnum T.type:=integer b) 设属性s和i用于传递属性type，属性t和j用于传递属性val。 翻译方案 产产生式 语义规则语义规则 ET R R.i:=T.type R.j:=T.val E.Type:=R.s E.val:=R.t R+T R1 IF (R.i=integer) and (T.type=integer) THEN BEGIN R1.i:=integer Print(+,R.j,T.val) R1.j:=R.j+T.val END ELSE BEGIN R1.i :=real IF R.i=integer THEN Begin R.i:=real R.j:=inttoreal(R.j) End IF T.type=integer THEN Be