三河网站推广【三河办理400电话】三河SEO优化、三河微信公众号APP客户端小程序开发、三河网站托管、三河APP开发

三河网站推广【三河办理400电话】三河SEO优化、三河微信公众号APP客户端小程序开发、三河网站托管、三河APP开发

三河古镇，古名鹊渚、鹊尾（渚）、鹊岸，是中国历史文化名镇，国家AAAAA级旅游景区，位于安徽省合肥市肥西县南端，地处肥西、庐江、舒城交界处，古镇总面积2.9平方公里。 [1-2] 

三河古镇原是巢湖中的高洲，因泥沙淤积，渐成陆地。南北朝后期称三汊河，明、清置三河镇。 [2] 

三河古镇有丰乐河、杭埠河、小南河在境内汇合，经新河向东流约15公里入巢湖。镇内有古城墙、古炮台、太平军指挥部旧址、英王府、一人巷、万年台、李府粮仓、鹤庐、刘同兴隆庄等历史遗迹，是庐剧的发源地，古镇有米饺、牛皮糖、酥糖、麦芽糖、茶干、米酒等特产。 [3] 

为表达对全体医护人员的敬意和感谢，自疫情结束恢复运营之日起至2020年12月31日，三河古镇景区所有收费景区将面向全国医护工作者实行免费游览政策。

11.4　分析树

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

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

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

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

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

示例 11.5

图11-8展示了一棵基于图11-2所示文法的分析树。不过，在这里我们把语法分类<表达式>、<数字>和<数码>分别简称为<E >、<N >和<D >。该分析树表示的字符串是3* (2+14)。

例如，这棵分析树的根节点及其子节点就表示产生式

<E >→<E >*<E >

就是图11-2中的产生式(6)。根节点的最右子节点及其子节点形成了产生式<E >→(<E >)，或者说是图11-2中的产生式(5)。

图 11-8　使用图11-2所示文法的字符串3*(2+14)对应的分析树

11.4.1　分析树的构建

每棵分析树都表示某一终结符串s，我们可将该串称为这棵树的产出（yield）。串s 由相应分析树所有叶子节点的标号按照从左到右的次序排列而成。此外，通过对分析树进行前序遍历并只依次列出那些属于终结符的标号，我们也可以得到这一产出。例如，图11-8所示分析树的产出就是3*(2+14)。

如果树只有一个节点，那么该节点的标号就只能是某个终结符或者ε，因为它是个叶子节点。如果该树不止有一个节点，那么根节点的标号就是语法分类，因为在一棵有两个或更多个节点的树中，根节点总是个内部节点。而且该语法分类的字符串中总是会包含该树的产出。与某给定文法对应的分析树的归纳定义如下所述。

依据。对文法中的每个终结符x来说，存在一棵只含一个标号为x的节点的树。当然，该树的产出就是x。

归纳。假设我们有产生式<S>→X1X2…Xn，其中各个Xi 要么是终结符，要么是语法分类。如果n=0，也就是说，该产生式实为<S >→ε，那么就有一棵像图11-9这样的树。其产出为ε，而且根节点为<S >，因为有该产生式，所以空串ε 显然是在L(<S >)中的。

图 11-9　由产生式<S >→ε 得到的分析树

现在假设<S>→X1X2…Xn 而且n≥1。我们可以按照如下方式，对每个i=1、2、…、n 而言，为各个Xi 选择树Ti 。

1. 如果Xi 是终结符，就必须选择标号为Xi 的单节点树。如果有两个或多个X是同一终结符，就必须为该终结符的每次出现选择具有相同标号的不同单节点树。

2. 如果Xi 是语法分类，我们可以选择任何已经构建好的以Xi 作为根节点标号的分析树，然后构建一棵像图11-10这样的树。也就是说，我们创建的根节点标号是该产生式左部的语法分类<S>，而这棵树根节点的子节点从左到右依次是为X1、X2、…、Xn 选择的树的根节点。如果有两个或多个X 是相同的语法分类，我们也许要为各语法分类选择相同的树，但是必须在该树每次被选中时为其生成不同的副本。我们还可以为同一语法分类的不同出现选择不同的树。

图 11-10　利用产生式和其他分析树构建分析树

示例 11.6

我们来研究一下图11-8中分析树的构造，看看它的结构是如何模仿证明字符串3*(2+14)在L(<E>)中的过程的。首先，可以为该树中的各个终结符构造一棵单节点树。然后图11-2中第(1)行的产生式组说明了10个数码都是属于L(<D>)的长度为1的字符串。我们用到其中的4个产生式创建图11-11所示的4棵树。例如，我们利用产生式<D>→1按照如下方式创建了图11-11a中的分析树，为右部中的符号1创建一棵只有一个标号为1的节点的树，然后，创建一个标号为<D>的节点作为根节点，并以我们为1选择的树的根节点（也是唯一的节点）作为其子节点。

图 11-11　使用产生式<D>→1以及相似的产生式构建的分析树

下一步是要利用图11-2中的产生式(2)，或者说是<N>→<D>，来揭示数码就是数字这一事实。例如，可以选择图11-11a所示的树替换产生式(2)右部中的<D>，得出图11-12a所示的树。图11-12中的另两棵树也是用相似的方式产生的。

图 11-12　使用产生式<N>→<D>构建的分析树

现在可以利用产生式(3)，也就是<N>→<N><D>了。我们将会为右部中的<N>选择图11-12a所示的树，并为<D>选择图11-11d所示的树。还要为左部创建一个标号为<N>的新节点，并为该节点指定两个子节点，也就是选中的两棵树的根节点。得到的树如图11-13所示。该树的产出是数字14。

图 11-13　用产生式<N>→<N><D>构建的分析树

三河网站推广【三河办理400电话】三河SEO优化、三河微信公众号APP客户端小程序开发、三河网站托管、三河APP开发