编译原理课件Chapter-4.pdf

第四章 语法分析 1. 语法分析的功能、基本任务 2. 自顶向下分析法 3. 自底向上分析法 11 4.1 语法分析概述 功能：根据文法规则，从源程序单词符号串中识别出语法 成分，并进行语法检查。 基本任务：识别符号串S是否为某语法成分。 两大类分析方法： 自顶向下分析 自底向上分析 22 自顶向下分析算法的基本思想为： + 若Z  S 则 S L(G[Z]) 否则S L(G[Z]) G[Z]  存在主要问题:  主要方法:  左递归问题 • 递归子程序法  回溯问题 • LL分析法 33 自底向上分析算法的基本思想为： + 若Z  S 则SL(G[Z]) 否则S L(G[Z]) G[Z] 存在主要问题: 主要方法: • 句柄的识别问题 • 算符优先分析法 • 若两个以上规则的右部有 • LR分析法 相同的符号串且构成句柄， 选哪个候选式？ 44 4.2 自顶向下分析 4.2.1 自顶向下分析的一般过程 给定符号串S，若预测它是某一语法成分，那么可根 据该语法成分的文法，设法为S构造一棵语法树。 若成功，则S最终被识别为某一语法成分。即 SL(G[Z]) 其中G[Z]为某语言成分的文法。 若不成功，则SL(G[Z]) 。 • 我们可以通过一例子来说明语法分析过程 55 2型文法！ 例 上下文无关文法 S = c a d G[ Z ]: 分析过程是设法建立一棵 Z ∷= c A d 语法树，使语法树的末端结点 A ∷= a b | a 与给定符号串相匹配。 求解 S L(G[Z]) ？ 1.开始：令Z为根结点。 Z · 2.用Z的右部符号串去匹配输入串