《编译原理6-4.2-4.3--自顶向下翻译-递归下降翻译ppt课件.ppt》由会员分享，可在线阅读，更多相关《编译原理6-4.2-4.3--自顶向下翻译-递归下降翻译ppt课件.ppt（17页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物6.4 L-6.4 L-属性文法和自顶向下翻译属性文法和自顶向下翻译 6.4.1 翻译模式翻译模式6.4.2 自顶向下翻译自顶向下翻译6.4.3 递归下降翻译器的设计递归下降翻译器的设计我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物6.4.2 自顶向下翻译自顶向下翻译l为了构造不带回溯的自顶向下语法分析，必为了构造不带回溯的自顶向下语法分析，必须消除文法中的左递归。须消除
2、文法中的左递归。l现在我们把前面讨论过的消除左递归的算法现在我们把前面讨论过的消除左递归的算法加以扩充，当消除一个翻译模式的基本文法加以扩充，当消除一个翻译模式的基本文法的左递归时同时考虑属性。的左递归时同时考虑属性。这种方法适合带这种方法适合带综合属性的翻译模式综合属性的翻译模式。这样，许多属性文法。这样，许多属性文法可以使用自顶向下分析来实现。可以使用自顶向下分析来实现。 我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物算术表达式的左递归文法相应的翻译模式算术表达式的左递归文法相应的翻译模式E E1+T
3、E. val := E1. val + T. val E E1-T E. val := E1. val - T. val E T E. val := T. val T (E)T. val := E. val T numT. val := num. val 图图6.13 带左递归的文法的翻译模式带左递归的文法的翻译模式我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物消除左递归，构造新的翻译模式消除左递归，构造新的翻译模式E T R.i := T.valRE. val := R.sR +TR1.i := R.i
4、 + T. valR1R.s := R1.sR TR1.i := R.i T. valR1R.s := R1.sR R.s := R.i T ( )T.val := E. val T numT. val := num. val图图6.14 消除左递归后的翻译模式消除左递归后的翻译模式我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物图图6.15 计算表达式计算表达式 9 5 + 2w 对于自顶向下分析，我们假定动作是在处于相同位对于自顶向下分析，我们假定动作是在处于相同位置上的符号置上的符号被展开被展开（匹配
5、成功）时执行的。（匹配成功）时执行的。 ET.val=9R.i=9num.val=9T.val=5R.i=4+T.val=2R.i=6 num.val=5num.val=2我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物l下面我们把转换左递归翻译模式的方法推广到一下面我们把转换左递归翻译模式的方法推广到一般，以便进行自顶向下分析。般，以便进行自顶向下分析。l假设我们有下面的翻译模式，它的每个文法符号假设我们有下面的翻译模式，它的每个文法符号都有一个综合属性，用小写字母表示，都有一个综合属性，用小写字母表示，
6、g和和f是任是任意函数。意函数。 A A1Y A.a：g(A1.a , Y.y) A X A.a：f(X.x) (6.1)我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物w 消除左递归，转换为如下文法消除左递归，转换为如下文法: A XRR YR | w 考虑语义动作，翻译模式变为考虑语义动作，翻译模式变为 A XR.i := f(X.x) RA.a := R.sR YR1.i := g(R.i , Y.y) R1 R.s := R1.sR R.s := R.i (6.2)(6.3)我吓了一跳，蝎子是多么丑
7、恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物XA.a := f( X.x)A.a := g(f( X.x), Y1.y)Y1A.a := g(g(f( X.x), Y1.y), Y2.y)Y2(a) 按按(6.1)自下而上计算自下而上计算A.aXR.i := f(X.x)Y1R.i := g(f(X.x),Y1.y)Y2R.i := g(g(f(X.x),Y1.y), Y2.y) R.sR.sR.s(b) 按按(6.3)自上而下计算自上而下计算图图6.16 计算属性值的两种方法计算属性值的两种方法我吓了一跳，蝎子是多么丑恶和恐
8、怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物l例例6.11 如果把构造抽象语法树的属性文法如果把构造抽象语法树的属性文法定义（见表定义（见表6.4)转化成翻译模式，那么关于转化成翻译模式，那么关于E的产生式和语义动作就变为：的产生式和语义动作就变为：EE1 + T E.nptr := mknode(+,E1.nptr, E2.nptr)EE1 - T E.nptr := mknode(-,E1.nptr, E2.nptr)ET E.nptr := T.nptr)T( E ) T.nptr := E.nptr Tnum T.nptr
9、:= mkleaf(NUM,num.val) Tid T.nptr := mkleaf(ID,id.entry) 我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物E T R.i := T.nptr R E.nptr := R.s R + T R1.i := mknode(+, R.i, T.nptr) R1 R.s := R1.s R - T R1.i := mknode(-, R.i, T.nptr) R1 R.s := R1.s R R.s := R.i /返回最终语法树返回最终语法树（其余不变，略）（
10、其余不变，略）删除左递归后：引入非终结符R图图6.17 构造抽象语法树的翻译模式构造抽象语法树的翻译模式我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物ET nptrT nptrid R-+T nptridnumididnum 4+ +- -to entry for ato entry for ci R s Ri 图图6.18 使用继承属性构造语法树使用继承属性构造语法树R.i 指向根结点指向根结点我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没
11、有错：表里边有一个活的生物6.4.3 6.4.3 递归下降翻译器的设计递归下降翻译器的设计 l对给定的适合于自顶向下翻译的翻译模式，下面对给定的适合于自顶向下翻译的翻译模式，下面给出设计递归下降翻译器的方法。给出设计递归下降翻译器的方法。l1.对每个非终结符对每个非终结符A构造一个构造一个函数函数过程，对过程，对A的每的每个继承属性设置一个形式参数，函数的返回值为个继承属性设置一个形式参数，函数的返回值为A的综合属性（作为记录，或指向记录的一个指的综合属性（作为记录，或指向记录的一个指针，记录中有若干域，每个属性对应一个域）。针，记录中有若干域，每个属性对应一个域）。为了简单，我们为了简单，我
12、们假设每个非终结只有一个综合属假设每个非终结只有一个综合属性性。A对应的函数过程中，为出现在对应的函数过程中，为出现在A的产生式的产生式中的每一个文法符号的中的每一个文法符号的每一个属性都设置一个局每一个属性都设置一个局部变量部变量。l2.非终结符非终结符A对应的函数过程中，根据当前的输对应的函数过程中，根据当前的输入符号决定使用哪个产生式候选。入符号决定使用哪个产生式候选。我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物l3.每个产生式对应的程序代码中，按照从左到右每个产生式对应的程序代码中，按照从左到右
13、的次序，对于单词符号（终结符）、非终结符和的次序，对于单词符号（终结符）、非终结符和语义动作分别作以下工作。语义动作分别作以下工作。o(1)对于带有综合属性对于带有综合属性x的终结符的终结符X，把把x的值存入的值存入为为X.x设置的变量中。然后产生一个匹配设置的变量中。然后产生一个匹配X的调用，的调用，并继续读入一个输入符号并继续读入一个输入符号advance。o(2)对于每个非终结符对于每个非终结符B，产生一个右边带有函数产生一个右边带有函数调用的赋值语句调用的赋值语句cB (b1，b2，bk），其中，其中，b1，bk是为是为B的继承属性设置的变量，的继承属性设置的变量，c是是为为B的综合属
14、性设置的变量。的综合属性设置的变量。o(3)对于语义动作，把动作的代码对于语义动作，把动作的代码抄进抄进分析器中，分析器中，用代表属性的变量来代替对属性的每一次引用。用代表属性的变量来代替对属性的每一次引用。o(4)函数结尾：函数结尾：return A的综合属性。的综合属性。我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物l例例6.12 图图6.17中的文法是中的文法是LL(1)的的,因此适因此适合于自顶向下分析。根据文法非终结符的合于自顶向下分析。根据文法非终结符的属性，得到关于非终结符属性，得到关于非终
15、结符E，R，T的函数的函数及其参数的类型，具体如下：及其参数的类型，具体如下： function E：AST-node； function R(in：AST-node)：AST-node； function T：AST-node； R.in : 继承属性作为继承属性作为R的参数的参数 我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物l把图把图6.17中的两个中的两个R产生式结合起来使翻产生式结合起来使翻译程序更小，新的产生式中用译程序更小，新的产生式中用addop代表代表+和和 -。 Raddop T R1
16、.i := mknode(addop.lexme， R.i，T.nptr） R1 R.s:=R1.s RR.s：R.i 我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物procedure R;beginif sym = addop then beginadvance; T; R endelse begin /* * 什么也不做什么也不做 * */ endend;图图6.19 产生式产生式R addop TR | 的分析过程的分析过程我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢
17、？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物function R (in : AST-node) : AST-node;var nptr , i1, s1, s : AST-node; addoplexeme : char;begin if sym = addop then begin /* 产生式 R addop T R */addoplexeme := lexval;advance;nptr := T; i1 := mknode(addoplexme, in , nptr) ; s1 := R (i1); s : = s1 endelse s := in; /* 产生式 R */return send;图图6.20 递归下降构造抽象语法树递归下降构造抽象语法树nptr: T.nptri1: R1.i s1: R1.ss : R.saddoplexeme: addop (+|-)