Wednesday, May 28, 2008

Peter Naur 和 BNF notation 和 Datalogy

这几天,在准备下下个月的IT新技术的讲演, 一个字还没写出来,资料倒读了很多。乱写几句吧。

--------------------------------------

Peter Naur是2005年Turing Award(图灵奖)的获奖者,他的主要成就是Algol 60语言和编译器。

他是个丹麦人,天文学博士。后来就去搞计算机基础语言去了。

ALGOL 国际代数语言

ALGOL是计算机发展史上首批产生的高级语言,当时还是晶体管计算机流行的时代,由于ALGOL语句和普通语言表达式接近,更适于数值计算,所以ALGOL多用于科学计算机。

ALGOL这个名称是算法语言的简称,这种语言不是计算机制造公司为某种特定机器设计的,而是纯粹面向描述计算过程的,也就是所谓面向算法描述的。

ALGOL是第一个清晰定义的语言,其语法是用严格公式化的方法说明的。ALGOL语言并没有被广泛的使用,但它是许多现代程序语言的概念基础。

Algol 58:1958年,ACM小组和以当时联邦德国的应用数学和力学协会GAMM在苏黎世把他们关于算法表示法的建议综合为一,形成了Algol 58,先被命名为IAL(国际代数语言,International Algebraic Language),后来改称Algol 58。

Algol 60:1960年1月,图灵奖获得者:艾伦.佩利(Alan J.Perlis)在巴黎举行的有全世界一流软件专家参加的讨论会上,发表了"算法语言Algol 60报告",确定了程序设计语言Algol 60。1962年,艾伦.佩利又对Algol 60进行了修正。

Algol 60引进了许多新的概念如:局部性概念、动态、递归、巴克斯瑙尔范式BNF(Backus-Naur Form)等等。

Algol 60是程序设计语言发展史上的一个里程碑,它标志着程序设计语言成为一门独立的科学学科,并为后来软件自动化及软件可靠性的发展奠定了基础。

Algol W:1966年,IFIP吸收沃思参加对Algol语言进行完善与扩充的工作小组。沃思参加进去以后,提交了一份建议书并由霍尔(Tony Hoars)等人修改、完善以后形成Algol W。同时还催生了一个新的语言PL 360。

BNF notation: N 就是Naur。巴科斯范式(BNF: Backus-Naur Form 的缩写)描述计算机语言语法的符号集

在双引号中的字("word")代表着这些字符本身。而double_quote用来代表双引号。
在双引号外的字(有可能有下划线)代表着语法部分。
尖括号( < > )内包含的为必选项。
方括号( [ ] )内包含的为可选项。
大括号( { } )内包含的为可重复0至无数次的项。
竖线( | )表示在其左右两边任选一项,相当于"OR"的意思。
::= 是“被定义为”的意思。

巴科斯范式示例

下面是用BNF来定义的Java语言中的For语句的实例:

FOR_STATEMENT ::=
"for" "(" ( variable_declaration |
( expression ";" ) | ";" )
[ expression ] ";"
[ expression ] ";"
")" statement

这是用BNF来定义的BNF本身的例子。

这个老头最有趣的有两点:

1)他痛恨“computer science ”, 并为此创立了一个新名词:datalogy, 丹麦已经不再用computer science 这个名词了,而用datalogy。

2)他反对现有的哲学和心理学试图找出事物之间的联系的思想,认为世界就是不同facts的集合,facts之间没有必然的联系。他发展了一种叫做Synapse-State Theory of Mental Life(他创立的名词)的思想观。

总之,这个老头蛮好玩的。

No comments: