網(wǎng)站: JavaEye  作者: justjavac  鏈接：http://justjavac.javaeye.com/blog/170054  發(fā)表時間: 2008年03月11日

聲明：本文系JavaEye網(wǎng)站發(fā)布的原創(chuàng)博客文章，未經(jīng)作者書面許可，嚴禁任何網(wǎng)站轉(zhuǎn)載本文，否則必將追究法律責(zé)任！

除了程序設(shè)計語言之外，沃思在其他方面也有許多創(chuàng)造。為了定義和描述語言，沃思對著名的“巴科斯-諾爾范式”BNF進行了擴充，成為EBNF（Extended BNF）。我們目前所看到的許多語言的 BNF實際上是EBNF，不過人們往往忽略掉這個E字。和BNF一起出現(xiàn)的，還常常有一些看上去像鐵路圖那樣的圖形，稱作“語法圖”（syntax chart或 syntax diagram）或“鐵路圖”（railroad diagram），這也是由沃思所設(shè)計與發(fā)明的，這種圖形標記法的描述能力等價于BNF，但當然更易于閱讀與理解，更加直觀。在語法圖中，用圓圈表示終結(jié)符，用方框表示非終結(jié)符，用有向弧表示走向，圖上一條通路就表示該語法結(jié)構(gòu)的一種正確定義方法。語法圖的4種基本構(gòu)造方法如下。

　　(1) 若產(chǎn)生式為W→W1W2W3,則語法圖如圖1。

　　(2) 若產(chǎn)生式為W→W1W2|W3a|bcW4 ，則語法圖如圖2。

　　(3) 若產(chǎn)生式為W→abW，則語法圖如圖3。

　　(4) 若產(chǎn)生式為W→ab|abW,則語法圖如圖4。

　　對于較復(fù)雜的產(chǎn)生式，其語法圖一般可通過上述4種語法圖進行組合而得。

　　在對上下文無關(guān)文法的研究中，一個很重要的問題是如何確定兩個符號之間的優(yōu)先關(guān)系。現(xiàn)在一般采用的辦法也是由沃思和他的同事韋伯提出來的，就叫沃思-韋伯優(yōu)先關(guān)系（Wirth－ Weber precedence relation），或叫簡單優(yōu)先關(guān)系。它規(guī)定上下文無關(guān)文法 G中任意兩個符號的優(yōu)先關(guān)系如下。

　　（1）X<Y，當且僅當有產(chǎn)生式 A→αXBβ，且有推導(dǎo)B+→Yr。

　　（2）X=Y，當且僅當有產(chǎn)生式A→αXYβ。

　　（3）X> Y，當且僅當有產(chǎn)生式 A→αBYβ，且有推導(dǎo)B+→rX及Y →*aδ。

　　其中A、B為非終結(jié)符，X、Y為待定優(yōu)先關(guān)系的兩個任意符號，α、β、Υ和δ為由終結(jié)符和非終結(jié)符組成的任意符號串，可以是空串。a是終結(jié)符。

　　沃思的學(xué)術(shù)著作很多，主要有如下幾種，其中一些原版是用德文寫的，翻譯成了英文。

　　《系統(tǒng)程序設(shè)計導(dǎo)論》（ Systematic Programming: An Introduction，Prentice－ Hall，1973。其德文版已出至第 5版）

　　《算法十數(shù)據(jù)結(jié)構(gòu)=程序》（Algorithms＋ Data Structures＝ Programs，Prentice－Hall，1976）

　　《算法和數(shù)據(jù)結(jié)構(gòu)》（Algorithms and Data Structures， Prentice - Hall ，1986）

　　《Modula－2程序設(shè)計》（Programming in M0dula－2，Spring6r，1988，第4版）

　　《PASCAL用戶手冊和報告： ISO PASCAL標準》 （PASCAL UserManual and Report： ISO PASCAL Standard， Sprillger， 1991）

　　《Oberon計劃：操作系統(tǒng)和編譯器的設(shè)計》（ Project Oberon：the Design of an Operating System and Compiler，ACM Pr.，1992）

　　《Oberon程序設(shè)計：超越Pascal和Modula》（Programming in Oberon: Steps beyond Pascal and Modula, ACM Pr，1992）

　　《數(shù)字電路設(shè)計教材》（Digital Circuit Design for Computer Science Students：An Introductory Textbook， Spnnger， 1995）

　　《編譯器構(gòu)造的原理和技術(shù)》（Theory and Techniques of Compiler Construction，Addison- Wesley，1996）

　　ACM除了1984年授予沃思圖靈獎外，1987年又授予他“計算機科學(xué)教育杰出貢獻獎”。另一重要的國際學(xué)術(shù)組織IEEE也授予過沃思兩個獎項： 1983年的 Emanual Piore獎和 1988年的計算機先驅(qū)獎（Computer Pioneer Award）。1992年，加州大學(xué)伯利分校命名沃思為“杰出校友”。

　　沃思是在1984年10月于舊金山舉行的ACM年會上接受圖靈獎的。沃思發(fā)表了題為“從程序設(shè)計語言設(shè)計到計算機建造”（From Programming Language Design to Computer Construction）的圖靈獎演說，回顧了自己在計算機領(lǐng)域所做的工作。演說全文刊載于Communications of ACM，1985年 2月，159－ 164頁，也可見《前 20年的 ACM圖靈獎演說集》（ACM Turing Award Lectures——The First 20 Years：1966－1985，ACM Pr．），179－196頁。沃思在演說中強調(diào)了程序設(shè)計語言簡 性的重要意義，也討論了它所需的硬件和軟件環(huán)境（因為沃思一直很重視語言的實現(xiàn)問題）。他介紹了在設(shè)計Modula－2和Lilith中的經(jīng)驗，指出第一手經(jīng)驗和選擇良好開發(fā)工具的無比價值。

　　沃思現(xiàn)仍在蘇黎世工學(xué)院任教，他的電子箱為：wirth @ inf.ethz.ch
本文的討論也很精彩，瀏覽討論>>


JavaEye推薦
中國領(lǐng)先的電子商務(wù)網(wǎng)站－淘寶網(wǎng)招賢納士，誠聘Java工程師



文章來源:http://justjavac.javaeye.com/blog/170054