PPT《*》

归约过程看成这一步最右推导的逆过程. * 《编译原理与技术》讲义 * 若干基本概念 分析树分析树看成是(句型)推导的图形表示;

反之,(句型)推导可理解为分析树的线形表示.分析树所有结点v(内部结点和叶子结点)由文法符号或?标记,即v∈ (VT∪VN∪{?} );

根结点由文法开始符号S标记;

内部结点A ∈ VN,其所有子结点从左往右排列构成以A为左部的某产生式的右部 * 《编译原理与技术》讲义 * 若干基本概念 分析树与推导文法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 * 《编译原理与技术........