编译原理与技术-GitHub.pptVIP

* 《编译原理与技术》讲义 * 若干基本概念 分析树与推导 文法G1推导句子i+i*i (最左)推导过程： 分析树 E ? E + E E E E + 圆圈内表示新构造的分析（子）树－即推导所用产生式 * 《编译原理与技术》讲义 * 若干基本概念 分析树与推导－句子i+i*i (最左)推导过程： 分析树 E ? E + E ? i + E E E E i + * 《编译原理与技术》讲义 * 若干基本概念 分析树与推导－句子i+i*i (最左)推导过程： 分析树 E ? E + E ? i + E ? i + E * E E E E i E E + * * 《编译原理与技术》讲义 * 若干基本概念 分析树与推导－句子i+i*i (最左)推导过程： 分析树 E ? E + E ? i + E ? i + E * E ? i + i * E E E E i E E i * + * 《编译原理与技术》讲义 * 若干基本概念 分析树与推导－句子i+i*i (最左)推导过程： 分析树 E ? E + E ? i + E ? i + E * E ? i + i * E ? i + i * i E E E i E E i i + * …1代结点 …2代结点 …3代结点 …4代结点 * 《编译原理与技术》讲义 * 若干基本概念 二义性文法 文法G是二义性文法，如果它的某个句子有两种不同的最左（或最右）推导；或有两棵不同的分析树。该句子称为文法G的二义性句子。 二义性语言 语言L是二义性的语言，如果不存在能产生它的非二义性的文法；或者能产生该语言的文法均为二义性文法。 * 《编译原理与技术》讲义 * 若干基本概念－ 二义性文法 e.g.8 文法G1是二义性文法。这是因为对于句子 i+i*i 有两种不同的最右推导。 推导1： E ? E + E ? E + E * E ? E + E * i ? E + i * i ? i + i * i 推导2： E ? E * E ? E * i ? E + E * i ? E + i * i? i + i * i * 《编译原理与技术》讲义 * 若干基本概念－ 二义性文法 e.g.9 文法G1是二义性文法。这是因为对于句子 i+i*i 有两棵不同的分析树。 E E E i E E i i + * E E i E E i i + * E i+i*i的一棵分析树 i+i*i的另一棵分析树 * 《编译原理与技术》讲义 * 若干基本概念－ 二义性文法 e.g.10 文法G1对于句子 i+i+i 有两棵不同的分析树。 E E E i E E i i + + E E i E E i i + + E i+i*i的一棵分析树 i+i*i的另一棵分析树 * 《编译原理与技术》讲义 * 若干基本概念－ 二义性文法 e.g.11 文法G2是非二义性文法。对于句子i+i*i有唯一的最左推导过程。（why?） 推导过程： E ? E + T ? T + T ? F + T ? i + T ? i + T * F ? i + F * F ? i + i * F ? i + i * i * 《编译原理与技术》讲义 * 若干基本概念－ 二义性文法 e.g.12 文法G2是非二义性文法。对于句子i+i*i有唯一的分析树。 E E T T F i i + * F T i F * 《编译原理与技术》讲义 * if－then－else 问题 e.g.13 文法G3如下： stmt ? if expr then stmt | if expr then stmt else stmt | others G3是二义性文法，因为对输入串， if E1 then if E2 then S1 else S2 有两棵不同的分析树（推导） * 《编译原理与技术》讲义 * stmt if expr then stmt E1 if expr then stmt E2 S1 else stmt S2 stmt if expr then stmt E1 if expr then stmt E2 S1 else stmt S2 * 《编译原理与技术》讲义 * if－then－else 问题 解决if-then-else的二义性 stmt ? matched | unmatched matched ? if expr then matched else matched