当前位置:文档之家› 第二章 前后文无关文法和语言 课后答案【khdaw_lxywyl】

第二章 前后文无关文法和语言 课后答案【khdaw_lxywyl】

第二章 前后文无关文法和语言 课后答案【khdaw_lxywyl】
第二章 前后文无关文法和语言 课后答案【khdaw_lxywyl】

第二章前后文无关文法和语言

1设有字母表A1={a,b,…,z},A2={0,1,…,9},试回答下列问题:(1)字母表A1上长度为2的符号串有多少个?(2)集合A1A2含有多少个元素?

(3)列出集合A1(A1∪A2)*中的全部长度不大于3的符号串。2试分别构造产生下列语言的文法。(1){anbn|n≥0};

(2){anbmcp|n,m,p≥0};

(3){an#bn|n≥0}∪{cn#dn|n≥0};

(4){w#wr#|w∈{0,1}*,wr 是将w 中的符号按逆序排列所得的符号串};(5)任何不是以0开始的所有奇整数所组成的集合;

(6)所有由偶数个0和偶数个1所组成的符号串的集合。

3试描述由下列文法所产生的语言的特点(文法的开始符号均为S)。(1)S→10S0S→aAA→bAA→a (2)S→SSS→1A0A→1A0A→ε(3)S→1AS→B0A→1AA→C

B→B0B→CC→1C0C→ε(4)S→bAdcA→AGSG→εA→a (5)S→aSSS→a

4设已给文法G=(VN,VT,P,S),其中:VN={S}

VT={a1,a2,…,an,∨,∧,~,[,]}

P={S→ai|i=1,2,…,n}∪{S→~S,S→[S∨S],S→[S∧S]},试指出此文法所产生的语言。

5考察文法G=(VN,VT,P,S),其中:VN={S,A,B,C,D,E,F,G}VT={a},

P={S→ABC,C→BC,C→A,BA→GE,BG→GBF,AG→AD,DB→BD,DE→AE,FB→BF,FE→Ea,AA→ε}(1)指出此文法的类型;

(2)证明此文法所产生的语言为L(G)={at(n)|n≥1}t(n)=∑n[]i=1i

6设已给文法G[〈程序〉]:

〈程序〉→〈分程序〉|〈复合语句〉

〈分程序〉→〈无标号分程序〉|〈标号〉:〈分程序〉

〈复合语句〉→〈无标号复合语句〉|〈标号〉:〈复合语句〉〈无标号分程序〉→〈分程序首部〉;〈复合尾部〉〈无标号复合语句〉→begin〈复合尾部〉

〈分程序首部〉→begin〈说明〉|〈分程序首部〉;〈说明〉〈复合尾部〉→〈语句〉end|〈语句〉;〈复合尾部〉〈说明〉→d 〈语句〉→s 〈标号〉→L

w w w .

k h d

a w .

c o m

(1)给出句子L:L:begin d;d;s;s end 的最左推导和最右推导。(2)画出上述句子的语法树。

7设已给文法G[S]:S→aAcBS→BdSB→aScAB→cAB

A→BaBA→aBcA→aB→b

试检验下列符号串中哪些是G[S]中的句子,给出这些句子的最左推导、最右推导和相应的语法树。(1)aacb

(2)aabacbadcd (3)aacbccb

(4)aacabcbcccaacdca (5)aacabcbcccaacbca

28设G=(VN,VT,P,S)为CFG,α1,α2,…,αn 为V 上的符号串,试证明:若

α1α2…αn *β则存在V 上的符号串β1,β2,…,βn,使β=β1β2…βn,且有ai *βi(i=1,2,…,n)

9设G=(VN,VT,P,S)为CFG,α和β都是V 上的符号串,且α *β,试证明:当α的首符号为终结符号时,β的首符号也必为终结符号;当β的首符号为非终结符号时,则α的首符号也必为非终结符号。

10试证明:文法S→ABS→DCA→aAA→a

B→bBcB→bcC→cCC→c

D→aDbD→ab 为二义性文法。

11对于下列的文法和相应的句子,试指出这些句子的全部短语;分别给出句子的最右推导,并指出各步直接推导所得句型的句柄。(1)S→ABS→cA→bAA→aB→aSbB→c bbaacb (2)S→(AS)S→(b)A→(SaA)A→(a)(((b)a (a))(b))(3)E→ET+E→TT→TF*T→FF→FP↑F→PP→EP→i iii*i+↑

12在自底向上的分析中,用来归约句型句柄的产生式称为句柄产生式。试证明:一个文法是无二义性的,当且仅当此文法的每一句型至多只有一个句柄和一个句柄产生式。13化简下列各个文法。

(1)S→aABSS→bCACdA→bABA→cSA

A→cCCB→bABB→cSBC→cS C→c

(2)S→aABS→EA→dDAA→e

B→bEB→fC→cABC→dSD C→aD→eAE→fAE→g (3)S→acS→bAA→cBCB→SA

C→bCC→d

14消去下列文法中的ε产生式。(1)S→aASS→bA→cSA→ε(2)S→aAAA→bAcA→dAeA→ε

15消去下列文法中的无用产生式和单产生式。(1)S→aBS→BCA→aAA→c

A→aDbB→DBB→CD→B C→b

(2)S→SAS→SBA→BB→[S]

w w w .

k h d

a w .

c o m

A→(S)S→AB→[]A→()(3)E→E+TE→TT→T*FT→F

F→P↑FF→PP→(E)P→i

第二章习题解答

1.(1)答:26*26=676(2)答:26*10=260

(3)答:{a,b,c,...,z,a0,a1,...,a9,aa,...,az,...,zz,a00,a01,...,zzz},

共26+26*36+26*36*36=34658个

2.构造产生下列语言的文法(1){anbn|n≥0}

解:对应文法为G(S)=({S},{a,b},{S→ε|aSb },S)(2){anbmcp|n,m,p≥0}

解:对应文法为G(S)=({S,X,Y},{a,b,c},{S→aS|X,X→bX|Y,Y→cY|ε},S)(3){an #bn|n≥0}∪{cn #dn|n≥0}

解:对应文法为G(S)=({S,X,Y},{a,b,c,d,#},{S→X,S→Y,X→aXb|#,Y→cYd|#},S)(4){w#wr#|w?{0,1}*,wr 是w 的逆序排列}

解:G(S)=({S,W,R},{0,1,#},{S→W#,W→0W0|1W1|#},S)(5)任何不是以0打头的所有奇整数所组成的集合

解:G(S)=({S,A,B,I,J},{-,0,1,2,3,4,5,6,7,8,9},{S→J|IBJ,B→0B|IB|e,I→J|2|4|6|8,Jà1|3|5|7|9},S)

(6)所有偶数个0和偶数个1所组成的符号串集合

解:对应文法为S→0A|1B|e,A→0S|1C B→0C|1S C→1A|0B 3.描述语言特点

(1)S→10S0S→aAA→bAA→a

解:本文法构成的语言集为:L(G)={(10)nabma0n|n,m≥0}。(2)S→SS S→1A0A→1A0A→ε

解:L(G)={1n10n11n20n2…1nm0nm |n1,n2,…,nm≥0;且n1,n2,…nm 不全为零}该语言特点是:产生的句子中,0、1个数相同,并且若干相接的1后必然紧接数量相同连续的0。(3)S→1AS→B0A→1AA→CB→B0B→CC→1C0C→ε

解:本文法构成的语言集为:L(G)={1p1n0n|p≥1,n≥0}∪{1n0n0q|q≥1,n≥0},特点是具有1p1n0n 或1n0n0q 形式,进一步,可知其具有形式1n0mn,m≥0,且n+m>0。(4)S→bAdcA→AGSG→εA→a 解:可知,S=>…=>baSndc n≥0

该语言特点是:产生的句子中,是以ba 开头dc 结尾的串,且ba、dc 个数相同。(5)S→aSSS→a

解:L(G)={a(2n-1)|n≥1}可知:奇数个a

4.解:此文法产生的语言是:以终结符a1、a2…an 为运算对象,以∧、∨、~为运算符,以[、]为分隔符的布尔表达式串

5. 5.1解:由于此文法包含以下规则:AA→e,所以此文法是0型文法。

5.2证明:略

6.解:

(1)最左推导:

<程序>T<分程序>T<标号>:<分程序>TL:<分程序>TL:<标号>:<分程序>

w w w .

k h d

a w .

c o m

T L:L:<分程序>

T L:L:<无标号分程序>

T L:L:<分程序首部>;<复合尾部>

T L:L:<分程序首部>;<说明>;<复合尾部>T L:L:begin<说明>;<说明>;<复合尾部>T L:L:begin d;<说明>;<复合尾部>T L:L:begin d;d;<复合尾部>

T L:L:begin d;d;<语句>;<复合尾部>T L:L:begin d;d;s;<复合尾部.T L:L:begin d;d;s;<语句>end T L:L:begin d;d;s;s end 最右推导:

<程序>T<分程序>T<标号>:<分程序>T<标号>:<标号>:<分程序>

T<标号>:<标号>:<无标号分程序>

T<标号>:<标号>:<分程序首部>;<复合尾部>

T<标号>:<标号>:<分程序首部>;<语句>;<复合尾部>T<标号>:<标号>:<分程序首部>;<语句>;<语句>;end T<标号>:<标号>:<分程序首部>;<语句>;s;end T<标号>:<标号>:<分程序首部>;s;s;end

T<标号>:<标号>:<分程序首部>;说明;s;s;end T<标号>:<标号>:<分程序首部>;d;s;s;end T<标号>:<标号>:begin 说明;d;s;s;end T<标号>:<标号>:begin d;d;s;s;end T<标号>:L:begin d;d;s;s;end TL:L:begin d;d;s;s;end

(2)句子L:L:begin d;d;s;s end 的相应语法树是:

w w w .

k h d

a w .

c o m

7.解:

aacb 是文法

G[S]中的句子,相应语法树是:

最右推导:S=>aAcB=>aAcb=>aacb 最左推导:S=>aAcB=>aacB=>aacb

(2)aabacbadcd 不是文法G[S]中的句子因为文法中的句子不可能以非终结符d 结尾(3)aacbccb 不是文法G[S]中的句子

可知,aacbccb 仅是文法G[S]的一个句型的一部分,而不是一个句子。(4)aacabcbcccaacdca 不是文法G[S]中的句子

因为终结符d 后必然要跟终结符a,所以不可能出现…dc…这样的句子。(5)aacabcbcccaacbca 不是文法G[S]中的句子

由(1)可知:aacb 可归约为S,由文法的产生式规则可知,终结符c 后不可能跟非终结符S,所以不可能出现…caacb…这样的句子。

8.证明:用归纳法于n,n=1时,结论显然成立。设n=k 时,对于α1α2...αkT*b,存在βi:i=1,2,..,k,αiT*bi 成立,现在设

α1α2...αkαk+1T*b,因文法是前后文无关的,所以α1α2...αk 可推导出b 的一个前缀b',αk+1可推导出b 的一个后缀=b"(不妨称为b k+1)。由归纳假设,对于b',存在βi :i=1,2,..,k,b'=β1β2...βk,使得

αiT*bi 成立,另外,我们有αk+1T*b"(=b k+1)。即n=k+1时亦成立。证毕。

9.证明:(1)用反证法。假设α首符号为终结符时,β的首符号为非终结符。即设:α=aω;β=Aω’且α=>*β。

由题意可知:α=aωT …T Aω’=β,由于文法是CFG,终结符a 不可能被替换空串或非终结符,因此假设有误。得证;(2)同(1),假设:β的首符号为非终结符时,α首符号为终结符。即设:α=aω;β=Aω’且α=aωT …T Aω’=β,与(1)同理,得证。

10.证明:因为存在句子:abc,它对应有两个语法树(或最右推导):STABTAbcTabc STDCTDcTabc

w w w .

k h d

a w .

c o m

所以,本文法具有二义性。11.解:

(1)ST AB TA aSb TAa c bT bA acbTb bA acbTbb a acb

上面推导中,下划线部分为当前句型的句柄。对应的语法树为:

全部的短语:

第一个a (a1)是句子bbaacb 相对于非终结符A (A1)(产生式A?a)的短语(直接短语);b1a1是句子bbaacb 相对于非终结符A2的短语;b2b1a1是句子bbaacb 相对于非终结符A3的短语;

c 是句子bbaacb 相对于非终结符S1(产生式S?c)的短语(直接短语);a2cb3是句子bbaacb 相对于非终结符B 的短语;

b2b1a1a2cb3是句子bbaacb 相对于非终结符S2的短语;注:符号的下标是为了描述方便加上去的。

(2)句子(((b)a(a))(b))的最右推导:

ST (AS)T(A (b))T((SaA)(b))T((Sa (a))(b))T(((b)a(a))(b))相应的语法树是:

w w w .

k h d

a w .

c o m

(3)解:iii*i+↑对应的语法树略。

最右推导:E TT=>F=>FP↑T FE↑T FET+↑T FEF+↑T FEP+↑T FEi+↑TFTi+↑T FTF*i+↑TFTP*i+↑T FTi*i+↑TFFi*i+↑T FPi*i+↑TFii*i+↑T Pii*i+↑Tiii*i+↑12.证明:充分性:当前文法下的每一符号串仅有一个句柄和一个句柄产生式T 对当前符号串有唯一的最左归约T 对每一步推导都有唯一的最右推导T 有唯一的语法树。必要性:有唯一的语法树T 对每一步推导都有唯一的最右推导T 对当前符号串有唯一的最左归约T 当前文法下的每一符号串仅有一个句柄和一个句柄产生式13.化简下列各个文法

(1)解:S→bCACdA→cSA|cCCC→cS |c

(2)解:S→aAB |fA |gA→e |dDAD→eAB→f (3)解:S→ac

14.消除下列文法中的ε产生式(1)解:S→aAS |aS |bA→cS

(2)解:S→aAA |aA |aA→bAc|bc |dAe|de 15.消除下列文法中的无用产生式和单产生式(1)消除后的产生式如下:S→aB |BC B→DB |b C→b

D→b |DB

(2)消除后的产生式如下:

S→SA |SB |()|(S)|[]|[S]A→()|(S)|[]|[S]Bà[]|[S]

(3)消除后的产生式如下:

E →E+T |T*

F |(E)|P↑F |i T →T*F |(E)|P↑F |i F →P↑F |(E)|i P →(E)|i

w w w .

k h d

a w .

c o m

上下文无关文法

第三部分上下文无关语言和下推自动机 前面介绍的有限自动机是计算的初级模型,它所接受的正规语言不太关心字符串自身的结构。上下文无关文法(CFL)是一种简单的描述语法规则的递归方法,语言中的字符串由这些规则产生。所有的正规语言都能用上下文无关文法描述,它也可以描述非正规语言。上下文无关文法描述的语法规则更复杂多变,可以在相当大的程度上,描述高级程序设计语言的语法和其他一些形式语言。 类似正则语言对应的抽象机模型是有限自动机,CFL也有对应的抽象机模型。CFL对应的计算模型是在有限自动机的基础上增加存储空间得到,并被设想成无限空间(对应有限自动机的有限空间),采用了一种简单的管理模式,栈(stack),这种新的计算模型(或抽象机)称为下推自动机(pushdown automata),下推是栈最典型的操作。有必要在下推自动机中保留非确定性,确定型下推自动机不能接受所有的CFL,但给定一个CFG,容易构造一个相应的非确定型下推自动机,它在识别字符串过程中的移动模拟了文法的推导过程,这个过程称为分析(parse)。分析不是一定需要下推自动机来完成。 CFL仍然不够通用,不能包括所有有意义的、或有用的形式语言。采用类似第五章的技术,我们将给出一些不是CFL的简单例子,这些技术也用于解决与CFL相关的判定问题。 6 上下文无关文法 6.1 上下文无关文法的定义 为了描述我们在第二部分考察的各种语言,包括一些非正则语言,我们引入一种语言的递归定义方法,称为文法。文法与我们熟悉的语言的语法描述相近,是描述语言和分析语言的有力工具。 问题:文法的形式化定义似乎可以模仿有限自动机,比如5元组或6元组之类。 例子6.1 正如我们在例子2.16中所见,字母表{a, b}上的回文语言pal可以用下面的递归方法描述: 1.Λ, a, b∈pal 2.对每个S∈pal,aSa和bSb也属于pal 3.pal中不包含其他字符串 如果将上面的符号S看成一个变量,代表了所有我们希望计算(比如某种递归算法)的pal 的元素,那么上面的规则1和规则2可以非正式地重新表述如下: 1.S的值可以是Λ, a, b 2.每个S可以写成aSa或bSb的形式 如果我们用→表示“可以取值为”,则可以写出下面的式子: S→aSa→abSba→abΛba=abba 上面的产生过程可以总结成下面的两组产生式(或称规则): S→a | b | Λ S→aSa | bSb 符号“|”表示“或”的含义。上式的含义是aSa或bSb,而不是a或b,即连接运算的优先级高于“|”。我们使用的这套术语中,小写字母a和b表示终结符,大写字母S表示非终结符,或称变量。总共有5条规则,或产生式(production)。符号S是非终结符,也是起始终结

编译原理 上下文无关文法 语法分析习题(附答案)_东华大学 姚励

作 业 一、选择题 1.、程序中出现的错误常数 3.14.15属于__(A)__。 (A) 语法错误 (B) 词法错误 (C) 语义错误 (D) 警告错误 2、表达式α0 αn 代表____(B)____ 。 (A) 直接推导 (B) 广义推导 (C) 推导 (D) 间接推导 3、文法),},,,{)},(,,*,,({2P +=E F T E i G 其中:产生式P 为: i E F F F T T T T E E |)(|*|→→+→ 则句型T+T*i+F 中的句柄是__(A)___。 (A) T (B) i (C) T*i (D) i+F 4、文法b B a aA A AS AB S →→→,|,|与下列哪个正规式等价__(B)___。 (A)+b aa * (B)b aa * (C)*)(ab (D) *)(ab a ; 第二题:(清华大学年考研试题)已知文法G[S]为: S → dAB A → aA | a B → Bb | ε G[S]产生的语言是什么?(请用自然语言或表达式描述语言特征) 答案:da +b * 第三题:(1) 构造一个文法G ,使得:L(G)={a 2m b m |m>0} (2) 构造一个文法G ,使得:L(G)={a n #b n | n>0} (3) 写出以0开头的8进制无符号整数的文法。

答案:(1) S→aaSb | aab (2) S→aSb | a#b (3) S→0 N N→DN | D D→0|1|2|3|4|5|6|7 四、有文法G[S]: S → a | ( T ) |ε T →T,S | S (1)请给出句子(a,(a,a))的最左、最右推导。 (2)请给出句子(a,(a,a))的短语、直接短语和句柄。答案:(1)最左推导: S=>(T) =>(T,S) =>(S,S) =>(a,S) =>(a,(T)) =>(a,(T,S)) =>(a,(S,S)) =>(a,(a,S)) =>(a,(a,a)) 最右推导: S=>(T) =>(T,S) =>(T,(T)) =>(T,(T,S)) =>(T,(T,a)) =>(T,(S,a)) =>(T,(a,a)) =>(S,(a,a)) =>(a,(a,a))

计算机理论导引实验报告2-上下文无关文法(CFG)

HUNAN UNIVERSITY 计算理论导引实验报告 题目:上下文无关文法(CFG)学生姓名: 学生学号: 专业班级:计算机科学与技术2班 上课老师: 实验日期:2014-1-5

一、实验目的 (2) 二、实验内容.......................................................................................... 错误!未定义书签。 三、实验代码.......................................................................................... 错误!未定义书签。 四、测试数据以及运行结果 (9) 五、实验感想 (13)

一、实验目的 1、掌握上下文无关文法概念。 2、掌握用动态规划算法验证某个字符串w是否属于某上下文无关文法。 二、实验内容 对于任意给定的一个上下文无关文法,并对任意字符串w, 用动态规划算法判断是否有w∈L(G)。 编写一个算法/程序,对于给定的输入,可以在多项式时间内判定ACFG。 三、实验代码 #include // 第一类规则,即规则右边只含有两个变元 class Regular_1 { public: int left; int right_1; int right_2; }; // 第二类规则,即规则右边只含有一个终结符或者空 class Regular_2 { public: int left; int right; }; // 表格类,用来存放中间数据 class Table { public: int size; // 表格的行和列的数量,与输入长度相同 int num_v; // 表格中每个单元格最多含有的数量大小,与cfg的变元数量相同 int ***value; // 用来存放数据的三元数组 Table(int num_v,int num_w); // 构造函数,参数指定输入字符串的长度以及cfg变元的数量 ~Table(); // 析构函数 void SetValue(int i,int j,int num); // 向表格第i行j列追加数据num bool CheckValue(int i,int j,int num); // 检查表格第i行j列是否含有数据num,含有则返回true,否则返回false void Print(); // 打印表格的内容

上下文无关的文法生成器

1 引言 几乎所有程序设计语言都是通过上下文无关文法来定义的。一个原因在于它们拥有足够强的表达力来表示大多数程序设计语言的语法,而且从另外一方面,上下文无关文法又足够简单,使得我们可以构造有效的分析算法来检验一个给定字符串是否是由某个上下文无关文法产生的。具体的例子可以参见LR分析器和LL分析器. 2 定义 上下文无关文法(英语:context-free grammar,缩写为CFG),在计算机科学中,若 一个形式文法G = (V, Σ, P, S) 的产生式规则都取如下的形式:A -> α,则谓之。其中A∈V ,α∈(V∪Σ)*。上下文无关文法取名为“上下文无关”的原因就是因为字符 A 总可以被字符串α自由替换,而无需考虑字符 A 出现的上下文。一个形式语言是上下文无关的,如果它是由上下文无关文法生成的. 正则语言和正则表达式,一个正则表达式可以用来表示一个句子集合(正则语言),且每个正则表达式都可以构造出有限状态自动机来判断任意的句子是否属于这个句子集合。因此,用正则表达式来表示正则语言是精确的、可操作的。 那么,可以用正则表达式来表示程序语言(比如 C 语言)所代表的句子集合吗? 很遗憾,答案是否定的。正则表达式毕竟太简单了,无法来表示程序语言这样复杂级别的句子集合。 为了表示程序语言的句子集合,需要采用表达能力更强大的工具——上下文无关语 法(context-free grammar)。 下面以一个简单的例子来说明什么是上下文无关语法,假设有一种非常非常原始的语言,我们把它成为 X 语言,它的句子只有:主语谓语宾语这样一种结构,主语中 只有我、你、他三个词,谓语中只有吃一个词.宾语中只有饭、菜两个词。我们 把它的语法写出下面这样的形式: 语句 -> 主语谓语宾语 主语 -> 我 主语 -> 你 主语 -> 他 谓语 -> 吃 宾语 -> 饭 宾语 -> 菜 可以看出, X 语言总共只有 6 个句子: { 我吃饭, 我吃菜, ..., 他吃菜 }。也就是说,我们可以用上面这个语法来表示 X 语言这个集合,我们可以从第一行的“语句 -> 主语谓语宾语” 开始,分别将主、谓、宾替换成可用的词,从而将所有满足语法的句子都推导出来。对于任意一个句子,我们也可以将句子和此语法来对比,判断它是否属于满足 X 语言。 上面这个语法中的每一行形如“语句 -> 主语谓语宾语” 的式子称为产生式(production)。 产生式左侧的符号(语句、主语、谓语和宾语)称为非终结符(nonterminal), 代表可以继续扩展或产生的符号,也就是说,当在某条产生式的右边遇到了此非终结符的时候,总是可以用本产生式的右边来替换这个非终结符。 而“我、你、他、吃、饭、菜” 这些符号是 X 语言中的词,无法再产生新的符号了,称为终结符(terminal)。终结符只能出现在产生式的右边,非终结符则左边和右边都可以出现。

上下文无关语言和非上下文无关语言

8 上下文无关语言和非上下文无关语言 8.1 上下文无关语言的泵引理 从第6章到第7章,我们给出了两种描述CFL的模型,CFG和PDA。这两种模型都没有提供直接、明确的方法来判断一个形式语言不是CFL。然而,正如例子6.7对自然语言的一个简单考察,我们发现CFG存在描述能力的局限。本节中,我们精确定义和讨论CFL的一个性质,它类似于正则语言的泵引理。利用这个性质能够发现许多不是CFL的语言。 正则语言的泵引理基于这样的事实,如果一个足够长的输入字符串x导致FA在状态转移中,到达某个状态超过一次,即接受路径上存在回路,根据回路容易将x分成三部分,u是回路之前的字符串,v是回路的字符串,w是回路后的字符串,那么在回路上的多次重复,得到的新的字符串也应该被FA接受,即对任意的m>=0,uv m w被FA接受。如果我们用CFG生成(而不是PDA移动)CFL,容易得到类似的观察。设CFG G的一个推导出现同一个非终结符的嵌套重复,如下面的形式, S?*vAz?*vwAyz?*vwxyz 其中,v, w, x, y, z∈∑*。推导过程中,出现了A?*wAy,我们可以多次重复这个推导过程,如 S?*vAz?*vwAyz?*vw2Ay2z?*vw3Ay3z?*...?*vw m Ay m z 又由于A?*x,因此所有这类字符串vxz, vwxyz, vw2xy2z, ..., vw m xy m z都输入语言L(G)。 为了将上面的观察总结成CFL的泵引理,我们必须说明对于足够长的字符串的推导过程中都会出现非终结符的嵌套重复。同时我们也尽量发现分解得到的5个子串:v, w, x, y, z,的一些性质。这类似于我们处理正则语言的泵引理。 在6.6节,我们证明了所有的CFG产生式都可以改写成Chomsky范式,而不会影响CFG 接受语言的能力(唯一的影响是不能接受空字符,由于此处仅仅关心足够长的字符串,因此这个影响可以忽略)。因此我们的讨论可以局限在Chomsky范式(CNF)表示的CFG,显然这类文法得到的推导树都是二叉树,即每个父节点至多有两个子节点。 我们先定义几个与二叉树相关的概念。路径是一串节点组成的序列,前后节点之间有父子关系;路径的长度是路径包含的节点的个数;二叉树的高度是最长路径的长度。由于非终结符数目有限,如果推导树足够高,那么存在一个路径,某个非终结符在该路径上出现了两次,即出现了前面提到的嵌套重复现象。 引理8.1 任给h>=1,如果二叉树的叶结点个数>2h-1,那么该二叉树的高度>h。 证明:这是一个数学问题。我们用数学归纳法证明它的逆反命题:如果二叉树的高度<=h,那么二叉树的叶节点个数<=2h-1。 1.归纳基础,h=1,此时二叉树只有一个根节点,它也是唯一的叶结点,命题成立。 2.归纳推理,设k>=1时,命题成立。要证明k+1时,命题也成立。设二叉树T的高度为 k+1,则它的根节点的两个子树(以子节点为跟的二叉树)的叶节点数都<=2k-1,因此T 的叶节点数<=2k-1+2k-1=2k。得证。 定理8.1 G=(V, ∑, S, P)是形式为CNF的CFG,共有p个非终结符,则对每个长度>=2p+1的属于L(G)的字符串,都能找到5个字符串v, w, x, y, z满足下面的条件: u=vwxyz |wy|>0 |wxy|<=2p+1 vw m xy m z∈L(G), ?m>=0 证明:根据引理8.1,任何一个生成u的推导树高度>=p+2,即至少存在一个长度>=p+2的路径,不妨设d是其中的一个,显然d的最底部是一个终结符,其上的符号都是非终结符,共

3、上下文无关语言练习

第3章、上下文无关语言习题解答 - 练习 3.1 回忆一下例3.3中给出的CFG G 4。为方便起见,用一个字母重新命名它的变元如下: E →E +T|T T →T ×E|F F →(E )|a 给出下述字符串的语法分析树和派生。 a. a b. a+a c. a+a+a d. ((a)) 答: a. E T F a ??? b. E E T T F F a a a ?+?+?+?+ c. E E T E T F T F a F a a a a a ?+?++?++?++?++ d. ()()()(())(())(())(())E T F E T F E T F a ????????? 3.2 a. 利用语言A={a m b n c n | m,n ≥0}和B={a n b n c m | m,n ≥0}以及例3.20(语言B={a n b n c n | n ≥0}不是上下文无关的),证明上下文无关语言在交的运算下不封闭。 b. 利用(a)和DeMorgan 律(定理1.10),证明上下文无关语言在补运算下不封闭。 证明: a.先说明A,B 均为上下文无关文法,对A 构造CFG C 1 S →aS|T|ε T →bTc|ε //生成b n c n 对B,构造CFG C 2 S →Sc|R|ε R →aRb |ε //生成a n b n 由此知 A,B 均为上下文无关语言。 由例3.20, A ∩B={a n b n c n |n ≥0}(假设m ≤n )不是上下文无关语言,所以上下文无关语言在交的运算下不封闭。

b. 用反证法。 假设CFL 在补运算下封闭,则对于(a)中上下文无关语言A,B ,A ,B 也为CFL 。因为CFL 对并运算封闭,所以A B U 也为CFL ,进而知道A B U 为CFL 。由DeMorgan 定律A B A B =U I ,得出A B I 是CFL 。 这与(a)的结论矛盾,所以CFL 对补运算不封闭。 3.3 设上下文无关文法G : R →XRX|S S →aTb|bTa T →XTX|X|ε X →a|b 回答下述问题: a. G 的变元和终结符是什么?起始变元是哪个? 答:变元是:R ,X ,S ,T ;起始变元是R 。终结符是:a ,b ,ε b. 给出L(G)中的三个字符串。答:ab ,ba ,aab 。 c. 给出不在L(G)中的三个字符串。答:a ,b ,ε。 d. 是真是假:T aba ?。答:假 e. 是真是假:* T aba ?。答:真 f. 是真是假:T T ?。答:假 g. 是真是假:* T T ?。答:假 h. 是真是假:* XXX aba ?。答:真 i. 是真是假:* X aba ?。答:假 j. 是真是假:* T XX ?。答:真 k. 是真是假:* T XXX ?。答:真 l. 是真是假:*X ε?。答:假 m. 用普通的语言描述L(G):

上下文无关文法与语言

第 5 章上下文无关文法及语言 现在我们把注意力从正则语言转移到另外一大类语言上来,它们叫做“上下文无关语言”。这个语言类有着自然、递归的表示方法,这种表示方法叫做“上下文无关文法”。从1960年以来,上下文无关文法一直在编译技术中扮演着重要的角色。它们能够把分析器(一类用来在编译过程中发掘源程序结构的程序)的实现从一种费时的、不通用方式的设计工作转变成为一种能够很快完成的工作。近年来,上下文无关文法也被用来描述文档格式:XML(eXtensible Markup Language 可扩展标记语言)中使用的DTD(Document-Type Definition 文档类型定义)就是用来描述Web上的信息交换格式的。 在本章中,我们将首先介绍上下文无关文法的表示方法,然后将介绍怎样用文法来定义语言。我们将会讨论到“语法分析树”──对一个文法处在它所表示的语言的字符串中结构的图形描述。语法分析树是对一个编程语言的语法分析器的产物,也是通常用来获得程序结构的途径。 上下文无关语言还有另外一种等价的自动机表示叫做“下推自动机”。我们将在第6章介绍下推自动机。虽然它不如有穷自动机重要,但仍然要介绍它,原因是作为一种语言的定义机制来说,它跟上下文无关文法具有等价性,后面在第7章研究如何判定上下文无关语言以及研究上下文无关语言的封闭性时,这种等价性是非常有用的。 5.1 上下文无关文法 这一章的内容将从非形式化地介绍上下文无关文法的表示法开始。形式化的定义会在读者了解到这些文法的一些重要的能力之后给出。届时我们将会说明怎样形式地定义一个文法,并将介绍一种叫作“推导”的过程:它能够决定在一个文法的语言中到底有哪些串。 5.1.1一个非形式化的例子 下面来考虑一个“回文(palindrome)”的语言。“回文”是指正向和反向读起来都一样的串,比如otto或者madamimadam(“Madam, I’m Adam,”引自Eve在Eden的花园里听到的第一句话)。换句话说,串w是一个回文当且仅当w = w R。考虑简单些的情况——只需要描述字母表{0, 1}上的回文,这个语言包括像0110,11011这样的串,也包括空串ε,但不包括像011或0101这样的串。 很容易验证这个0,1上的回文语言L pal不是正则语言,要做到这点只需要使用泵引理即可:假设L pal是一个正则语言,令n是与其相关的常数,考虑回文串w = 0n10n,如果L pal 是正则的,那么我们就能够把w写为w = xyz,其中y由第一组0中的若干个(但至少一个)构成。接下来,如果L pal是正则的话那么xz也应该在L pal里。然而由于xz的两端的0的个数不同,进而可知它不可能是回文串,由此得出的矛盾可以推翻前面关于L pal是正则语言的假设。 对于什么样的0,1串在L pal里,有一个自然的、递归的定义,它从一个最基本的显然属于L pal中的串开始,接着利用一个最直观的思想:如果一个串在L pal里,那么它开头和结尾

上下文无关文法与上下文有关文法

上下文无关文法 形式语言理论中一种重要的变换文法,用来描述上下文无关语言,在乔姆斯基分层中称为2型文法。由于程序设计语言的语法基本上都是上下文无关文法,因此应用十分广泛。 简介 上下文无关文法(Context-Free Grammar, CFG) 在计算机科学中,G = (N, Σ, P, S) 的产生式规则都取如下的形式:V -> w,则称之为上下文无关的,其中V∈N ,w∈(N∪Σ)* 。上下文无关文法取名为“上下文无关”的原因就是因为字符V 总可以被字串w 自由替换,而无需考虑字符V 出现的上下文。一个形式语言是上下文无关的,如果它是由上下文无关文法生成的﹙条目上下文无关语言﹚。 来定义的。另一方面,上下文无关文法又足够简单,使得我们可以构造有效的分析算法来检验一个给定字串是否是由某个上下文无关文法产生的。例子可以参见LR 分析器和LL 分析器。

BNF ﹙巴克斯-诺尔范式﹚经常用来表达上下文无关文法。 文法规则使用相似的表示法。名字用斜体表示(但它是一种不同的字体,所以可与正则表达式相区分)。竖线仍表示作为选择的元符号。并置也用作一种标准运算。但是这里没有重复的元符号(如正则表达式中的星号*),稍后还会再讲到它。表示法中的另一个差别是现在用箭头符号“→”代替了等号来表示名字的定义。这是由于现在的名字不能简单地由其定义取代,而需要更为复杂的定义过程来表示,这是由定义的递归本质决定的。

文法规则是定义在一个字母表或符号集之上。在正则表达式中,这些符号通常就是字符,而在文法规则中,符号通常是表示字符串的记号。我们利用C中的枚举类型定义了在扫描程序中的记号;为了避免涉及到 特定实现语言(例如C 记号。此时的记号就是一个固定的符号,如同在保留字while 中或诸如+或: =这样的特殊符号一样,对于作为表示多于一个串的标识符和数的记号来说,代码字体为斜体,这就同假设这个记号是正则表达式的名字(这是它经常的表示)一样。 上下文无关文法的却利用了与正则表达式中极为类似的命名惯例和运算,二 recursive)。 例子 例子1一个简单的上下文无关文法的例子是:S -> aSb | ε 。这个文法产生了语言{anbn : n ≥ 0} 。不难证明这个语言不是正规的。 例子2 这个例子可以产生变量x,y,z 的算术表达式: S -> T + S | T - S | T T -> T * T | T / T | ( S ) | x | y | z 例如字串"( x + y ) * x - z * y / ( x + x )" 就可以用这个文法来产生。 例子3 字母表{a,b} 上 a 和 b 数目不相等的所有字串可以由下述文法产生: S -> U | V U -> T aU | T aT

基于上下文无关文法的句法分析

基于上下文无关文法的句法分析
常宝宝 北京大学计算语言学研究所 chbb@https://www.doczj.com/doc/c06292790.html,

句法分析导引
以“词”为单位的分析技术
词语切分(segmentation, tokenization) 形态分析(morphological analysis, lemmatization, stemming) 词类标注(part-of-speech tagging) ……
以“句”为单位的分析技术
句法分析(syntactic parsing) ……
以“篇”为单位的分析技术
指代分析(anaphora resolution) ……
句法分析关心句子的组成规律(词如何组成句子?)

句法学(syntax)
In linguistics, syntax is the study of the rules, or "patterned relations", that govern the way the words in a sentence come together. It concerns how different words are combined into clauses, which, in turn, are combined into sentences. From Wikipedia, the free encyclopedia 语言学中研究句子组成规则的学科是句法学

句子成分分析
句子是词的线性序列,但词和词之间结合的松紧程度 并不一样。
今天 上午 我们 有 两 节 课
句子在构造上具有层次性,较小的成分还可以进一步 组成较大的成分。
今天 上午 我们 有 两 节 课 | | | | | | | | |
不同性质的成分可以有不同的句法功能和分布,可以 区分成不同的类型。
名词短语 (可以充当主谓结构中的主语、述宾结构中的宾语等) 两节课 动词短语 (可以充当主谓结构中的谓语等)

上下文无关文法

上下文无关文法 百科名片 形式语言理论中一种重要的变换文法,用来描述上下文无关语言,在乔姆斯基分层中称为2型文法。由于程序设计语言的语法基本上都是上下文无关文法,因此应用十分广泛。 目录[隐藏] 简介 例子 范式 同态映射下的性质 文法形式和文法的相似性 文法的二义性 子文法类 [编辑本段] 简介 上下文无关文法(Content-Free Grammar, CFG) 在计算机科学中,若一个形式文法G = (N, Σ, P, S) 的 上下文无关文法 产生式规则都取如下的形式:V -> w,则称之为上下文无关的,其中V∈N ,w∈(N ∪Σ)* 。上下文无关文法取名为“上下文无关”的原因就是因为字符V 总可以被字串w 自由替换,而无需考虑字符V 出现的上下文。一个形式语言是上下文无关的,如果它是由上下文无关文法生成的﹙条目上下文无关语言﹚。 上下文无关文法重要的原因在于它们拥有足够强的表达力来表示大多数程序设计语言的语法;实际上,几乎所有程序设计语言都是通

上下文无关文法 过上下文无关文法来定义的。另一方面,上下文无关文法又足够简单,使得我们可以构造有效的分析算法来检验一个给定字串是否是由某个上下文无关文法产生的。例子可以参见LR 分析器和LL 分析器。 BNF ﹙巴克斯-诺尔范式﹚经常用来表达上下文无关文法。 文法规则使用相似的表示法。名字用斜体表示(但它是一种不同的 上下文无关文法 字体,所以可与正则表达式相区分)。竖线仍表示作为选择的元符号。并置也用作一种标准运算。但是这里没有重复的元符号(如正则表达式中的星号*),稍后还会再讲到它。表示法中的另一个差别是现在用箭头符号“→”代替了等号来表示名字的定义。这是由于现在的名字不能简单地由其定义取代,而需要更为复杂的定义过程来表示,这是由定义的递归本质决定的。 同正则表达式类似,文法规则是定义在一个字母表或

第二章文法和形式语言

第二章文法和形式语言 《编译原理》课程组 计算机工程学院 第二章文法和形式语言 2.1 文法的直观概念 2.2 符号和符号串 2.3 文法和语言的形式定义 2.4 文法的类型 2.5 上下文无关文法机器语法树 2.6 句型分析 2.7 文法的实用限制 第2章文法和语言 【学习目标】 本章目的是为语言的语法描述寻求工具 ◇掌握对源程序给出精确无二义(严谨、简洁、易读)的语法描述手段之一——文法。 ◇对形式语言的理论有一个初步基础 ◇根据语言文法的特点指导语法分析的过程 本章将讨论词法分析程序的设计原则,单词的描述技术,识别机制及词法分析程序的自动构造原理。 第2章文法和语言 【教学重点】 概念:文法,推导,直接推导,最左(右)推导,产生式,句型,短语,直接短语,句柄,语法树,规范推导,二义文法等 4种文法的定义、文法的构造和文法的推导 语法树的构造和最左(右)推导; 二义文法、二义性的证明; 句型分析; 2.1 文法的直观概念 一、语言概述 语言是由符合语法的句子组成的集合。 –汉语-- 所有符合汉语语法的句子的全体 –英语-- 所有符合英语语法的句子的全体 –程序设计语言-- 所有该语言的程序的全体

每个句子构成的规律 研究语言每个句子的含义 每个句子和使用者的关系 一、语言概述(续1) 研究程序设计语言 每个程序构成的规律 每个程序的含义 每个程序和使用者的关系 语言研究的三个方面 语法Syntax 语义Semantics 语用Pragmatics 一、语言概述(续2) 语法:指语言的一组规则,用它可以形成和产生一个合适的程序。 –如何由基本字符构成一个个单词; –如何由一系列单词构成程序 语法只定义什么样的符号序列是合法的,而不表达这些符号及符号序列的含义 语义:明确程序各部分的含义 –静态语义:由一系列限定规则组成,并确定哪些合乎语法的程序是合适的; –动态语义:表明程序要做些什么,要计算什么 一、语言概述(续3) 形式语言:只考虑语法而不考虑语义的符号语言。 每种语言具有两个可识别的特性, –语言的形式 –该形式相关联的意义 “形式”是指这样的事实:语言的所有规则只以什么符号串能出现的方式来陈述。 形式语言理论是对符号串集合的表示法、结构及其特性的研究,是程序设计语言语法分析研究的基础。 语言可以看成在一个基本符号集上定义的,按一定规则构成的基本符号串组成的所有集合。 二、文法的直观概念 表达语言时,一般无法穷尽语言的所有句子,常用规则加以描述 例:汉语句子的构成规则: 〈句子〉∷=〈主语〉〈谓语〉 〈主语〉∷=〈代词〉|〈名词〉 〈代词〉∷= 我| 你| 他 〈名词〉∷= 王明| 大学生| 工人| 英语 〈谓语〉∷=〈动词〉〈直接宾语〉 〈动词〉∷= 是| 学习 〈直接宾语〉∷=〈代词〉|〈名词〉

上下文无关文法的基本概念

上下文无关文法的基本概念 定义:上下文无关文法G是一个四元组G = (N,T,P,S),其中 N是非终结符的有限集合; T是终结符或单词的有限集合,它与N不相交; P是形如A →α的产生式的有限集合,其中A∈N,α∈V﹡,V=T∪N S是N中的区分符号,称为开始符号或句子符号。V中的符号称为文法符号,包括终结符和非终结符。 特殊情况:A →ε空产生式 例如,if语句结构的文法产生式表示: stmt →if expr then stmt else stmt Backus - Naur范式(Backus-Naur form)或BNF文法 符号的使用约定: 符号是终结符: 字母表中比较靠前的小写字母,如a,b,c等。 操作符,如+、-等。 标点符号,如括号、逗号等。 数字0,1, (9) 黑体串,如id、if等。 符号的使用约定: 下列符号是非终结符: 字母表中比较靠前的大写字母,如A、B、C等。 字母S,它常常代表开始符号。 小写斜体名字,如expr、stmt等。 字母表中比较靠后的大写字母,如X、Y、Z等,表示文法符号,也就是说,可以是非终结符也可以是终结符。 符号的使用约定: 字母表中比较靠后的小写字母,如u,v,…,z等,表示终结符号的串。 小写希腊字母,如α、β、γ等,表示文法符号的串。因此,一个通用产生式可以写作A →α,箭头左边(产生式左部)是一个非终结符A,箭头右边是文法符号串(产生式右部)。 符号的使用约定: 如果A →α1、A →α2、…、A →αk 是所有以A为左部的产生式(称为A产生式),则可以把它们写成A →α1|α2|…|αk,我们将α1、α2、…、αk称为A的候选式。除非另有说明,否则第一个产生式左部的符号是开始符号。 例1考虑下面的关于简单算术表达式的文法,非终结符为<表达式>和<运算符>,终结符有ID,+,-,*,/,↑,(,)。产生式有 <表达式> → <表达式> <运算符> <表达式> <表达式> → (<表达式>) <表达式> → - <表达式> <表达式> →ID <运算符> → + <运算符> → - <运算符> → * <运算符> → / <运算符> →↑

第二章文法和语言的概念和表示

第二章文法和语言的概念和表示 本章概述 本章中,我们将概述高级程序语言的结构和主要的共同特征,并介绍程序语言的语法描述方法。 主要学习内容:程序设计语言的定义,高级语言的一般特性,高级语言的语法描述,上下文无关文法,语法分析树和二义性,乔姆斯基文法体系。 学习目标:理解程序语言的词法、语法和语义等概念,进一步掌握高级程序设计语言的一般结构和主要共同特征,使学生具有必要的基础知识;理解文法和语言的一些基本概念,如文法的定义和构造、句型、句子、语言、推导、语法树等。 学习重点和难点:语法,语义,文法的构造。 2.1 概述 显然,用高级语言编程比用低级语言来得方便,但要解决两个问题: 1.计算机怎样懂得高级语言程序,这就需要一个翻译程序实现从源程序到目标程序的转换。 2.用什么方法来精确定义高级语言,即怎样精确描述高级语言。 要构造一个编译程序,应深刻理解被编译的源语言的结构(即词法和法)及其含义(即语义),同时要弄清源语言的语法规则和语义规则是采用什么理论或什么方法来描述的。 当我们表述一种语言时,无非是说明这种语言的句子,如果语言只含有穷多个句子,则只需列出句子的有穷集就行了,但对于含有无穷句子的语言来讲,存在着如何给出它的有穷表示的问题。 以自然语言为例,人们无法列出全部句子,但是人们可以给出一些规则,用这些规则来说明(或者定义)句子的组成结构,比如汉语句子可以是由主语后随谓语而成,构成谓语的是动词和直接宾语。 任何语言均可看作一个集合。这个集合中的每个元素都是在一定符号集(字母表)上的一个符号串。 对于自然语言来说,它们是定义在某个字母表上的句子的集合。 对于程序语言来说,它们也是定义在某个字母表上的句子的集合。这里的句子,就是一个源程序。 通常,源程序是由关键字、标识符、常数、运算符以及一些界限符组成。这些语法成分统称为单词或单词符号。 单词符号是语言中具有独立意义的最基本单位。语言的单词符号是由词法规则所确定的,即词法规则规定了单词符号的形成规则。 “我是大学生”是汉语的一个句子。 用语法来描述: 〈句子〉∷=〈主语〉〈谓语〉 〈主语〉∷=〈代词〉|〈名词〉 〈代词〉∷=我|你|他 〈名词〉∷=王明|大学生|工人|英语 〈谓语〉∷=〈动词〉〈直接宾语〉 〈动词〉∷=是|学习 〈直接宾语〉∷=〈代词〉|〈名词〉 有了这一组规则以后,按照如下方式用它们导出句子: 开始去找∷=左端的带有〈句子〉的规则并把它由∷=右端的符号串代替,这个动作表示成: 〈句子〉?〈主语〉〈谓语〉, 然后在得到的串〈主语〉〈谓语〉中,选取〈主语〉或〈谓语〉,再用相应规则的∷=右端代替之。比如,选取了〈主语〉,并采用规则〈主语〉∷=〈代词〉,那么得到:〈主语〉〈谓语〉?〈代词〉〈谓语〉, 重复做下去,这样句子“我是大学生”的导出的全部动作过程是: 〈句子〉?〈主语〉〈谓语〉 ?〈代词〉〈谓语〉

第二章编译原理习题

例题2.1 是非题 1.因名字都是用标识符表示的,故名字与标识符没有区别。() 2.正规文法产生的语言都可以用上下文无关文法来描述。() 3.上下文无关文法比正规文法具有更强的描述能力。() 分析 1.标识符是高级语言中定义的字符串,一般是以英文字母开头(包括大小写字母)的,由数字、字母和一些特殊字符(如下划线等)组成的一定长度(不同的高级语言对标识符的长度的规定不同)的字符串,它只是一个标志,没有其它含义。名字是用标识符表示的,但名字不仅仅是一个字符串,它还具有属性和值,就象一个人的名字不仅仅是一个符号,对于认识这个人的人来说,它还代表着这个人,因此本题错。 2.乔姆斯基把文法分成4种类型,从4种文法的形式化描述来看,它们的差别主要在对规则形式的约束上。0型文法的规则形式是:每个产生式α→β都满 足,α∈(V N ∪V T )*且至少含有一个非终结符,β∈(V N ∪V T )*,0型文法也叫短语 文法。1型文法的规则形式是:每个产生式α→β均满足|α|≤|β|,仅仅S→ε例外,且S不得出现在任何产生式的右部,1型文法也称上下文有关文法,从两种文法的规则形式来看,1型文法对规则形式的约束比0型文法强,1型文法能描述的语言0型文法也能描述,而0型文法能描述的语言1型文法不一定能够描述,1 型文法是0型文法的特例。2型文法的规则形式是A→β,其中A∈V N ,β∈(V N ∪ V T )*,2型文法也称上下文无关文法,分析2型文法的规则形式不难发现,2型文法是1型文法的特例,也是0型文法的特例。3型文法的规则形式是A→αB或 A→α,其中α∈,A、B∈V N ,3型文法也称正规文法,可以看出3型文法是前面3种文法的特例。从上面的分析可以,正规文法是上下文无关文法的特例,可以用正规文法描述的语言,其正规文法描述的形式也是上下文无关文法的描述形式,即可以用上下文无关文法描述,因此本题对。 3.上下文无关文法是2型文法,正则文法是3型文法,从上题的分析可以看出,3型文法是2型文法的特例,3型文法可以描述的语言都可以用2型文法来描述,而2型文法可以描述的语言则不一定能用3型文法来描述。即2型文法比3型文法的描述能力强,因此本题对。 例题2.2 填空题 1.程序语言是由()和()两方面定义的。 3.文法G所产生的句子的全体的(),将它记为()

相关主题
相关文档 最新文档