- 1、本文档共39页,可阅读全部内容。
- 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
- 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载。
- 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
查看更多
* * (2)逆波兰表示的特点 a.标识符(运算对象)出现的顺序(从左到右)和原有顺序相同。 b. 运算符是按实际计算顺序(从左到右)出现的。 c. 运算符紧跟在运算对象的后面出现,并且没有括号。 * * (3) 好处:易于对表达式的计算处理 对于一般表达式的计算,系统需要用两个工作栈分别处理运算对象和运算符。 对于逆波兰表示的表达式计算处理只用一个工作栈。 一般的计算过程是:自左至右扫描后缀式,每碰到运算量就把它推进栈。每碰到k目运算符就把它作用于栈顶的k个项,并用运算结果代替这k个项。 * * 例:逆波兰式ab+c*的计算处理过程 遇运算对象a,b入栈 扫描ab+c* b a 栈 遇二目运 算符+c* 取出a,b,运算结果T入栈 T c T 取出c,T作运算,设结果T1 T1 遇运算符* c* 遇运算对象c入栈 * * 2. 形成逆波兰表示 怎样将一般表达式转换成逆波兰表示? 基本思想:从左到右扫描表达式,每遇到: 1o 表达式中的运算对象则往左去。 2o 表达式中的运算符,则与运算符栈顶元素比较优先数: * * 逆波兰表示 表达式 运算对象 运算符 进栈 出栈 运算符栈 如果运算符栈顶元素的优先数大于或等于表达式中当前的运算符优先数,则栈顶元素退栈向左去。然后当前运算符继续与栈顶的新元素比较优先数。直到栈顶元素的优先数小于表达式中当前运算符为止。此时,才将表达式中当前运算符进栈。 * * 例:画出形成表达式a*(b+c/d)的逆波兰表示过程 a *(b+c/d)# # 步骤① a (b+c/d)# * # 步骤② a b+c/d)# ( * # 步骤③ ab +c/d)# ( * # 步骤④ ab c/d)# + ( * # 步骤⑤ abc /d)# + ( * # 步骤⑥ * * abc d)# / + ( * # 步骤⑦ abcd )# / + ( * # 步骤⑧ / + ( * # abcd/ )# 步骤⑨ + ( * # abcd/+ )# 步骤⑩ * # abcd/+* # 步骤 ⑾ * * 形成逆波兰表示的过程,实质上是表达式的翻译过程。(算法不难写出) 例:a/b/c+d = ab/c/d+ (a+b)*(c-d/e) = ab+cde/-* * * 数组POST存放后缀式:k为下标,初值为1 上述语义动作可实现为: 产生式 程序段 E→E(1)op E(2) {POST[k]:=op; k:=k+1} E→ (E(1)) {} E→i {POST[k]:=i; k:=k+1} 例:输入串a+b+c的分析和翻译 POST: 1 2 3 4 5 E→E(1)op E(2) E.code:= E(1).code || E(2).code ||op E→ (E(1)) E.code:= E(1).code E→id E.code:=id a b + c + … * * 7.1.2 图表示法 图表示法 DAG 抽象语法树 * * 7.1.2 图表示法 无循环有向图(Directed Acyclic Graph,简称DAG) 对表达式中的每个子表达式,DAG中都有一个结点 一个内部结点代表一个操作符,它的孩子代表操作数 在一个DAG中代表公共子表达式的结点具有多个父结点 * * a:=b*(-c)+b*(-c)的图表示法 assign a + * b uminus c DAG assign a + * b uminus c 抽象语法树 * b uminus c * * 抽象语法树对应的代码: T1:=-c T2:=b*T1 T3:=-c T4:=b*T3 T5:=T2+T4 a:=T5 assign a + * b uminus c 抽象语法树 * b uminus c * * DAG对应的代码: T1:=-c T2:=b*T1 T5:=T2+T2 a:=T5 assign a + * b uminus c DAG 抽象语法树对应的代码: T1:=-c T2:=b*T1 T3:=-c T4:=b*T3 T5:=T2+T4 a:=T5 * * 产生赋值语句抽象语法树的属性文法 产 生 式 语义规则 S→id:=E S.nptr:=mknode(‘assign’, mkleaf(id,id.place),E.nptr) E→E1+E2 E.nptr:=mknode(‘+’,E1.nptr,E2.nptr) E→E1*E2 E.nptr:=mknode(‘*’,E1.nptr,E2.nptr) E→-E1
文档评论(0)