RFC1058中文
Network Working Group C. Hedrick Request for Comments: 1058 Rutgers University
June 1988
翻译：马儿快跑
2002.4
路由信息协议（Routing Information Protocol）
本备忘录的状态
本备忘录描述了一个已经存在的协议，它用以在网关(gateways)和其他主机(hosts)间交换路由信息。它被作为在Internet开发网关软件的基础。引用本备忘录没有限制。
目录
1. 简介
1.1. 协议的局限性
1.2. 本文档的组成
2. 距离向量算法
2.1. 拓扑结构改变时的处理
2.2. 避免不稳定性
2.2.1. 水平分割
2.2.2. 触发更新
3. 协议详述
3.1. 信息格式
3.2. 考虑地址
3.3. 记时器
3.4. 输入进程
3.4.1. 请求
3.4.2. 回应
3.5. 输出进程
3.6. 兼容性
4. 控制功能
综述
本备忘录包含以下内容：
- 说明一种已经被广泛使用而没有被正式成文的路由协议和算法，
- 改进算法以提高其在大型网络中的稳定性。这些改进不会引起已有网络的不兼容，这些改进可以和原有的实现方式容为一体。
- 建议一些功能以提供更好的配置和控制，这些功能用以解决在NSFnet通讯中显示出的问题。当然，它们应当提供更通用的功能。
这里提到的路由信息协议(RIP)，是由伯克莱(Berkeley)4.3的“routed”项目发布的。当然还有很多其他的实现方式。很不幸，多种实现在细节上有很多不同。这里描述的是各个实现功能上的组合。我们相信根据本文设计的程序可以和其他RIP的实现协同工作。
本文对尺度(metrics)增加采取了与大多数实现不同的视角。通过对本地网段的尺度做相应的调整，保持了和其他实现方式的兼容性。详见3.6节
1. 简介
本备忘录描述了一种使用Bellman-Ford(或称为距离向量)算法的协议。这种算法早先在ARPANET上被用于计算网络路由信息。具体的协议描述、包格式是基于伯克莱(Berkeley) UNIX的“routed”项目。这已经成为了网关和主机间交换路由信息的事实标准，用以不同厂商的网关产品间通讯。虽然，同一厂商的产品往往使用其自己的协议。
这个协议是作为“内部网关协议(interior gateway protocol)”而使用的。如当前Internet般的大型网络，是不可能在整个网络上使用一种单一的路由协议的。网络将被分成为一系列的“自治系统(autonomous systems)”。每个自治系统都被赋予为一个实体，提供技术上和管理上的控制。每个自治系统可以有不同的路由方式。在自治系统中使用的路由协议被称为内部网关协议(IGR)。另一种路由协议面向自治系统，最早的这类协议是“EGP(外部网关协议/exterior gateway protocol)”,目前还在Internet上使用。这些协议现在被叫做自治系统间(inter-AS)路由协议。RIP在同类协议中被设计为适合于中等规模网络使用。适合于那些网络间连接线路的速度差别不大的网络作为IGP。关于RIP适用条件的详细说明见：[3] Braden and Postel。
RIP使用一类叫做“距离向量”的算法。这类算法最早是由Ford and Fulkerson [6]提出的。所以这也被称为Ford-Fulkerson算法。有时也被称为Bellman-Ford算法，这是因为这一描述是基于Bellman公式。(这一领域的介绍见[1]）其描述文档见[2]，该文讲述了路由算法的数学模型，并描述且证明了算法中的变量，及其他相关内容。该算法的最初实现在1969年被用于ARPANET。这一协议家族还包括Xerox网络协议(XNS),PUP协议(见[4])。一个较新的版本使用了XNS的结构，并更名为路由信息协议(见[7])。Berkeley的算法与其大致相同，不过将XNS的地址转换为一种更通用的格式用以包括IP等地址，并将路由更新时间限定在30秒。因为其相似性，RIP这一名称被用于XNS协议和其他协议中。
RIP被设计为在基于IP的Internet中使用。Internet可以被理解成通过网关相连的一系列网络。在这里网络可以是点对点的连接，或复杂些的网络如以太网或ARPANET。主机和网关使用IP地址在网络中出现。路由是指主机和网关决定向何处发送包的方法。当目标在主机或网关直接相连的网络时，包将被直接发送到目标。令人感兴趣的是，当目标不直接可达时，主机或网关将试图将包发往更靠近目标的网关。路由协议的目标很简单：支持需要被路由的信息。
1.1. 协议的局限性
本协议不解决所有的路由问题。如上所述，是被设计为适合中等规模网络做为IGP使用。另外，还要注意一下限制：
- 协议限定网络最大路径为15跳。设计者认为这一协议不适合于大型网络。注意，这一限定声明是在假设经过每个网络的成本(cost)为1，正如RIP一般配置的情况。如果管理员选择了较大的成本,15的上限可能成为问题。
- 协议使用“记数到无穷大”表示一些特殊情况(将在下一节中说明)。如果系统中有几百个网络，路由回路(routing loop)将会充斥其间。解决路由回路或需要很多时间(如果路由更新的频率受到限制)，或需要很多带宽(如果每次改变都发送更新)。这样在回路被纠正前会消耗很多带宽。我们相信，在现实情况下，这不会产生问题(除非是低速线路)。即使这样，这个问题还需要被认真对待，而且使用多种预防措施来避免在大多数情况下出现这样的问题。
- 协议使用固定的“尺度(metrics)”来描述不同的路径。当路径选择需要基于实时参数，如：延迟、可靠性、负载时是不适合的。使用这类实时参数会明显产生不稳定性。
1.2. 本文档的组成
本文档的主体内容分为两部分，占据下面两章：
2 从概念上了解距离向量算法的发展和原理。
3 实际协议的描述
这两章大致按这样的范围叙述。第2章给出了算法大致的数学模型，一开始先描述简单算法，然后再逐渐细致，呈“螺旋上升”的方法。第3章描述实际的协议，将第2章的内容具体化。通过第3章的描述，就可以实现整个RIP。
2.距离向量算法
路由的任务就是找到一条从源到目标的路径。在IP“Catenet model”中，这被简化为寻找网络间的网关。当通讯处于一个网络或子网时，由该特定的网络来解决路由问题。如以太网和ARPANET都定义了方法，使在一个网络中，任何源能够和指定的目标通讯。当源和目标不在同一网段时，IP路由才变的必要。这时，通讯必须通过连接网络的网关。当网络不邻接时，通讯将通过一系列用网关相连的网络。当通讯到达与目标处于同一网络的网关后，将使用该网络自身的方法到达目标。
在本章中，术语“网络(network)”包含单一广播网络(如以太网)、点对点线路或ARPANET。其关键点是网络被作为IP的单一实体。即便在不需要路由(如点对点线路)，或路由被设置为对IP透明的情况，都允许IP将整个网络作为是一个完全连接的系统(如以太网或ARPANET)。这里的术语“网络”和在讨论IP地址时使用的“网络”有所不同。在讨论IP地址时，一个网络可能被分为多个“子网(subnet)”。而在这里，我们对子网同样使用“网络”这个术语。
在网络间寻找路径有多种方法。最常用的分类方法是按照网关间交换信息的不同类型。距离向量算法仅交换少量信息，每个参与路由协议的实体(网关或主机)都保留所有目标的信息。通常，同一个网络中所有实体的信息被汇总成一个路由项，用以表示到达该网络上所有目标的路径。这是因为对IP而言，一个网络内的路由是不存在的。路由数据中的每一个项都包含了到达目标的下一跳网关，以及衡量到达目标距离的“尺度(metric)”。距离没有明确的概念，可以是到达目标的延迟、或发送信息的货币成本等等。距离向量算法的得名来源于比较不同的距离来得到最佳路径。此外，信息只在邻接，即共享同一网络的实体间交换。
虽然路由通常是基于网络信息，有时也需要保持到达独立主机的路径信息。RIP协议对待网络与主机没有差别。不管是网络还是主机，RIP都交换其信息(但是，有一些实现不支持主机路由，见3.2节)。事实上，在数学模型中将其做转换是很方便的。当在抽象描述算法的时候，最好将到达一个网络的路由项看作为所有连接该网络的实体项的缩写。这是因为在IP层，一个网络内部没有层次结构。我们也将一个给定网络中的所有项赋予同样的距离。
上面曾说到每个实体都要为每个路由项保留所有的信息。在实际中一般需要保留以下信息：
- 地址：该算法的IP实现中，必须有主机或网络的IP地址。
- 网关：到达目标的路径上的第一个网关。
- 接口：到达第一个网关的物理网段。
- 尺度：表示到达目标距离的数值。
- 时间：表示自从该项上次更新以来的时间。
此外还包括多种标志和内部信息。这些信息在初始时包含了直接相连的实体。当从邻居网关接收到信息后，信息将会被更新。
主机和网关之间的信息主要通过更新来传递。每个参与路由协议的实体都将自己当前的路由信息作为更新信息发送。这样仅通过与邻居实体交换信息，就可以得到整个系统的最佳路径。算法将在下一节中描述。
如上所述，路由的任务是寻找到达最终目标的路径。距离向量算法是基于一张给出系统内各目标最佳路径的表。为了定义什么样的路径是最好的，需要对路径进行衡量。这就是“尺度(metric)”。
在简单系统中，常常使用的尺度是计算信息需要经过多少个网关。复杂些的系统中，将信息传输所需的延迟、所需的成本等作为尺度。还需要将各个跳数的“成本”相加。
如果实体i、j直接相连而不通过其他网关，公式d(i,j)和i、j间的费用相关。在正常情况下，给定网络上的所有实体被平等看待，其d(i,j)表示使用该网络的成本，且其值相同。衡量一条完整的路径，要将各跳的成本相加。在本备忘录中，设定成本为正整数。
公式D(i,j)表明实体i、j间的最佳尺度。这在每一对实体间都需定义。d(i,j)表示的是独立的一步。当实体i、j直接相连时，d(i,j)表示其连接成本；对实体i、j不直接相连的情况d(i,j)为无穷大。(注意d(i,i)为无穷大，因为不认为一个节点直接连接到自己。)因为费用被考虑，下面列出的是最佳尺度的计算公式。
D(i,i) = 0, 所有的i
D(i,j) = min [d(i,k) + D(k,j)], 不同的k
最佳的路径是使d(i,k) + D(k,j)达到最小的邻居k。（这样的计算在路由器上会作多次）第二个等式中的k可以被限定为i的直接邻居，不然d(i,k)将是无穷大，总的等式不可能最小。
计算就是基于这样简单的算法。实体i从其邻居k发送的信息中得到目标j的距离。当收到后，i加上i、k之间的费用d(i,k)。并比较所有的邻居取得最小值。
在[2]中证明了，当拓扑结构不变时，算法可以在有限的时间内使D(i,j)正确汇聚。作者没有假设各个实体发送信息的次序，也没有指出何时重新计算最小值。基本上，实体将不断的发送信息并重计算尺度，而且网络不能延迟这些信息(实体的崩溃将导致拓扑改变)。他们同样证明，除了可以肯定是非负数，不要对D(i,j)的初始值作出假设。事实上，不需要假设是很好也很重要的。不对实体发送信息的次序作出假设，可以使各实体按照其各自的时钟异步的运行算法；更新信息也可以被网络丢弃，只要不被全部丢弃。不对初始值作出假设，可以使算法处理拓扑改变。当系统改变后，路由算法可以从旧的状态向新的状态稳定。不然，可能会有导致不汇聚的情况。
上面的算法(以及说明)都假设每一个实体都保持了从其邻居获得信息的所有备份，并在其中得出一个最小值。实际的实现不需这样，仅仅记住一个最佳尺度，及发送这个尺度的邻居。当发现一个更好(更小)的尺度后再替换。这样可以不用存储所有邻居的信息而计算出最小值。
上面的描述和实际的RIP协议还有一个不同：在描述中，每个实体有其自身的一项，其距离为0。而事实上一般不这样。
回忆上面所说，同一个网络中所有实体的信息被汇总成一个路由项。考虑以下情况：主机或网关G连接到网络A上。C为使用网络A的成本(通常是1)。(再回忆：对IP而言，一个网络内的路由是不存在的，一个网络中的两个实体有同样的成本）在理论上，G可以得到网络A上所有实体H的信息，并认为到自身的成本为0。G将计算出到H的成本为C+0，G将仅维持一条到网络A、成本是C的项，而不是为每个H建立一项。这一项可以被认为是到达网络A上所有实体的汇总；唯一不能被汇总的项是到G自身，其成本是0而不是C。但我们从不使用0实体，可以将其和网络A的项合并。考虑这一策略的另一含义：因为我们不使用0实体，不作为网关的主机就不需要发送更新信息。不作为网关的主机(也就是只连接到一个网络的主机)，只会发送自身的一项D(i,i)=0。因为这些主机只有一个接口，要到达其他网络的路径如果到达该端口也会被从同一端口返回。这样其成本就会比C大。所以非网关根本不需要参与路由协议。
让我们来汇总一下主机或网关G的工作：对于系统中的每一个目标，G都保持当前的尺度，和发送这一尺度的邻居网关。如果目标在与G直接相连的网络上，G将使用表示网络成本的一项，而不使用任何网关。显然，当计算汇聚到正确的尺度后，按这种技术记录下的邻居将是到达目标的路径上的第一个网关(如果有多条等价路径，第一个网关将是其中之一)。也就是说将通过网关可以用多少成本到达目标。
仅当有更小的尺度到达的时候，当前保留的尺度才能被降低。尺度也可能被增加，因为一开始的估计较小。可以做这样的规定：设当前到目标的路径是使用网关G，尺度D；对于从其他网关得到的信息，只有当其尺度比D好时才使用；而对于从G来的信息，不管好坏都将被使用。可以看到，通过这样的规定得到的路由表与保持所有从邻居得到的信息得到的路由表是一致的。(注意在这里的讨论中，网络被认为是静态的，系统中没有网络会失效。)
以上是距离向量算法的简单概述。(这还不是RIP协议的描述，仍需要更精确的描述)。每一个参与路由协议的实体都需要按照下面的步骤。每个网关都必须包括，非网关主机也可以参与。
- 保持到达系统中每个目标的表项。每一项都包括到达目标的距离和路径上的第一个网关。理论上讲，需要有指向自身，尺度为0的一项。但事实上可以不包括。
- 向每一个邻居周期性的发送路由更新。更新中的信息包括路由表中的所有信息。包含到达每个目标的项，及到达目标的距离。
- 邻居G'发送路由更新，将其尺度加上G'相关联的网络成本(是更新信息到达的网络)得到新的距离D'。将结果与当前路由表中的项比较。如果D'比现有的D小时，采用新的路径；即将新的路径改为使用G'，距离D'。当G'=G时，使用新的尺度，即使尺度变大。
2.1. 拓扑结构改变时的处理
以上的讨论都假设网络拓扑是固定的。实际上，网关和线路经常会出错和恢复。我们需要对算法作出一些细小的变动来处理这些情况。在理论化的算法中包括了所有的直接邻居，如果拓扑改变，在下一次计算中就会有反映。而在实际算法中，简化了算法，仅保持给定目标的最佳路径。当包含在路径中的网关或网络崩溃后，计算将不会反映这一变化。算法依赖于其邻居发现尺度改变，如果网关崩溃，就不会向其邻居报告变化。
为了解决这类问题，距离向量协议必须使用路径时效来进行预防。不同的协议，其细节不同。例如，RIP网关每30秒周期性的向其所有的邻居发送更新信息。如使用网关G到达网络N，如果有180秒没有收到G的更新，就假设网关G或连接G的网络崩溃了。这样我们就可以标志路径无效。如果从另一邻居得到到达网络N的有效路径，就将其替代无效的项。注意因为信息在传输中可能被丢失，所以将等待180秒即使每30秒就将会有更新信息。仅因为一次信息的遗失而使路径失效是不适合的。
正如我们下面将说的，将无效的路径通知其邻居是非常有用的。RIP和许多其他同类协议一样，通过在普通更新信息中标识网络为不可到达来实现。一个比最大的有效尺度更大的数值用来表示不可到达，在当前的RIP中使用16。16虽然是一个非常小的数字，但在这里通常
被称为“无穷大”，很多实现都是这样规定的。其原因下面很快就要讲到。
2.2. 避免不稳定性
上面描述的算法使主机、网关通过计算得到正确的路由表。但在实际使用中还是不十分实用。上面仅证明了路由表会在有限时间内汇聚，但没有保证其汇聚速度可以用于实用；对网段变为不可到达的情况也没有涉及。
对算法进行扩展使其能够处理路径无效很简单。如上所述，选择一个表示“无穷大”的数值。这个数值必须比所有可能得到的实际数值要大。在本例中使用16来表示不可到达。假设一个网络变的不可到达，该网络的所有直接邻居将到达此网络的尺度标为16。我们可以这样来分析：假设每个邻居网关有连接到一个虚网段的连接，其成本为16。因为这是连接虚网段的唯一路径，系统中的其他网关通过这些网关到达虚网段的成本将至少为16。离原始邻居网关相距一跳的网关的成本为17，相距两条的成本为18等等。对于超过最大值的成本都会被设为16。明显，到达虚网段的路径将都是16。
很不幸，这样简单的方法不能解决在多长时间内汇聚的问题。在更深入之前，需要看一下一个例子(是从[2]中借鉴)。注意，下面的情况不会在现实中出现，从中可以明白新功能实现的必要。下面的字母是网关，连线是网络。
A-----B
\ / \
\ / |
C / C、D间线路的成本是10
| / 其他线路的成本是1
|/
D
|<=== 目标网络
每个网关都有到各网络的路由表。但在本例中，我们只需要考虑到达图中最下方网络的路径。
D: 直接相连，尺度1
B: 通过D相连，尺度2
C: 通过B相连，尺度3
A: 通过B相连，尺度3
现在假设B、D间的线路失效。连接将通过C、D间的路径。很不幸，要做好转换将花相当长时间。当B发现到D的路径失效时，路由开始改变。我们假设各网关同时发送路由更新来简化情况。下表显示了各网关到达目标网络的路径和尺度。
时间------>
D: 直连, 1 直连, 1 直连, 1 直连, 1 ... 直连, 1 直连, 1
B: 不可到C, 4 C, 5 C, 6 C, 11 C, 12
C: B, 3 A, 4 A, 5 A, 6 A, 11 D, 11
A: B, 3 C, 4 C, 5 C, 6 C, 11 C, 12
问题在于：虽然B可以使用超时来去处失效的路径，但将使用太长的时间。一开始，A、C 还是相信可以通过B可以到达目标，并使用尺度3。下面B错误的认为可以从A或C到达目标，而且没有办法来解决。A、C当发现B的路径失效后，它们之间还会认为可以通过对方到达目标。虽然最后系统可以汇聚，但这将花去太多的时间。在最坏的情况下，当一个网络与系统的其他部分彻底失去连接时，将花费相当长的时间来使其他网络知道这一情况。这个问题叫作“记数到无穷大(counting to infinity)”。
所以，所谓的“无穷大”需要选择的尽可能小。当网络彻底失去连接时，将尽可能快的记数结束。无穷大必须比实际可能的路径尺度要大，但不应更大。其数值的选择是在网络大小和汇聚时间两者之间的折中。RIP协议的设计者认为这个协议不适用于直径大于15的网络。
可以通过一些方法来解决这些问题。在RIP中使用了“带逆向毒化的水平分割(split horizon with poisoned reverse)”与“触发更新(triggered updates)”。
2.2.1. 水平分割
上面的问题之所以产生，原因之一是因为A、C相互错误的宣告可以到达D。可以通过下面的办法来避免这一情况。具体来说就是：不向发送该路径的邻居宣告该目标可达。“水平分割”就是不向发送该条路径的邻居网关发送包括该路径的更新。“带逆向毒化的水平分割”就是发送此类更新，但将其尺度标为无穷大。
如果A认为可以从C到达D，那么A就向C发送信息表示D不可达。如果C宣告的路径是存在的，那么C可能和D直接相连，或可以通过其他网关到达D。C的路径不能回到A，这样会产生回路。A通过向C宣告D不可达，就可以认为C的路径不通过A。前面讨论的是A、C在点对点链路的情况，当A、C在广播网，如以太网中时，在网络中就可能会有其他的网关。如果A有通过C的路径，A也会向网络中的其他网关宣告D不可达。网络中的其他网关会从C直接得到路径，而不需要通过A到达C。所以，如果A有通过C的路径，其他网关也就有了通过C的路径。这很幸运，C就可以通过广播向网络中的所有网关发送更新信息了。
通常情况下，带逆向毒化的水平分割比不同的水平分割更安全。两个相连的网关相互发送尺度为16的逆向路径，就可以直接避免回路。如果不发送逆向路径，错误的路径需要一段时间过后才能被消除。但是，毒化的逆向路径也有缺点：它增加了路由信息数量。考虑一个骨干网络连接了几幢建筑。每幢建筑中有一个网关连接着本地网络。网关的路由更新将广播到骨干网络上。每个网关都需要了解其他网关连接着怎样的网络。在使用普通水平分割时，只有被发送到骨干上的路由更新出现在路由信息中；而使用带逆向毒化的水平分割时，网关还要保存从骨干收到的很多尺度为16的路径。随着系统的增大，这可能产生很多更新信息来表示不可达网络。
在静态情况下，宣告尺度为16的逆向路径不提供更多可用信息。在一个广播网络中如果有很多网关的话，这会需要额外的带宽。使用逆向宣告的原因使提高动态性能。当拓扑改变的
时候，宣告不可使用的路径可以加快汇聚。但在一些情况下，网络管理员宁可汇聚减慢也要使路由负载减少。所以在实现中使用了普通水平分割，而不是带逆向毒化的水平分割；或者提供一个选项给管理员来选择。同样允许将两种情况混合使用，如在路由改变后的一段时间里使用逆向毒化，而后忽略。
2.2.2. 触发更新
带逆向毒化的水平分割可以避免两个网关之间的路由回路。但在三个网关的情况时，还会出现相互欺骗。例如A认为可以从B得到路径，B认为从C，而C认为从A。水平分割不能解决这样的回路。这样的回路只有当尺度达到无穷大以后而认为不可达。触发更新试图加速这样情况下的汇聚。实现触发更新，需要加入如下规则：当网关发现路径的尺度改变后，需要尽快地发送更新信息，而不管周期性信息发送的时间是否到达。(具体的时间根据协议不同，一些距离向量协议，如RIP，指定了一个很小的延迟，以避免触发更新占据过多的网络流量)。将这和计算新尺度的规则结合。假设有通过网关G到达目标N的路径，如果从G得到新的更新，接收的网关必须相信这个新的信息，而不管这个尺度比原来的好还是坏。当尺度改变时，接收的网关也必须向它的每一个直接邻居发送触发更新。这将引起一系列的触发更新，很容易知道哪些网关和主机将参与这一系列触发更新。当网关G发现目标N的路径无效时，就向它的邻居发出触发更新。只有哪些认为要通过G到达N的邻居才相信这一信息，其他网关将忽略该信息，因为新的更新使用一个更差的尺度。使用G到达N的邻居更新尺度，并向他们的邻居发送触发更新。同样，只有使用这些路径的邻居才会注意这一信息。这样，触发更新将传遍所有使用网关G的路径。传播在使用其他路径到达目标N的地方停止。
如果系统能够保证这一系列的触发更新发送，就可以保证记数到无穷大不会发送。错误的路径会马上被去除，也不会有回路。
很不幸，事情没有这么巧。触发更新也许会和周期性更新同时发送；没有收到触发更新的网关还会发送不存在的路径。网关也许会先收到触发更新，在收到错误的周期更新。这将会产生局部的错误路径。触发更新不会发送的那么及时，而记数到无穷大总还会存在。
3.协议详述
RIP的目的是为在IP网络环境中的主机和网关交换信息而计算路径。RIP是一个距离向量协议，其主要功能在第2章中已经描述。主机和网关都可以实现RIP，在很多IP文档中，使用术语“主机(host)”来范指。RIP是传输“目标(destinations)”的路径信息，目标可以包括独立的主机、网络或一个特殊的默认路径。
每个使用RIP的主机都有接口连接一个或多个网络。这些被成为“直接连接网络(directly-connected networks)”。协议就是使用这些网络的相关信息。信息中最重要的是尺度(metric)或叫作成本(cost)，网络的尺度在整数1-15之间。大多数实现都使用1作为尺度，新的版本中允许管理员为每个网络设定成本。除了成本，每个网络有一个IP网络地址和相对应的掩码，这是由系统管理员手工设置的，且与本协议无关。
注意在3.2节中的规则：每个IP网络只有一个子网掩码，以及只有直接连接网络的子网掩码是已知的。但是，也有可能需要在一个网络中存在多种子网掩码；或需要知道远端网络的
掩码。这需要修改协议使其传送子网信息，这样的修改提高了可用性。
每个实现RIP协议的主机都有一张路由表，表中为每个通过RIP得到的目标建立一项。每一项中都至少有下列信息：
- 目标的IP地址。
- 尺度，表示主机到目标的总成本。是从主机到目标路径上的各网络成本之和。
- 到达目标的下一网关的地址。如果目标是直接连接网络，此项不需要。
- 表示路径最近有改变的标志。被叫做“路径改变标志(route change flag)”。
- 路径的有效时间。详见3.3节。
主机使用与协议无关的信息建立直接连接网络的各项。在RIP中，直接连接网络的尺度永远是1。复杂的尺度可以用来表示一些特殊的网络，如不同的带宽和可靠性。
也可以允许系统管理员输入额外的路径，这常是因为主机或网络在路由系统范围之外。
除了在初始状态下的各项外，其他到达目标的项是由下面描述的算法增加和更新的。
为了建立完整的路由信息，系统中的每个网关都要参与。不是网关的主机不一定需要，但很多实现都允许这些主机接收路由信息来维持路由表。
3.1. 信息格式
RIP是基于UDP的协议，使用RIP的主机都有一个路由进程在UDP端口520上发送和接收信息。所有直接发送到其他主机RIP进程的信息都使用目标端口520；所有的路由更新信息使用源端口520。主动路由更新信息的源、目标端口都是520；回应信息的目的端口使用发送者的源端口。特别的查询和调试信息可以不使用源端口520，但目标端口需使用520。
协议中允许有“沉默”RIP进程。沉默进程是指平常不发送任何信息，但从其他主机接收信息。沉默RIP常被用于不作为网关的主机，它们需要接收路由信息来监视本地网关以维持正确的路由表。(见[5]描述了主机了解网络拓扑的多种方法)当网关只剩下一个网络连接而失去了其他连接的时候，就变的沉默了，因为这时它们已不再是网关。
当然，在邻居网关需要依赖这些信息来判断失效的网络是否恢复的时候，不应当使用沉默。(伯克莱4使用路由包来监视点对点连接的操作。)
包格式见图1。
包格式中包含了网络信息，各域的大小被按字节写成。除非特别指出，域为二进制整数，按重要字节在前的Internet次序。
0 1 2 3 3
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| command (1) | version (1) | must be zero (2) |
+---------------+---------------+-------------------------------+
| address family identifier (2) | must be zero (2) |
+-------------------------------+-------------------------------+
| IP address (4) |
+---------------------------------------------------------------+
| must be zero (4) |
+---------------------------------------------------------------+
| must be zero (4) |
+---------------------------------------------------------------+
| metric (4) |
+---------------------------------------------------------------+
.
.
.
从地址簇标识到尺度的部分可以被重复25次。IP地址就是4字节的Internet地址。
图1. 包格式
每个包包含一个命令(command)、版本号(version)和可能的参数。本文档描述的是协议的版本1。细节的版本描述见3.4节。命令域表示包的用途，这里汇总了版本1中的命令：
1 - 请求(request) 请求被响应者发送其全部或部分路由表。
2 - 回应(response) 包含发送者的全部或部分路由表；可以是响应请求；或是更新信息。
3 - 跟踪开(traceon)废止，忽略。
4 - 跟踪关(traceoff)废止，忽略。
5 - 保留(reserved) 被Sun系统使用，可以被忽略。后继版本的新命令会从6开始。
在请求和回应中，包中的其他内容是目标的信息。列表中的每一项都包括了目标网络或主机，以及它们的尺度。这一包格式可以使RIP能够处理多种协议的路由信息。不同的协议使用不同的协议簇号(address family identifier)，本文档只描述IP协议，其协议簇号为2。(还没有关于其他类型的地址。)但为了将来，需要忽略不同协议簇号的信息(这些项的大小和IP协议一样)。在过滤掉不支持信息后开始信息处理。IP地址是4字节的，尺度用来说明目标，其值在1到15之间；对不可达的目标，尺度是16。由一个网关发来的路径总将取代同一网关发来的到达同一目标的路径。
包最大可以有512字节，这只包含前面描述的部分，不包括IP和UDP头。网络信息可以被分为多个包传送，不必须连续，包可以被独立处理而最终得到正确结果。
3.2. 考虑地址
就象在第2章所说，距离向量路由可以用来描述独立的主机或网络，RIP协议对此都允许。在请求、回应信息中出现的目标可以是网络、主机或表示默认路径的特殊值。通常何种目标被允许取决于路由策略，很多网络不允许路由独立主机信息。如果给定网络上的每一个主机都可以通过同一个网关到达，也就没有必要使用主机路由。但在点对点连接中，可能需要网关到达特定的主机。是否需要这一功能取决于系统的地址和路由。如果不支持主机路由，将丢弃这一类回应(见3.4.2节)。
RIP在包格式中不区分各类地址。下面几种都被标为“地址(address)”:
主机地址
子网地址
网络地址
0，作为默认路径
每个RIP的实体都使用更精确匹配的信息来转发数据。也就是，当向一个目标转发数据时，先检查是否有相匹配的主机地址；再检查是否匹配已知的子网或网络地址；最后，如果没有匹配，才使用默认路径。
当RIP接收到主机评估信息时，它将根据是否知道该网络的子网掩码来作出决定。如果知道的话，就可以就此知道地址的含义。如128.6.有着子网掩码255.255.255.0，那么128.6.0.0是网络地址；128.6.4.0是子网地址；128.6.4.1是主机地址。但当不知道子网掩码时，就会产生含糊。如果主机部分为非0的话，将分不清到底是主机还是子网地址。没有子网掩码，子网地址就无法识别，地址会被理解为主机地址。为了避免这样，不能向不知道正确子网掩码的主机发送子网信息。主机一般只知道直接连接网络的子网掩码，所以，除非做了修正，不应当向网络外发送该网络的子网信息。
这种过滤发生在划分子网网络的边界，这些网关连接两个网络。在被子网化的网络里，每个子网被对待为独立的网络，每个子网的路由项由RIP传送。但边界网关向其他网络仅发送表示该整个网络的一项。也就是说，边界网关向不同的邻居发送不同的信息；对连接在子网化网络中的邻居，发送所有直接相连的子网信息；对其他网络的邻居，仅发送表示整个网络的一项，其尺度一般是该网关连接的子网中最小的尺度。
同样，边界网关不应向其他网络发送其直接连接网络中的主机路径。这些路径应当被汇总在一条网络路径中发送到其他网络。我们不需要知道“远方”主机的路径(是指不在直接连接网络上的主机)。这些路径指出网络上的一部分主机可达，而另一部分不可达。
特殊的地址0.0.0.0被用来描述为默认路径。当RIP更新不能包括所有网络的路径，或着一个或多个直接相连的网关被用来处理所有没有列出的网络时可以使用默认路径。网关可以产生地址为0.0.0.0的项，好象有这么一个网络连接一样。如何产生0.0.0.0的项是由实现者
决定。通常，系统管理员将为0.0.0.0项指定一个网关，但也有其他方法。如可以认为宣告EGP的网关为默认网关，这允许网络管理员为各项选择尺度。当有多个网关的时候，可以选择一个最好的。0.0.0.0的项在RIP中被和其他项一样对待，只不过用来转发不匹配路由表中各项的目标。这一实现不是必须的，但被极力推荐。不支持0.0.0.0的实现必须忽略这一项，这些网关不能将这一项加入到自己的RIP更新中。管理员需要注意0.0.0.0的路由没有被传播到不应该的地方。通常，每个自治系统都有自己首选的默认路由，0.0.0.0项不应被传输过自治系统边界。但这不是本文档论述的范围。
3.3. 记时器
本节讨论被记时器触发的所有事件。
每30秒，输出进程向每个邻居网关发送完整的响应。当一个网络上有多个网关时，它们往往会在趋向于在同时发送路由更新，这在进程启动后每30秒发生。但同步发送更新信息有缺点，这会在网络中产生不必要的碰撞和广播。通常有两种预防方法。
- 用独立的时钟时钟产生30秒的更新，而与系统负载、更新花费的时间无关。
- 将30秒添加小范围的偏移。
每个路径都有两个时间相联系，“超时(timeout)”与“垃圾收集时间(garbage-collection time)”。在超时后，路径将无效，但还会在路由表中存在一小段时间，使邻居能够发现路径无效。当垃圾收集时间过后，路径从表中删除。
当路径建立时，超时记时器开始记时，如有收到该路径的更新信息则重置记时器。如果记时到180秒，说明路径终止，删除进程开始。
有两个原因可导致删除：(1) 到达超时(2) 从当前网关收到尺度为16的更新(见3.4.2节处理更新)。这两种情况都有下列时间发生：
- 设立120秒的垃圾收集记时器。
- 将路径的尺度设为16(无穷大)，这将使路径被删除。
- 做标志此项以改变，输出进程将产生一个触发更新。
在垃圾收集时间期满前，此项路径被包含在由主机发送的更新中，其尺度为16(无穷大)。当该时间期满，路径从表中删除。
在垃圾收集时间中，如果有到达该网络的新路径，可以替代原有路径，同时清除垃圾收集记时器。
3.5节描述了触发更新前需要的延迟，虽然这也需要记时器，但还是放到3.5节中叙述。
3.4. 输入进程
本节描述处理从UDP端口520接到的信息。在做进一步的工作前，需要检查格式，这取决于包中的版本号。
0 要忽略版本0的包，这是以前按不同机器指定的版本。
1 需要处理的是版本1的包，要检查所有必须为0的域，如有非0值要忽略整条信息。
>1 版本大于1的包在后面会说明。对版本1而言，将忽略所有必须为0的域，因为新版本可能在其中放入数据。
在做了版本号等的初步检查后，进程将根据不同的命令域做出处理。
3.4.1. 请求
请求是用来要求得到包含全部或部分路由表的回应。(注意：术语主机被用于所有主机和网关，一般非网关主机不发送RIP信息)。一般请求使用广播，通过UDP端口520发送。沉默进程不回应请求，沉默进程是指不需要了解其路由信息的进程。但考虑这样的情况，有监视程序想得到沉默进程的路由表，所以沉默进程不回应源端口是520的请求，但对其他端口的请求需要回应。
请求是按项处理的，如果没有项就没有回应。有一特殊项，在请求中只有一项地址为0(意为不指定)，尺度为无穷大(指16)，表示请求全部的路由表。这时调用输出进程向请求端口发送所有的路由表。
除了这一特殊情况，处理过程都很简单。将请求项一个个处理。对每一项查找路由数据，如果找到对应项就将路由尺度填入包的尺度域中；如果没有就在其中填入无穷大(16)。处理完所有的域后，将命令改为回应发回到发来数据的端口去。
处理指定目标和全部路由表的方法有所不同。如果处理全部路由表，是按照正常输出进程完成的，这包括水平分割(见2.2.1节)和子网隐藏(见3.2节)，从当前项得到的路由不会显示。如果请求是特定项，就返回表中的项而不使用水平分割，并可能返回子网掩码。我们认为不同的请求是为了不同的目的。当主机启动后，它向每个相连的网络广播其请求以获得完整的路由表。我们假设完整的路由请求被用来更新主机的路由表，所以需要使用水平分割和其他过滤。而指定目标请求仅被诊断软件使用，而不被用于路由，所以需要返回竟可能多的信息而不隐藏。
3.4.2. 回应
收到回应可能是由于以下不同原因：
回应特定的查询
周期性更新
尺度改变后的触发更新
但处理过程不因此而不同
因为处理回应将引起主机的路由表更新，所以必须仔细检查其有效性。必须忽略源端口不是520的信息；其IP源地址必须是一个有效的邻居；且处于直接连接网络。还需要检查回应是否来自主机自己的地址，在广播网上的接口往往会收到自己发送的广播，如果将其作为输入可能产生混淆。对于收到的这些包必须忽略(除了在下面描述的情况)。
在真正处理回应前，需要将其用来保持接口状态。如上所述，对于一段时间没有消息发送的路径将被超时而去除。这将保证从其他网关得到路径的正确性；也可以使我们知道直接连接网络是否失效。本文档不涉及和具体网络硬件相关的方法。但是从接口接收到包是一种常用的方法，这表明接口正常。但要小心，接口可能能够收到包而不能正确发送。
当包的正确性验证后，将按次序一项项处理各项。重申包先要验证。如项中的尺度大于无穷大，则忽略。(在其他主机正常工作时，这种情况不会发生。错误的尺度和其他格式错误应当被记录或报警。)然后查看目标地址，检查地址簇标识，如果不是所期望的值(对IP而言是2)，忽略该项。检查地址项是合法地址，对于D、E类地址，网络0(除了用以标识默认路径的0.0.0.0)、网络127(回环网络)都将被忽略。同样忽略广播地址(即主机位全1的地址)。对于不支持主机路由的实现(见3.2节)，检查主机位是否非0，如果是，也被忽略。
在地址域种有一些未用的字节，对于版本1的包而言，它们必须为0，不然将被忽略。(这多表示发送信息的主机工作不正常，这些错误需要被记录或报警。)
将收到的尺度和信息到达的网络尺度相加来进行更新。如果结果大于16，取16。即
metric = MIN (metric + cost, 16)
检查地址是否已经存在于路径中。如果没有，一般将其加入。当然有例外，如尺度为无穷大就不加入。(对于已有的项将更新，但不新加尺度为无穷大的项。)当一条主机路径不比相对应的网络路径更好的时候，我们将不加入这条主机路径。如果所有这些例外都不满足，新的项被加入到路由数据中，这包括：
- 设定从包中得到的目标和尺度。
- 将包的来源作为网关。
- 初始化路径的超时记时器，停止该路径可能的的垃圾收集时间。(见3.3节的描述)
- 设定路径改变标志，并引发触发更新(见3.5节)。
如果路径已经存在，首先比较网关。如果是从同一网关得到的相同路径，重置超时记时。下面比较尺度，当同一网关发送了新的尺度，或新的尺度比原有的小，执行以下步骤：
- 采用新的路径。即采用新的网关和尺度来代替原有的。
- 重置超时记时。
- 设定路径改变标志，并引发触发更新(见3.5节)。
如果新的尺度是16(无穷大)，开始删除进程。路径不在用于转发包，删除记时器开始(见3.3节)。注意，删除仅在尺度第一次变为16的时候开始，如果原先的尺度也是16，不会开始新的删除。(删除进程包括开始或删除记时器，我们不希望在30秒后再次收到无穷大尺度的时候重置记时器。)
当新的尺度和原有一样的时候，不再做什么(除了上面说的重置记时器)。在伯克莱4中多提到了一点。通常更换一个同等尺度的不同路径是无意义的，但如果当前路径看起来要超时的时候，可以立即将其换到另一条路径，而不必等到完全超时。(见3.3节超时的描述)。这样的话，当新的尺度和原有一样的时候，检查原有路径的超时记时器，当它超过一半时，将转到新的路径上。这一做法是可选的。
不符合上面条件的项被忽略，因为它们只提供了较差的路径。
3.5. 输出进程
本节描述产生回应信息的过程。这可能被以下情况触发：
- 回应请求，这时结果信息只被发送到单独的目标。
- 周期性更新，每过30秒将向所有邻居发送完整的路由表。(见3.3节)
- 触发更新，当尺度改变后将引起触发更新。(更新将被延迟，见下)
在描述信息产生之前，需要知道在下两种情况下，如何选择目标。通常当回应发送到所有目标时(不管时周期性更新还是准备触发更新)在点对点端口是被直接连接的对端主机接收到；在支持广播的端口是被所有相连的主机接收到。这样回应就被直接相连的主机接收到了。但有时情况并不这么好，网络也许不支持广播(如ARPANET)，或存在哑网关。这就需要有邻居主机的列表，并将回应逐一向其发送。这就需要决定是否需要一种机制来定义邻居列表。
触发更新因为以下两个原因需要仔细对待。首先，经验表明在网络上有很多网关且网络容量有限的情况下，触发更新会产生过多的负载。所以需要限制触发更新的频率，当需要触发更新时，设定一个1-5秒随机的记时器，如果在此期间有另一个需要引起触发更新的改变，那么一次更新就够了；并再次设定1-5秒随机的记时器。如果在触发更新等待期间发生了周期性更新，触发更新被取消。
其次，触发更新不需要包括全部的路由表。原则上只要包括那些改变了的路径就可以，也就是包括设了改变标志的那些路径。根据实现者的判断，可能会包含多一些路径或全部路径。如果需要多个包来发送全部路由更新，那是很沮丧的。触发更新需要包括那些直接连接网络，
同正常更新一样，需要使用水平分割(见下)。
在水平分割后，改变了的路径表现的和以前一样，那就不需要发送；如果最后没有路径需要发送，在这个网络上的更新被取消。(如果路径只是改变了尺度，或使用了和原有网关处于同一网络的新网关，需要向旧网关发送无穷大尺度来表示该路径。)当所有触发更新产生后，路径改变标志被清除。
如果在准备输出的时候允许输入进程，需要实现互锁。在此期间，路径改变标志不应当被输入进程修改。
触发更新和其他更新信息的唯一不同在于后者包含大量没有改变的路由信息。下面的机制必须被触发更新使用。
下面描述为直接连接网络产生回应：
IP源地址必须是主机在该网络的地址。因为源地址被保存在其他主机的路由表中，如果使用不正确的源地址，其他主机就不能转发包。有时，在同一物理接口上会设定多个IP地址，这表明在同一物理媒体中用多个逻辑网段。这时，需要把每个地址作为源地址，分别发送更新信息。
设定当前RIP的版本号(本文档描述的时版本1)；设定命令为回应；设定所有必须为0的项。然后开始填入各项。
将路由表中的所有路径填入各项，因为包最大为512字节，所以当没有空间时，发送当前信息并开始一个新的包。对触发更新而言，仅需要填入设立了路由改变标志的项。
见3.2节描述的关于主机路径和子网的问题。到达本地网络子网的路径对于本网络外是无效的，必须对外网忽略本地的子网信息；而仅发送一条描述整个网络的路径。同样，主机路径也要被包含在网络路径中，正如3.2节所讲。
如果路径通过了这些测试，那么讲目标和尺度放入输出包的各项中，对于尺度为无穷大的各项也必须包括。这些无穷大项仅被放入表示其来源的网络中，而在其他网络中忽略。包含尺度为16的项就是带逆向毒化的水平分割。完整的描述见2.2节。
3.6. 兼容性
按照本文档的描述而实现的协议可以与其他RIP的实现协同工作。但本文在尺度增加上采用了与早先实现不同的视角。以前的观点是：在内部路由表中将所有直接连接网络的尺度设为0，当发送路径信息的时候再加上其成本(通常为1)；相对应的是：本文档中，直接连接网络的尺度是其自身的成本，而不一定是1，成本在路径被接收到更新信息后就加到了路径尺度上，发送的时候不在修改。(除非被水平分割修改。)
两种不同的视角产生同样的更新信息，而不会产生不同的结果，只不过保存在路由表中的尺度有所不同。这样的改变是为了处理不同尺度的直接连接网络。
对于只支持网络成本为1的实现而言，不需要按新的视角来做；但对于其他方面，必须按照本文档的描述。
4. 控制功能
本章描述管理控制。这不是协议的本质内容，但已有的网络经验告诉我们这很重要。这些不是协议所必须的，可以作为选项，但我们还是强烈建议至少实现其中的部分功能。
这些控制的目的是为了RIP可以连接到一些不稳定或容易出错的网络，如：
限制接收从某些主机或网络发来的信息，一些错误配置的主机会发送不适当的信息。
在更新信息中限制一部分网络。如A机构和B机构直接相连，出于效率或安全性的考虑，A 不希望其他机构使用这一连接。这样，A在向第三方发送更新的时候就不能包括B机构的网络信息。
下面是一些典型方法，虽然RIP协议不是必须使用。
- 邻居列表：网络管理员可以为每个主机定义邻居列表，主机只接受列表中的邻居。
- 允许或禁止特定的目标：网络管理员可以设定一个目标地址列表以决定是否允许。每个列表要和特定的接口以及输入或输出方向相结合。只有被允许的请求或回应可以进出。当使用允许列表时，其他的地址都被禁止；当使用禁止列表是，其他的地址都被允许。
参考书目
[1] Bellman, R. E., "Dynamic Programming", Princeton University
Press, Princeton, N.J., 1957.
[2] Bertsekas, D. P., and Gallaher, R. G., "Data Networks",
Prentice-Hall, Englewood Cliffs, N.J., 1987.
[3] Braden, R., and Postel, J., "Requirements for Internet Gateways",
USC/Information Sciences Institute, RFC-1009, June 1987.
[4] Boggs, D. R., Shoch, J. F., T aft, E. A., and Metcalfe, R. M.,
"Pup: An Internetwork Architecture", IEEE Transactions on
Communications, April 1980.
[5] Clark, D. D., "Fault Isolation and Recovery," MIT-LCS, RFC-816,
July 1982.
[6] Ford, L. R. Jr., and Fulkerson, D. R., "Flows in Networks",
Princeton University Press, Princeton, N.J., 1962.
[7] Xerox Corp., "Internet Transport Protocols", Xerox System
Integration Standard XSIS 028112, December 1981.
实验一 词法分析器的设计
实验一词法分析器的设计 (2) 1.1 词法分析器的结构和主要任务 (2) 1.1.1 输入输出接口 (2) 1.1.2 条件限制 (2) 1.2 词法分析程序的总体设计 (3) 1.3 词法分析程序的详细设计 (4) 1.4实验步骤 (5) 1.5输入数据 (15) 1.6结果输出 (15)
实验一词法分析器的设计 实验目的：掌握词法分析的概念，设计方法，熟悉高级语言中词法的定义，词法分析程序的编写。 实验要求：在8学时内实现SAMPLE语言的词法分析器，要求用VC窗口界面实现。 实验内容：分为4次实验完成。 1.1 词法分析器的结构和主要任务 1.1.1 输入输出接口 图1-1词法分析器的输入输出界面 词法分析程序的主要任务是从左到右扫描每行源程序，拼成单词，换成统一的内部表示(token)输出，送给语法分析器。具体包括： 1.组织源程序的输入； 2.按规则拼单词，并转换成二元形式； 3.滤掉空白符，跳过注释、换行符及一些无用的符号(如字符常数的引号) 4.进行行列计数，用于指出出错的行列号，并复制出错部分； 5.列表打印源程序； 6.发现并定位词法错误； 7.生成符号表。 token文件和符号表用作语法分析的输入部分。 1.1.2 条件限制 本实验可以作如下假定： (1) 假定SAMPLE语言采用自由格式书写； (2) 可以使用注解，用/*……*/或者{……}标识，但注解不能插在单词内部，注解要在一行内结束，若一行结束，没有遇到注释后面的结束标记，自动认为注释也结束； (3) 一行可以有多个语句，一个语句也可以分布在多行中，单词之间和语句之间可以插入任意空格，单词中间不能有空白符号，单词中间也不能有回车换行符，即单词不能跨行书写； (4) 关键字都是保留字。
中文汉语语法
中文汉语语法 一、语素 语素和语素分类语素是最小的语音语义结合体，是最小的语言单位。语素按音节分类可以分成：单音节 语素，双音节语素，多音节语素。 ①单音节语素如土、人、水、风、子、民、大、海等。 ②双音节语素组成该语素的两个音节合起来才有意思，分开来没有与该语素有关的意义，双音节语素主要包括联绵字、外来词和专用名词。 A.双声，声母相同的联绵字：如琵琶、乒乓、澎湃、鞑靼、尴尬、荆棘、蜘蛛、踯躅、踌躇、仿佛、瓜葛、忐忑、淘汰、饕餮、倜傥、含糊、慷慨、叮当、蹊跷、玲珑、犹豫等。 B.叠韵，韵母相同的联绵字：如从容、葱茏、葫芦、糊涂、匍匐、灿烂、蜿蜒、苍茫、朦胧、苍莽、邋遢、罗嗦、怂恿、螳螂、桫椤、倥侗、蜻蜓、轰隆、当啷、惝恍、魍魉、缥缈、飘渺、耷拉等。 C.非双声叠韵联绵字：如蜈蚣、蓊郁、珊瑚、疙瘩、蚯蚓、惺忪、铃铛、奚落、褡裢、茉莉、蚂螂、窟窿、伉俪、蝴蝶、笊篱、蹦达、蟪蛄、狡狯、狡猾、蛤蚧、蛤蜊、牡丹、磅礴、提溜等。 D.外来词，由汉语以外的其他语种音译过来的词语。如干部、涤纶、甲克（夹克）、的士、巴士、尼龙、吉普、坦克、芭蕾、哒爹等。 E.专用名词，主要是地名、人和事物名称。如纽约、巴黎、北京、苏轼、李白、孔子、萝卜、菠菜、番茄、红薯等。 ③多音节语素 主要是拟声词、专用名词和音译外来词。如：喜马拉雅、珠穆朗玛、安迪斯、法兰克福、奥林匹克、白兰地、凡士林、噼里啪啦、淅淅沥沥、马克思主义、中华人民共和国。 二、词 词是由语素组成的最小的造句单位。有两种分类方式，1、按构成方式分单纯词和合成词；2、按词性分为实词和虚词。 从构成方式来看，可以分成： ①单纯词：由一个语素组成的词，自由的单音节语素和所有的双音节、多音节语素都可以组成单纯词。如：山、水、天、地、人、有、土、红、凑；仿佛、苍茫、蜈蚣、琉璃、参差、蹉跎；敌敌畏、阿司匹林、萨克斯、麦克风等。 ②合成词：由两个或两个以上的语素组成的词。 从词性来看，可以分成：实词共6个有实际意义的词，包括： （1）名词：表示人或事物名称的词。 有人物名词：如学生、群众、老头、妇女、同志、叔叔、维吾尔族、酒鬼等； 有事物名词：如笔、杉木、蜗牛、猎豹、奥托、棒球、战斗机、冥王星、思想、中学、物理、过程等； 有时间名词：如上午、过去、将来、午夜、三更、甲戊、世纪等； 有方位名词：如东南、上面、前方、内部、中间等。 （2）动词：表示动作行为及发展变化的词。 有行为动词：如跑、唱、喝、敲、吆喝、盯、踢、闻、听、摸； 有发展动词：如生长、枯萎、发芽、结果、产卵； 有心理动词：如喜欢、恨、气愤、觉得、思考、厌恶； 有存现动词：如消失、显现、有、丢失、幻灭； 有使令动词：如使、让、令、禁止、勒令；
词法分析小结
词法分析小结 词法分析是编译器工作的第一阶段，它的工作就是从输入（源代码）中取得token，以作为parser（语法分析）的输入，一般在词法分析阶段都会把一些无用的空白字符（whitespace，即空格、tab和换行）以及注释剔除，以降低下一步分析的复杂度，词法分析器一般会提供一个gettoken()这样的方法，parser可以在做语法分析时调用词法分析器的这个方法来得到下一个token，所以词法分析器并不是一次性遍历所有源代码，而是采取这种on-demand的方式：只在parser需要时才工作，并且每次只取一个token。 token和lexeme 首先，token不等于lexeme。token和lexeme的关系就类似于面向对象语言中“类”和“实例”（或“对象”）之间的关系，这个用中文不知该如何解释才好，比如语言中的变量a和b，它们都属于同一种token：identifier，而a的lexeme是”a”，b则是”b”，而每个关键字都是一种token。token可以附带有一个值属性，例如变量a，当调用词法分析器的gettoken()时，会返回一个identifier类型的token，这个token带有一个属性“a”，属性可以是多样的，例如表示数字的token
可以带有一个表示数字值的属性，它是整型的。 如下代码： intage=23; intcount=50; 可以依次提取出8个token：int(值为”int”)，id(值为”age”)，assign(值为”=”)，number(值为整型数值23)，int(值为”int”)，id(值为”count”)，assign(值为”=”)，number(值为50) 正则表达式 正则表达式可以用来描述字符串模式，例如我们可以用digit+来表示number的token，其中digit表示单个数字（这里说正则表达式并不完全和实现的正则引擎所识别的正则表达式等价，这里只是为了描述问题而已）。 然而像c语言的的多行注释，用正则表达式来描述就比较麻烦，此时更倾向于直接用有穷自动机（finiteautomaton）来描述，因为用它来描述非常直观且很容易。
基于多知识源的中文词法分析系统
第３０卷第１期计算机学报ｖ０１．３０Ｎｏ．１２００７年１月ＣＨＩＮＥＳＥＪＯＵＲＮＡＬ０ＦＣＯＭＰＵＴＥＲＳＪａｎ．２００７ 基于多知识源的中文词法分析系统 姜维王晓龙关毅赵健 （哈尔滨工业大学计算机科学与技术学院哈尔滨１５０００１） 摘要汉语词法分析是中文自然语言处理的首要任务．文中深入研究中文分词、词性标注、命名实体识别所面临的问题及相互之间的协作关系，并阐述了一个基于混合语言模型构建的实用汉语词法分析系统．该系统采用了多种语言模型，有针对性地处理词法分析所面临的各个问题．其中分词系统参加了２００５年第二届国际汉语分词评测，在微软亚洲研究院、北京大学语料库开放测试中，分别获得Ｆ量度为９７．２％与９６．７％．而在北京大学标注的《人民日报》语料库的开放评测中，词性标注获得９６．１％的精确率，命名实体识别获得的Ｆ量度值为８８．６％． 关键词词法分析；汉语分词；词性标注；命名实体识别；语言模型 中图法分类号ＴＰ３９１ ＲｅｓｅａｒｃｈｏｎＣｈｉｎｅｓｅＬｅｘｉｃａｌＡｎａｌｙｓｉｓＳｙｓｔｅｍｂｙ ＦｕｓｉｎｇＭｕｌｔｉｐｌｅＫｎｏｗｌｅｄｇｅＳｏｕｒｃｅｓ ＪＩＡＮＧＷｅｉＷＡＮＧＸｉａｏ—ＬｏｎｇＧＵＡＮＹｉＺＨＡＯＪｉａｎ （Ｓｃ＾ｏｏｚｏ，Ｃｏｍ户“ｆｅｒＳｃｉＰｎｃＢｎ咒ｄ：Ｉ。≥ｃ＾７２０ｆｏｇｙ，Ｈａｒ６ｆ雄ｊ知ｓ￡ｉｔ“抛ｏ，Ｔ奢ｃ＾竹。ｚｏｇｙ，Ｈ口ｒ６ｉｎ１５０００１） ＡｂｓｔｒａｃｔＣｈｉｎｅｓｅｌｅｘｉｃａｌａｎａｌｙｓｉｓｉｓｔｈｅｆｏｕｎｄａｔｉｏｎｔａｓｋｆｏｒｍｏｓｔＣｈｉｎｅｓｅｎａｔｕｒａｌｌａｎｇｕａｇｅｐｒｏ—ｃｅｓ８ｉｎｇ，Ｉｎｔｈｉｓｐａｐｅｒ，ｗｏｒｄｓｅｇｍｅｎｔａｔｉｏｎ，ＰＯＳｔａｇｇｉｎｇ，ｎａｍｅｄｅｎｔｉｔｙｒｅｃｏｇｎｉｔｉｏｎａｎｄｔｈｅｉｒｒｅｌａ—ｔｉｏｎ－ａｒｅｗｅｌｌｄｉｓｃｕｓｓｅｄ．ＩⅥｏｒｅｏｖｅｒ，ａｐｒａｇｍａｔｉｃｌｅｘｉｃａｌａｎａｌｙｓｉｓｓｙｓｔｅｍｂａｓｅｄｏｎｍｉｘｅｄｌａｎｇｕａｇｅｍｏｄｅｌｓｉｓｐｒｅｓｅｎｔｅｄ，ｗｈｉｃｈａｄｏｐｔｓｍａｎｙｍｏｄｅｌｓ，ｓｕｃｈａｓ以一ｇｒａｍ，ｈｉｄｄｅｎＩⅥａｒｋｏｖｍｏｄｅｌ，ｍａｘｉ—ｍｕｍｅｎｔｒｏｐｙｍｏｄｅｌ，ｓｕｐｐｏｒｔｖｅｃｔｏｒｍａｃｈｉｎｅａｎｄｃｏｎｄｉｔｉｏｎａｌｒａｎｄｏｍｆｉｅｌｄｓ，ｔｈｅｙｈａｖｅｇｏｏｄｐｅｒ～ｆｏｒｍａｎｃｅｉｎｔｈｅｓｐｅｃｉａｌｓｕｂ—ｔａｓｋｓ．ＴｈｅＷｏｒｄＳｅｇｍｅｎｔｅｒｐａｒｔｉｃｉｐａｔｅｄｉｎｔｈｅＳｅｃｏｎｄＩｎｔｅｒｎａｔｉｏｎａｌＣｈｉｎｅｓｅＷｏｒｄＳｅｇｍｅｎｔａｔｉｏｎＢａｋｅｏｆｆｉｎ２００５，ａｎｄａｃｈｉｅｖｅｄ９７．２％ａｎｄ９６．７％ｉｎｔｅｒｍｓｏｆＦ～ｍｅａｓｕｒｅｉｎＭＳＲａｎｄＰＫＵｏｐｅｎｔｅｓｔｒｅｓｐｅｃｔｉｖｅｌｙ．ＷｈｉｌｅｔｈｅＰＯＳｔａ套ｇｉｎｇａｎｄｎａｍｅｄｅｎｔｉｔｙｒｅｃｏｇ～ｎｉｔｉｏｎｍｏｄｕｌｅｓａｃｈｉｅｖｅｄ９６．１％ｉｎｐｒｅｃｉｓｉｏｎａｎｄ８８．６％ｉｎＦ—ｍｅａｓｕｒｅｒｅｓｐｅｃｔｉｖｅｌｙｉｎｏｐｅｎｔｅｓｔｗｉｔｈｔｈｅｃｏｒｐｕｓｔｈａｔｃａｍｅｆｒｏｍｓｉＸ－ｍｏｎｔｈｃｏｒｐｏｒａｏｆＣｈｉｎｅｓｅＰｅｏｐｌｅｓ’Ｄａｉｌｙ． ＫｅｙｗｏｒｄｓｌｅｘｉｃａｌａｎａＩｙｓｉｓ；Ｃｈｉｎｅｓｅｗｏｒｄｓｅｇｍｅｎｔａｔｉｏｎ；ｐａｒｔ—ｏｆ—ｓｐｅｅｃｈｔａｇｇｉｎｇ；ｎａｍｅｄｅｎｔｉｔｙｒｅｃｏｇｎｉｔｉｏｎ；ｌａｎｇｕａｇｅｍｏｄｅｌ 引 词法分析主要包括分词、词性标注与命名实体识别三项子任务，它是句法分析与语义分析的基础，其性能将直接影响到后续应用，如机器翻译、信息抽取、问答系统的性能．本文以国家自然科学基金重点项目“问答式信息检索的理论与方法”为背景，全面 收稿日期：２００５—１１一１５；修改稿收到日期：２００６一０６一０６．本课题得到国家自然科学基金重点项目“问答式信息检索的理论与方法”（６０４３５０２０）及国家自然科学基金（６０５０４０２１）资助．姜维，男，１９７８年生，博士研究生，研究方向为自然语言处理、词法分析、信息抽取．Ｂｍａｉｌ：ｊｗＳｅａＢｒｅｅｚｅ＠ｈｉｔ．ｅｄｕ．ｃｎ．王晓龙，男，１９５５年生，教授，博士生导师，主要研究领域为人工智能、自然语言处理．关毅，男，１９７０年生，博士，副教授，研究方向为问答系统、ｗｅｂ挖掘．赵健，男，１９７５年生，博士，研究方向为中文命名实体识别、信息抽取．吉目 万方数据
编译原理 简单样本语言的词法分析器
昆明理工大学信息工程与自动化学院学生实验报告 （2012 —2013 学年第 1 学期） 课程名称：编译原理开课实验室：信自楼44 年月日 一、实验目的及内容 设计、编制、调试一个词法分析子程序－识别单词，加深对词法分析原理的理解。 二、实验原理及基本技术路线图（方框原理图或程序流程图） 对给定的程序通过词法分析器弄够识别一个个单词符号，并以二元式(单词种别码，单词符号的属性值)显示。而本程序则是通过对给定路径的文件的分析后以单词符号和文字提示显示。 三、所用仪器、材料（设备名称、型号、规格等或使用软件） W INDOWS下的VISUAL C++6.0; 四、实验方法、步骤（或：程序代码或操作过程） #include
#define MAX 22 char ch =' '; string key[15]={"begin","end","if","then","else","while","write","read", "do", "call","const","char","until","procedure","repeat"}; int Iskey(string c){ //关键字判断 int i; for(i=0;i 中文语法的基本知识 一.语素和语素分类： 语素是最小的语音语义结合体，是最小的语言单位。语素按音节分类可以分成： ①单音节语素：如土、人、水、风、子、民、大、海等。 ②双音节语素，组成该语素的两个音节合起来才有意思，分开来没有与该语素有关的意义，双音节语素主要包括联绵字、外来词和专用名词。 A.双声，声母相同的联绵字：如琵琶、乒乓、湃、鞑靼、尴尬、荆棘、蜘蛛、踯躅、踌躇、仿佛、瓜葛、忐忑、淘汰、饕餮、倜傥、含糊、慷慨、叮当、蹊跷、玲珑、犹豫等。 B.叠韵，韵母相同的联绵字：如从容、葱茏、葫芦、糊涂、匍匐、灿烂、蜿蜒、苍茫、朦胧、苍莽、邋遢、罗嗦、怂恿、螳螂、桫椤、倥侗、蜻蜓、轰隆、当啷、惝恍、魍魉、缥缈、飘渺、耷拉等。 C.非双声叠韵联绵字：如蜈蚣、蓊郁、珊瑚、疙瘩、蚯蚓、惺忪、铃铛、奚落、褡裢、茉莉、蚂螂、窟窿、伉俪、蝴蝶、笊篱、蹦达、蟪蛄、狡狯、狡猾、蛤蚧、蛤蜊、牡丹、磅礴、提溜等。 D.外来词，由汉语以外的其他语种音译过来的词语。如干部、涤纶、甲克（夹克）、的士、巴士、尼龙、吉普、坦克、芭蕾、哒爹等。 E.专用名词，主要是地名、人和事物名称。如纽约、巴黎、北京、苏轼、李白、孔子、萝卜、菠菜、番茄、红薯等。 ③多音节语素，主要是拟声词、专用名词和音译外来词。如：喜马拉雅、珠穆朗玛、安迪斯、法兰克福、奥林匹克、白兰地、凡士林、噼里啪啦、淅淅沥沥、马克思主义、中华人民共和国 词 二.词和词的分类。 词是由语素组成的最小的造句单位。 (“单位”是名词类。) 从构成方式来看，可以分成： ①单纯词：由一个语素组成的词，自由的单音节语素和所有的双音节、多音节语素都可以组成单纯词。如：山、水、天、地、人、有、土、红、凑；仿佛、苍茫、蜈蚣、琉璃、参差、蹉跎；敌敌畏、阿司匹林、萨克斯、麦克风等。 ②合成词：由两个或两个以上的语素组成的词。 词法分析器实验报告 词法分析器设计 一、实验目的： 对C语言的一个子集设计并实现一个简单的词法分析器，掌握利用状 态转换图设计词法分析器的基本方法。利用该词法分析器完成对源程 序字符串的词法分析。输出形式是源程序的单词符号二元式的代码， 并保存到文件中。 二、实验内容： 1. 设计原理 词法分析的任务：从左至右逐个字符地对源程序进行扫描，产生一个个单词符号。 理论基础：有限自动机、正规文法、正规式 词法分析器(Lexical Analyzer) 又称扫描器(Scanner)：执行词法分析的程序 2. 词法分析器的功能和输出形式 功能:输入源程序、输出单词符号 程序语言的单词符号一般分为以下五种：关键字、标识符、常数、运算符,界符 3. 输出的单词符号的表示形式: 单词种别用整数编码，关键字一字一种，标识符统归为一种，常数一种，各种符号各一种。 4. 词法分析器的结构 单词符号 5. 状态转换图实现 三、程序设计 1．总体模块设计 /*用来存储目标文件名*/ string file_name; /*提取文本文件中的信息。*/ string GetText(); /*获得一个单词符号,从位置i开始查找。并且有一个引用参数j，用来返回这个单词最后一个字符在str的位置。*/ string GetWord(string str,int i,int& j); /*这个函数用来除去字符串中连续的空格和换行 int DeleteNull(string str,int i); /*判断i当前所指的字符是否为一个分界符，是的话返回真，反之假*/ bool IsBoundary(string str,int i); /*判断i当前所指的字符是否为一个运算符，是的话返回真，反之假*/ bool IsOperation(string str,int i); 2上帝那里没有现成的果实 三个人千辛万苦找到了上帝，请求他给予帮助。上帝问他们各需要什么。第一个人说他要一座大宅院；第二个人说，他要一个农庄；第三个人说他要一块大金条。上帝说他可以满足他们的需要。于是上帝给了第一个人一堆砖头，给了第二个人一把种子，给了第三个人一把沙子。 No Ready-made Fruit in God’s Hand Three guys finally got the God through trials and errors. They were eager to ask God for help. Right after the God asked what they want, the first man claim a big courtyard, the second a farmstead, and the third a bar of gold. God promised them. At last, the first man was given a pile of bricks, the second a bag of seed and the third a mass of sand. 3虫子的压力 有这么一种虫子，它的体长还不到一毫米，也许因为在电子显微镜下看起来像一头黑熊，所以人们叫它雄虫。它主要生活在淡水的沉渣，潮湿土壤以及苔藓植物的水膜中。最近日本冈山大学物理学家小野文久发现了一个惊人的现象：当20只小熊虫被放入密封的容器内，在实验室制造的7.5万个大气压下，20只熊虫只有两只死亡，其余的18只安然无恙。7.5万个大气压！它相当于每平方豪米要承受700多千克重物的压力，它足以上淀粉瞬间变性，生米顷刻为熟饭。自然条件下，地球上也只有180千米的地幔深处才拥有如此大的压力。 至今没有人能弄清楚熊虫为何如此能忍。不只是出于对这种超强生命力的尊重还是怀疑，有人叫它地狱之虫。一个长度不超过1毫米的微不足道的虫子，能承受命运给他如此的压力，相比较而言，我们这些自称是高级动物，智慧生命，万物之灵的人呢？在人的现实生活中，有多少小小的心结，小小的压力构成我们所谓的生存压力。在这样的压力下又有多少悲观失落之人将美好的人生称作地狱？现在一比才觉得，其实我们的压力就好比是真空，我饿美女的地狱就是天堂中的天堂。在那一刻，我在心里默默地鞠了一躬，不是为熊虫，而是感谢造物主没有把这样的压力降在人间。 W orm’s Pressure This is a worm whose body is no less than one millimeter. It is called 熊虫(XC) perhaps for the reason that it looks like a black bear under the microscop. The XC usually habited in the slurry of fresh water, wet soil and the 水膜of moss plants. Recently, there was an amazing news discovered by 日本冈山大学物理学家小野文久: when 20 little XC were placed in a sealed container under the 7.5 万个大气压making in experiment condition, there were only two died and the other 18 have no trouble at all. 7.5 万个大气压, equal to over 700 kilogram stress per square meter, which is powerful enough to它足以上淀粉瞬间变性and the rice ready to eat. In natural condition, this pressure can only be found in the 地幔beneath the earth 180 kilogram. Till now, nobody have an idea about the tolerance of XC. Someone also call it worm of hell out of admiration or suspicion. A worm, with its length less than one 汉语语法基础知识 词类和词性 （一）知识概述 词类是指词在语法上的分类，也就是把汉语里的所有词，根据它们的词汇意义和语法特点进行分类，这样得出的结果就是词类。现代汉语教学系统把词分为十二类： 实词可以分为： 1、名词：表示人或事物名称的词叫名词。 （1）表示人：老师、学生、作家、工人、鲁迅 （2）具体事物：天、地、花、草、天空、海洋 （3）抽象概念：方法、科学、法律、事业 （4）处所：北京、青岛、黄河、长江、三味书屋 （5）方位：东、西、南、北、上、下、前、后、左、右、里、外、内、中、间、旁、以前、以南、之下、之后、东边、西面、里头。 （6）时间：早晨、正午、晚上、半夜、上午、白天、夏天、立秋、今天、星期二 2、动词：表示动作行为、发展变化、心理活动等意义的词叫动词。 (1) 动作行为：穿、跳、走、纪念、朗诵。 (2) 存在变化：有、增加、缩小、扩大、发生。 (3) 心理活动：想、懊悔、喜欢、担心。 (4) 可能意愿：应该、应当、能够、愿意、必须、敢、肯、会、能、要、可以。 (5) 趋向：上、下、来、去、上去、下去、进来、进去、起来、上来。 (6) 判断：是、就是、正是 (7) 使令：使、让、派、请、叫、要求、命令、推举、允许、鼓动、鼓励。 3、形容词：表示事物的形状、性质或状态的词叫形容词。 （1）形状：大、小、高、圆、长、短、高大、肥胖。 （2）性质：好、坏、镇定、勇敢、乐观、伟大、优秀 （3）状态：愉快、慌张、急躁、迅速、朦胧、桔红 4、数词：表示数目的词叫数词。 （1）基数（确数）一、二、千、万、亿 （2）序数：第一、三叔、三年级、六楼、初五、老三。 （3）分数：三分之一、九成 （4）倍数：三倍、十倍、翻一番 （5）概数：十几概数、十余人、三十多岁、两三个、成千上万、很多人 5、量词：表示事物单位或行为、动作单位的词叫量词。 无量（表示人或事物单位的词） （1）个体：个、位、尺、只、台、条 （2）集体：批、帮、群、套、双、副、对、类 （3）不定量：些、点 （4）度量衡：丈、尺、里、亩 动量（表示动作行为的单位）次、回、下、趟、遍、阵、场、遭、焉 动量词也可以借用跟动作有关的事物的名词。如：画一笔、切一刀、工作一星期、学习一下午、踢一脚、送一车 说明：在现代汉语中，数词本身只表示抽象的数的概念，在计算事物或动作的数量时，数词的后面必须加上量词。数词跟量词连用就是数量词。 6、代词：具有指示、代替作用的词叫代词。代词可分为人称代词、指示代词、疑问代词。 ⑴人称代词：代替人或事物的名称的代词。 理工大学信息工程与自动化学院学生实验报告 （2012 —2013学年第一学期） 一、实验目的及容 编译技术是理论与实践并重的课程，而其实验课要综合运用所学的多门课程的容，用来完成一个小型编译程序。从而巩固和加强对词法分析、语法分析、语义分析、代码生成和报错处理等理论的认识和理解；培养学生对完整系统的独立分析和设计的能力，进一步培养学生的独立编程能力。 调试并完成一个词法分析程序，加深对词法分析原理的理解。 二、实验原理及基本技术路线图（框原理图或程序流程图） 1、待分析的简单语言的词法 （1）关键字： begin if then while do end 所有关键字都是小写。 （2）运算符和界符： := + –* / < <= <> > >= = ; ( ) # （3）其他单词是标识符（ID）和整型常数（NUM），通过以下正规式定义：ID=letter（letter| digit）* NUM=digit digit * （4）空格由空白、制表符和换行符组成。空格一般用来分隔ID、NUM,运算符、界符和关键字，词法分析阶段通常被忽略。 2、各种单词符号对应的种别码 3、词法分析程序的功能 输入：所给文法的源程序字符串。 输出：二元组（syn，token或sum）构成的序列。 其中：syn为单词种别码； token为存放的单词自身字符串； sum为整型常数。 二、所用仪器、材料（设备名称、型号、规格等或使用软件） 1台PC以及VISUAL C++6.0软件。 三、实验法、步骤（或：程序代码或操作过程） （1）程序代码： #include 中英文小故事 One day, a little monkey is playing by the well. 一天，有只小猴子在井边玩儿。 He looks in the well and shouts : 它往井里一瞧，高喊道： “Oh !My god! The moon has fallen into the well!” “噢！我的天！月亮掉到井里头啦！” An older monkeys runs over, takes a look,and says, 一只大猴子跑来一看，说， “Goodness me! The moon is really in the water!” “糟啦！月亮掉在井里头啦！” And olderly monkey comes over. 老猴子也跑过来。 He is very surprised as well and cries out: 他也非常惊奇，喊道： “The moon is in the well.” “糟了，月亮掉在井里头了！” A group of monkeys run over to the well . 一群猴子跑到井边来， They look at the moon in the well and shout: 他们看到井里的月亮，喊道： “The moon did fall into the well!Come on!Let’get it out!” “月亮掉在井里头啦！快来！让我们把它捞起来！” Then, the oldest monkey hangs on the tree up side down ,with his feet on the branch . 然后，老猴子倒挂在大树上， And he pulls the next monkey’s feet with his hands. 拉住大猴子的脚， All the other monkeys follow his suit, 其他的猴子一个个跟着， And they join each other one by one down to the moon in the well. 它们一只连着一只直到井里。 Just before they reach the moon, the oldest monkey raises his head and happens to see the moon in the sky, 正好他们摸到月亮的时候，老猴子抬头发现月亮挂在天上呢 He yells excitedly “Don’t be so foolish! The moon is still in the sky!” 它兴奋地大叫：“别蠢了！月亮还好好地挂在天上呢！” 英语寓言故事《狗和狼》 (类别：英语故事浏览人数：11297) A wolf was almost dead with hunger. A house-dog saw him, and asked, "Friend, your irregular life will soon ruin you. "Why don't you work steadily as I do, and get your food regularly?" "I would have no objection," said the wolf, "if I could only get a place." "I will help you," said the dog. "Come with me to my master, and you shall share my work." 实验二：词法分析 一、实验目的：编制一个读单词过程，从输入的源程序中，识别出各个具有独立意义的单词， 即基本保留字、标识符、常数、运算符、分隔符五大类。并依次输出各个单词的内部编码及 Error”，然后跳过错误部分继续显示） 二、估计实验时间：1.课余准备15小时；2.上机二次4小时；3.完成实验报告5小时。 三、实验过程和指导： （一）准备：1.阅读课本有关章节，花一周时间明确语言的语法，写出基本保留字、标识符、 常数、运算符、分隔符和程序例。2.初步编制好程序。3.准备好多组测试数据。 （二）上课上机：将源代码拷贝到机上调试，发现错误，再修改完善。第二次上机调试通过。 （三）程序要求：Array程序输入/输出示例： 如源程序为C语言。输入如下一段： main() { int a,b; a = 10; b = a + 20; } 要求输出如右图。 要求： 识别保留字：if、int、for、while、do、return、break、 其他的都识别为标识符； 常数为无符号整形数； 运算符包括：+、-、*、/、=、>、<、>=、<=、!= 分隔符包括：,、;、{、}、(、) 程序思路（仅供参考）： 0.定义部分：定义常量、变量、数据结构。 1.初始化：从文件将源程序全部输入到字符缓冲区中。 2.取单词前：去掉多余空白。 3.取单词后：去掉多余空白（可选，看着办）。 4.取单词：利用实验一的成果读出单词的每一个字符，组成单词，分析类型。（关键是如何判断取单词结束？取到的单词是什么类型的单词？） 5.显示结果。 （四）练习该实验的目的和思路： 程序开始变得复杂起来，可能是大家以前编过的程序中最复杂的，但相对于以后的程序来说还是简单的。因此要认真把握这个过渡期的练习。程序规模大概为200行。本实验和以后的实验相关。通过练习，掌握对字符进行灵活处理的方法。 （五）为了能设计好程序，主意以下事情： 1.模块设计：将程序分成合理的多个模块（函数），每个模块做具体的同一事情。 2.写出（画出）设计方案：模块关系简图、流程图、全局变量、函数接口等。 3.编程时注意编程风格：空行的使用、注释的使用、缩进的使用等。 四、上交： 1.程序源代码； 中文语法 语法是语言组合的规律和法则。汉语语法分析可以按由小到大分为五级单位，即语素（字）、词、短语、句子、句群。 二、为什么要学习语法 为了掌握语言的组合规律、规则，提高理解语言的、运用语言的能力。 第一节、词类 一、实词和虚词 词是由语素（字）构成的。词按语法功能和语法意义可分为实词和虚词。 实词是有实在意义的词,它可分为:名词、动词、形容词、数词、量词、代词等六类。 虚词是没有实在意义的词，它可为副词、介词、连词、助词、叹词、拟声词等六类。 二、名词 名词是表示人或事物名称的词。 1、普通名词：牛、人、学生、云、飞机、菜 2、专有名词：中国、黄河、泰山、毛泽东 3、抽象名词：精神、文化、人生、思想 4、时间名词：现在、去年、明天、星期一 5、方位名词：上、前、东、夏天、以上、之南、之东、一旁、底下、跟前、当中、里外、左右、上下 三、动词 动词是表示动作、行为、存在、变化、心理活动等意义的词。 1、表示动作行为：看、听、笑、唱、跳、飞、劳动、研究、认识、安慰、团结、休息 2、表示心理活动：爱、恨、怕、想、希望、喜欢、回忆、思考、理解、厌恶 3、表示发展变化：增加、扩大、提高、降低 4、表示存在、出现、消失：存在、出现、消失、死亡、停、丢 5、表示使令：叫、让、派、请、使、要求、命令、禁止、 6、表示可能、意愿——能愿动词：能、能够、会、可以、可能、应该、应当、必须、要、愿意、需要、肯、敢、情愿 7、表示动作趋向——趋向动词：上、下、来去、进、出、过、起来、回去 8、表示判断——判断词：是 四、形容词 形容词是表示人、事物的形状、性质或者动作、行为、发展、变化状态的词。 1、表示形状：大、小、圆、粗、滑、平、高、低、宽、窄、肥、胖、美、丑、温柔、平缓、笔直 2、表示性质：好、坏、冷、热、酸、甜、苦、软、聪明、朴素、老实、正确、勇敢、特殊 3、表示状态：快、忙、急、稳、轻松、高兴 五、数词 数词是表示数目的词。数词可分为基数、序数、分数、小数、倍数和概数。 1、基数：一、二、三、……十、百、千、万、亿 2、序数：第一…头一回、初一…老大…老幺 3、分数、25?、几分、几成 4、小数：0?2 5、12?34 5、倍数：一倍… 6、概数：几、两、来、多、把、左右、上下、以上、以下、成千、上万、近亿、三四个、两三年 简单词法分析器 1、将源文件中的单词识别出来，以用'$'为首的标识符标记识别出的单词 2、单词符号及内部表示如表： 单词符号种别编码助记符内码值 DIM 1 $DOM — IF 2 $IF — DO 3 $DO — STOP 4 $STOP — END 5 $END — 标识符 6 $ID 内部字符串 常数7 $INT 标准二进制形式= 8 $ASSIGN — + 9 $PLUS — * 10 $STAR — ** 11 $POWER — ; 12 $SEMICOLON — { 13 $LBRACE — } 14 $RBRACE — /* * 词法分析：将源文件中的单词符号一一识别 * 并将其与助记符保存到文本文件 */ #include "iostream" #include "string" using namespace std; //reserve保留字 string reserve[5] = {"DIM","IF","DO","STOP","END"}; //结构体数组，保存已识别的单词 struct table { string str; string name; }table[400]; int count = 0; //判断是否为保留字 bool Reserve(string str) { bool flag = false; for(int i=0; i 《词法分析》设计说明书 学生姓名 学 号 5011110122 5011110133 5011110128 所属学院 信息工程学院 专 业 计算机科学与技术 班 级 计算机15-1班 信息工程学院 《编译原理及实践》结课大作 业 摘要 编译，简单的说，就是把源程序转换为可执行程序。从hellow worl说程序运行机制里面简单的说明了程序运行的过程，以及一个程序是如何一步步变成可执行文件的。在这个过程中，编译器做了很多重要的工作。对于编译的内部实现，也就是编译的原理。 这篇论文主要说的是编译器前端，词法分析器的原理，最后会给出一个词法分析器的简单实现。 编译简单的说，就是把源程序转化为另一种形式的程序,而其中关键的部分就是理解源程序所要表达的意思，才能转化为另一种源程序。 可以用一个比喻来说明问题：人A和人B想要交谈，但是他们都不知道彼此的语言，这就需要一个翻译C，同时懂得A和B的语言。有了C做中间层，A和B才能正常交流。C的作用就有点像编译器，它必须能理解源程序所要表达的意思，才能把信息传递给另一个。编译器也一样，它的输入是语言的源文件（一般可以是文本文件）对于输入的文件，首先要分离出这个输入文件的每个元素（关键字、变量、符号、、），然后根据语言的文法，分析这些元素的组合是否合法，以及这些组合所表达的意思。 程序设计语言和自然语言不一样，都是用符号来描述，每个特定的符号表示特定的意思，而且程序设计语言是上下文无关的。上下文无关就是某一个特定语句所要表达的意思和它所处的上下文没有关系，只有它自身决定。 这篇论文主要说的就是词法分析，也就是把输入的符号串整理成特定的词素。 关键词：单片机；词法分析 中英文小故事 Home 家 An artist who had painted many pictures of greatbeauty found that he had not yet painted the one "real" picture. 一位画过许多杰出精美画作的艺术家，发现自己甚至连幅“真的”画都没有画出来。 In his search along a dusty road, he met an agedpriest who asked him where he was going . 他沿着一条布满尘土的路一路追寻，他遇到一位年老的牧师，牧师问他要去哪里。 "I don’t know, " said the artist, "I want to paint the most beautiful thing in the world . Perhaps you can direct me to it. " 艺术家回答：“我不知道，我想画世界上最美好的东西。也许，你能给我指引。”"How simple, " replied the priest, "in any church or creed, you will find it—— "faith" is the most beautiful thing in the world. " 牧师说，“很简单，在任何教堂或者信条中，你会发现——世界上最美好的东西是“信仰”。 The artist traveled on . Later , he met a young bride who told him that the most beautifu thing in the world is :"love". "love" makes the world go round. 艺术家继续前行。后来，他遇到一个年轻的新娘，她告诉他，“爱”是世界上最美好的东西。 I builds poverty into riches. sweetens tears and makes much of little . Without love there is no beauty. “爱”使世界运转，让贫穷变得富有，泪水变成甜蜜，渺小变成伟大。没有爱，也就没有美。 Still the artist continued his search and met a weary soldier. 艺术家继续他的追寻，他又遇到一个疲惫不堪的士兵。中文语法的基本知识
词法分析器实验报告
励志小故事(中英文对照)
(完整版)汉语语法基础知识
编译原理实验报告一 简单样本语言的词法分析器
中英文小故事
词法分析
中文语法词性和句式
简单词法分析器
词法分析课程设计
中英文小故事资料