Posted on 六月 30th, 2010 in 备忘 | 9 Comments »
随便写了下，没仔细调试。
大约这么定义
double parse_expr(char *input, char **output);
input就是表达式的字符串，output是解析剩下的部分。如果output==input，就是解析失败。如果正确，返回运算结果。
用起来大约这样
char *out, *exp="2+(1+3)*4";
double r = parse_expr(exp, &out);
if (out==exp){
printf("parse fail\n");
return 0;
}
printf("%s => %f \n", exp, r);回头想下，思路跟以前写的parser几乎是葫芦画瓢，也该算是递归下降吧。
代码如下
exp.h
double parse_expr(char *input, char **output);
double parse_term(char *input, char **output);
double parse_fact(char *input, char **output);
double parse_numb(char *input, char **output);
exp.c
#include "exp.h"
// expr ::= term {[+-] term}
double parse_expr(char *input, char **output){
double r=0;
char *tmp, op;
tmp = input;
// factor
r = parse_term(tmp, output);
if (output==tmp){
return 0;
}
// {[+-] term}
tmp = *output;
while ((op=*tmp)=='+' || op=='-'){
double r2 = parse_term(++tmp, output);
if (tmp==*output){
*output = input;
return 0;
}
r = (op=='+')? r+r2: r-r2;
tmp = *output;
}
return r;
}
// term ::= factor {[*/] factor}
double parse_term(char *input, char **output){
double r=0;
char *tmp, op;
tmp = input;
// factor
r = parse_fact(tmp, output);
if (output==tmp){
return 0;
}
// {[*/] factor}
tmp = *output;
while ((op=*tmp)=='*' || op=='/'){
double r2 = parse_fact(++tmp, output);
if (tmp==*output){
*output = input;
return 0;
}
r = (op=='*')? r*r2: r/r2;
tmp = *output;
}
return r;
}
// fact ::= (expr) | numb
double parse_fact(char *input, char **output){
double r=0;
char *tmp;
// (expr)
if (*input=='(') {
tmp = input+1;
r = parse_expr(tmp, output);
if(**output==')'){
(*output)++;
return r;
}
// if fail, output == input
else {
*output = input;
return 0;
}
}
// numb
r = parse_numb(input, output);
return r;
}
double parse_numb(char *input, char **output){
double r = 0;
char ch, *tmp=input;
while((ch = *tmp++)>='0' && ch<='9'){
r = r*10+ch-'0';
}
*output = tmp-1;
return r;
}main.c
int main(){
double r;
char *out, exp[1024];
scanf("%256s", exp);
r = parse_expr(exp, &out);
if (out==exp){
printf("parse fail\n");
return 0;
}
printf("%s => %f \n", exp, r);
return 0;
}
Posted on 五月 26th, 2010 in 备忘 | 4 Comments »
看的这个教程 http://share.solrex.org/WriteOS/
仿照《自己动手写操作系统》的格式，除却gas确实很囧的因素，大体上还是不错的。万事开头难，在开头的bootloader这里卡了好久的说…不过动手写一下也不过半小时的功夫 TvT
机器在启动的时候可能是遍历每个磁盘分区，若有发现第512字节位置是个0xAA55的魔数，就认为这是个引导的分区了。然后就把它的前512字节装入内存，从0×7c00位置开始执行。这就是最简单的引导方式了好像。
我们把汇编代码编译成一个512bytes的二进制文件，再把它放到一个软盘的映像里就好。
boot.S
[bits 16] ;real mode
[org 0x7c00] ;put code start at 0x7c00
[section .text]
_start:
mov ax, cs ; init seg registers
mov ds, ax
mov es, ax
call _print_str
_print_str:
mov ax, str
mov cx, len
mov bp, ax
mov bx, 0x000c
mov dl, 0
mov ax, 0x1301
int 0x10 ;int 0x10, just as manual says
_loop:
jmp _loop ; forever loop
str: db "screw you guys all fucked up~",10,13
len: equ $-str
times 510-($-$$) db 0 ; fill the rest with 0
dw 0xAA55 ; magic number编译之
生成一个boot.bin，下一步搞个软盘镜像
dd if=boot.bin of=boot.img bs=512 count=1
dd if=/dev/zero of=boot.img skip=1 seek=1 bs=512 count=2879
ls -l 下，大约会是这样
-rwxr-xr-x 1 ssword ssword 512 2010-05-26 21:28 boot.bin
-rw-r--r-- 1 ssword ssword 1474560 2010-05-26 21:28 boot.img
-rw-r--r-- 1 ssword ssword 399 2010-05-26 21:28 boot.S
然后打开virtualbox，设置软驱映像为boot.img。启动虚拟机就可以看到一个可爱的”screw you all”什么的了 >v<
每次修改代码一般只会涉及一部分文件，大部分代码都是不必重复编译的。而且编译明显是分步骤也有依赖关系，比如要测试程序就得先链接出一个可执行文件，要链接就得先编译成.o。。。所以就有了make，自动分析任务的依赖关系，只对有变更的文件执行编译，省心省时间。
不过make的语法晦涩啊…就有了rake
rake提供了file函数可以指明文件的依赖关系，比如：
file 'fdict.o' => ['src/fdict.c', 'src/fdict.h'] do
sh 'gcc -Wall -c src/fdict.c'
end
file 'test.o' => ['src/test.c'] do
sh 'gcc -Wall -c src/test.c'
end
file就是个ruby的函数调用，把重复的东西去掉很简单
CFlags = '-Wall'
[
['src/fdict.c', 'src/fdict.h'],
['src/test.c']
].each do |fn_c, *_|
fn_o = File.basename(fn_c).ext('o')
file fn_o => [fn_c, *_] do
sh "gcc #{CFlags} -c #{fn_c}"
end
end再就是链接和执行
OFiles = %w{fdict.o test.o}
task :run => [:link] do
sh "./test"
end
task :link => OFiles do
sh "gcc #{CFlags} #{OFiles.join(' ')} -o test"
end每修改两行C程序到控制台下边一个rake run就可以立即执行，这一来写c就有点像写脚本了。
有可能是imageMagick没装利索。找不到imagemagick，显示错误信息的时候试图把上传的文件对象序列化，就505了。
sudo apt-get install imagemagick --fix-missing
使用三方库就得做好不可预料事件的准备哇
关于paperclip的使用，这两篇简介好像不错：
http://jimneath.org/2008/04/17/paperclip-attaching-files-in-rails/
http://thewebfellas.com/blog/2008/11/2/goodbye-attachment_fu-hello-paperclip
ps: 又遇到了个没预料的问题，上传validates_attachment_content_type指定的类型之外的文件时候同样会遇到个500 internal server error，未解中。
Posted on 五月 8th, 2010 in 备忘 | 5 Comments »
发觉算法太弱了 =”=
当年在ACM那里呆了两天就隐身了，可惜那个老师非常非常非常好的（实验室里还有空调 >_<）。总觉得这玩意水太深，掉进去就出不来了....“不成熟的优化乃万恶之源”这话又正好应了惰性心理，心安理得地“出了性能问题再说之前先弄出来再说管算法干嘛”...可现实往往是，不会算法你压根就弄不出来...
先从一棵二叉查找树开始好了。挖坑慢慢填，时间有的是(?)
module BTree where
data BTree a b = Empty
| BNode {
kv :: (a, b),
left :: BTree a b,
right :: BTree a b
}
deriving(Show, Eq)
insert :: (Ord a) => (a, b) -> BTree a b -> BTree a b
insert (k,v) Empty = BNode (k, v) Empty Empty
insert (k,v) pnode@(BNode (pk, _) lnode rnode)
| k == pk = pnode { kv = (k,v) }
| k < pk = pnode { left = insert (k,v) lnode }
| k > pk = pnode { right = insert (k,v) rnode }
find :: (Ord a) => a -> BTree a b -> Maybe b
find k Empty = Nothing
find k (BNode (pk,pv) lnode rnode)
| k == pk = Just pv
| k <= pk = find k lnode
| k > pk = find k rnode
find _ _ = Nothing
remove :: (Ord a) => a -> BTree a b -> BTree a b
remove k Empty = Empty
remove k pnode@(BNode (pk,pv) lnode rnode)
| k == pk = merge lnode rnode
| k <= pk = pnode { left = remove k lnode }
| k > pk = pnode { right = remove k rnode }
merge :: (Ord a) => BTree a b -> BTree a b -> BTree a b
merge lnode rnode = fromList $ (toList lnode) ++ (toList rnode)
--helper
isEmpty Empty = True
isEmpty _ = False
fromList :: (Ord a) => [(a,b)] -> BTree a b
fromList = foldl (flip insert) Empty
toList :: BTree a b -> [(a,b)]
toList Empty = []
toList (BNode (k,v) lnode rnode) =
(toList lnode) ++ [(k,v)] ++ (toList rnode)
-- for test
root = fromList $ [
(4, "fleurer"),
(10, "ssword"),
(100, "ssword"),
(2, "xx")]haskell做数据结构好像别扭的很…不用ST Monad或者IO的话什么都是值还不能引用，像二叉树的旋转什么的就没想出常数时间的办法。像上面那个remove就直接简单粗暴了orz
(邪恶音：用ST Monad不就好了嘛)
(ST Monad都用了还用haskell干嘛 TvT)
FeedBurner