3_文法和语言【荐】.ppt

第3章 文法和语言 3.1 文法的直观理解 3.2 字符串及其运算 3.3 文法的形式定义 3.4 文法的类型 3.5 递归规则与递归文法 3.6 规范推导与句柄 3.7 语法树和二义性 3.8 语言和文法构造讨论和小结 3.9 文法的实用限制和变换 3.1 文法的直观理解 设z = xy是符号串，则称x是z的头，y是z的 尾。 若y非空，则x是z的真（固有）头或真前缀。 若x非空，则y是z的真（固有）尾或真后缀。 例7: 设z = abc, 则 z的头有ε, a, ab, abc, 除了abc，其余都 是固有头； 3.3 文法的形式定义 定义 文法G定义为四元组（VN，VT，P，S）, 其中：VN：非终结符集； VT：终结符集， 并且 VN∩VT＝φ； 　P：产生式集合；S： 开始符号或识别符号； P中产生式形式为：α→β， 书写符号约定 非终结符用大写字母A,B,C,…表示,S,Z用作开始符 终结符用小写字母a,b,c,… 表示 Z,Y,X,… 表示文法符号 u,v,w,x,… 表示符号串 第一条规则的左部符号是开始符 3.4 文法的类型 0 型文法 1 型文法 2 型文法 3 型文法 四种文法之间的关系： 由于四种文法是按照将产生式做进一步限制而 定义的，所以它们之间是逐级“包含”的关系，由四 种文法产生的语言也是逐级“包含”的关系。即： 3型语言类 2型语言类 1型语言类 0型语言类 3.5 递归规则与递归文法 1、递归的概念 　所谓递归，是指： ① 同一个（或一组）操作的连续重复； ② 一种处理过程的性质，这种过程的某一步要用到它自身的上一步（或上几步）的结果。 递归定义是指在定义某事物时，又用到该事物本身。　 定义：形如A→Ay 的规则称为左递归规则； 形如A→xA 的规则称为右递归规则； 　形如A→xAy且x,yε的规则称为内递归规 则，或自嵌入规则； 若文法中至少包含一条递归规则，则称此 文法是直接递归的。 若对文法以下推导成立　　 　 A=Ay 或 A =xA 或 A =xAy (x,yε) 则称文法为间接左递归，或间接右递归，或间接内递归。 递归文法的判别 若文法中存在A，可建立推导A=xAy，则该文法是递归的。 例：文法G:S→aB | bB B→a | b 是非递归的。 　　 表达式文法Ge是递归的。 递归文法的作用 可用有穷的文法描述无穷语言。因此，描述程序设计语言的文法必定都递归文法。 3.6 规范推导与句柄 3.7 语法树和二义性 3.7 语法树和二义性 例：文法Ge中的一棵语法树 3.7 语法树和二义性 例：构造文法Ge的句型T*(i+T)+F的语法树(推导的每一步对应一个分支) 3.7 语法树和二义性 例32：对于句型T*(i+T)+F的语法树逐次减去 一个叶子分支的孩子，可得到一个归约序列。 3.7 语法树和二义性 对语法树有以下结论： ① 语法树的叶子结点从左至右组成的符号串 对应文法中的一个句型 ② 每一句型推导都有一棵对应的语法树，但 每一语法树至少对应一个推导。语法树与推 导顺序无关，更能从本质上反映语法结构。 ③ 每一分支表示一个直接推导 3.7 语法树和二义性 子树与短语的关系： ④每个子树的叶子串是相对于该子树的根的短语 ⑤每个叶子分支(简单子树)的叶子串是一简单短语 ⑥最左的叶子分支的叶子串是句柄（最左简单短语） 3.7 语法树和二义性 例（二义性） 我没说她偷了我的钱。（可是有人这么说） 我没说她偷了我的钱。（我确实没这么说） 我没说她偷了我的钱。(可是我是这么暗示的） 我没说她偷了我的钱。（可是有人偷了） 我没说她偷了我的钱。(但她用这钱做了某事) 我没说她偷了我的钱。（她偷了别人的钱） 我没说她偷了我的钱。（她偷了别人的东西） 3.7 语法树和二义性 定义　如果一个句子存在不止一棵语法树， 则称该句子是二义性的。如果一个文法包含有二 义性的句子，则称该文法是二义性的。 注意： ① 二义性是指文法，不是指语言。如果一个语言不存在无二义性文法，才是二义性的语言。 ② 句子的二义性是指文法上的，不是语义的。 ③ 文法的二义性是不可判定的，实践中只能给出一些判断的充分条件。 3.7 语法树和二义性 例：二义性文法 Ge: E→E+E | E*E | (E) | i 对句子i*i+i可画出两棵不同的语法树： 对应有两个不同的最左推导 E=E+E=E*E+E=i*E+E=i*i+E=i*i+i E=E+E