《形式语言与自动机理论--第六章(蒋宗礼)》由会员分享，可在线阅读，更多相关《形式语言与自动机理论--第六章(蒋宗礼)（108页珍藏版）》请在金锄头文库上搜索。
1、形式语言与自动机理论 Formal Languages and Automata Theory蒋宗礼课程目的和基本要求 课程性质 技术基础 基础知识要求 数学分析（或者高等数学），离散数学 主要特点 抽象和形式化 理论证明和构造性 基本模型的建立与性质 课程目的和基本要求 本专业人员4种基本的专业能力 计算思维能力 算法的设计与分析能力 程序设计和实现能力 计算机软硬件系统的认知、分析、设计与应用能 力 计算思维能力 逻辑思维能力和抽象思维能力 构造模型对问题进行形式化描述 理解和处理形式模型课程目的和基本要求 知识 掌握正则语言、下文无关语言的文法、识 别模型及其基本性质、图灵机的基本知识。
2、 能力 培养学生的形式化描述和抽象思维能力。 使学生了解和初步掌握“问题、形式化描 述、自动化（计算机化）”这一最典型的计 算机问题求解思路。 主要内容 语言的文法描述。 RL RG、 FA、RE、RL的性质 。 CFL CFG(CNF、GNF)、PDA、CFL的性质。 TM 基本TM、构造技术、TM的修改。 CSL CSG、LBA。教材及主要参考书目 蒋宗礼，姜守旭. 形式语言与自动机理论. 北 京：清华大学出版社，2003年 John E Hopcroft, Rajeev Motwani, Jeffrey D Ullman. Introduction to Automata Theory,
3、 Languages, and Computation (2nd Edition). Addison-Wesley Publishing Company, 2001 John E Hopcroft, Jeffrey D Ullman. Introduction to Automata Theory, Languages, and Computation. Addison-Wesley Publishing Company, 1979第6章 上下文无关语言 Gbra：SS(S)| L(Gbra)不是RL,是CFL高级程序设计语言的绝大多数语法结构都 可以用上下文无关文法(CFG)描述。BNF(巴
4、科斯范式：Backus normal form， 又叫Backus-naur form)。第6章 上下文无关语言 主要内容 关于CFL的分析派生和归约、派生树 CFG的化简 无用符、单一产生式、空产生式 CFG的范式 CNF GNF CFG的自嵌套特性 第6章 上下文无关语言 重点 CFG的化简。 CFG到GNF的转换。 难点 CFG到GNF的转换，特别是其中的用右 递归替换左递归的问题。6.1 上下文无关语言 文法G=(V，T，P，S)被称为是上下文 无关的。 如果除了形如A的产生式之 外，对于P，均有|，并 且V成立。 关键：对于AV，如果AP， 则无论A出现在句型的任何位置，我们都 可以
5、将A替换成，而不考虑A的上下文 。 6.1.1 上下文无关文法的派生树 算术表达式的文法 Gexp1：EE+T|E-T|T TT*F|T/F|F FFP|P P(E)|N(L)|id Nsin|cos|exp|abs|log|int LL,E|E 6.1.1 上下文无关文法的派生树 算术表达式x+x/y2的不同派生 EE+TT+TF+TP+Tx+Tx+T/Fx+F/F x+P/Fx+x/Fx+x/FPx+x/PPx+x/yP x+x/y2 EE+TE+T/FE+T/FPE+T/F2E+T/P2 E+T/y2 E+F/y2 E+P/y2 E+x/y2 T+x/y2 F+x/y2 P+x/y2x+
6、x/y2 EE+TT+TT+T/FF+T/FF+T/FP P+T/FPx+T/FPx+F/FPx+F/F2 x+F/P2x+P/P2x+P/y2x+x/y2 6.1.1 上下文无关文法的派生树 文法Gexp1句子x+x/y2的结构。 6.1.1 上下文无关文法的派生树 派生树(derivation tree) 一棵(有序)树(ordered tree) 树的每个顶点有一个标记X，且 XVT 树根的标记为S； 如果非叶子顶点v标记为A，v的儿子从左 到右依次为v1，v2，vn，并且它们分别标 记为X1，X2，Xn，则AX1X2XnP； 如果X是一个非叶子顶点的标记，则 XV； 如果顶点v标记为，
7、则v是该树的叶子， 并且v是其父顶点的惟一儿子。 6.1.1 上下文无关文法的派生树 别称 生成树 分析树(parse tree) 语法树(syntax tree) 顺序 v1，v2是派生树T的两个不同顶点，如果 存在顶点v，v至少有两个儿子，使得v1是v的 较左儿子的后代，v2是v的较右儿子的后代， 则称顶点v1在顶点v2的左边，顶点v2在顶点v1 的右边。 6.1.1 上下文无关文法的派生树 结果(yield) 派生树T的所有叶子顶点从左到右依次 标记为X1，X2，Xn，则称符号串 X1X2Xn是T的结果。 一个文法可以有多棵派生树，它们可以 有不同的结果。 句型的派生树：“G的结果为的派
8、生 树”。6.1.1 上下文无关文法的派生树 派生子树(subtree) 满足派生树定义中除了对跟结点的标记 的要求以外各条的树叫派生子树(subtree) 。 如果这个子树的根标记为A，则称之为 A子树。 惟一差别是根结点可以标记非开始符号 。6.1.1 上下文无关文法的派生树定理6-1 设CFG G=(V，T，P，S)， S*的充分必要条件为G有一棵结果为 的派生树。 证明： 证一个更为一般的结论：对于任意AV， A*的充分必要条件为G有一棵结果为的A -子树。 充分性：设G有一棵结果为的A-子树，非 叶子顶点的个数n施归纳，证明A*成立。 6.1.1 上下文无关文法的派生树 设A-子树有
9、k+1个非叶子顶点，根顶点 A的儿子从左到右依次为v1，v2，vm ，并且它们分别标记为X1，X2，Xm 。 AX1X2XmP 。 以X1，X2，Xm为根的子树的结果 依次为1，2，m 。 X1，X2，Xm为根的子树的非叶子 顶点的个数均不大于k。 6.1.1 上下文无关文法的派生树 X1*1 X2*2 Xm*m 而且 =12m6.1.1 上下文无关文法的派生树AX1X2Xm*1X2Xm*12Xm*12m6.1.1 上下文无关文法的派生树6.1.1 上下文无关文法的派生树 必要性 设An，现施归纳于派生步数n，证明存在结 果为的A-子树。 设nk(k1)时结论成立，往证当n=k+1时结论也 成
10、立：令Ak+1，则有： AX1X2Xm*1X2Xm*12Xm *12m 6.1.1 上下文无关文法的派生树6.1.1 上下文无关文法的派生树 例6-1设Gbra：SS(S)|，()()和 (S)(S)的派生树。6.1.1 上下文无关文法的派生树 关于标记的结点6.1.1 上下文无关文法的派生树 最左派生(leftmost derivation) 的派生过程中，每一步都是对当前句型 的最左变量进行替换。 左句型(left sentencial form)最左派生得到的句型可叫做左句型。 最右归约(rightmost reduction) 与最左派生对相的归约叫做最有归约。6.1.1 上下文无关文
11、法的派生树 最右派生(rightmost derivation) 的派生过程中，每一步都是对当前句型 的最右变量进行替换。 右句型(right sentencial form)最右派生得到的句型可叫做右句型。 最左归约(leftmost reduction)与最左派生对相的归约叫做最右归约。6.1.1 上下文无关文法的派生树 规范派生(normal derivation)最右派生。 规范句型(normal sentencial form)规范派生产生的句型。 规范归约(normal reduction)最左归约。6.1.1 上下文无关文法的派生树定理6-2 如果是CFG G的一个句型， 则G中
12、存在的最左派生和最右派生。证明： 基本思路：对派生的步数n施归纳，证 明对于任意AV，如果An，在G中 ，存在对应的从A到的最左派生：An 左。 6.1.1 上下文无关文法的派生树AX1X2 Xm*1X2Xm*12Xm*12 mA左X1X2Xm*左1X2Xm*左12Xm*左12m 同理可证，句型有最右派生。 6.1.1 上下文无关文法的派生树定理6-3 如果是CFG G的一个句型， 的派生树与最左派生和最右派生是一一 对应的，但是，这棵派生树可以对应多个 不同的派生。6.1.2 二义性 简单算术表达式的二义性文法 Gexp2：EE+E|E-E|E/E|E*E E EE|(E)|N(L)|id
13、Nsin|cos|exp|abs|log|int LL,E|E 6.1.2 二义性 E E+E x+E x+E/E x+x/E x+x/EE x+x/y E x+x/y 2句子x+x/y2在文法中的三个不同的最左派生 E E/E E+E/E x+E/E x+x/E x+x/EE x+x/yE x+x/y2 E EE E/EE E+E/EE x+E/EE x+x/EE x+x/yE x+x/y2 6.1.2 二义性 对 应3 个 不 同 的 语 法 树6.1.2 二义性 二义性(ambiguity) CFG G=(V，T，P，S)，如果存在 wL(G)，w至少有两棵不同的派生树， 则称G是二义性
14、的。否则，G为非二义性 的。 二义性的问题是不可解的(unsolvable) 问题。 6.1.2 二义性 例6-2 用其他方法消除二义性。 Gifa：Sif E then S else S | if E then S Gifm：SU|M Uif E then S Uif E then M else U Mif E then M else M|S Gifh：STS|CS Cif E then T CS else 6.1.2 二义性 例 6-3 设 Lambiguity=0n1n2m3m|n,m10n1m2m3n|n,m 1 可以用如下文法产生语言Lambiguity： G：SAB|0C3 A01|0A1 B23|2B3 C0C3|12|1D2 D12|1D2 语言Lambiguity不存在非二义性的文法。 6.1.2 二义性 固有二义性的(inherent ambiguity) 如果语言L不存在非二义性文法，则称L 是固有二义性的，又称L是先天二义性的 。 文法可以是二义性的。 语言可以是固有二义性的。 6.1.3 自顶向下的分析和自底向 上的分析 自顶向下的分析方法 通过考察是否可以从给定文法的开始符号 派生出一个符号串，可以判定一个符号串是 否为该文法的句子。
