自顶向下语法分析方法讲述.ppt

T: procedure T; begin F; while char = * do begin READ(char); F end end E: procedure E; begin T; while char=+ do begin READ(char); T end end F: procedure F; begin if char =( then begin READ(char); E; if char≠ ) then ERROR else READ(char) end else P end E→T{+T} T→F{*F} F→P| (E) P→ i| i(E) P: procedure P begin if char ≠ i then ERROR else begin READ(char); if char =( then begin READ(char); E; if char≠ ) then ERROR else READ(char) end end end E→T{+T} T→F{*F} F→P| (E) P→ i| i(E) 5.5.2 预测分析方法（LL方法） LL(k)文法是采取确定的自左至右扫描（输入串）和自顶向下分析技术的最大一类文法。LL系指：自左向右扫描（输入串），自上而下进行最左推导。 一般来说，一个文法当其分析器对输入串进行自左至右扫描并采用自顶向下方法进行分析的过程中，如果每步仅利用当前的非终结符（事实上此时它已位于分析栈顶）和至多向前查看k个输入符号就能唯一 决定采取什么动作，那么这个文法称为LL(K)文法。 对于大多数程序设计语言而言。K=0或1就足够了。因此我们将主要讨论k≤1的情形。 一、LL(1)方法的分析过程 从实现的角度来说，上述替换过程需要花较多的时间，因为 它除了把一个候选式替换掉x1,还需要x2 … xn统统进行移位处理, 这时很麻烦的。我们的处理方法是用栈来保存x1x2 … xn,而且 是把xn作为栈底，x1作为栈顶，那么上述的替换动作就简单了， 只需在栈顶进行替换。即去掉x1把候选式的符号串按逆序方式 压入栈中即可。 设分析的当前格局为（x1x2 …. xn#, y1y2 …. ym#)，其中xi表示句型的后端部分，诸yj表示输入流的后端部分（终结符串）。则可能有下述动作之一： 1.替代：当x1∈VN时，则选相应的候选式去替换x1 。 2.匹配：当x1∈VT时，它与y1进行匹配，其结果为两种可能，如 果匹配成功，则去掉x1和y1（即只指针后移一位）否则报错。 3.接受：当格局为(#, #）时，报告分析成功结束。 关键 bBc# bbbdc# ↑ ↑ Bc# bbbdc# ↑ ↑ aBc# abbbdc# ↑ ↑ 例： 设有文法：S→aBc|bB B→bB|d  且给定输入串abbbdc，看其自顶向下的分析过程。 栈： 流： ? 替 S# abbbdc# ↑ ↑ ? 匹 ? 替 ? 匹 Bc# bbdc# ↑ ↑ ? 替 bBc# bb