上往建站提供服务器空间服务商，百度快照排名，网站托管，百度推广运营,致力于设计外包服务与源代码定制开发，360推广，搜狗推广,增加网站的能见度及访问量提升网络营销的效果,主营：网站公司,百度推广公司电话,官网搭建服务,网站服务企业排名,服务器空间,英文域名等业务，专业团队服务，效果好。

黄骅小程序制作【黄骅企业邮箱】黄骅网站外包、黄骅微信商城开发、黄骅网店美工、黄骅淘宝设计

黄骅市，河北省辖县级市，由沧州市代管。因纪念1943年牺牲于此的冀鲁边区司令员、革命烈士黄骅而得名。位于河北省东部，渤海湾西岸，总面积1544.7平方公里， [94]  常住人口46.7万人（2016年），辖3个街道、8个镇、3个乡。市人民政府驻骅西街道渤海西路777号。

黄骅市地处华北平原东端，地势平坦。属暖温带半湿润季风气候，年平均气温12.9℃，年平均降水量567.8毫米。东临渤海，有子牙新河、捷地减河等12条河道入海，地下水多为苦咸水，盐碱地分布广泛。矿产资源以石油、天然气、地热为主。

黄骅市处于环渤海经济圈中部位置和环京津枢纽地带，是沧州渤海新区的核心区，渤海新区管委会、南大港产业园区（农场）、中捷产业园区（农场）、沧州临港经济技术开发区、长芦盐场坐落于境内，是原盐、石化、五金、汽车等工业生产基地。主要种植小麦、玉米、棉花等作物，特产黄骅冬枣，渔业以海洋捕捞、海水养殖为主。黄骅市交通区位条件优越，境内有国际深水亿吨大港黄骅港，是河北省东出西联的出海口和桥头堡，朔黄铁路、沧港铁路、邯邢黄铁路联通腹地，荣乌高速、黄石高速、沿海高速、205国道、228国道、307国道、337国道等干线公路穿境而过。2019年，财政收入和公共预算收入分别增长8.4%和10%；固定资产投资增长6.9%；规上工业增加值增长6%；实际利用外资4428万美元，同比增长23.5%，创历史新高；城镇、农村居民人均可支配收入分别增长8%和9%。 [1] 

黄骅市先后获得国家卫生城市 [2]  、国家园林城市 [3]  等荣誉称号。

第二轮开始时，有L={ε }和S={s;}。产生式(1)现在让我们可以把wcs;添加到S 中，因为s;已经在S 中了。也就是说，在产生式(1)的右部中，终结符w和c只能代表它们本身，语法分类<S>则可以被替换为语言S 中的任意字符串。因为目前s;是S 中唯一的字符串，所以我们只能作出这一个选择，而这一选择的结果就是wcs;。

产生式(2)添加了字符串{}，因为终结符{和}只能代表它们自身，不过语法分类<L>可以代表语言L 中的任意字符串，而此刻L 中只含有ε。

因为产生式(3)的右部只由终结符构成，所以它决不会产生除s;之外的字符串，因此从现在开始就可以忘掉该产生式了。同样，产生式(5)也不会产生除ε 之外的字符串，所以在本轮及以后的轮次中也可以忽略它。

最后，当我们用ε 代替<L>并用s;代替<S>之后，产生式(4)就为L 产生了字符串s;。在第二轮结束的时候，语言S＝{**s;wcs;,{}**}，而语言L={ε;s;}。

在下一轮中，可以使用产生式(1)、(2)和(4)产生新的字符串。产生式(1)中替换<S>的选择有3种，分别是s;、wcs;和{}。用s;替换后得到的字符串是语言S 中已经具有的，不过替换了另两个字符串后得到的是新字符串wcwcs;和wc{}。

对产生式(2)而言，可以用ε 或s;替换<L>，为语言S 得出旧字符串{}和新字符串{s;}。在产生式(4)中，可以用ε 或s;替换<L>，并用s;、wcs;或{}替换<S>，这给语言L带来了一个旧字符串s;，以及5个新字符串wcs;、{}、s;s;、s;wcs;和s;{}。1

1我们非常关心用字符串替换语法分类的方式。假设经过每一轮替换，语言L和S都和它们在上一轮结束时的定义保持不变。每个产生式的右部都要进行替换。这些右部可以为左部的语法分类产生新的字符串，不过在同一轮替换中，我们不会在一个产生式的右部使用由另一个产生式新构建的字符串。但这也没关系，所有要生成的字符串最终都会在某一轮中生成，不管我们是立即在右部中循环使用新字符串，还是等待在下一轮中再使用新字符串。

这样语言就成了S={s;,wcs;,{},wcwcs;,wc{},{s;}}和L={ε ,s;,wcs;,{},s;s;,s;wcs;,s;{}}。我们可以按照自己的意愿继续这一过程。图11-7总结了前3轮的情况。

图 11-7　前3轮每轮产生的新字符串

正如示例11.4中那样，由文法定义的语言可能是无限的。如果语言是无限的，我们就不能一一列出所有字符串。能做到的最佳做法就是按轮次枚举这些字符串，就像示例11.4中一开始所做的那样。该语言中的任何字符串都将在某轮出现，不过在任何一轮都不可能产生出所有的字符串。可以被放进语法分类<S>的语言中的那些字符串组成的集合，就形成了（无限）语言L(<S>)。

习题

1. 在示例11.4中，第四轮添加的新字符串都有哪些？

2. * 在示例11.4的第i 轮替换中，为各语法分类产生的新字符串中最短的字符串各是什么？为下列语法分类产生的最长新字符串又分别是什么？

(a) <S>

(b) <L>？

3. 分别使用下列图中的文法按轮次生成平衡括号串。

(a) 图11-3

(b) 图11-4

这两种文法在相同轮次中是否会生成相同的平衡括号串？

4. 假设每个以某语法分类<S>为其左部的产生式在其右部中也含有<S>，那么为什么L(<S>)为空？

5. *在如本节所描述的方式按轮次生成字符串时，为语法分类<S>生成的新字符串只可能是通过替换某有关<S>的产生式中右部的语法分类得到，满足至少有一个被替换的字符串是在上一轮中新发现的。解释一下为什么楷体标记的条件是正确的。

6. ** 假设我们想分辨某个特定的字符串s 是否在某语法分类<S>的语言中。

(a) 解释一下，为什么如果在某轮中所有为任意语法分类生成的新字符串都比s 长，而且s尚未为L(<S>)生成，s 就不可能被放入L(<S>)中。提示：利用习题(5)。

(b) 解释一下，为什么在有限轮次的替换后，一定没法继续生成不长于s 的新字符串。

(c) 使用(a)和(b)的结论设计一种算法，接受某文法、该文法的一种语法分类<S>，以及某个终结符串s，并分辨出s是否在L(<S>)中。

11.4　分析树

正如我们已经看到的，通过反复应用产生式，可以为某语法分类<S>得出字符串s属于语言L(<S>)的结论。从由右部中不含语法分类的依据产生式得到的字符串开始。然后，对已经从各语法分类得到的字符串“应用”产生式。每次应用都要用字符串替换产生式右部中出现的各语法分类，并构造出属于产生式左部中语法分类的字符串。最终，我们将通过应用左部为<S>的产生式来构造字符串s。

把s在L(<S>)中的“证明”画成一棵称作分析树（parsetree）的树往往是很实用的。分析树的节点都是带标号的，要么是终结符，要么是语法分类，要么是符号ε。叶子节点只会被标记为终结符或符号ε，而内部节点只可能用语法分类作为标号。

每个内部节点v 都表示产生式的应用。也就是说，一定存在某个产生式同时满足下列条件：

1. 标号v 的语法分类是该产生式的左部；

2. v 的子节点的标号从左往右构成了该产生式的右部。

黄骅小程序制作【黄骅企业邮箱】黄骅网站外包、黄骅微信商城开发、黄骅网店美工、黄骅淘宝设计

上往建站提供搭建网站，域名注册，官网备案服务，网店详情页设计，企业网店，专业网络店铺管理运营全托管公司咨询电话，服务器空间，微信公众号托管，网页美工排版,致力于域名申请，竞价托管，软文推广，全网营销,提供标准级专业技术保障，了却后顾之忧,主营：虚拟主机，网站推广，百度竞价托管，网站建设，上网建站推广服务，网络公司有哪些等业务，专业团队服务，效果好。

服务热线：400-111-6878 手机微信同号:18118153152（各城市商务人员可上门服务）