编译原理(文法知识)

《编译原理(文法知识)》由会员分享，可在线阅读，更多相关《编译原理(文法知识)（12页珍藏版）》请在金锄头文库上搜索。

1、文法是一个四元组：G = VT,VN,S,P 其中 VT是一个非空有限的符号集合，它的每个元素成为终结符号。VN 也是一个非空有限的符号集合，它的每个元素称为非终结符号，并且 VTVN=。SVN，称为文法 G 的开始符号。P 是一个非空有限集合，它的元素称为产生式。所谓产生式，其形式为 ， 称为产生式的左部， 称为产生式的右部，符号“” 表示“定义为” ，并且 、(VT VN)*，即、 是由终结符和非终结符组成的符号串。开始符 S 必须至少在某一产生式的左部出现一次。另外可以对形式 ， 的产生式缩写为 |，以方便书写。 注：一般以大写字母表示非终结符，以小写字母表示终结符。 著名语言学家 No

2、am Chomsky(乔姆斯基) 根据对产生式所施加的限制的不同，把文法分成四种类型，即 0 型、1 型、2 型和 3 型。 0 型文法 设 G=VT,VN,S,P，如果它的每个产生式 是这样一种结构： (VTV N)* 且至少含有一个非终结符，而 (VT VN )*，则 G 是一个 0 型文法。0 型文法也称短语文法。一个非常重要的理论结果是：0 型文法的能力相当于图灵机(Turing)。或者说，任何 0 型文语言都是递归可枚举的，反之，递归可枚举集必定是一个 0 型语言。0 型文法是这几类文法中限制最少的一个，所以一般见到的至少是 0 型文法。 1 型文法 1 型文法也叫上下文有关文法，此

3、文法对应于线性有界自动机。它是在 0 型文法的基础上每一个 ，都有|=|。这里的|表示的是 的长度。注意：虽然要求|=|，但有一特例： 也满足 1 型文法。如有 A-Ba 则|=2,|=1 符合 1 型文法要求。反之 ,如 aA-a，则不符合 1 型文法。2 型文法 2 型文法也叫上下文无关文法，它对应于下推自动机。2 型文法是在 1 型文法的基础上，再满足：每一个 都有 是非终结符。如 A-Ba，符合 2 型文法要求。如 Ab-Bab 虽然符合 1 型文法要求, 但不符合 2 型文法要求，因为其 =Ab，而 Ab 不是一个非终结符。 3 型文法 3 型文法也叫正规文法，它对应于有限状态自动机

4、。它是在 2 型文法的基础上满足：A|B（右线性）或 A|B（左线性）。如有：A-a,A-aB,B-a,B-cB，则符合 3 型文法的要求。但如果推导为:A-ab,A-aB,B-a,B-cB 或推导为：A-a,A-Ba,B-a,B-cB 则不符合 3 型方法的要求了。具体的说，例子 A-ab,A-aB,B-a,B-cB 中的 A-ab 不符合 3 型文法的定义,如果把后面的 ab,改成“ 一个非终结符一个终结符”的形式( 即为 aB)就对了。例子 A-a,A-Ba,B-a,B-cB 中如果把 B-cB 改为 B-Bc 的形式就对了，因为 A|B(右线性)和A|B(左线性)两套规则不能同时出现在

5、一个语法中，只能完全满足其中的一个，才能算 3型文法。一些相关的定义： 1、当 G 为 2 型或 3 型文法时，命题“L(G)是空集、有限集或无限集”才是可判断的。 2、当 G1 和 G2 都是 3 型文法时，命题 “L(G1)=L(G2)”才是可判断的。 3、最左 /右推导：推导的每一步都对最左/右的非终结符使用推导公式 4、若 S 可以推出 mAn，而 A 可以推出 a，则称 a 是非终结符号 A 的、句型 mAn 的短语。若存在 A=a，则为直接短语。 5、一个句型的最左直接短语称为该句型的句柄 6、素短语是一个短语，它至少包含一个终结符，并除自身外不包含其他的素短语。 * 注：此类问题

6、可以用语法树来判定，规则如下 1.每个句型对应一棵语法树 2.每棵语法树的所有叶子结点从左到右排列构成一个句型 3.每棵语法树的子树的叶子结点从左到右排列构成一个短语 4.每棵语法树的简单子树(只有父子两层结点 )的叶子结点从左到右排列构成一个简单(直接)短语 5.每棵语法树的最左简单子树(只有父子两层结点) 的叶子结点从左到右排列构成句柄 6.素短语是至少包含一个终结符的短语，但它不能包含其它素短语 7.最左推导：在每个推导过程中，总是首先考虑对当前最左边的非终结符号进行推导 8.最右推导：在每个推导过程中，总是首先考虑对当前最右边的非终结符号进行推导 举例如下： Vt=a,b,d,(,).

7、Vn=S,T,S 是开始符S - a|b|(T)T - TdS|S句型(Sd(T)db)是 S 的一个_,其中_ 是句柄;_是最左素短语;_是该句型的直接短语,_是短语。 语法树如下： S / | ( T ) / | T d S / | | T d S b | /| S ( T ) 1.首先在 T-S 之后还有一个 S-b 的推导，所以该句型不是最左推导，只是一个简单的推导 2.再看直接短语，有 S,(T),b 这 3 个，其余子树均大于或等于 3 层 3.句柄为最左直接短语，即 S 4.素短语在短语中从左往右找，S 不是排除，Sd(T) 包含了(T)，排除，最后剩下 (T)为最左素短语 5.

8、短语很多，直接从备选答案里找即可 鸣谢： http:/ * - 有限状态自动机 注：说明一点，只要是有限状态自动机，则必定符合 3 型文法，且可用正则表达。 一个确定的有限状态自动机 M(记做 DFA)是一个五元组：M=(,Q,q0,F,) 其中： (1) Q 是一个有限状态合集 (2) 是一个字母集，其中的每个元素称为一个输入符号 (3) q0 Q，称为初始状态 (4) FQ，称为终结状态集合 (5) 是一个从 Q(Q 与 的笛卡尔积)到 Q 的单值映射： (q,a)=q* (q,q*Q, a) 以上式子表示当前状态为 q，输入符号 a 时，自动机将转换到下一个状态 q*，q*称为 q 的一

9、个后继。 若 Q=q1,q2,.,qn ,=a1,a2,.,an，则 (qi,aj)nm是一个 n 行 m列矩阵，称为 DFA 的状态转换矩阵，或称转换表。 有限状态自动机可以形象地用状态转换图表示，举例如下： DFA M=(S,A,B,C,f,1,0,S,f ,) 其中：(S,0)=B, (S,1)=A, (A,0)=f, (A,1)=C, (B,0)=C, (B,1)=f, (C,0)=f , (C,1)=f 则对应的状态转换图如下所示： 其中圈表示状态结点，双圈表示终结状态结点，而边表示状态的转换，代表映射。边上的符号表示此转换需要输入的符号，代表映射的输入。 对于 上的任何字符串 w*

10、，若存在一条从初始结点到终态结点的路径，在这条路径上的所有边的符号连接称的符号串恰好是 w，则 w 被 DFA 所识别(或接受、读出) 。DFA 所能识别的符号串的全体记为 L(M)，称为 DFA 所识别的语言。 NFA 介绍 之前介绍的是确定的有限自动机，即一个状态对于待定的输入字符有一个确定的后继状态。而当一个状态对于特定的输入字符有一个以上的后继状态时，我们称该有限自动机为非确定有限自动机(记做 NFA)，其形式定义也是 M=(,Q,q0,F,)，且前面的字符定义均和 DFA 相同，但是 ：Q 对应所有 Q 的任意子集。 在 NFA 中能够识别的路径与 DFA 中定义也相同。 对任何一个

11、 NFA，都存在一个 DFA*使 L(M*)=L(M)，这时我们称 M*与 M 等价。构造与M 等价的 M*的基本方法是让 M*的状态对应于 M 的状态集合。即如果 (q,a)=q1,q2,.,qn，则把q1,q2 ,.,qn看作 M*的一个状态，即 M*中的状态集合 Q*的一个元素。 正则表达式的转换 DFA 和 NFA 和正则式的转换比较模式化，看一个例子就明白了，具体的方法可以看下面这篇博客： * 利用有限自动机分析正则表达式 版权声明：可以任意转载，但转载时必须标明原作者 charlee、原始链接 http:/ 以及本声明。 程序编译的第一个阶段是词法分析，即把字节流识别为记号（tok

12、en）流，提供给下一步的语法分析过程。而识别记号的方法就是正则表达式的分析。本文介绍利用有限自动机分析表达式的方法。 概念 将正则表达式转换为 NFA(Thompson 构造法) o 算法 o 性质 o 示例 将 NFA 转化为 DFA o 算法 o 示例 NFA 和 DFA 的效率 概念 记号 有字母表中的符号组成的有限长度的序列。记号 s的长度记为|s|。长度为 0 的记号称为空记号，记为。 有限自动机(Finite State Automaton) 为研究某种计算过程而抽象出的计算模型。拥有有限个状态，根据不同的输入每个状态可以迁移到其他的状态。 非确定有限自动机(Nondetermin

13、istic Finite Automaton) 简称 NFA，由以下元素组成： 1. 有限状态集合 S； 2. 有限输入符号的字母表 ； 3. 状态转移函数 move； 4. 开始状态 sSUB0； 5. 结束状态集合 F，F S。 自动机初始状态为 sSUB0，逐一读入输入字符串中的每一个字母，根据当前状态、读入的字母，由状态转移函数 move 控制进入下一个状态。如果输入字符串读入结束时自动机的状态属于结束状态集合F，则说明该自动机接受该字符串，否则为不接受。 确定有限自动机(Deterministic Finite Automaton) 简称 DFA，是 NFA 的一种特例，有以下两条限

14、制： 1. 对于空输入 ，状态不发生迁移； 2. 某个状态对于每一种输入最多只有一种状态转移。将正则表达式转换为 NFA(Thompson 构造法) 算法 算法 1 将正则表达式转换为 NFA(Thompson 构造法) 输入 字母表 上的正则表达式 r 输出 能够接受 L(r)的 NFA N 方法 首先将构成 r 的各个元素分解，对于每一个元素，按照下述规则 1 和规则 2 生成NFA。 注意：如果 r 中记号 a 出现了多次，那么对于 a 的每次出现都需要生成一个单独的NFA。 之后依照正则表达式 r 的文法规则，将生成的 NFA 按照下述规则 3 组合在一起。 规则 1 对于空记号 ，生成下面的 NFA。 规则 2 对于 的字母表中的元素 a，生成下面的 NFA。 规则 3 令正则表达式 s 和 t 的 NFA 分别为 N(s)和 N(t