复习：程序语言的语法描述 最左推导：任何一步o→B都是对α中的最 左非终结符进行替换。 最右推导：任何一步α→B都是对o中的最 右非终结符进行替换。 国防科技大学计算机系602教研室
国防科技大学计算机系602教研室 复习：程序语言的语法描述 ◼ 最左推导：任何一步 都是对中的最 左非终结符进行替换。 最右推导：任何一步 都是对中的最 右非终结符进行替换
复习：程序语言的语法描述 ■用一张图表示一个句型的推导，称为语法树。 E E→(E) E→(E) →(E+E) →(E+E) E →(E*E+E) →(E+i) →(i*E+E) →(E*E+i) →(i*i+E) →(E*i+i) 1 1 →(i*i+iD) →(i*i+i) 国防科技大学计算机系602教研室
国防科技大学计算机系602教研室 复习：程序语言的语法描述 ◼ 用一张图表示一个句型的推导,称为语法树。 E (E) (E+E) (E*E+E) (i*E+E) (i*i+E) (i*i+i) E (E) (E+E) (E+i) (E*E+i) (E*i+i) (i*i+i)
复习：程序语言的语法描述 ■定义：如果一个文法存在某个句子对应两 颗不同的语法树，则说这个文法是二义的。 ■ 语言的二义性：一个语言是二义性的，如 果对它不存在无二义性的文法。 国防科技大学计算机系602教研室
国防科技大学计算机系602教研室 复习：程序语言的语法描述 ◼ 定义：如果一个文法存在某个句子对应两 颗不同的语法树，则说这个文法是二义的。 ◼ 语言的二义性：一个语言是二义性的，如 果对它不存在无二义性的文法
复习：程序语言的语法描述 ■形式语言鸟瞰 ◆0型（短语文法，图灵机）： 产生式形如：Q→B 其中：∈(VUVW且至少含有一个非终结符；B∈ VOVN) ◆1型（上下文有关文法，线性界限自动机）： 产生式形如：→阝 其中：I侧≤βl,仅S→ε例外。 国防科技大学计算机系602教研室
国防科技大学计算机系602教研室 复习：程序语言的语法描述 ◼ 形式语言鸟瞰 0型(短语文法，图灵机)： 产生式形如： → 其中： (VT VN) *且至少含有一个非终结符； (VT VN) * 1型(上下文有关文法，线性界限自动机)： 产生式形如： → 其中：|| ||，仅 S→ 例外
复习：程序语言的语法描述 ■形式语言鸟瞰 ◆2型（上下文无关文法，非确定下推自动机）： 产生式形如：A→阝 其中：A∈VN;B∈VTUVN). ◆3型（正规文法，有限自动机）： 产生式形如：A→B或A→o 其中：∈Vr;A,B∈VN 产生式形如：A→B0或Ao 其中：o∈VT；A,B∈VN 国防科技大学计算机系602教研室
国防科技大学计算机系602教研室 复习：程序语言的语法描述 ◼ 形式语言鸟瞰 2型(上下文无关文法，非确定下推自动机)： 产生式形如： A → 其中：A VN； (VT VN) * 。 3型(正规文法，有限自动机)： 产生式形如：A → B 或 A → 其中： VT * ；A，BVN 产生式形如：A → B 或 A → 其中： VT * ；A，BVN