文档详情

第五章—自下而上语法分析节9.ppt

发布:2018-07-07约4.62千字共25页下载文档
文本预览下载声明
第5章 自下而上语法分析 §5.1 引言 1. 任务 §5.2 规范归约分析法 “移进-规约”分析算法 ⑴ 栈中放入# ⑵ 重复执行以下步骤 1) 若栈顶的若干项形成句柄,则归约; 2) 若1)不成立,则移进; 3) 若在某一步,用 1)归约后,栈中内容为#S, 当前输入符号为#,则语法分析结束,是句子。 如果不能达到这种格局,则有语法错误。 * 5.1 引言 5.2 规范归约分析法 5.3 算符优先分析法 5.4 LR分析法介绍 判定一个单词符号串能否构成一个合法的语法单位。 即:给定一个串α,判定α是否是句子。 自下而上语法分析:从树的末端结点开始往上,向根结点方向构造语法树, 即寻找归约序列: α= αn-1 = αn-2 = … = α2 = α1 = S 归约序列:i+i*i =F+i*i =T+i*i =E+i*i 例:G[E]:E? E+T|T T?T*F|F F?i|(E) 符号串:i+i*i ⑺ ⑶ ⑻ ⑹ ⑸ ⑷ ⑵ ⑴ i + i * i F =E+F*i =E+T*i =E+T*F =E+T =E √ i + i * i F T i + i * i F T E i * i F T E F + i i * i F T E F + i T i * F T E F + i T F i i * F T E F + i T F i T i * F T E F + i T F i T E ⑺ ⑶ ⑻ ⑷ i + i * i F T E i * i F T E F + i i * F T E F + i T F i T E T + E F * T + E i * T + E *T + E T + E F + E i + E + E E T F i 归 归 归 进 进 归 归 进 进 归 归 归 进 归约序列: i+i*i=F+i*i =T+i*i=E+i*i =E+F*i=E+T*i =E+T*F=E+T =E ⑹ ⑸ ⑵ ⑴ i + i * i F T i + i * i F i * i F T E F + i T i * F T E F + i T F i i * F T E F + i T F i T E 如何识别可归约串 * 可归约串一定在栈顶 * 可归约串 ≠ 产生式右部 2.自下而上语法分析的主要问题 例:G1[E]:E→E+T|T T→T*F|F F→(E)|i 在E+T*i 处,若选E+T,得:E+T*i=E*i=E*F ? 若选T, 得:E+T*i=E+E*i=E+E*F ? 归约序列: i+i*i=F+i*i=T+i*i=E+i*i=E+F*i=E+T*i =E+T*F=E+T=E … T + E F + E i + E + E E T F i … 归 归 进 进 归 归 归 进 自下向上语法分析,根据可归约串的不同定义区分: 规范归约分析法:可归约串 — 句柄 算符优先分析法:可归约串 — 最左素短语 算符优先分析法 自下向上 规范归约分析法 语法分析方法 自上而下 预测分析法(LL(1)分析) 递归下降分析法 短语:令G[S]是一文法,αβδ是文法G的一个句型;如果有:S αAδ,且 A β; 则称β是句型αβδ相对于非终结符A的短语。 2.直接短语:令G[S]是一文法,αβδ是文法G的一个句型;如果有:S αAδ,且 A=β; 则称β是句型αβδ相对于非终结符A的直接短 语(也称简单短语)。 3.句柄:句型的最左直接短语称为该句型的句柄。 例:G[E]: E?E+T|T T?T*F|F F?(E)|i 符号串:T+i1*i2, 求:短语、直接短语、句柄 解:∵ 文法中没有 A?? 的产生式 ∴ 只找非空子串 有: T T+ T+i1 T+i1* T+i1*i2 + +i1 +i1* +i1*i2 i1 i1* i1*i2 * *i2 i2 短语条件: ⑴ αβδ是句型; ⑵ S αAδ; A β 对 β=T,α= ? δ= +i1*i2 找A,满足: E A +i1*i2 A T ∵ E = E+T = E+T*F = E+T*i = E+F*i =E+i*i 又∵ E=T ∴T是句型T+i1*i2相对于非终结符E的短语,并且是直接短语 短语条件: ⑴ αβδ是句型; ⑵ S αAδ;
显示全部
相似文档