编译原理讲义 (第四章:语法分析 自顶向下分析技术) 南京大学计算机系 赵建华
编译原理讲义 (第四章:语法分析-- 自顶向下分析技术) 南京大学计算机系 赵建华
在词法分析完成之后,进入语法分析阶 段 ·语法分析阶段的任务是:检查程序的语 法是否正确,并生成内部中间表示形式 语法分析的 输入:属性字序列。 输出:程序的内部中间表示形式
引言 • 在词法分析完成之后，进入语法分析阶 段。 • 语法分析阶段的任务是：检查程序的语 法是否正确，并生成内部中间表示形式。 • 语法分析的 – 输入：属性字序列。 – 输出：程序的内部中间表示形式
自顶向下分析技术与识别算法 从推导的角度看,从识别符号出发,试 图推导出与输入符号串相同的符号串。 般来讲,构造出的推导是最左推导。 从语法树的角度看,从根节点,试图向 下一个语法树,其末端节点正好与输入 符号串相同
自顶向下分析技术与识别算法 • 从推导的角度看，从识别符号出发，试 图推导出与输入符号串相同的符号串。 一般来讲，构造出的推导是最左推导。 • 从语法树的角度看，从根节点，试图向 下一个语法树，其末端节点正好与输入 符号串相同
讨论前提 输入的是符号序列,不对符号构造情况 感兴趣。 语法分析的文法是上下文无关文法。 自顶向下分析技术的理论基础是定理2.7: 如果z:=X1X2.Xn且y为句子。那么如 果X1X2Xn→>y,必然存在y1y2…yn使 得X→>*y且
讨论前提 • 输入的是符号序列，不对符号构造情况 感兴趣。 • 语法分析的文法是上下文无关文法。 • 自顶向下分析技术的理论基础是定理2.7： 如果Z::=X1X2…Xn且y为句子。那么如 果X1X2…Xn=>y，必然存在y1 ,y2 ,…,yn使 得Xi=>*yi且y=y1y2… yn
要解决的基本问题 对于特定的终结符号,实用那个重写规 则来替换?
要解决的基本问题 • 对于特定的终结符号，实用那个重写规 则来替换？