第2章高級(jí)語言及其語法描述

程序語言的定義高級(jí)語言的一般特性程序語言的語法描述文法形式語言鳥瞰高級(jí)語言及其語法描述共23頁，您現(xiàn)在瀏覽的是第1頁!程序語言的定義記號(hào)系統(tǒng)=語法+語義+[語用]詞法規(guī)則語法規(guī)則高級(jí)語言及其語法描述共23頁，您現(xiàn)在瀏覽的是第2頁!語法：定義：是指規(guī)定如何由基本符號(hào)組成一個(gè)完整的程序的規(guī)則?？梢苑治囊话愕脑~法規(guī)則和語法規(guī)則（產(chǎn)生規(guī)則）。例子：0.5*X1+C語言的詞法規(guī)則——單詞符號(hào)的形成規(guī)則

單詞符號(hào)是語言中具有獨(dú)立意義的最基本單位，包括各類型的常數(shù)、標(biāo)識(shí)符、基本字、算符和界符等。語言的語法規(guī)則——語法單位的形成規(guī)則規(guī)定如何從單詞符號(hào)形成語法單位（包括：表達(dá)式、語句、分程序、函數(shù)、過程和程序等）的規(guī)則。語法規(guī)則的描述——上下文無關(guān)文法詞法規(guī)則和語法規(guī)則定義了程序的形式結(jié)構(gòu)，是判斷輸入字符串是否構(gòu)成一個(gè)形式上正確程序的依據(jù)。高級(jí)語言及其語法描述共23頁，您現(xiàn)在瀏覽的是第3頁!語義——單詞符號(hào)和語法單位的意義。語義：形式上完全相同的語法單位在不同的語言中語義是不相同的。高級(jí)語言及其語法描述共23頁，您現(xiàn)在瀏覽的是第4頁!高級(jí)語言的分類程序結(jié)構(gòu)數(shù)據(jù)類型與操作（P19）高級(jí)語言的一般特性：類別特點(diǎn)語法形式示例類別特點(diǎn)示例備注高級(jí)語言及其語法描述共23頁，您現(xiàn)在瀏覽的是第5頁!賦值語句（P24）：A：=B右值，表示名字的值左值，存儲(chǔ)單元，地址高級(jí)語言及其語法描述共23頁，您現(xiàn)在瀏覽的是第6頁!連接積——UV={|U且V}（U、V是*的子集）即UV中的符號(hào)串是U和V中的符號(hào)串連接而成的。用*表示*上的所有符號(hào)串的全體例如：={a,b}，則*={,a,b,aa,ab,ba,bb,aaa,…}例如：U={a,b}、V={aa,bb}則UV={aaa,abb，baa，bbb}Vn=V

V

V……V規(guī)定V0={}高級(jí)語言及其語法描述共23頁，您現(xiàn)在瀏覽的是第7頁!上下文無關(guān)文法（P27）：1、概念文法——描述語言的語法結(jié)構(gòu)的形式規(guī)則（即語法規(guī)則）上下文無關(guān)文法——文法所定義的語法單位是完全獨(dú)立于這種語法單位可能出現(xiàn)的環(huán)境的。2、上下文無關(guān)文法G={終結(jié)符VT，非終結(jié)符集VN，開始符號(hào)S，產(chǎn)生式集P}（P27）文法的表示方法；G,G[S]高級(jí)語言及其語法描述共23頁，您現(xiàn)在瀏覽的是第8頁!<字母>->A|B|…|Z|a|b|…|z<數(shù)字>->0|1|2|3|4|5|6|7|8|9|該子語言文法的開始符號(hào)為（），終結(jié)符號(hào)為（）非終結(jié)符號(hào)為（）。高級(jí)語言及其語法描述共23頁，您現(xiàn)在瀏覽的是第9頁!<句子>語法樹<主語><間接賓語><直接賓語><謂語>he<代詞>gave<動(dòng)詞>me<代詞><冠詞><名詞>abook高級(jí)語言及其語法描述共23頁，您現(xiàn)在瀏覽的是第10頁!5、語法樹（P31）

可以用語法樹表示一個(gè)句子的結(jié)構(gòu)。語法樹是以開始符號(hào)（識(shí)別符）為根，以句子的推導(dǎo)過程為依據(jù)，對(duì)每個(gè)非終結(jié)符，把它的推導(dǎo)所用產(chǎn)生式的右部的全部符號(hào)作為它的子結(jié)點(diǎn)。語法樹的全部葉子，從左到右就是這個(gè)句子。高級(jí)語言及其語法描述共23頁，您現(xiàn)在瀏覽的是第11頁!6、語法樹和語法的二義性（P31）某個(gè)文法的某個(gè)句子存在兩個(gè)不同的語法樹。不能在有限的步驟中一般地證明一個(gè)文法是二義的例如：文法2.1：E→E+E|E*E|（E）|i的句子(i*i+i)的最右推導(dǎo)和最左推導(dǎo)就對(duì)應(yīng)2棵不同的語法樹）E（E+EEE*Eiii）E（E*EEE+Eiii判定的額結(jié)果是針對(duì)文法的，但判定的關(guān)鍵是兩棵不同的語法樹對(duì)應(yīng)同一個(gè)選定的句子。高級(jí)語言及其語法描述共23頁，您現(xiàn)在瀏覽的是第12頁!復(fù)習(xí)總結(jié)文法的使用限制語法樹與二義性文法和語言的形式定義符號(hào)與符號(hào)串文法和語法字母表與符號(hào)串符號(hào)串集合的運(yùn)算（閉包）文法的形式定義語法分析的基本術(shù)語語言的形式定義推導(dǎo)與規(guī)約句型、句子和語言短語與句柄最左、最右推導(dǎo)與歸約語法樹的構(gòu)造語法的二義性語法樹與短語高級(jí)語言及其語法描述共23頁，您現(xiàn)在瀏覽的是第13頁!程序語言的基本功能：

描述數(shù)據(jù)和對(duì)數(shù)據(jù)運(yùn)算。程序語言的每個(gè)組成成分都有（抽象的）邏輯和計(jì)算機(jī)實(shí)現(xiàn)兩方面的意義。高級(jí)語言及其語法描述共23頁，您現(xiàn)在瀏覽的是第14頁!標(biāo)識(shí)符——由字母或數(shù)字組成的以字母為開頭的一個(gè)字符串。它沒有意義。名字——是代表一個(gè)抽象的存儲(chǔ)單元，存儲(chǔ)單元的內(nèi)容就是該名字的值，也是名字所表示的一個(gè)具體對(duì)象，名字還有明確的屬性（包括類型和作用域）和意義。數(shù)據(jù)類型與操作（P19）：類別數(shù)據(jù)運(yùn)算示例初等數(shù)據(jù)類型數(shù)據(jù)結(jié)構(gòu)抽象數(shù)據(jù)類型高級(jí)語言及其語法描述共23頁，您現(xiàn)在瀏覽的是第15頁!程序語言的語法形式描述(P25)

：字母表——有窮符號(hào)集合(注意：是“符號(hào)”，而不是“字符”)符號(hào)——字母表中的元素例如：={a,b,c,d,e,….z}={begin,end,if,for,while}符號(hào)串——字母表中的符號(hào)構(gòu)成的有窮序列

例如：{aa,bb,cc,dd,…}（顯然是一個(gè)無窮的集合）

空字：不包含任何符號(hào)的序列，記為。注意區(qū)分：，{}，{}高級(jí)語言及其語法描述共23頁，您現(xiàn)在瀏覽的是第16頁!

閉包：V*=V0U

V1U

V2U

V3U……正則閉包：V+=VV*例如：已知字母表X={0,1,2,3,4,5,6,7}，求X*和X+解答：X0=

{}，X1=

X={0,1,2,3,4,5,6,7}，X2=

{00,01,02,03,04,05,06,07，……，77}…………X*={,

0,1,2,3,4,5,6,7,00，…77，000，…，777，…}X+=XX*={0,1,2,3,4,5,6,7,00，…77，000，…，777，…}高級(jí)語言及其語法描述共23頁，您現(xiàn)在瀏覽的是第17頁!例子：給定如下子語言框架：<程序>->Program<程序>；<分程序><分程序>-><分程序體>|<說明>；<分程序體><說明>->Integer<標(biāo)識(shí)符表>|Real|<標(biāo)識(shí)符表>|Bloolean<標(biāo)識(shí)符表>|Procedure<過程標(biāo)識(shí)符><分程序>|<說明>；<說明>；<分程序體>->Begin<語句>End<語句>-><標(biāo)識(shí)符>|<特殊字符>|<語句>；<語句><程序名>-><標(biāo)識(shí)符><過程標(biāo)識(shí)符>-><標(biāo)識(shí)符><標(biāo)識(shí)符表>-><標(biāo)識(shí)符>|

<標(biāo)識(shí)符>|

<標(biāo)識(shí)符表><標(biāo)識(shí)符>-><字母>|<標(biāo)識(shí)符><字母>|<標(biāo)識(shí)符><數(shù)字><特殊字符>->$高級(jí)語言及其語法描述共23頁，您現(xiàn)在瀏覽的是第18頁!例子：hegavemeabook.VT={he，gave，me，a，book}VN={<句子>,<主語>,<謂語>,<直接賓語>,<間接賓語>,<代詞>,<冠詞>,<動(dòng)詞>,<名詞>}S=<句子>P={<句子>-><主語><謂語><直接賓語><間接賓語>,<主語>-

-><代詞>,…………<代詞>-

->he,…………}高級(jí)語言及其語法描述共23頁，您現(xiàn)在瀏覽的是第19頁!3、推導(dǎo)（P29）、最左推導(dǎo)和最右推導(dǎo)（P30）4、句型、句子（P29）例如：文法2.1：E→E+E|E*E|（E）|i的推導(dǎo)E→（E）→（E+E）→（E*E+E）→（i*E+E）→（i*i+E）→（i*i+i）句型有：（E）、（E+E）、（E*E+E）、（i*E+E）、（i*i+E）、（i*i+i）句子有：（i*i+i）高級(jí)語言及其語法描述共23頁，您現(xiàn)在瀏覽的是第20頁!<句子>語法樹<主語><間接賓語><直接賓語><謂語>he<代詞>gave<動(dòng)詞>me<代詞><冠詞><名詞>abook高級(jí)語言及其語法描述共23頁，您現(xiàn)在瀏覽的是第21頁!形式語言鳥瞰：文法的4種類型：0型文法——短語文法1型文法——上下文有關(guān)文法2型文法——上下文無關(guān)文法3型文法——左/右線性文