Posts in category compiler

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 python - 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 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 python - Tagged , , ,

yacc,ast and graphviz

六15
2007 1 Comment Written by Filia.Tao

这几天忙着写编译原理课程设计的另一部分. Seu YACC的实现.

这个程序的核心算法实现不是有我来完成,我负责后端输出的模板代码的书写.

实际上就是一个基于LALR分析表的parser.

我附带加上了生成抽象语法树的功能, 并输出DOT 文件,通过graphviz 生成图片.

下面贴一段Min-C 语言的抽象语法树.(图片比较大)

ast.png

对应的代码为

int main ( )
{
int x = 0 ;
int b = 2 ;
int c = 5 ;
int d = 6 ;
int a = b ;
if ( x < y )
{
int x = y ;
}
while ( c == d )
{
int m = c + d ;
m = x + y ;
}
}

Tagged , ,

how to write lex (11)

五07
2007 Leave a Comment Written by Filia.Tao

DFA最小化的详细算法
说明:下面的算法在空间复杂度上有一点小问题,我已经改用deque来实现.算法的基本思想是一致的.
下面的算法比使用deque的实现方式更通俗易懂,所以没有更新下面的描述了.
数据结构：

  • 一个MAP map<int,int> mapping　表示原来的状态编号对应到最小化以后的状态编号
    mapping[1] = 2 表示原来的状态１，对应到最小化后状态２中。
  • 一个min-DFA 状态列表sss。其中的元素为未最小化的DFA的状态的集合。
    上面的MAP中的最小化状态就用列表的下标表示。
  • 一个循环控制量count

算法：

  1. 把DFA的状态分成若干个集合。
    一个是非终态集合。终态集合中对应不同规则的终态放到不同集合中。
    把这些集合加入到sss中。count = sss.size();
  2. 初始化mapping
  3. 如果count > 0 从sss中取下一个集合,否则到6
  4. 遍历字母表判断是否可以分割这个集合。(关于是否可以分割的定义,书本上都有，这里就不写了)
    如果某一个字符可以分割这个集合.

    • 将分割后的来两个集合s1,s2加入到sss中，
    • 对连个集合中的状态更新mapping.
      对s1中的状态i，mapping[i] = sss.size() -2 ;
      对s2中的状态j, mapping[j] = sss.size()-1;
    • count = sss.size() – 当前集合的在sss中下标 -1
    • 退出字母表遍历

    如果任何字符都不能分割这个集合

    • 将当前集合加入到sss的末尾。
    • 对集合中的状态更新mapping.
      对当前集合中的状态i，mapping[i] = sss.size() -1 ;
    • count –
  5. 回到3
  6. 从mapping 中收集信息,建立min-DFA.(用mdfa 表示，原DFA用dfa表示）
    • 初态　mdfa.initialState = mapping[dfa.initialState]
    • 状态　foreach( i in dfa.states) mdfa.states.insert(mapping[i])
    • 转换
      foreach( t in dfa.transitions)
      mdfa.transitions.insert(triple(mapping[t->from],mapping[t->to],mapping[t->label]))
    • 终态和meta data
      foreach( s in dfa.finalStates)

      mdfa.finalStates.insert(mapping[dfa.finalStates])
      if (!mdfa.meta[mapping[s]] || mdfa.meta[mapping[s]] > dfa.meta[s])
      //这里体现了lex输入文件中先出现的规则优先的原则。mdfa.meta[mapping[s]] = dfa.mata[s]

Posted in lex - Tagged
« Older Entries

最近评论

My Tweets

分类

文章归档