1、第三讲 程序语言的语法描述作业： P36（ 6， 7， 8） 其中 6（ 2）做 01278（ 1）做 i+i*i1上下文无关文法语法范畴完全独立于这种范畴可能出现的环境1）文法与语言 文法上下文无关文法 G是一个四元式（ VT， VN， S， P）。 其中VT：非空 集，每个元素叫终结符VN： 非空有限集，每个元素称为非终结符S： 非终结符，叫做开始符号P： 产生式集（有限）， 形式为 P-, 其中 P VN, (VT VN)*注意 : 开始符 S至少必须在某个产生式的左部出现一次 . P- 1 P- 2 P- n 可以缩写为 P- 1 | 2 | | n 每个 i 也 叫 P 的一个侯选式
2、 . 讨论中多以大写字母表示非 终结符 语言上下文无关文法定义语言的办法 : 从文法的开始符出发 ,反复连续使用产生式 ,对非终结符实施替换和展开 .E.G. 文法 E-E+E |E*E | (E) | i (P28)据规则 : E -(E),我们说 : 从 “ E” 可以直接推出 “ (E)”, 记为 E=(E);对 “ (E)” 中 “ E” 再用 E-E+E 便有 : (E)=(E+E), 即 由 “ E” 可以推出 (E+E). 表示为 :E=(E)=(E+E)基本术语 (P29) 学员阅读直接推出推导可推导出1 =+ n1 =* n 文法的句型文法 G的句子全体形成它的语言 L(G)
3、= | S=* 且 VT*最左推导 (最右推导 )E=(E)=(E+E) = (E*E+E) = (i*E+E) = (i*i+E) = (i*i+i) 2) 语法树及二义性 语法树（ P31图 2.2,侯选式中自左至右的每个符号对应一个新结点)包含了最左、最右推导，但不含所有可能推导 E（ E ）E + E 文法的二义性 E * E ii i 文法的二义性文法二义性 若一文法中存在某个句子 ,它有两个不同的最左(最右 )推导 ,或者说一文法存在某个句子对应两棵不同的语法树 .例 : P31图 2.2, P32图 2.3 (i*i+i)语言的二义性 某语言由不同文法刻画两种二义性有何不同P28的表达式文法可以通过规定 *,+优先顺序 ,结合规则而构造一无二义的文法 .E - T | E+T 概念分层思想T - F | T*FF - (E) | i对 上下文无关文法的两点限制 文法中不含任何 P-P 形式的产生式 (会产生二义 ?) 每个非终结符都有用处即存在 S =* P , 则必有 VT*, 使得 P =* .3) 形式语言鸟瞰Chomsky 将文法分为四类 : 0, 1, 2, 30: 每个产生式 满足 : (VN VT)*且至少含一个非终结符 , 而 (VN VT)*.1: 每个产生式 满足 : | 0 2型 文法无法产生 anbncn| n0
