第二章高級語言及其語法描述

1、第二章 高級語言及其語法描述 2.1 程序語言的定義(描述) 2.2 高級語言的一般特性 2.3 程序語言的語法描述2.1 程序語言的定義 語法： 語言的語法是指這樣的一組規(guī)則，用它可以產(chǎn)生和形成一個(gè)合式的程序。 例如：變量的標(biāo)示符要以非數(shù)字開頭 語法分為詞法規(guī)則和語法規(guī)則。 詞法規(guī)則： 指單詞符號的形成規(guī)則，單詞符號包括：各種類型常數(shù)、標(biāo)示符、算符和界符等。 詞法分析工具：有正規(guī)式和有限自動機(jī)理論。 語法規(guī)則： 是語法單位的形成規(guī)則。 語法單位包括：表達(dá)式、語句、子程序、函數(shù)等。 語法規(guī)則描述工具有上、下文無關(guān)文法。 語義： 是指這樣的規(guī)則，使用它可以定義一個(gè)程序的意義。 語義描述的方法：屬

2、性文法的語法制導(dǎo)翻譯方法。該方法接近形式化方法。 相同語句不同含義的例子： Z=X+Y可以表示整數(shù)相加和實(shí)數(shù)相加等不同的語義。 編譯程序的就是要從基本的單詞符號和語法單位分析程序的語義。2.2 高級語言的一般特性 高級語言分類： 過程式語言-命令驅(qū)動、面向語句，如C語言等。 函數(shù)式語言-從功能出發(fā)構(gòu)造函數(shù)，如LISP等。 基于規(guī)則的語言-檢查一定的條件，當(dāng)他滿足直，則執(zhí)行適當(dāng)?shù)膭幼?，如Prolog語言。 面向?qū)ο蟮恼Z言-支持封裝、繼承和多態(tài)性等。2.3 程序語言的語法描述 基本概念： ：是一個(gè)有窮字母表，它的每個(gè)元素稱為一個(gè)符號。 上的字（符號串）：是指由中的符號所構(gòu)成的一個(gè)有窮序列。 ：不包

3、含任何符號的序列稱為空字。 ：表示上所有字的集合，其中包括空字。 : 不包含任何元素的集合 = 集合運(yùn)算： 集合的積運(yùn)算：UV=|U&V Vn=VVV 其中V0= 集合的或運(yùn)算：UV=|U ORV 集合的閉包運(yùn)算：V=V0V1V2V3 集合的正規(guī)閉包：V+=VV2.3.1 上下文無關(guān)文法 文法：描述語言的語法結(jié)構(gòu)的形式規(guī)則。 特點(diǎn)：這些規(guī)則必須是準(zhǔn)確的，易于理解的，而且，應(yīng)當(dāng)有相當(dāng)強(qiáng)的描述能力，足以描述各種不同的結(jié)構(gòu)。 例如：- 上下文無關(guān)文法： 它所定義的語法范疇是完全獨(dú)立于這種范疇可能出現(xiàn)的環(huán)境的。 一個(gè)上下文無關(guān)文法G包括四個(gè)組成部分： 一組終結(jié)符號 一組非終結(jié)符號 一個(gè)開始符號

4、 一組產(chǎn)生式 終結(jié)符號： 是組成語言的基本符號，在程序語言中就是以前屢次提到的單詞符號，如基本字、標(biāo)識符、常數(shù)、算符和界符等。 非終結(jié)符號： 用來代表語法范疇。如：語句A、表達(dá)式B等。 開始符號： 是一個(gè)特殊的非終結(jié)符號，它代表所定義的語言中我們最終感興趣的語法范疇，這個(gè)語法范疇通常稱為“句子”或是“程序”。 產(chǎn)生式： 是定義語法范疇的一種書規(guī)則。 一個(gè)產(chǎn)生式的形式是A或A:= A：是非終結(jié)符號 ：是由終結(jié)符號或與非終結(jié)符號組成的一個(gè)符號串。 例如：一個(gè)簡單的算術(shù)表達(dá)式文法： Ei EE+E EE*E (2-1) E(E) 終結(jié)符號：i 非終結(jié)符號：E 開始符號：算術(shù)表達(dá)式 產(chǎn)生式：(2-1)

5、 形式化定義： 一個(gè)上下文無關(guān)文法是一個(gè)四元式（VT ,VN ,S , ）VT是一個(gè)非空有限集，它的每個(gè)元素稱為終結(jié)符號； VN是一個(gè)非空有限集，它的每個(gè)元素稱為非終結(jié)符號，VTVN=； S是一個(gè)非終結(jié)符號，稱為開始符號；SVN。 是一個(gè)產(chǎn)生式集合（有限），每個(gè)產(chǎn)生式的形式是P。 其中，PVN ，（VTVN）。開始符號S至少必須在某個(gè)產(chǎn)生式的左部出現(xiàn)一次。 P1|2|n。其中，i稱為是P的一個(gè)候選式。 讀作定義，直豎讀為“或”,它是元語言元語言符號。 上下文無關(guān)文法語言：從文法的開始符號出發(fā)，反復(fù)使用產(chǎn)生式，對非終結(jié)符施行替換和展開。 例子：求解文法2-1的語言？ E (E)(E+E)(i+E

6、)(i+i) 推導(dǎo)：稱A直接推出 ，即：A ，僅當(dāng)A是產(chǎn)生式，且、(VTVN)* 如果11 n，則稱序列是一個(gè)推導(dǎo)；稱1可推出n；n 1表示經(jīng)一步或若干步可推出表示經(jīng)0步或若干步推出n*1假定G是一個(gè)文法，S是它的開始符號。如果有:則稱是一個(gè)句型。僅含終結(jié)符號的句型是一個(gè)句子。文法G所產(chǎn)生的句子的全體是一個(gè)語言，將它記為L(G)。L(G)= =|S*&VT* *S 最左推導(dǎo)： 任何一步=都是對中的最左非終結(jié)符進(jìn)行替換的。 最右推導(dǎo)： 任何一步=都是對中的最右非終結(jié)符進(jìn)行替換的。 例2.1、例2.2、例2.32.3.2 語法分析樹與二義性 語法樹定義： 句型推導(dǎo)的樹形表示稱為語法樹。EE

7、E(根)()i*+EEEii 文法二義性： 文法存在某個(gè)句子對應(yīng)兩顆不同的語法樹，則稱這個(gè)文法是二義性文法。 例如：EEE(根)()i*+EEEiiEEE(根)()i+*EEEii 二義性文法特點(diǎn)： 文法的二義性和語言的二義性不同，不同的文法可以有相同的語言，即L(G)=L(G*)，其中G是二義性文法。 文法的二義性證明是NP-Hard問題。 上下文無關(guān)文法的限制： 文法中不含任何下面形式的產(chǎn)生式 PP 每個(gè)非終結(jié)符P必須都有用處。即：必須存在含P的句型，并且對于P不存在永不終結(jié)的回路。 無二義性文法推導(dǎo)舉例： 文法：TETEFTFT*iEF)(E看作“表達(dá)式”，T看作“項(xiàng)”，F(xiàn)看作“因子”，

8、則上述文法可以表示為：表達(dá)式-項(xiàng)|表示式+項(xiàng)項(xiàng)-因子|項(xiàng)*因子因子-(表達(dá)式)|i表達(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)2.3.3 形式語言鳥瞰 喬姆斯基（Chomsky）把文法分四類： 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,），對每個(gè)產(chǎn)生式有（VNVT）*且（VNVT）*對0型文法分別施加以下第i條限制，就得到I型文法： 每個(gè)產(chǎn)生式為均滿足|;僅 S例外，但S不得出現(xiàn)在任何產(chǎn)生式的右部。G為任何產(chǎn)生式為A，AVN

9、 ，（VNVT）。 G的任何產(chǎn)生式為(1) AB 或A (2) AB 或A 其中VT，A、BVN。(1)式右線性文法；(2)式左線性文法 文法說明： 1型文法也稱上下文有關(guān)文法。這種文法意味著，對非終結(jié)符進(jìn)行替換時(shí)務(wù)必考慮上下文，并且，一般不允許替換成空串。例如，假若A是1型文G的一個(gè)產(chǎn)生式，和都不空，則非終結(jié)符A只有在和這樣的一個(gè)上下文環(huán)境中才可以把它替換為。 2型文法也稱上下文無關(guān)文法。 3型文法也稱線性文法，或稱為正規(guī)文法。文法應(yīng)用舉例 例1：判斷文法SaSb|ab的類型，并推斷文法語言。 由于S aSb|ab與a、b無關(guān)，則是上下文無關(guān)文法。 S aSb|ab，有SaSb aaSbb anSbn，文法文法對應(yīng)的語言為：對應(yīng)的語言為：L2=anbn|n 1 例2現(xiàn)有文法如下：語句if條件 then 語句| if條件 then 語句 else 語句|其它語句試判斷文法的二義性和類型？ 由文法可以推導(dǎo)出下面的二義性句型If C1 then if C2 then S1