帐前卒专栏

code, software architect, articles and novels.
代码,软件架构,博客和小说

转自 http://blog.csdn.net/lpioneer/archive/2008/01/16/2046940.aspx

广义表(Lists,又称列表)是线性表的推广。即广义表中放松对表元素的原子限制,容许它们具有其自身结构。

** 1、广义表定义 **
广义表是n(n≥0)个元素a1,a2,…,ai,…,an的有限序列。
其中:
①ai–或者是原子或者是一个广义表。
②广义表通常记作:
Ls=( a1,a2,…,ai,…,an)。
③Ls是广义表的名字,n为它的长度。
④若ai是广义表,则称它为Ls的子表。
注意:
①广义表通常用圆括号括起来,用逗号分隔其中的元素。
②为了区分原子和广义表,书写时用大写字母表示广义表,用小写字母表示原子。
③若广义表Ls非空(n≥1),则al是LS的表头,其余元素组成的表(a1,a2,…,an)称为Ls的表尾。
④广义表是递归定义的

** 2、广义表表示 **
(1)广义表常用表示
① E=()
E是一个空表,其长度为0。
② L=(a,b)
L是长度为2的广义表,它的两个元素都是原子,因此它是一个线性表
③ A=(x,L)=(x,(a,b))
A是长度为2的广义表,第一个元素是原子x,第二个元素是子表L。
④ B=(A,y)=((x,(a,b)),y)
B是长度为2的广义表,第一个元素是子表A,第二个元素是原子y。
⑤ C=(A,B)=((x,(a,b)),((x,(a,b)),y))
C的长度为2,两个元素都是子表。
⑥ D=(a,D)=(a,(a,(a,(…))))
D的长度为2,第一个元素是原子,第二个元素是D自身,展开后它是一个无限的广义表。

(2)广义表的深度
一个表的"深度"是指表展开后所含括号的层数。
【例】表L、A、B、C的深度为分别为1、2、3、4,表D的深度为∞。

(3)带名字的广义表表示
如果规定任何表都是有名字的,为了既表明每个表的名字,又说明它的组成,则可以在每个表的前面冠以该表的名字,于是上例中的各表又可以写成:
①E()
②L(a,b)
③A(x,L(a,b))
④B(A(x,L(a,b)),y)
⑤C(A(x,l(a,b)),B(A(x,L(a,b)),y))
⑥D(a,D(a,D(…)))

(4)广义表的图形表示
(a)广义表的图形表示:
①图中的分支结点对应广义表
②非分支结点一般是原子
③但空表对应的也是非分支结点。
【例】下图给出了几个广义表的图形表示。
![](http://p.blog.csdn.net/images/p_blog_csdn_net/lpioneer/{CA68B4E4-D76B-45
21-9E58-0533AA5C011A%7D.bmp)
(b)广义表的图形形状划分:
①与树对应的广义表称为纯表,它限制了表中成分的共享和递归
②允许结点共享的表称再入表
【例】上图(d),子表A是共享结点,它既是C的一个元素,又是子表B的元素;
③允许递归的表称为递归表
【例】上图(e),表D是其自身的子表。

(5)递归表、再入表、纯表、线性表之间的关系满足:
wu
广义表不仅是线性表的推广,也是树的推广。

** 3、广义表运算
** 由于广义表是对线性表和树的推广,并且具有共享和递归特性的广义表可以和有向图(见第7章)建立对应,因此广义表的大部分运算与这些数据结构上的运算类似。
在此,只讨论广义表的两个特殊的基本运算:取表头head(Ls)和取表尾tail(Ls)。
根据表头、表尾的定义可知:任何一个非空广义表的表头是表中第一个元素,它可以是原子,也可以是子表,而其表尾必定是子表。
【例】
head(L)=a, tail(L)=(b)
head(B)=A, tail(B)=(y)
由于tail(L)是非空表,可继续分解得到:
head(tail(L))=b, tail(tail(L))=()
对非空表A和(y),也可继续分解。
注意:
广义表()和(())不同。前者是长度为0的空表,对其不能做求表头和表尾的运算;而后者是长度为l的非空表(只不过该表中惟一的一个元素是空表),对其可进行分解,
得到的表头和表尾均是空表()。

This is graph for getting through firewall.  This is another method for climbing over the wall.

Phase1. setup the connection between client and server by three-way handshake. when server send ACK and seq to the client. Client should let the wall know this connection is over. So client send FIN and seq to server. The wall get it, and consider the connection from client is over. Because the wall is not based on status. Then server get it, and find the seq of  package is wrong. And server send the RESET package to client. The wall get the package and consider the connection from server is over. Client receive and ignore the RESET package, and then it send the ACK and seq+1 to server.  The connection between client and server is established. However, the connection between client and server is over from viewpiont of the wall. The wall will not exam contents of the connection. So we can get though the wall!

Read more »

自己经常使用sqlserver,不怎么使用mysql.所以也对mysql不咋米了解。这里转两个帖子关于mysql中的InnoDB和MyIsAM的介绍,个人觉
得还是不错的。

转载自 http://database.51cto.com 2009-05-19 09:58
邵宗文  IT168

链接:http://database.51cto.com/art/200905/122382.htm

浅谈MySQL存储引擎选择 InnoDB还是MyISAM

MyISAM
是MySQL中默认的存储引擎,一般来说不是有太多人关心这个东西。决定使用什么样的存储引擎是一个很tricky的事情,但是还是值我们去研究一下,这
里的文章只考虑 MyISAM 和InnoDB这两个,因为这两个是最常见的。

下面先让我们回答一些问题:
◆你的数据库有外键吗?
◆你需要事务支持吗?
◆你需要全文索引吗?
◆你经常使用 什么样的查询模式?
◆你的数据有多大?

思考上面这些问题可以让你找到合适的方向,但那并不是绝对的。如果你需要事务处理或是外键,那么InnoDB 可能是比较好的方式。如果你需要全文索引,那么通常来说
MyISAM是好的选择,因为这是系统内建的,然而,我们其实并不会经常地去测试两百万行记录。所以,就算是慢一点,我们可以通过使用Sphinx从
InnoDB中获得全文索引。

数据的大小,是一个影响你选择什么样存储引擎的重要因素,大尺寸的数据集趋向于选择InnoDB方式,因为其支持事务处理和故障恢复。数据库的在小
决定了故障恢复的时间长短,InnoDB可以利用事务日志进行数据恢复,这会比较快。而MyISAM可能会需要几个小时甚至几天来干这些事,InnoDB
只需要几分钟。

您操作数据库表的习惯可能也会是一个对性能影响很大的因素。比如: COUNT() 在 MyISAM 表中会非常快,而在InnoDB
表下可能会很痛苦。而主键查询则在InnoDB下会相当相当的快,但需要小心的是如果我们的主键太长了也会导致性能问题。大批的inserts
语句在MyISAM下会快一些,但是updates 在InnoDB 下会更快一些——尤其在并发量大的时候。

所以,到底你检使用哪一个呢?根据经验来看,如果是一些小型的应用或项目,那么MyISAM 也许会更适合。当然,在大型的环境下使用MyISAM
也会有很大成功的时候,但却不总是这样的。如果你正在计划使用一个超大数据量的项目,而且需要事务处理或外键支持,那么你真的应该直接使用InnoDB方
式。但需要记住InnoDB 的表需要更多的内存和存储,转换100GB 的MyISAM 表到InnoDB 表可能会让你有非常坏的体验。

转载自 http://database.51cto.com 2009-05-19 09:58
邵宗文  IT168

链接:http://database.51cto.com/art/200905/124370.htm

InnoDB还是MyISAM 再谈MySQL存储引擎的选择

两种类型最主要的差别就是Innodb 支持事务处理与外键和行级锁.而MyISAM不支持.所以MyISAM往往就容易被人认为只适合在小项目中使用。

我作为使用MySQL的用户角度出发,Innodb和MyISAM都是比较喜欢的,但是从我目前运维的数据库平台要达到需求:99.9%的稳定性,
方便的扩展性和高可用性来说的话,MyISAM绝对是我的首选。

原因如下:

1、首先我目前平台上承载的大部分项目是读多写少的项目,而MyISAM的读性能是比Innodb强不少的。

2、MyISAM的索引和数据是分开的,并且索引是有压缩的,内存使用率就对应提高了不少。能加载更多索引,而Innodb是索引和数据是紧密捆绑
的,没有使用压缩从而会造成Innodb比MyISAM体积庞大不小。

3、从平台角度来说,经常隔1,2个月就会发生应用开发人员不小心update一个表where写的范围不对,导致这个表没法正常用了,这个时候
MyISAM的优越性就体现出来了,随便从当天拷贝的压缩包取出对应表的文件,随便放到一个数据库目录下,然后dump成sql再导回到主库,并把对应的
binlog补上。如果是Innodb,恐怕不可能有这么快速度,别和我说让Innodb定期用导出xxx.sql机制备份,因为我平台上最小的一个数据
库实例的数据量基本都是几十G大小。

4、从我接触的应用逻辑来说,select count(*) 和order by
是最频繁的,大概能占了整个sql总语句的60%以上的操作,而这种操作Innodb其实也是会锁表的,很多人以为Innodb是行级锁,那个只是
where对它主键是有效,非主键的都会锁全表的。

5、还有就是经常有很多应用部门需要我给他们定期某些表的数据,MyISAM的话很方便,只要发给他们对应那表的frm.MYD,MYI的文件,让
他们自己在对应版本的数据库启动就行,而Innodb就需要导出xxx.sql了,因为光给别人文件,受字典数据文件的影响,对方是无法使用的。

6、如果和MyISAM比insert写操作的话,Innodb还达不到MyISAM的写性能,如果是针对基于索引的update操作,虽然
MyISAM可能会逊色Innodb,但是那么高并发的写,从库能否追的上也是一个问题,还不如通过多实例分库分表架构来解决。

7、如果是用MyISAM的话,merge引擎可以大大加快应用部门的开发速度,他们只要对这个merge表做一些select
count(*)操作,非常适合大项目总量约几亿的rows某一类型(如日志,调查统计)的业务表。

当然Innodb也不是绝对不用,用事务的项目如模拟炒股项目,我就是用Innodb的,活跃用户20多万时候,也是很轻松应付了,因此我个人也是
很喜欢Innodb的,只是如果从数据库平台应用出发,我还是会首选MyISAM。

另外,可能有人会说你MyISAM无法抗太多写操作,但是我可以通过架构来弥补,说个我现有用的数据库平台容量:主从数据总量在几百T以上,每天十 多亿
pv的动态页面,还有几个大项目是通过数据接口方式调用未算进pv总数,(其中包括一个大项目因为初期memcached没部署,导致单台数据库每天处理
9千万的查询)。而我的整体数据库服务器平均负载都在0.5-1左右。

首先使用sudo ssh-keygen -t rsa 生成key,key分公私钥,公钥是,然后使用launchpad登录,然后出现

Warning: Permanently added ‘bazaar.launchpad.net,91.189.90.11’ (RSA) to the
list of known hosts.
Permission denied (publickey).
bzr: ERROR: Connection closed: Unexpected end of message. Please check
connectivity and permissions, and report a bug if problems persist.

这样之后使用ssh-agent bash清洗一下。然后再使用ssh-add
key.这里key是私钥。这里添加的话是普通权限的user的key.当然如果你真想添加,然么就要改下key的访问权限。

如果使用sudo ssh-agent bash,之后就变为root用户。添加一致。

之后再使用 sudo bzr launchpad-login [username]   这里的 username是在launchpad.org中注册的。
然后再sudo bzr lp:XXX dir, lp:XXX是分支名,dir是将分支存放在某个目录下。

use douban: http://douban.fm/radio

download: desktop(32 bit)

server(32 bit)

Ubuntu 10.04 LTS (Lucid Lynx) Beta 1

计算器程序有优先级。所以文法归于必须有先后顺序。也就是高优先级的先规约,低优先级的后规约。也就是在写文法时,见到高优先级便扩展。

例如: -+在*/之后扩展

Express = Express ‘+’ F | Express ‘-’ F F = T ‘*’ T | T ‘/’ T T = terminal

这就完事了吗?no…因为这样很有可能产生shift/reduce文法错误。解决方法为:

Express = Express ‘+’ F | Express ‘-’ F | F F = F ‘*’ T | F ‘/’ T | T T = num

这里num和terminal一致。都为终结符

这样做完之后,不会出现shift/reduce错误。我觉得解决shift/reduce可能有某种规律,例如在左递归文法中,每句几乎都是以非终结符开始,并以终
结符结束。并且在最后一种扩展中添加下一个非终结符。当然这对于简单文法可能是成立的。至少这样不会有错。但是如果这个是文法的话,计算器不会终止。也就是说如果执行
1+2*3-4/5,则在最后一个低优先级符号处结束。也就是说最后规约为7-0.8,之后不会继续规约。所以这里必须将明确的结束符告诉程序。例如下一段中最终的结
束符为=或者回车:

Value = Express ‘/n’ | Express ‘=’ Express = Express ‘+’ F | Express ‘-’ F | F
F = F ‘*’ T | F ‘/’ T | T T = num

ex3.y: In function ‘yyerror’:
ex3.y:32: warning: incompatible implicit declaration of built-in function
‘printf’

这一条是因为.y缺少头文件。在.y文件中需要在%{…%}之中写入#include
<stdio.h>等头文件。如果只有printf那就只用这个头文件就行了。

ex3.l: In function ‘yylex’:
ex3.l:11: error: ‘yylval’ undeclared (first use in this function)
ex3.l:11: error: (Each undeclared identifier is reported only once
ex3.l:11: error: for each function it appears in.)

这一条信息是由于yylval 对于lex不可见造成的。原因yacc调用yylex()读取token,lex读到一个token就将这个token返回,但这个t
oken同时可能有值。此值必须保留在yylval中。但是古老的yacc不让lex见到,那么就需要extern YYSTPYE
yylval.传说这就需要加在y.tab.h中。但是经我测试这是不行的。(我也不知道为啥偏偏就我这么倒霉。)我在加上extern YYSTPYE
yylval之后产生如下错误:

ex3.l:5: error: expected ‘=’, ‘,’, ‘;’, ‘asm’ or ‘attribute’ before
‘yylval’
ex3.l: In function ‘yylex’:

…不过还有救,我不使用byacc,而改用bison。之后去掉extern YYSTPYE yylval再编译:

ex3.y: In function ‘yyparse’:
ex3.y:26: warning: format ‘%s’ expects type ‘char *’, but argument 2 has type
‘YYSTYPE’

这是因为YYSTYPE这个变量是int型的。所以要在.y文件的%{…%}中添加两行

typedef char* string; #define YYSTPYE string

然后编译成功,却冒出了:

ex3.l: In function ‘yylex’:
ex3.l:10: warning: assignment makes integer from pointer without a cast

这肯定是yylval=strdup(yytext);处没有进行强制转换。于是改为yylval=(int)strdup(yytext);就ok了。但这里的问题
是yylval应该是一个YYSTYPE的变量。但是却必须转换为int型,确实有些诡异。之后又尝试在gcc中添加-Wstrict-
prototypes来查看此错误。结果发现又报一错⚠️ function declaration isn’t a
prototype.这个错误的确是自己从来不喜欢写void造成的。将main()改为main(void)
即可。

首先要有flex 和 bison两个东东,没有就yum或者apt-get

最终的两个文件和编译命令为:

ex3.l文件:

%{ #include <stdio.h> #include “ex3.tab.h” %} name [a-zA-Z][a-zA-Z0-9]* age
[1-9][0-9]* eq = %% {name} {yylval=(int)strdup(yytext); return NAME;} {age}
{yylval=(int)strdup(yytext); return AGE;} {eq} {return EQ;} %% int yywrap() {
return 1; }

ex3.y文件

%{ typedef char* string; #define YYSTYPE string #include <stdio.h> #include
<string.h> int main(void) { // extern int yyparse(void); yyparse(); return 0;
} int yyerror(char * msg) { printf(“%s is error in line”,msg); } %} %token
NAME EQ AGE %% file : record file | record ; record : NAME EQ NAME {
printf(“%s’s age is equal with %s./n”,$1,$3); } | NAME EQ AGE {
printf(“ssssss/n”); } ; %%

这之后执行:

root@chico-laptop:~/compiler# bison -d ex3.y root@chico-laptop:~/compiler#
flex ex3.l root@chico-laptop:~/compiler# cc -Wstrict-prototypes lex.yy.c
ex3.tab.c -o test root@chico-laptop:~/compiler# ./test

input:

AA = BB

output:

AA’s age is equal with BB.

简单的东西算是完成了

但是还有一个问题没有解决,为啥使用bison就可以解决问题,而使用byacc就不行呢?我看了下bison生成的ex3.tab.h文件,其中有几句话:

#if ! defined YYSTYPE && ! defined YYSTYPE_IS_DECLARED typedef int YYSTYPE; #
define yystype YYSTYPE /* obsolescent; will be withdrawn */ # define
YYSTYPE_IS_DECLARED 1 # define YYSTYPE_IS_TRIVIAL 1 #endif extern YYSTYPE
yylval;

直接将上面的话贴入byacc生成的y.tab.h即可编译通过。不过即使你在其中更改 typedef char*
YYSTYPE;lex程序还是会将yylval默认为int型。

不过想要通过c++编译的话,还需要做些改动。

ex4.y

%{ #include #include using namespace std; typedef char*
strings; #define YYSTYPE strings extern “C” { int yyparse(void); int
yylex(void); int yydebug; int yyerror(const char*); } int main(void) { //
extern int yyparse(void); yydebug=1; yyparse(); return 0; } int yyerror(const
char * msg) { printf(“%s is error in line”,msg); } %} %token NAME EQ AGE %%
file : record file | record ; record : NAME EQ NAME { printf(“%s’s age is
equal with %s./n”,$1,$3); } | NAME EQ AGE { printf(“ssssss/n”); } ; %%

ex4.l

%{ #include <stdio.h> #include “ex4.tab.h” %} name [a-zA-Z][a-zA-Z0-9]* age
[1-9][0-9]* eq = %% {name} {yylval=(int)strdup(yytext); return NAME;} {age}
{yylval=(int)strdup(yytext); return AGE;} {eq} {return EQ;} %% int
yywrap(){return 1;}

编译指令:

root@chico-laptop:~/compiler# bison -d ex4.y root@chico-laptop:~/compiler#
flex ex4.l root@chico-laptop:~/compiler# cc -c lex.yy.c -o lex.yy.o root
@chico-laptop:~/compiler# c++ lex.yy.o ex4.tab.c -o ex4test

常见的编译error和warning有:

ex4.tab.c:1519: warning: deprecated conversion from string constant to ‘char*’
这里去查看了一下ex4.tab.c发现是函数yyerror的问题,将int yyerror(char*)改为int yyerror(const
char*)即可。

另外不要typedef char* string;这可能会重,不定义又会报出:

ex4.y: In function ‘int yyparse()’:
ex4.y:36: warning: cannot pass objects of non-POD type ‘struct
std::basic_string<char, std::char_traits, std::allocator >’
through ‘…’; call will abort at runtime

所以改为typedef char* strings;

另外lex.yy.c要先用cc或gcc编译为.o文件,然后在用g或c联合编译。

转自
Ashish Bansal [email protected], 软件工程师, Sapient 公司

Lex

Lex 是一种生成扫描器的工具。扫描器是一种识别文本中的词汇模式的程序。这些词汇模式(或者常规表达式)在一种特殊的句子结构中定义,这个我们一会儿就要讨论。

一种匹配的常规表达式可能会包含相关的动作。这一动作可能还包括返回一个标记。当 Lex
接收到文件或文本形式的输入时,它试图将文本与常规表达式进行匹配。它一次读入一个输入字符,直到找到一个匹配的模式。如果能够找到一个匹配的模式,Lex
就执行相关的动作(可能包括返回一个标记)。另一方面,如果没有可以匹配的常规表达式,将会停止进一步的处理,Lex 将显示一个错误消息。

Lex 和 C 是强耦合的。一个 _ .lex _ 文件(Lex 文件具有 _ .lex _ 的扩展名)通过 lex 公用程序来传递,并生成 C
的输出文件。这些文件被编译为词法分析器的可执行版本。

Lex 的常规表达式

常规表达式是一种使用元语言的模式描述。表达式由符号组成。符号一般是字符和数字,但是 Lex 中还有一些具有特殊含义的其他标记。 下面两个表格定义了 Lex
中使用的一些标记并给出了几个典型的例子。

用 Lex 定义常规表达式

** 字符 **
** 含义 **

** A-Z, 0-9, a-z **
构成了部分模式的字符和数字。

** . **
匹配任意字符,除了 /n。

** - **
用来指定范围。例如:A-Z 指从 A 到 Z 之间的所有字符。

** [ ] **
一个字符集合。匹配括号内的 _ 任意 _ 字符。如果第一个字符是 ** ^ ** 那么它表示否定模式。例如: [abC] 匹配 a, b, 和
C中的任何一个。


匹配 _ 0个 _ 或者多个上述的模式。

** + **
匹配 _ 1个 _ 或者多个上述模式。

** ? **
匹配 _ 0个或1个 _ 上述模式。

** $ **
作为模式的最后一个字符匹配一行的结尾。

** { } **
指出一个模式可能出现的次数。 例如: A{1,3} 表示 A 可能出现1次或3次。

** / **
用来转义元字符。同样用来覆盖字符在此表中定义的特殊意义,只取字符的本意。

** ^ **
否定。

** | **
表达式间的逻辑或。

** “<一些符号>” **
字符的字面含义。元字符具有。

** / **
向前匹配。如果在匹配的模版中的“/”后跟有后续表达式,只匹配模版中“/”前面的部分。如:如果输入 A01,那么在模版 A0/1 中的 A0 是匹配的。

** ( ) **
将一系列常规表达式分组。

常规表达式举例

** 常规表达式 **
** 含义 **

joke[rs]

匹配 jokes 或 joker。

A{1,2}shis+

匹配 AAshis, Ashis, AAshi, Ashi。

(A[b-e])+

匹配在 A 出现位置后跟随的从 b 到 e 的所有字符中的 0 个或 1个。

注:这小朋友将A{1,2}shis*写为了A{1,2}shis+。

Lex 中的标记声明类似 C 中的变量名。每个标记都有一个相关的表达式。(下表中给出了标记和表达式的例子。)使用这个表中的例子,我们就可以编一个字数统计的程
序了。我们的第一个任务就是说明如何声明标记。

标记声明举例

** 标记 **
** 相关表达式 **
** 含义 **

数字(number)

([0-9])+

1个或多个数字

字符(chars)

[A-Za-z]

任意字符

空格(blank)

" "

一个空格

字(word)

(chars)+

1个或多个 _ chars _

变量(variable)

(字符)+(数字)(字符)(数字)*

Lex 编程

Lex 编程可以分为三步:

  1. 以 Lex 可以理解的格式指定模式相关的动作。
  2. 在这一文件上运行 Lex,生成扫描器的 C 代码。
  3. 编译和链接 C 代码,生成可执行的扫描器。

注意: 如果扫描器是用 Yacc 开发的解析器的一部分,只需要进行第一步和第二步。关于这一特殊问题的帮助请阅读 Yacc
将 Lex 和
Yacc 结合起来

部分。

现在让我们来看一看 Lex 可以理解的程序格式。一个 Lex 程序分为三个段:第一段是 C 和 Lex 的全局声明,第二段包括模式(C
代码),第三段是补充的 C 函数。 例如, 第三段中一般都有 main() 函数。这些段以%%来分界。 那么,回到字数统计的 Lex
程序,让我们看一下程序不同段的构成。

C 和 Lex 的全局声明

这一段中我们可以增加 C 变量声明。这里我们将为字数统计程序声明一个整型变量,来保存程序统计出来的字数。我们还将进行 Lex 的标记声明。

** 字数统计程序的声明 **
%{
int wordCount = 0;
%}
chars [A-za-z/_/'/./“]
numbers ([0-9])+
delim [” "/n/t]
whitespace {delim}+
words {chars}+
%%
两个百分号标记指出了 Lex 程序中这一段的结束和三段中第二段的开始。

Lex 的模式匹配规则

让我们看一下 Lex 描述我们所要匹配的标记的规则。(我们将使用 C 来定义标记匹配后的动作。)继续看我们的字数统计程序,下面是标记匹配的规则。

** 字数统计程序中的 Lex 规则 **
{words} { wordCount++; /*
increase the word count by one*/ }
{whitespace} { /* do
nothing*/ }
{numbers} { /* one may
want to add some processing here*/ }
%%
C 代码

Lex 编程的第三段,也就是最后一段覆盖了 C 的函数声明(有时是主函数)。注意这一段必须包括 yywrap() 函数。 Lex
有一套可供使用的函数和变量。 其中之一就是 yywrap。一般来说,yywrap() 的定义如下例。我们将在 高级 Lex
中探讨这一问题。

** 字数统计程序的 C 代码段 **
void main()
{
yylex(); /* start the
analysis*/
printf(" No of words:
%d/n", wordCount);
}
int yywrap()
{
return 1;
}
上一节我们讨论了 Lex 编程的基本元素,它将帮助你编写简单的词法分析程序。 在 高级 Lex
这一节中我们将讨论
Lex 提供的函数,这样你就能编写更加复杂的程序了

将它们全部结合起来

_ .lex _ 文件是 Lex 的扫描器。它在 Lex 程序中如下表示:

   $ lex <file name.lex>  

这生成了 lex.yy.c 文件,它可以用 C 编译器来进行编译。它还可以用解析器来生成可执行程序,或者在链接步骤中通过选项�ll 包含 Lex 库。

这里是一些 Lex 的标志:

  • _ -c _ 表示 C 动作,它是缺省的。
  • _ -t _ 写入 lex.yy.c 程序来代替标准输出。
  • _ -v _ 提供一个两行的统计汇总。
  • _ -n _ 不打印 -v 的汇总。

高级 Lex

Lex 有几个函数和变量提供了不同的信息,可以用来编译实现复杂函数的程序。下表中列出了一些变量和函数,以及它们的使用。 详尽的列表请参考 Lex 或
Flex 手册(见后文的 资源
)。

Lex 变量

yyin

FILE* 类型。 它指向 lexer 正在解析的当前文件。

yyout

FILE* 类型。 它指向记录 lexer 输出的位置。 缺省情况下,yyin 和 yyout 都指向标准输入和输出。

yytext

匹配模式的文本存储在这一变量中(char*)。

yyleng

给出匹配模式的长度。

yylineno

提供当前的行数信息。(lexer不一定支持。)

Lex 函数

yylex()

这一函数开始分析。 它由 Lex 自动生成。

yywrap()

这一函数在文件(或输入)的末尾调用。如果函数的返回值是1,就停止解析。 因此它可以用来解析多个文件。代码可以写在第三段,这就能够解析多个文件。 方法是使用
yyin 文件指针(见上表)指向不同的文件,直到所有的文件都被解析。最后,yywrap() 可以返回 1 来表示解析的结束。

yyless(int n)

这一函数可以用来送回除了前�n? 个字符外的所有读出标记。

yymore()

这一函数告诉 Lexer 将下一个标记附加到当前标记后。

对 Lex 的讨论就到这里。下面我们来讨论 Yacc…

Yacc

Yacc 代表 Yet Another Compiler Compiler。 Yacc 的 GNU 版叫做
Bison。它是一种工具,将任何一种编程语言的所有语法翻译成针对此种语言的 Yacc 语 法解析器。它用巴科斯范式(BNF, Backus Naur
Form)来书写。按照惯例,Yacc 文件有 .y 后缀。编译行如下调用 Yacc 编译器:

       $ yacc <options>  
        <filename ending with .y>  

在进一步阐述以前,让我们复习一下什么是语法。在上一节中,我们看到 Lex
从输入序列中识别标记。如果你在查看标记序列,你可能想在这一序列出现时执行某一动作。这种情况下有效序列的规范称为语法。Yacc
语法文件包括这一语法规范。它还包含了序列匹配时你想要做的事。

为了更加说清这一概念,让我们以英语为例。 这一套标记可能是:名词, 动词,
形容词等等。为了使用这些标记造一个语法正确的句子,你的结构必须符合一定的规则。一个简单的句子可能是名词+动词或者名词+动词+名词。(如 I care.
See spot run.)

所以在我们这里,标记本身来自语言(Lex),并且标记序列允许用 Yacc 来指定这些标记(标记序列也叫语法)。

** 终端和非终端符号 **
** 终端符号 ** : 代表一类在语法结构上等效的标记。终端符号有三种类型:

_ 命名标记 _ : 这些由 _ %token _ 标识符来定义。按照惯例,它们都是大写。

_ 字符标记 _ : 字符常量的写法与 C 相同。例如, – 就是一个字符标记。

_ 字符串标记 _ : 写法与 C 的字符串常量相同。例如,“<<” 就是一个字符串标记。

lexer 返回命名标记。

** 非终端符号 ** : 是一组非终端符号和终端符号组成的符号。按照惯例,它们都是小写。 在例子中,file 是一个非终端标记而 NAME 是一个终端标记。

用 Yacc 编写语法

如同 Lex 一样, 一个 Yacc 程序也用双百分号分为三段。它们是:声明、语法规则和 C 代码。 我们将解析一个格式为 姓名 =
年龄的文件作为例子,来说明语法规则。我们假设文件有多个姓名和年龄,它们以空格分隔。 在看 Yacc 程序的每一段时,我们将为我们的例子编写一个语法文件。

C 与 Yacc 的声明

C 声明可能会定义动作中使用的类型和变量,以及宏。还可以包含头文件。每个 Yacc
声明段声明了终端符号和非终端符号(标记)的名称,还可能描述操作符优先级和针对不同符号的数据类型。 lexer (Lex)
一般返回这些标记。所有这些标记都必须在 Yacc 声明中进行说明。

在文件解析的例子中我们感兴趣的是这些标记:name, equal sign, 和 age。Name 是一个完全由字符组成的值。 Age
是数字。于是声明段就会像这样:

** 文件解析例子的声明 **
%
#typedef char* string; /*
to specify token types as char* /
#define YYSTYPE string /

a Yacc variable which has the value of returned token /
%}
%token NAME EQ AGE
%%
你可能会觉得 YYSTYPE 有点奇怪。但是类似 Lex, Yacc 也有一套变量和函数可供用户来进行功能扩展。 YYSTYPE 定义了用来将值从
lexer 拷贝到解析器或者 Yacc 的 yylval (另一个 Yacc 变量)的类型。默认的类型是 int。 由于字符串可以从 lexer
拷贝,类型被重定义为 char
。 关于 Yacc 变量的详细讨论,请参考 Yacc 手册(见 资源
)。

Yacc 语法规则

Yacc 语法规则具有以下一般格式:

1
2
3
4
result: components { /*  
action to be taken in C */ }
;

在这个例子中,result 是规则描述的非终端符号。Components 是根据规则放在一起的不同的终端和非终端符号。 如果匹配特定序列的话
Components 后面可以跟随要执行的动作。 考虑如下的例子:

1
2
3
4
5
param : NAME EQ NAME {  
printf("/tName:%s/tValue(name):%s/n", $1,$3);}
| NAME EQ VALUE{
printf("/tName:%s/tValue(value):%s/n",$1,$3);}
;

如果上例中序列 NAME EQ NAME 被匹配,将执行相应的 { } 括号中的动作。 这里另一个有用的就是 $1 和 $3 的使用, 它们引用了标记
NAME 和 NAME(或者第二行的 VALUE)的值。 lexer 通过 Yacc 的变量 yylval 返回这些值。标记 NAME 的 Lex
代码是这样的:

1
2
3
4
5
6

char [A-Za-z]
name {char}+
%%
{name} { yylval = strdup(yytext);
return NAME; }

这里yylval=strdup(yytext);需要进行强制转换。否则有warning.

文件解析例子的规则段是这样的:

** 文件解析的语法 **

1
2
3
4
5
6
7
8
9

file : record file
| record
;
record: NAME EQ AGE {
printf("%s is now %s years old!!!", $1, $3);}
;
%%

附加 C 代码

现在让我们看一下语法文件的最后一段,附加 C 代码。(这一段是可选的,如果有人想要略过它的话:)一个函数如 main() 调用 yyparse()
函数(Yacc 中 Lex 的 yylex() 等效函数)。 一般来说,Yacc 最好提供 yyerror(char msg) 函数的代码。
当解析器遇到错误时调用 yyerror(char msg)。错误消息作为参数来传递。 一个简单的 yyerror( char* ) 可能是这样的:

1
2
3
4
5
6
int yyerror(char* msg)  
{
printf("Error: %s
encountered at line number:%d/n", msg, yylineno);
}

yylineno 提供了行数信息。

这一段还包括文件解析例子的主函数:

** 附加 C 代码 **

1
2
3
4
5
6
7
8
9

void main()
{
yyparse();
}
int yyerror(char* msg)
{
printf("Error: %s
encountered /n", msg);

要生成代码,可能用到以下命令:

       $ yacc _d <filename.y>  

这里的命令有误:其实为 yacc -d <filename.y>

这生成了输出文件 y.tab.h 和 y.tab.c,它们可以用 UNIX 上的任何标准 C 编译器来编译(如 gcc)。

命令行的其他常用选项

  • _ ‘-d’ ,‘–defines’ _ : 编写额外的输出文件,它们包含这些宏定义:语法中定义的标记类型名称,语义的取值类型 _ YYSTYPE _ , 以及一些外部变量声明。如果解析器输出文件名叫 ‘name.c’, 那么 ‘-d’ 文件就叫做 ‘name.h’。 如果你想将 _ yylex _ 定义放到独立的源文件中,你需要 ‘name.h’, 因为 _ yylex _ 必须能够引用标记类型代码和 _ yylval _ 变量。
  • _ ‘-b file-prefix’ ,‘–file-prefix=prefix’ _ : 指定一个所有Yacc输出文件名都可以使用的前缀。选择一个名字,就如输入文件名叫 ‘prefix.c’.
  • _ ‘-o outfile’ ,‘–output-file=outfile’ _ : 指定解析器文件的输出文件名。其他输出文件根据 ‘-d’ 选项描述的输出文件来命名。

Yacc 库通常在编译步骤中自动被包括。但是它也能被显式的包括,以便在编译步骤中指定 _ �ly _ 选项。这种情况下的编译命令行是:

1
$ cc <source file names> -ly  

将 Lex 与 Yacc 结合起来

到目前为止我们已经分别讨论了 Lex 和 Yacc。现在让我们来看一下他们是怎样结合使用的。

一个程序通常在每次返回一个标记时都要调用 _ yylex() _ 函数。只有在文件结束或者出现错误标记时才会终止。

一个由 Yacc 生成的解析器调用 _ yylex() _ 函数来获得标记。 _ yylex() _ 可以由 Lex 来生成或完全由自己来编写。 对于由
Lex 生成的 lexer 来说,要和 Yacc 结合使用,每当 Lex 中匹配一个模式时都必须返回一个标记。 因此 Lex 中匹配模式时的动作一般格式为:

       {pattern} { /* do smthg*/  
        return TOKEN_NAME; }  

于是 Yacc 就会获得返回的标记。当 Yacc 编译一个带有 _d 标记的 _ .y _ 文件时,会生成一个头文件,它对每个标记都有 _ #define
_ 的定义。 如果 Lex 和 Yacc 一起使用的话,头文件必须在相应的 Lex 文件 _ .lex _ 中的 C 声明段中包括。

让我们回到名字和年龄的文件解析例子中,看一看 Lex 和 Yacc 文件的代码。

** Name.y - 语法文件 **

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

{%
typedef char* string;
#define YYSTYPE string
%}
%token NAME EQ AGE
%%
file : record file
| record
;
record : NAME EQ AGE {
printf("%s is %s years old!!!/n", $1, $3); }
;
%%
int main()
{
yyparse();
return 0;
}
int yyerror(char *msg)
{
printf("Error
encountered: %s /n", msg);
}

** Name.lex - Lex 的解析器文件 **

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
%{  
#include "y.tab.h"
#include <stdio.h>
#include <string.h>
extern char* yylval;
%}
char [A-Za-z]
num [0-9]
eq [=]
name {char}+
age {num}+
%%
{name} { yylval = strdup(yytext);
return NAME; }
{eq} { return EQ; }
{age} { yylval = strdup(yytext);
return AGE; }
%%
int yywrap()
{
return 1;
}

作为一个参考,我们列出了 _ y.tab.h _ , Yacc 生成的头文件。

** y.tab.h - Yacc 生成的头文件 **
# define NAME 257
# define EQ 258
# define AGE 259
当然即使你执行了yacc -d <filename.y>,也执行了lex <filename.l>, 并且执行了gcc y.tab.c lex.yy.c
-o -ly

还是有可能会报错。 欲知解决方案请参考我的下篇文章

我们对于 Lex 和 Yacc的讨论到此为止。今天你想要编译什么语言呢?

参考资料

  • 您可以参阅本文在 developerWorks 全球站点上的 英文原文 .
  • Lex and Yacc , Levine, Mason 和 Branson, O�Reilly 及其合作公司,2nd Ed。
  • Program Development in UNIX , J. T. Shen, Prentice-Hall India。
  • Compilers: Principles, Techniques and Tools , Ahoo, Sethi 和 Ullman, Addison-Wesley Pub. Co., 1985,11。
  • Lex and Yacc and compiler writing 指导。
  • Java 版的 Lex 指导, 叫做 Jlex
  • 使用 Lex 和 Yacc 的 formalizing a grammar 实例。

程序员能力矩阵 by XGuru is licensed under a

Creative Commons 署名-非商业性使用-相同方式共享 2.5 中国大陆 License
. 原文请看 [ 这 里
](http://www.indiangeek.net/wp-
content/uploads/Programmer%20competency%20matrix.htm) 。
Thanks to bearice for debugging.
Thanks to John Haugeland for a reformatting of it that
works much more nicely on the web.

[译文]程序员能力矩阵 Programmer Competency Matrix

注意:每个层次的知识都是渐增的,位于层次 _ n _ ,也蕴涵了你需了解所有低于层次 _ n _ 的 知识。

计算机科学 Computer Science

2 n (Level 0)

n 2 (Level 1)

n (Level 2)

log(n) (Level 3)

Comments

数据结构

不知道数组和链表的差异

能够解释和使用数组, 链表,字典等,并且能够用于实际的编程任务。

了解基本数据结构时间和空间的折中,比如数组vs 链表,能够解释如何实现哈希表和处理冲突,了解优先队列及其实现。

高等的数据结构的知识,比如B-树、二项堆、斐波那契堆、AVL 树、红黑树、伸展树、跳跃表以及前缀树等。

算法

不能够找出一个数组各数的平均值(这令人难以置信,但是我的确在应聘者 中遇到过)

基本的排序,搜索和数据的遍历和检索算法。

树,图,简单的贪婪算法和分而治之算法,能够适度了解矩阵该 层的含义。

能够辨识和编写动态规划方案,良好的图算法知识,良好的数值估算的知识,能够辨别NP问题等。

Working with someone who has a good topcoder ranking would be an unbelievable
piece of luck!

编程体系

不知道何为编译器、链接器和解释器。

对编译 器、链接器、解释器有基本的了解。知道什么是汇编代码以及在硬件层如何工作。有一些虚拟内存和分页知识。

了解内核模式vs用户模式, 多线程,同步原语以及它们如何实现,能够阅读汇编代码。了解网络如何工作,了解网络协议和socket级别编程。

了解整个程序堆栈、 硬件(CPU+内存+中断+微码)、二进制代码、汇编、静态和动态链接、编码、解释、JIT(just-in-
time)编译、内存碎片回收、堆、栈、存 储器编址…

软件工程 Software Engineering

2 n (Level 0)

n 2 (Level 1)

n (Level 2)

log(n) (Level 3)

Comments

源码版本控制

通过日期备份文件夹

VSS和初级的 CVS/SVN用户

熟练地使用CVS和SVN特性。知道如何分支和归并,使用程序库补丁安装特性等

有分布式VCS 系统的知识。尝试过Bzr/Mercurial/Darcs/Git

自动化编译

只知道在IDE下编译

知道如何编译在命令行 下编译系统

能够安装一个脚本构建基本的系统

能够安装一个脚本来构建系统并且归档,安装程序,生成发布记录和给源 码控制中的代码分配标签。

自动化测试

认为所有的测试都是测试员的工作。

能够编写 自动化的单元测试,能够为正在编写的代码提出良好的测试用例。

按照TDD (Test Driven Development)方式编写代码。

了解并且能够有效自动化安装,载入/性能和UI测试

程序设计 Programming

2 n (Level 0)

n 2 (Level 1)

n (Level 2)

log(n) (Level 3)

Comments

问题分解

只有直线式的代码,通过复制粘贴来复用

能够把 问题分散到多个函数中

能够想出可复用的函数/对象来解决大题的问题

使用适宜的数据结构和算法,写出通用的/面向 对象的代码来封装问题的易改变的层面。

系统分解

N想不出比单一的文件/类更好的层面

如果不在 同一平台或没采用相同的技术,能够把问题空间和设计方案分解。

能够设计跨技术/平台的系统。

能够在多个产品线和 与外部体系一体化中虚拟化和设计复制的系统。同时也能够设计支持系统监视、报告、故障恢复等。

交流

不能向同伴表达想法/主意。匮乏拼写和语法的能力。

同 伴能了解你在说什么。有良好的拼写和语法能力。

能够和同伴进行高效的交流

能够使用清晰的方式了解和交流想法/设计 /主意/细则,能适应每种环境的交流

This is an often under rated but very critical criteria for judging a
programmer. With the increase in outsourcing of programming tasks to places
where English is not the native tongue this issue has become more prominent. I
know of several projects that failed because the programmers could not
understand what the intent of the communication was.

同一文件中代码组织

同一文件中组织没有依据

按照逻辑 性或者易接近的方法

代码分块和对于其他源文件来说是易于是释,引用其他源文件时有良好的注释

文档头部有许可声 明,总结,良好的注释,一致的空格缩进。文档外观美观。

2 n (Level 0)

n 2 (Level 1)

n (Level 2)

log(n) (Level 3)

Comments

跨文件代码组织

没够想过给代码跨文件组织

相关文件按文件 夹分组

每个物理文件都有独立的目的,比如一个类的定义,一个特性的实现等。

代码在物理层组织紧密,在文件名上与 设计和外观相匹配,可以通过文件分布方式洞察设计理念。

源码树组织

一切都放在一个文件夹内

初步地将代码分散进 对应逻辑的文件夹。

没有循环依赖,二进制文件,库,文档,构建,第三方的代码都组织进合适的文件夹内。

源码树的 物理布局与逻辑层次、组织方式相匹配。可以通过目录名称和组织方式洞察设计理念。

The difference between this and the previous item is in the scale of
organization, source tree organization relates to the entire set of artifacts
that define the system.

代码可读性

单音节的名称 (在国内应该是那些类似用汉语拼音命名的习惯)

对文件、变量、类、方法等,有良好的命名。

没有长函数、注释解释不常规的代码,bug修复,代码假设。

代 码假设验证使用断言,自然的代码流,没有深层嵌套的条件和方法

防御性编码

不知道这个概念

检查代码中所有的参数,对关键 的假设进行断言

确保检查了返回值和使代码失败的异常。

有自己的库来帮助防御性编程、编写单元测试模拟故障

2 n (Level 0)

n 2 (Level 1)

n (Level 2)

log(n) (Level 3)

Comments

错误处理

只给乐观的情形编码

基本的代码错误处理,抛出 异常/生成错误

确保错误/异常留在程序中有良好的状态,资源,连接,内存都有被合适的清理。

在编码之前察觉可能 出现的异常,在代码的所有层次中维持一致性的异常处理策略,提出整个系统的错误处理准则。

IDE

IDE大部分用来进行文本编辑

了解其周围的接 口,能够高效地通过菜单来使用IDE

了解最常操作的键盘快捷键

编写自定义宏

API

需要频繁地查阅文档

把最频繁使用的API记在脑 子里

广阔且深入的API知识。

为了使实际任务中常用API使用更加便捷,编写过API的上层库,填补API之间 的缺口。

E.g. of API can be Java library, .net framework or the custom API for the
application

框架

没有使用过主平台外的任何框架

听过但没用过平台下 流行的可用框架

在专业的职位中使用过一个以上的框架,通晓各框架的特色。

某框架的作者

2 n (Level 0)

n 2 (Level 1)

n (Level 2)

log(n) (Level 3)

Comments

需求分析

接受给定的需求和代码规格

能对规格的遗漏提出 疑问

了解全面情况,提出需要被规格化的整体范围。

能够提出更好的可选方案,根据经验的浮现给出需求

脚本

不具备脚本工具的知识

批处理文件/shell脚本

Perl/Python/Ruby/VBScript/Powershell

写过并且发表过可重用的代码

数据库

认为Excel就是数据库

知道基本的数据库概
念,规范化、ACID(原子性Atomicity、一致性Consistency、隔离性Isolation、持久性Durability)、事务化,能
够写简单的select语句

能够牢记在运行时必要查询中设计良好的规范化数据库模式,
精通用户视图,存储过程,触发器和用户定义类型。知道聚集与非聚集索引之间的差异。精通使用ORM(Object Relational
Mapping对象关系映射)工具

能做基本的数据库管理,性能优化,索引优化,编写高级的select查询,能够使用相关sql来替
换游标,理解数据内部的存储,了解如何镜像、复制数据库。知道两段数据提交如何工作

经验 Experience

2 n (Level 0)

n 2 (Level 1)

n (Level 2)

log(n) (Level 3)

Comments

专业语言经验

命令式语言和面向对象语言

命令式语言,面向对象语言和说明型语言(SQL),如果了解静态类型vs动态类型,弱类型vs强类型则有加分

函数式语言,如果了解延 缓求值,局部套用函数,延续则有加分

并发语言(Erlang, Oz) 逻辑语言(Prolog)

专业平台经验

1

2-3

4-5

6+

专业经验年龄

1

2-5

6-9

10+

领域知识

没有该领域的知识

在该领域中曾经至少为一个 产品工作过

在同一领域中为多个产品工作过

领域专家。在该领域设计和实现数种产品/方案。精通该领域使用的标准条款 和协议

学识 Knowledge

2 n (Level 0)

n 2 (Level 1)

n (Level 2)

log(n) (Level 3)

Comments

工具知识

仅限于主要的IDE(VS.Net, Eclipse等)

知 道一些流行和标准工具的备选方案

对编辑器、调试器、IDE、开源的备选方案有很好的了解。比如某人了解大多数Scott Hanselman的威力工具列表中的工具,使用过ORM工具。

实际地编写过工具和脚本,如果这些被发布则有加分

语言接触

命令式语言和面向对象语言

命令式语言、面向对象 语言和说明型语言(SQL),如果了解静态类型vs动态类型、弱类型vs强类型则有加分

函数式语言,如果了解延缓求值、局部套用函 数、continuations (源于scheme中的一种高级控制结构)则有加分

并发语言(Erlang, Oz) 逻辑语言(Prolog)

代码库知识

从来没有查询过代码库

基本的代码层知识,了 解如果构建系统

良好的代码库工作知识,实现过几次bug修复或者完成了一些细小的特性

实现了代码库中多个大型特 性,能够轻松地将多数特性的需求变更具体化,从容地处理bug修复。

下一代技术知识

从来没听说过即将到来的技术

听说过某领 域即将到来的技术

下载过alpha preview/CTP/beta版本,并且读过一些文章和手册

试用过预览 版而且实际地构建过某物,如果共享给其他人的话则有加分

2 n (Level 0)

n 2 (Level 1)

n (Level 2)

log(n) (Level 3)

Comments

平台内部

对平台内部毫无所知

有平台基本的内部工作的 知识

深度的平台内部知识,能够设想平台如何将程序转换成可执行代码。

编写过增强平台或者为其平台内部提供信息的 工具。比如,反汇编工具,反编译工具,调试工具等。

书籍

菜鸟系列,21天系列,24小时系列,蠢货系列…

《代 码大全》,《别让我思考》, 《精通正则表达式》

《设计模式》,《人件》,《代码珠玑》,《算法设计手册》,《程序员修炼之道》, 《人月神话》

《计算机程序设计与解释》,《事务处理:概念与技术》,《计算机程序设计模型》,《计算机程序设计艺术》,《数据库系统 导论》 C.J
Date版,《Thinking Forth》 ,《Little Schemer》(没找到其中译本)

博客

听过但是从来抽不出空去接触

阅读一些科技/编程 /软件工程的博客,并且经常的收听一些播客

维护一些博客的链接,收集博主分享的有用的文章和工具

维护一个在编程方 面,分享有个人见解和思考的博客

0%