Posts in category 计算机科学

fInterpretor中静态语义检查的实现

四27
2008 Leave a Comment Written by Filia.Tao

这几天在解释器fInterpretor 中加入了静态语义检查

静态语义检查分为下面几个方面:

  1. 名字检查
    • 类型名
    • 函数名
    • 变量名
  2. 类型匹配检查
    • 各种运算 (比如算术,逻辑)的类型约束
    • 函数调用实参和形参的类型匹配
    • 函数实际返回类型和声明的返回类型是否匹配
  3. 变量初始化检查 (非必须)
    • 检查局部变量在引用前是否已经初始化 (尚未实现)
现在基本对L1 语言做好了上述的检查, 中间做了好多弯路.
主要是在进行静态类型检查的时候在类型约束信息放在哪里的这个问题上一开始做了错误的选择,过度依赖Python的语言特性修饰器,动态的添加类型约束到一个统一的地方.
最终的选择还是比较”分布式的”, 每个类型定义一个 do_type_trans(self, op_name, arg = None) 方法对各种操作进行类型约束检查,同时返回对应操作后正确的类型(类型计算), 这样还有一个好处就是将”类型计算”的逻辑移动到类型定义文件中,而不是写在ASTAction 中.
嗯.基本就是这样了. 争取在5.1前把这些加入到L2语言中. 还有更重要的就是测试了. 特别是需要覆盖测试,测试目标语言的各种特性是否被正确实现了.
Posted in compiler, python - Tagged , , , , ,

数据结构总结－堆

十14
2007 2 Comments Written by Filia.Tao

堆结构是一类很重要的数据结构，特别是在实现优先队列方面。
堆结构实际上都是树（或森林），不过按节点的存储方式又可以分为两种

  1. 顺序存储
    这种情况下，必须保持是完全树。 （在插入,删除后及时调整)
    可以通过下标运算找到父节点，字节点。
  2. 链接存储
    如果是二叉树，一般就用LeftChild,RightChild 两个指针。
    否则一般用环链表表示一个 节点的子女。

下面的表格在blog 中显得很拥挤，建议在这里查看.


数据结构 存储方式 定义与性质 支持的操作 及 复杂度（分摊）
最大堆 顺序存储 完全二叉树，最大树 插入
O(log n)
删除最大元素 O(log n)
最小最大堆 顺序存储 完全二叉树，树的各层交替为最小层和最大层 插入
O(log n)
删除最大元素 O(log n)
删除最小元素 O(log n)
双堆 顺序存储 完全二叉树
或者为空,或者同时满足:
1.根结点不含元素
2.左子树是最小堆
3.右子树为最大堆
4.若右子树不为空,设i 为左子树中的任意结点,
j为右子树的对应结点.
若j不存在,则令j为右子树中对应i的父结点的结点。
必有结点i的key 小于 结点j的key值		 插入
O(log n)
删除最大元素 O(log n)
删除最小元素 O(log n)
左偏树
(最小/最大)		 链接存储 1.是左偏树
每一个内部结点x 有
shortest(LeftChild(x))
>=shortes(RightChild(x))
2.是最小/最大树		 插入
O(log n)
删除最小/最大元素 O(log n)
合并 O(log n)
二项式堆
(最小/最大)		 链接存储 最小/最大二项式树的集合.
度为k的二项式树(记作Bk)定义为:
若k=0,该树只有1个结点.
若k>0,该树的根的度为k,其子树为B0,B1,…..,Bk-1		 插入 O(1)
删除最小/最大元素 O(log n)
合并 O(1)
斐波纳契堆
(最小/最大)		 链接存储 最小/最大树的集合.
二项式堆是斐波纳契堆的特殊情况.
使用双环链表,并在结点中加入parent和childcut.
关键是瀑布修剪		 插入 O(1)
删除最小/最大元素 O(log n)
合并 O(1)
减少指定结点key值
O(1)
删除指定结点元素
O(log n)
Posted in 算法 - Tagged , ,

使用PLY 构建一个汇编器(2)

九29
2007 2 Comments Written by Filia.Tao

Lex 和Yacc 总是需要合作来完成任务. Lex 返回token , Yacc 根据产生式来生成语法分析器.
在PLY 中可以非常容易的书写语义动作, 完成我们的任务. 类似 lex, yacc 也使用以”p_”开头的函数(文档字符串表示产生式), 函数的内容就是语义动作.根据我们的目标, 我们需要对输入文件做三次扫描.

  1. 翻译.
    • 将数据/指令翻译成mif 文件的格式 , 这里我们使用16 进制.
    • 建立符号表
    • 对于翻译时还没有得到地址的符号名, 使用类似{BUF_16} 的字符串表示. (16位的BUF变量)
  2. 符号替换
    • 将类似{BUF_16}的记号 用符号表中的地址替换
    • 将2进制转换成16进制
  3. 添加注释
    • 将原来文件的内容放在 翻译后的代码后面. (一行对应一行)

下面是代码, 比较长. 而且有一些Ugly.
READ MORE »

Posted in compiler, python - Tagged ,

使用PLY 构建一个汇编器(1)

九28
2007 Leave a Comment Written by Filia.Tao

PLY 是一个Python 的Lex/YACC 实现. 官方网站在这里http://www.dabeaz.com/ply/
这学期有一门课叫 ” 计算机综合课程设计-基于MIPS16的SOC设计实践” ,其中有一部分是实现一个汇编器. 将MIPS汇编程序转换成Quartus 的mif 文件.

这样的需求使用Lex/YACC 最合适不过, 本来是想使用Flex/Bison , 或上学期自己实现的lex和yacc. 但是在尝试了一下后,决定放弃.原因在于C/C++ 对文本的操纵比较麻烦,另外yacc 的语义动作限制比较大. (主要是数据类型问题)

而PLY 这个实现学习成本很低, 而且很Pythonic.加入符号表等等功能也很简单.
首先我们先来看我们要处理的汇编文件的格式.

1
2
3
4
5
6
7
8
9
10
11
12
13

ORG_DATA  0000           ;The start address of data
BUF   DW  00FF, 5500
NEXT  DW  0CFF, 5D00
ORG_CODE  0000		       ;The start address of code
start:  addi  $t0, $Zero, 0     ;A label for the first statement,$t0=0
 	lw    $v0, BUF($t0)      ;$v0=00FF  (BUF[0])
 	addi  $t0, $t0, 2
 	lw	  $v1, BUF($t0)	 ;$v1=5500  (BUF[2])
 	add   $v0, $v0, $v1	;$v0=$v0+$v1=55FF
 	addi  $t0, $t0, 2
 	sw    $v0, BUF($t0)    	;BUF[4]=55FF
 	j	  start
end  start

下面我们来书写汇编文件的lex 定义. token 类型大概有下面这些.

  1. MIPS 基本指令 (课程设计的要求是31条)
  2. 若干伪指令 (很少, 主要有ORG_DATA , ORG_CODE 等)
  3. 符号地址 / 标号
  4. 注释
  5. 立即数
  6. 地址
  7. 其他的符号 (逗号,括号, 冒号等)

PLY 的lex 文件格式其实就是一个标准的Python 文件, 不过使用一些规定的格式/名字来指定.
(下面的代码比较长, 所以我要用–MORE–了)
READ MORE »

Posted in compiler, python - Tagged , , ,

Find the Array

九13
2007 1 Comment Written by Filia.Tao

接着做题.原题在这里 Find the Array.

草草的翻译一下就是

有一个原始数组o[1..n], 1..n的一个排列. 另有一个数组, g[1..n] , g[i] 表示在o[i+1..n] 中比 o[i] 小的数的数目. 给定g 求 o .

问题上挺简单的.我的解答如下:

the given array g[1..n]
the original  array o[1..n]

let i = the index of first 0 in g then o[i] = 1
for j =1 to i
     g[i] = g[i] -1
again , let i = the index of first 0 in g , then o[i] = 2

repeat the steps utils find all the element.

我的这个算法时间复杂度为 2n + 2(n -1) + 2(n -2)+ 2(n-3) + ….. 2 * 1 =O(n**2)
很不好.. 网站是说有nlogn 的方法, 我想不出来….
这个算法实际上和counting sort 有一些类似.
更抽象一点的话, 都是用某一种数据结构来保存了次序信息. (昨天BBS 上有人讨论胜者树, 也是一种保存次序信息的数据结构).

Posted in 算法 - Tagged
« Older Entries

最近评论

My Tweets

分类

文章归档