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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

　　《算法十?dāng)?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è)計(jì)》（Programming in M0dula－2，Spring6r，1988，第4版）

　　《PASCAL用戶手冊(cè)和報(bào)告： ISO PASCAL標(biāo)準(zhǔn)》 （PASCAL UserManual and Report： ISO PASCAL Standard， Sprillger， 1991）

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

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

　　《數(shù)字電路設(shè)計(jì)教材》（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年授予沃思圖靈獎(jiǎng)外，1987年又授予他“計(jì)算機(jī)科學(xué)教育杰出貢獻(xiàn)獎(jiǎng)”。另一重要的國(guó)際學(xué)術(shù)組織IEEE也授予過(guò)沃思兩個(gè)獎(jiǎng)項(xiàng)： 1983年的 Emanual Piore獎(jiǎng)和 1988年的計(jì)算機(jī)先驅(qū)獎(jiǎng)（Computer Pioneer Award）。1992年，加州大學(xué)伯利分校命名沃思為“杰出校友”。

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

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


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



文章來(lái)源:http://justjavac.javaeye.com/blog/170054