第三章文法和语言

1、 设x和y是符号串，则 xy为它们的连接。例如，假定有 x=aa, y=bb，则有:xy = aabb。 特别对任一符号串特别对任一符号串 有有 =设A和B是符号串的集合，则用 AB表示集合A、B的乘积。 AB= xy |x A，y B。因因为为=所以有所以有 A = A= AA = A= A 不包含任何元素的集合称为空集合，不包含任何元素的集合称为空集合，记为记为。 对任一集合，有对任一集合，有A = A = A = A = 集合乘积定义如下：集合乘积定义如下： 同一符号串的序列可表示成方幂形式x0 =x1 = xx2 = xxxn = xxx （n个x）对符号串集合也定义方幂：对符号串集合

2、也定义方幂：A0 =A1 = AA2=AAAn = An-1A 其中A是任一集合 设设为字母表或一集合，为字母表或一集合， 上的所有有穷上的所有有穷长的串的集合用长的串的集合用*表示表示, 称为集合称为集合的闭包。的闭包。写成写成： *= 0 1 2 n 设设为任一为任一字母表或字母表或集合，则用集合，则用+ 表示表示的正闭包。其定义如下：的正闭包。其定义如下： + = 1 2 3 n *= 0 + = + 设V VN和V VT T都是非空有穷集，S VS VN 且且V VNVVT T = =。记记 V=VV=VNVVT T，称G =G =（V VN，V VT T，P P，S S）为文法。其中

3、： ：G G的变量集，非终结符的有穷集合（大写字母表示）：终结符的非空有穷集合（小写字母表示） ：G G的产生式集（形为 的产生式的有穷集合） : : 被指定为文法的开始符号。（。（ S VS VN ）其中： （V VN NVVT T）+ +，（V VN NVVT T） 不能再推导的符号：可再推导下去的符号n从上而下分析法n从下而上分析法如果用若干次规则式可从符号串X X推导出符号Y Y，则称Y Y为X X的推导。即从文法的开始符号出发，反复使用各种产生式，寻找“匹配”于输入符号串的过程设X和Y是符号串，若用一次规则式可从X推导出Y，则称为X的直接推导，并记为XY。如果用若干次规则式可从符号串

4、X X推导出符号Y Y，则称Y Y为X X的推导，并记为记为: :为方便起见，再引进符号为方便起见，再引进符号 ，其定义如下： 当且仅当当且仅当 X = Y 或或X + Y。显然，根据定义对任一符号串显然，根据定义对任一符号串X都有都有 X * Xn若存在直接推导的序列：V=W0W1W2Wn=W（n0）则称V推导出W,推导长度为n。n从输入符号串开始，逐步进行n“”，直至归约到文法的开始符号V=W0W1W2Wn=W（n0），称W归约到V。记作归约和推导是相对的概念，推导是把句型中的非终极符用规则式的一个的过程。而归约是把句型中的某子串的过程。令G G是一文法，且 U u 是G中的规则式。 有有

5、x U y x u y （），），则有 x u y x U y（）。）。：设GS是一文法，如果符号串X是从识别符号（开始符开始符）推导出来的，即有S* x，则称x是文法G的句型。：不包含非终极符的句型称为句子。也就是说，x是一个句子Z* x 且x VT*。所有句子的集合称为语言。设G G是给定文法,S S是开始符，由文法G G所定义的语言L L（G G）可描述如下： L（G）= x | S * x 且 x VT* 设G1和G2是给定文法,若有L（G1）= L（G2）则称G1和G2等价。这就是说，不同的文法可定义相同的语言。等价等价文法：（短语结构文法）（短语结构文法）:规则式具有下面形式; ，

6、 其中、都是符号串， , （VNVT）*，且 至少含有一个非终极符（上下文有关文法）：（上下文有关文法）：规则式限制为下面形式： A u 其中其中AVN，u是非空串，显然有| A| | u|（产生式非缩减的）这里把A替换为符号串u是有条件的，即A前面必须是 ，A后面必须是，因此称为上下文有关文法。 （上下文无关文法）：规则式限制为下面形式：A 所有产生式左端是一非终极符，其中AVN，（VNVT）*，为非空串，取代A时与A所在的上下文无关。大部分程序设计语言的文法近似于2型文法，因此2型文法是我们研究对象。（正规文法）：规则式限制为下面形式之一： A aA a A a BA a B 其中 A A

7、、BVBVN N，aVaVT T* *。3 3型文法与自动机有密切关系。上面的分类格式是由ChomskyChomsky与19591959年提出的。 上面分析得出上面分析得出四种文法间的关系四种文法间的关系:3 3型文法必是型文法必是2 2型文法，型文法，2 2型文法必是型文法必是1 1型文法，型文法，1 1型文法必是型文法必是0 0型文法。即：型文法。即： 文法的递归性：说A是直接左递归的，其 规则式为：A A说A是直接右递归的，其规则式为： A A若有推导式：A + A，说A是左递归的若有推导式：A + A，说A是右递归的文法的递归性v表达式v项v因子按推导过程，画出一棵树型结构称为语 法树

8、。 ：设G=G=（V VN ，V VT，P P，S S）是给定文法，则满足下面条件的树称为G G的一棵语法树，也叫推推导树。导树。每个结点都有标记，该标记是G G中的某一终极符 或非终极符。树根的标记是文法的开始符S S。若结点的标记为A A，并且它至少有一个从它出来的分枝，则A A一定是非终极符。由某一结点及其所有分枝组成的部分称为原树的一棵子树。：只有单层分枝的子树称为简单子树。如果标记为A A的结点有n n个从它出来的分枝，并且这些分枝结点的标记从左至右分别为A A1 1，A A 2， A An，则AAAA1 1，A A 2 2， A An一定是G G的一个文法规则式。设xUy xuy

9、是一个直接推导。如果y是终极符串或空，即U是句型xUy中的最右非终极符，则称这种推导为规范直接推导。记为： xUy r右 xuy （XUy r右 Xuy ）若推导x + y中的每步都是规范直接推导， 则称该推导为规范推导。 并记为x +r右 y，也称为最右推导。 ：设G为给定文法，S是开始符，W= xuy是一个句型，如果满足下面两个条件： S *xUy U+u 则称句型xuyxuy中的子串u为句型xuyxuy相对于非终极符U的短语。（简单短语）：）：如果满足条件 S * xUy U u则称u为句型xuy的直接短语（简单短语）。第二个条件表示有文法规则式Uu存在存在。 一个句型多个简单短语中最左

10、边的直一个句型多个简单短语中最左边的直接短语称为该句型的句柄。接短语称为该句型的句柄。 从根符号开始的对句型构造的语法树的方法是从上向下分析的方法。从输入串开始，逐步进行“”，直至归到文法的开始符号。或者说，从语法树的末端开始，步步向上“归约”直到根部。二义性二义性：如果文法G G的一个句子有两棵以上语法树，则称该句子有二义性。例如，对于例36的文法G,句型 i*i+i 就有两个不同的最左推导，它们所对应的语法树分别如图32和图33所示。：指形如UU的产生式，该种产生式对描述语言是没有必要的，只会引起文法的二义性：指文法中连一个句子的推导都用不到的规则，分为不可达到和不可终止两种情况有关文法的说明有关文法的说明:if i=5 then x=y词法分析器（3，if）（1，指向I的符号表入口）（4，=）（2，5）（3，then）（1，指向x的符号表入口）（4，=）（1，指向y的符号表入口）1）结果用二元式表示2）二元式形式是：（单词种别，单词自身的值）3）定义单词种别为：1：标识符2：常数3：保留字4：运算符5：界符词法例子的结论n单词归根结底是一个符号串n这些符号处在一个基本符号集中n基本符号集是一非空有穷集合n单词符号是基本符号按一定规则构成的基本符号串，是定义在基本符号集上的标识符单词