1、高級(jí)語(yǔ)言及其語(yǔ)法描述第1頁(yè)，共28頁(yè)，2022年，5月20日，21點(diǎn)54分，星期四2.1 程序語(yǔ)言的定義語(yǔ)法：語(yǔ)言的語(yǔ)法是指這樣的一組規(guī)則，用它可以產(chǎn)生和形成一個(gè)合式的程序。例如：變量的標(biāo)示符要以非數(shù)字開(kāi)頭語(yǔ)法分為詞法規(guī)則和語(yǔ)法規(guī)則。詞法規(guī)則：指單詞符號(hào)的形成規(guī)則，單詞符號(hào)包括：各種類(lèi)型常數(shù)、標(biāo)示符、算符和界符等。詞法分析工具：正規(guī)式和有限自動(dòng)機(jī)理論。第2頁(yè)，共28頁(yè)，2022年，5月20日，21點(diǎn)54分，星期四語(yǔ)法規(guī)則：是語(yǔ)法單位的形成規(guī)則。語(yǔ)法單位包括：表達(dá)式、語(yǔ)句、子程序、函數(shù)等。語(yǔ)法規(guī)則描述工具：上、下文無(wú)關(guān)文法。第3頁(yè)，共28頁(yè)，2022年，5月20日，21點(diǎn)54分，星期四語(yǔ)義：是指

2、這樣的規(guī)則，使用它可以定義一個(gè)程序的意義。語(yǔ)義描述的方法：屬性文法的語(yǔ)法制導(dǎo)翻譯方法。該方法接近形式化方法。相同語(yǔ)句不同含義的例子： Z=X+Y可以表示整數(shù)相加和實(shí)數(shù)相加等不同的語(yǔ)義。編譯程序就是要從基本的單詞符號(hào)和語(yǔ)法單位分析程序的語(yǔ)義。第4頁(yè)，共28頁(yè)，2022年，5月20日，21點(diǎn)54分，星期四2.2 高級(jí)語(yǔ)言的一般特性高級(jí)語(yǔ)言分類(lèi)：過(guò)程式語(yǔ)言-命令驅(qū)動(dòng)、面向語(yǔ)句，如C語(yǔ)言等。函數(shù)式語(yǔ)言-從功能出發(fā)構(gòu)造函數(shù)，如LISP等?；谝?guī)則的語(yǔ)言-檢查一定的條件，當(dāng)他滿(mǎn)足，則執(zhí)行適當(dāng)?shù)膭?dòng)作，如Prolog語(yǔ)言。面向?qū)ο蟮恼Z(yǔ)言-支持封裝、繼承和多態(tài)性等。第5頁(yè)，共28頁(yè)，2022年，5月20日，21

3、點(diǎn)54分，星期四2.3 程序語(yǔ)言的語(yǔ)法描述基本概念：是一個(gè)有窮字母表，它的每個(gè)元素稱(chēng)為一個(gè)符號(hào)。上的字（符號(hào)串）：是指由中的符號(hào)所構(gòu)成的一個(gè)有窮序列。：不包含任何符號(hào)的序列稱(chēng)為空字。：表示上所有字的集合，其中包括空字。: 不包含任何元素的集合 = 第6頁(yè)，共28頁(yè)，2022年，5月20日，21點(diǎn)54分，星期四集合運(yùn)算：集合的積運(yùn)算：UV=|U&VVn=VVV： 其中V0=集合的或運(yùn)算：UV=|U ORV集合的閉包運(yùn)算：V=V0V1V2V3 集合的正規(guī)閉包：V+=VV第7頁(yè)，共28頁(yè)，2022年，5月20日，21點(diǎn)54分，星期四2.3.1 上下文無(wú)關(guān)文法文法：描述語(yǔ)言的語(yǔ)法結(jié)構(gòu)的形式規(guī)則。特點(diǎn)：

4、這些規(guī)則必須是準(zhǔn)確的，易于理解的，而且，應(yīng)當(dāng)有相當(dāng)強(qiáng)的描述能力，足以描述各種不同的結(jié)構(gòu)。例如：-第8頁(yè)，共28頁(yè)，2022年，5月20日，21點(diǎn)54分，星期四上、下文無(wú)關(guān)文法：它所定義的語(yǔ)法范疇是完全獨(dú)立于這種范疇可能出現(xiàn)的環(huán)境的。一個(gè)上、下文無(wú)關(guān)文法G包括四個(gè)組成部分：一組終結(jié)符號(hào)一組非終結(jié)符號(hào)一個(gè)開(kāi)始符號(hào)一組產(chǎn)生式第9頁(yè)，共28頁(yè)，2022年，5月20日，21點(diǎn)54分，星期四終結(jié)符號(hào)：是組成語(yǔ)言的基本符號(hào)，在程序語(yǔ)言中就是以前屢次提到的單詞符號(hào)，如基本字、標(biāo)識(shí)符、常數(shù)、算符和界符等。非終結(jié)符號(hào)：用來(lái)代表語(yǔ)法范疇。如：語(yǔ)句A、表達(dá)式B等。開(kāi)始符號(hào)：是一個(gè)特殊的非終結(jié)符號(hào)，它代表所定義的語(yǔ)言中

5、我們最終感興趣的語(yǔ)法范疇，這個(gè)語(yǔ)法范疇通常稱(chēng)為“句子”或是“程序”。第10頁(yè)，共28頁(yè)，2022年，5月20日，21點(diǎn)54分，星期四產(chǎn)生式：是定義語(yǔ)法范疇的一種書(shū)寫(xiě)規(guī)則。一個(gè)產(chǎn)生式的形式是A或A:=A：是非終結(jié)符號(hào)：是由終結(jié)符號(hào)或與非終結(jié)符號(hào)組成的一個(gè)符號(hào)串。第11頁(yè)，共28頁(yè)，2022年，5月20日，21點(diǎn)54分，星期四例如：一個(gè)簡(jiǎn)單的算術(shù)表達(dá)式文法：EiEE+EEE*E (2-1)E(E)終結(jié)符號(hào)：i非終結(jié)符號(hào)：E開(kāi)始符號(hào)：算術(shù)表達(dá)式產(chǎn)生式：(2-1)第12頁(yè)，共28頁(yè)，2022年，5月20日，21點(diǎn)54分，星期四形式化定義：一個(gè)上下文無(wú)關(guān)文法是一個(gè)四元式（VT ,VN ,S , ）VT是

6、一個(gè)非空有限集，它的每個(gè)元素稱(chēng)為終結(jié)符號(hào)；VN是一個(gè)非空有限集，它的每個(gè)元素稱(chēng)為非終結(jié)符號(hào)，VTVN=；S是一個(gè)非終結(jié)符號(hào)，稱(chēng)為開(kāi)始符號(hào)；SVN。 是一個(gè)產(chǎn)生式集合（有限），每個(gè)產(chǎn)生式的形式是P。其中，PVN ，（VTVN）。開(kāi)始符號(hào)S至少必須在某個(gè)產(chǎn)生式的左部出現(xiàn)一次。P1|2|n。其中，i稱(chēng)為是P的一個(gè)候選式。 讀作定義，直豎讀為“或”,它是元語(yǔ)言符號(hào)。第13頁(yè)，共28頁(yè)，2022年，5月20日，21點(diǎn)54分，星期四上、下文無(wú)關(guān)文法語(yǔ)言：從文法的開(kāi)始符號(hào)出發(fā)，反復(fù)使用產(chǎn)生式，對(duì)非終結(jié)符施行替換和展開(kāi)。例子：求解文法2-1的語(yǔ)言？E (E)(E+E)(i+E)(i+i)推導(dǎo)：稱(chēng)A直接推出 ，

7、即：A ，僅當(dāng)A是產(chǎn)生式，且、(VTVN)*第14頁(yè)，共28頁(yè)，2022年，5月20日，21點(diǎn)54分，星期四如果11 n，則稱(chēng)序列是一個(gè)推導(dǎo)；稱(chēng)1可推出n；表示經(jīng)一步或若干步可推出表示經(jīng)0步或若干步推出假定G是一個(gè)文法，S是它的開(kāi)始符號(hào)。如果有:則稱(chēng)是一個(gè)句型。僅含終結(jié)符號(hào)的句型是一個(gè)句子。文法G所產(chǎn)生的句子的全體是一個(gè)語(yǔ)言，將它記為L(zhǎng)(G)。L(G)=|S*&VT* 第15頁(yè)，共28頁(yè)，2022年，5月20日，21點(diǎn)54分，星期四最左推導(dǎo)：任何一步=都是對(duì)中的最左非終結(jié)符進(jìn)行替換的。最右推導(dǎo)：任何一步=都是對(duì)中的最右非終結(jié)符進(jìn)行替換的。例2.1、例2.2、例2.3第16頁(yè)，共28頁(yè)，2022

8、年，5月20日，21點(diǎn)54分，星期四2.3.2 語(yǔ)法分析樹(shù)與二義性語(yǔ)法樹(shù)定義：句型推導(dǎo)的樹(shù)形表示稱(chēng)為語(yǔ)法樹(shù)。EEE(根)()i*+EEEii第17頁(yè)，共28頁(yè)，2022年，5月20日，21點(diǎn)54分，星期四文法二義性：文法存在某個(gè)句子對(duì)應(yīng)兩顆不同的語(yǔ)法樹(shù)，則稱(chēng)這個(gè)文法是二義性文法。例如：EEE(根)()i*+EEEiiEEE(根)()i+*EEEii第18頁(yè)，共28頁(yè)，2022年，5月20日，21點(diǎn)54分，星期四二義性文法特點(diǎn)：文法的二義性和語(yǔ)言的二義性不同，不同的文法可以有相同的語(yǔ)言，即L(G)=L(G*)，其中G是二義性文法。文法的二義性證明是NP-Hard問(wèn)題。上、下文無(wú)關(guān)文法的限制：文法

9、中不含任何下面形式的產(chǎn)生式 PP 每個(gè)非終結(jié)符P必須都有用處。即：必須存在含P的句型，并且對(duì)于P不存在永不終結(jié)的回路。第19頁(yè)，共28頁(yè)，2022年，5月20日，21點(diǎn)54分，星期四無(wú)二義性文法推導(dǎo)舉例：文法：E看作“表達(dá)式”，T看作“項(xiàng)”，F(xiàn)看作“因子”，則上述文法可以表示為：表達(dá)式-項(xiàng)|表示式+項(xiàng)項(xiàng)-因子|項(xiàng)*因子因子-(表達(dá)式)|i第20頁(yè)，共28頁(yè)，2022年，5月20日，21點(diǎn)54分，星期四表達(dá)式項(xiàng)因子(表達(dá)式)(表達(dá)式+項(xiàng))(項(xiàng)+項(xiàng))(項(xiàng)*因子+項(xiàng))(因子*因子+項(xiàng))(i*因子+項(xiàng))(i*i+因子)(i*i+i)第21頁(yè)，共28頁(yè)，2022年，5月20日，21點(diǎn)54分，星期四2.3

10、.3 形式語(yǔ)言鳥(niǎo)瞰喬姆斯基（Chomsky）把文法分四類(lèi)：0型、1型、2型和3型。其描述能力的強(qiáng)度有下列關(guān)系：0型強(qiáng)于1型、1型強(qiáng)于2型、2型強(qiáng)于3型。0型文法：設(shè)G=（VT,VN,S,），對(duì)每個(gè)產(chǎn)生式有（VNVT）*且（VNVT）*第22頁(yè)，共28頁(yè)，2022年，5月20日，21點(diǎn)54分，星期四對(duì)0型文法分別施加以下第i條限制，就得到I型文法： 每個(gè)產(chǎn)生式為均滿(mǎn)足|;僅 S例外，但S不得出現(xiàn)在任何產(chǎn)生式的右部。G為任何產(chǎn)生式為A，AVN ，（VNVT）。 G的任何產(chǎn)生式為(1) AB 或A (2) AB 或A 其中VT，A、BVN。(1)式右線(xiàn)性文法；(2)式左線(xiàn)性文法第23頁(yè)，共28頁(yè)，2

11、022年，5月20日，21點(diǎn)54分，星期四文法說(shuō)明：1型文法也稱(chēng)上、下文有關(guān)文法。這種文法意味著，對(duì)非終結(jié)符進(jìn)行替換時(shí)務(wù)必考慮上下文，并且，一般不允許替換成空串。例如，假若A是1型文G的一個(gè)產(chǎn)生式，和都不空，則非終結(jié)符A只有在和這樣的一個(gè)上下文環(huán)境中才可以把它替換為。2型文法也稱(chēng)上、下文無(wú)關(guān)文法。3型文法也稱(chēng)線(xiàn)性文法，或稱(chēng)為正規(guī)文法。第24頁(yè)，共28頁(yè)，2022年，5月20日，21點(diǎn)54分，星期四文法應(yīng)用舉例例1：判斷文法SaSb|ab的類(lèi)型，并推斷文法語(yǔ)言。由于S aSb|ab與a、b無(wú)關(guān)，則是上下文無(wú)關(guān)文法。S aSb|ab，有SaSb aaSbb anSbn，文法對(duì)應(yīng)的語(yǔ)言為：L2=anbn|n1第25頁(yè)，共28頁(yè)，2022年，5月20日，21點(diǎn)54分，星期四例2現(xiàn)有文法如下：語(yǔ)句if條件 then 語(yǔ)句| if條件 then 語(yǔ)句 else 語(yǔ)句|其它語(yǔ)句試判斷文法的二義性和類(lèi)型？由文法可以推導(dǎo)出下面的二義性句型If C1 then if C2 then S1 else S2 ，其中 else 不知與那個(gè)then 匹配，所以它是二義性文法。由于替換僅在右側(cè)進(jìn)行，且不考慮條件，所以