第三章语法分析.pptVIP

计算机科学与工程系 先看一个例子：“我是大学生”，它的语法结构可以由以下规则描述（用→表示“由…组成” 或“定义为”）： 句子 → 主语谓语 主语 → 代词 | 名词 代词 → 我 | 你 | 他 名词 → 王明 | 大学生 | 工人 | 英语 谓语 → 动词直接宾语 动词 → 是 | 学习 直接宾语 → 代词 | 名词 “我是大学生”的构成符合上述规则，而“我大学生是”不符合上述规则，我们说它不是句子。这些规则成为我们判别句子结构和法与否的依据，换句话说，这些规则看成是一种元语言，用它描述汉语。这样的语言描述称为文法。 一旦有了一组规则以后，可以按照如下方式用它们去推导或产生句子。 句子 ? 主语 谓语 ? 代词 谓语 ? 我谓语 ? 我动词 直接宾语 ?我是 直接宾语 ?我是 名词 ?我是大学生 显然，按照上述办法，不仅生成“我是大学生”，还可以生成： “王明是大学生” “王明学习英语” “我学习英语” “你学习英语” “他是工人” “你学习王明” 等几十个句子。 事实上，使用文法作为工具，不仅为了严格地定义句子的结构，也是为了用适当条数的规则把语言的全部句子描述出来，可以说文法是以有穷的集合刻画无穷的集合的一个工具。 定义1：文法G定义为四元组 (VT，VN，S，ξ)，其中： (1) VT为终结符号集，这是一个非空有限集，它的每个元素称为终结符号； (2) VN为非终结符集，它也是一个非空有限集，其每个元素称为非终结符号，且有VT∩VN=Φ； (3) S为一文法开始符号（或识别符号），是一个特殊的非终结符号，即S∈VN； (4) ξ是产生式的非空有限集，其中每个产生式(或称规则)是一序偶(α，β)，通常写作 α→β或α::=β α为产生式的左部，β为产生式的右部，α∈(VT∪VN)+且至少有一个非终结符，而β∈(VT∪VN)* 说明： ①终结符号是指语言不可再分的基本符号，通常是一个语言的字母表；终结符代表了语法的最小元素，是一种个体记号。 ②非终结符号也称语法变量，它代表语法实体或语法范畴。每个非终结符代表着由一些终结符和非终结符且满足一定规则的符号串组成的集合。 ③文法开始符号是一个特殊的非终结符，它代表文法所定义的语言中我们最终感兴趣的语法实体，即语言的目标，而其它语法实体只是构造语言目标的中间变量；如表达式文法的语言目标是表达式，而程序语言的目标通常为程序。 ④产生式是定义语法实体的一种书写规则。一个语法实体的相关规则可能不止一个。例如，有： P→α1 P→α2 …… P→αn 为书写方便，可将这些有相同左部的产生式合并为一个，即缩写成 P→α1∣α2∣…∣αn 其中，每个αi(i=1,2,…,n)称为P的一个候选式，直竖“∣”读为“或”，它与“→”一样是用来描述文法的元语言符号(即不属于Σ的字符)。 例3.1： 构造产生标识符的文法。 解：标识符是以字母开头的字母数字串。 用L表示“字母”类非终结符； 用D表示“数字”类非终结符； 用T表示“字母或数字”类非终结符。 则有： L→a∣b∣…∣z D→0∣1∣…∣9 T→L∣D 用S表示“字母数字串”类，由于T是一字母或数字，ST也是字母数字串。 则有： S→T∣ST 其中，产生式S→T∣ST是一种左递归形式，由它可以产生一串T。 作为“标识符”的非终结符I，它或者是一单个字母，或者为一字母后跟字母数字串。 则有： I→L∣LS 最后可得，产生标识符的文法G[I]为： ? G = ({a,b,…,z,0,…,9},{I,S,T,L,D},I,ξ) ξ: I→L∣LS S→T∣ST T→L∣D L→a∣b∣…∣z D→0∣1∣…∣9 例3.2：写一文法，使其语言是奇数集合，但不允许出现以0打头的奇数。 解： 可以将奇数划分为如图所示的三个部分 即最高位允许出现1～9，用非终结符B表示；中间部分可以出现任意多位数字0～9，每一位用非终结符D表示；最低位只允许出现1、3、5、7、9等奇数，用A表示。