X03 文法.pdf

《X03 文法.pdf》由会员分享，可在线阅读，更多相关《X03 文法.pdf（10页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、文法 Grammar (I) 文法 文法是定义和阐明（一类）语言的一种 规则化方式，也可以说是以有穷的集合 刻画无穷的集合的一个工具。 20世纪50年代，美国语言学家乔姆斯基 （Avram Noam Chomsky）提出了短语 结构文法。 乔姆斯基根据产生语言的文法的产生式 的不同特点，将文法和对应产生的语言 分为三大类。 2 文法 一个短语结构文法短语结构文法（phrase structure grammar）（或简称文法文法）G 包括： (1) 一个有限集合 N，其元素称为非终结符非终结符 号号（non-terminal symbol）。 (2) 一个有限集合 T，其元素称为终结符号终结符

2、号 （terminal symbol），其中 NT=。 (3) (NT) T (NT) 的一个有限子集 P，称为产生式的集合产生式的集合。 (4) 一个开始符号 N。 记作 G=(N, T, P, )。 3 文法 产生式 (, ) P 通常写为 。 在产生式 中， (NT) T ， 于是 至少包括一个非终结符号， 而 能够由非终结符号和终结符号 的任意组合构成。 称作这个产生式的左部左部， 称作这 个产生式的右部右部。 4 文法 设 G=(N, T, P, ) 是一个文法。如果 是一个产生式且 xy (NT) ，这 里 x, y (NT) ，则称 xy 可直接从 xy 推导，并写成 xyxy。

3、 如果对于 i (NT) (i=1, , n1)，都 有 i+1 (i=1, , n1) 可直接从 i 推导， 则称 n 可从可从 1 推导推导，并写成 1 n。 我们称 1 2. n 是 n（从 1 ） 的推导推导（derivation）。 5 文法 约定：(NT) 的任意元素都是 从自身可推导的。w T 称为是 文法正确文法正确的当且仅当 w。 容易看出，是(NT) 上的关 系，而且具有传递性。 6 文法 例 N = sentence, noun, verb, adverb T = BAT, TABLE, EAT, SLEEP, FAST, HORRIBLY P 中元素为： sentenc

4、e noun verb adverb，noun BAT，noun TABLE， verb EAT，verbSLEEP，adverbFAST，adverb HORRIBLY = sentence 则 “BAT EAT FAST”是文法正确的； 而“FAST BAT SLEEP”不是文法正确的。 注意“文法正确”和“语义正确”是不同的 “TABLE SLEEP HORRIBLY”是文法正确的但不存在正常的语义 7 sentence noun verb adverb BAT verb adverb BAT EAT adverb BAT EAT FAST 文法 由 G 生成生成的语言的语言是指从 可推

5、导的 T 上的所 有字符串组成的集合，记作 L(G) 。 例 (a) 文法 G = ( , x, x ， x, ) 生 成的语言是 L(G) = xn | n 1 (b) 文法 G = ( , x, x ， , ) 生 成的语言是 L(G) = xn | n 0 (c) 文法 G = ( , x, x y, xy, ) 生成的语言是 L(G) = xnyn | n 1 (d) 文法 G = ( , x, x y, , ) 生成 的语言是 L(G) = xnyn | n 0 8 文法 如果如果 L(G)=L(G) ，那么称文法 G 和 G 等价等价。 例 (a) 文法 G=( , x, x ， x, ) 生 成的语言是 L(G) = xn | n 1 (b) 文法 G=( , x, x， x, ) 生成的语言是 L(G) = xn | n 1 9 End