3文法和语言09年9月.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 规范推导与句柄 3.6 语法树和二义性 3.6 语法树和二义性 例：文法Ge中的一棵语法树 3.6 语法树和二义性 例：构造文法Ge的句型T*(i+T)+F的语法树(推导的每一步对应一个分支) 3.6 语法树和二义性 例32：对于句型T*(i+T)+F的语法树逐次减去 一个叶子分支的孩子，可得到一个归约序列。 3.6 语法树和二义性 对语法树有以下结论： ① 语法树的叶子结点从左至右组成的符号串 对应文法中的一个句型 ② 每一句型推导都有一棵对应的语法树，但 每一语法树至少对应一个推导。语法树与推 导顺序无关，更能从本质上反映语法结构。 ③ 每一分支表示一个直接推导 3.6 语法树和二义性 子树与短语的关系： ④每个子树的叶子串是相对于该子树的根的短语 ⑤每个叶子分支(简单子树)的叶子串是一简单短语 ⑥最左的叶子分支的叶子串是句柄（最左简单短语） 3.6 语法树和二义性 定义　如果一个句子存在不止一棵语法树， 则称该句子是二义性的。如果一个文法包含有二 义性的句子，则称该文法是二义性的。 注意： ① 二义性是指文法，不是指语言。如果一个语言不存在无二义性文法，才是二义性的语言。 ② 句子的二义性是指文法上的，不是语义的。 ③ 文法的二义性是不可判定的，实践中只能给出一些判断的充分条件。 3.6 语法树和二义性 例：二义性文法 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=i*E=i*E+E=i*i+E=i*i+i 3.6 语法树和二义性 例：文法GIF也是二义性的 GIF: S→if b then S else S S→if b then S S→a 句子if b then if b then a else a对应两棵语法树： 　　S S if b then S if b then S else S if b then S else S if b then S a a a a 3.6 语法树和二义性 对二义性的处理： ① 把二义性文法变换为无二义性的。如可把文法Ge变换为文法GE Ge: E→E+E|E*E|(E)|i GE: E→E+T|T T→T*F|F F→(E)|i ② 附加去掉二义性的信息。 如if语句，规定else只与紧前的未配对 的then配对。 3.7 语言和文法构造讨论 已知文法，写出相应语言描述（是唯一的） 例如：文法G[S]： S→bS | a 已知语言描述，写出相应文法（可能不止 一个） 例如：若语言由0、1符号串组成，串中0 和1的个数相同，构造其文法。 3.7 语言和文法构造讨