分享
 
 
 

我的编译器 C3编译器

王朝other·作者佚名  2006-01-09
窄屏简体版  字體: |||超大  

C3编译器

2.1 结构

其实,既然语言已经确定了,剩下的事情就好办了。接下来我们要做的事情就是手工实现C3的编译器,而后面我们将使用我们的自动分析器来处理其他语言,这样我们就可以看到它们的区别。

由于要表示成一种内部表示,也就意味着要设计一个类集,来分别表示这些东西。首当其冲的就是Rule,这是毫无疑问的。

Class Rule

Public Name As String

Public RuleText As String

End Class

我想谁也不会使用这样的类。这样编译出来的结果根没有编译是一样的——都是文本格式的规则说明。我们需要一个语法规则的表示方法!再经过了长期的思考与试验之后,我选择了一个我称之为路线图的方法(在后来的进一步学习当中我发现这与Wirth在1976年提出的一方法有异曲同工之处)。

左图就是一个基本图元。但是只是这样的话它并不好使,原因与上面的Rule类是一样的——太简单了,我们需要一些实用的东西以及后面的编译器用得到的有用的信息——就因为这是一个服务程序。我们要使它改变并使它尽量接近C3并尽量接近计算机语言的表示,经过大量尝试性的开发使其不断的完善从而得到了下面的表示方案。

路线图的基本图元的表示方法:

普通图元:

可选图元:

*闭包图元:

+闭包图元:

注:非法出口一律不予表示。

右下角标有小方块的图元表示这是一个可选的图元即可以匹配也可以不匹配。

闭包的匹配出口都是指向自己的,这是由于只要匹配,就要继续进行匹配,而只有不再匹配的时候才由不匹配出口转到下一个图元。而正闭包其实就是星闭包之前加上一个副本,并且要求必须匹配,这与其数学含义是相同的。

下面是几个经过路线图化的规则:

Integer=>Digit+

String=>""""((""""!)|"""""")*""""

Float=>Digit*"."Digit+

于是产生了RuleMap和RuleMapItem分别对应路线图和图元。因而RuleMap是一个集合类,按照.NET的要求它需要实现IEnumeratable接口。而RuleMapItem需要可选、匹配出口、不匹配出口和名称。

Class RuleMap

Implements IEnumeratable

Public Function GetEnumerator() As IEnumerator

Public Name As String

Public Count As Integer

Public Item(Index As Integer) As RuleMapItem

Public Function Add(Name As String) As RuleMapItem

End Class

Class RulMapItem

Public Name As String

Public Optional As Boolean

Public Match As RuleMapItem

Public DisMatch As RuleMapItem

End Class

语法规则的定义基本上完成了,接下来就是规则的容器:Section。由于在语义上Section也是一条规则,只不过其规则的代码是其内部所有成员的或操作,也即可以匹配其内部任何一个规则,所以理所当然的Section继承自Rule。但是作为容器类,它也应当实现Ienumerable接口。

Class Section

Inherits Rule

Implements IEnumerable

Public Function GetEnumerator() As IEnumerator

Public Count As Integer

Public Sub Add(r As Rule)

Public Sub Remove(Index As Integer)

Public Item(Index As Integer) As Rule

End Class

由于Class与Section唯一的区别只是名称不同,位置不同,所以又在Section中加入了IsClass属性。

2.2路线图的组合原则

路线图的内部最重要的一点就是编译过程中路线图的合法与非法出口都应当指向何处?比如: (a|(b[c]))d

a分析完了之后是b,为什么放在不匹配出口?因为他们是或的关系,只有a不匹配时才会考虑b路径上的匹配。于是有

那c呢?由于其与b为联结关系所以应该在b的合法出口,也就是匹配出口。那又为什么a的匹配出口不指向c呢?因为a与c根本就不在一个表达式里!又不对了——a与b也不在一个表达式里呀。没错,但是a、b所在的表达式在同一表达式里。而实际上可选的c也是一个表达式只不过只有一项。

之后就是最复杂和麻烦的地方:d,它与前面的表达式为联结关系,那么应该放在合法出口。那么那里是合法出口?按照C3的定义可选图元的不匹配出口也是合法的出口。都指向d?分析一下可选的含义吧,匹配不匹配都要匹配下一个。也就是说,匹配出口与不匹配出口都要指向后继图元,也就是d。

完了吗?如果输入是一个以a开头的字符串,又如何?按照这个规则ad是可以接受的。但是如果按照上面的路线图扫描的话,只有a被接受,d并没有被接受。这显然是错误的。所以a的匹配出口也应当指向d。

但是,这个问题并不指向上面说的那么简单——如何找到所有这3个合法出口?显然我们需要查找所有的合法出口,并且对所有的合法出口进行赋值。其间有两个问题,其一,由于路线图是网状结构,如何遍历,这其实在算法类书籍中都有描述,这里不再详细说明;其二就是如何判断那个出口是合法的,当然匹配出口只要不指向任何图元永远都是合法的,主要就是不匹配出口的问题——上面的c就是一个典型的例子——解决方案就是,可选图元的不匹配出口为合法出口。

基本上框架设计完成了,来考虑一下实现问题、软件工程问题以及逻辑问题。首先是实现问题,由于类、接口与重点、难点的算法都已经设计完成,剩下的只是填写代码,比较简单。然后是软件工程问题,是否有健壮性、可维护性以及可扩展性,最值得注意的是可扩展性,因为这个试验性质的项目并不是一个成熟的技术,所以可扩展性显得非常重要,因为我们不清楚什么时候我们可能忘了点什么东西没有添加进去。而且逻辑上则可以非常清楚。

其实现阶段考虑上面的问题除了可扩展性之外没有太多需要在意的地方。在具体的实现上,我采取了将编译部分的代码集成在这些类中。但实际上这并不是一个好主意,因为这样就需要一个专门的类来处理编译问题,并且由于编译代码的分散时维护起来有些麻烦。相对的使用完全的分体式的C3编译器来处理虽然可能比较复杂(相对而言),但可维护性要好得多。

上面提到的专门处理编译问题的类就是后来诞生的Grammar类。它全权负责C3的编译工作以及编译后的序列化/反序列化工作。较详细地说明见匹配规则说明文档。

之后在制作分析器的过程中我们需要出错信息,这样就在上面的架构下添加函数及相应的类实现了出错信息的自动生成。但是,既然在这里能够自动生成,那么在分析其运行时当然也可以自动生成,于是这些代码实际上用处并不大,但为了防止将来又需要,从1.0版本即一直保留至今,但是在1.2版以后已经不再使用。

在上述工作完成之后,我写了一个C-,一个C的简化版本,并针对.NET作了相应的改变,详见程序测试报告1,当然这份报告是在扫描器与分析器都完成之后才出来的,之前只是测试其功能是否能够实现、序列化/反序列化是否正确。通过这一点也可以了解到测试用例是多么的重要,没有用例我们甚至不能对我们的代码有半点信任——根本没有测试,怎么知道对不对?

 
 
 
免责声明:本文为网络用户发布,其观点仅代表作者个人观点,与本站无关,本站仅提供信息存储服务。文中陈述内容未经本站证实,其真实性、完整性、及时性本站不作任何保证或承诺,请读者仅作参考,并请自行核实相关内容。
2023年上半年GDP全球前十五强
 百态   2023-10-24
美众议院议长启动对拜登的弹劾调查
 百态   2023-09-13
上海、济南、武汉等多地出现不明坠落物
 探索   2023-09-06
印度或要将国名改为“巴拉特”
 百态   2023-09-06
男子为女友送行,买票不登机被捕
 百态   2023-08-20
手机地震预警功能怎么开?
 干货   2023-08-06
女子4年卖2套房花700多万做美容:不但没变美脸,面部还出现变形
 百态   2023-08-04
住户一楼被水淹 还冲来8头猪
 百态   2023-07-31
女子体内爬出大量瓜子状活虫
 百态   2023-07-25
地球连续35年收到神秘规律性信号,网友:不要回答!
 探索   2023-07-21
全球镓价格本周大涨27%
 探索   2023-07-09
钱都流向了那些不缺钱的人,苦都留给了能吃苦的人
 探索   2023-07-02
倩女手游刀客魅者强控制(强混乱强眩晕强睡眠)和对应控制抗性的关系
 百态   2020-08-20
美国5月9日最新疫情:美国确诊人数突破131万
 百态   2020-05-09
荷兰政府宣布将集体辞职
 干货   2020-04-30
倩女幽魂手游师徒任务情义春秋猜成语答案逍遥观:鹏程万里
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案神机营:射石饮羽
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案昆仑山:拔刀相助
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案天工阁:鬼斧神工
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案丝路古道:单枪匹马
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案镇郊荒野:与虎谋皮
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案镇郊荒野:李代桃僵
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案镇郊荒野:指鹿为马
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案金陵:小鸟依人
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案金陵:千金买邻
 干货   2019-11-12
 
推荐阅读
 
 
 
>>返回首頁<<
 
靜靜地坐在廢墟上,四周的荒凉一望無際,忽然覺得,淒涼也很美
© 2005- 王朝網路 版權所有