【正文】 1 第四章 文法和語言 本章目的 為語言的語法描述尋求工具 工具要對程序設(shè)計語言給出精確無二義的語法描述。（嚴(yán)謹(jǐn)、簡潔、易讀） 形式 工具 形式語言抽象地定義為一個數(shù)學(xué)系統(tǒng)?！靶问健笔侵高@樣的事實(shí)：語言的所有規(guī)則只以什麼符號串能出現(xiàn)的方式來陳述 2 本章知識點(diǎn) (內(nèi)容 ) 引言和預(yù)備知識 文法和語言的形式定義 文法的類型 上下文無關(guān)文法及其語法樹 上下文無關(guān)文法 的句型分析 有關(guān)文法實(shí)用中的一些說明 3 文法的直觀概念和 語言概述 當(dāng)我們表述一種語言時，無非是說明這種語言的句子，如果語言只含有有窮多個句子，則只需列出句子的有窮集就行了，但對于含有無窮句子的語言來講，存在著如何給出它的有窮表示的問題。 以自然語言為例，人們無法列出全部句子，但是人們可以給出一些規(guī)則，用這些規(guī)則來說明 (或者定義 )句子的組成結(jié)構(gòu)，比如漢語句子可以是 由主語后隨謂語而成，構(gòu)成謂語的是動詞和直接賓語，我們采用第 2章所介紹的 EBNF來表示這種句子的構(gòu)成規(guī)則： 4 “我是大學(xué)生 ” 。是漢語的一個句子 〈 句子 〉 ∷ =〈 主語 〉〈 謂語 〉 〈 主語 〉 ∷ =〈 代詞 〉 ｜ 〈 名詞 〉 〈 代詞 〉 ∷ =我 ｜ 你 ｜ 他 〈 名詞 〉 ∷ =王明 ｜ 大學(xué)生 ｜ 工人 ｜ 英語 〈 謂語 〉 ∷ =〈 動詞 〉〈 直接賓語 〉 〈 動詞 〉 ∷ =是 ｜ 學(xué)習(xí) 〈 直接賓語 〉 ∷ =〈 代詞 〉 ｜ 〈 名詞 〉 5 有了一組規(guī)則以后，按照如下方式用它們導(dǎo)出句子：開始去找∷ =左端的帶有 〈 句子 〉 的規(guī)則并把它由 ∷ =右端的符號串代替，這個動作表示成： 〈 句子 〉 ? 〈 主語 〉〈 謂語 〉 ， 然后在得到的串 〈 主語 〉〈 謂語 〉 中，選取 〈 主語 〉 或 〈 謂語 〉 ，再用相應(yīng)規(guī)則的 ∷ =右端代替之。比如，選取了 〈 主語 〉 ，并采用規(guī)則 〈 主語 〉 ∷ =〈 代詞 〉 ， 那么得到： 〈 主語 〉〈 謂語 〉 ? 〈 代詞 〉〈 謂語 〉 ， 重復(fù)做下去， 句子： “ 我是大學(xué)生 ” 的全部動作過程是： 〈 句子 〉 ? 〈 主語 〉〈 謂語 ? 〈 代詞 〉〈 謂語 〉 ?我 〈 謂語 ?我 〈 動詞 〉〈 直接賓語 〉 ? 我是 〈 直接賓語 〉 ?我是 〈 名詞 〉 ?我是大學(xué)生 6 “我是大學(xué)生 ” 的構(gòu)成符合上述規(guī)則，而 “ 我大學(xué)生是 ” 不符合上述規(guī)則，我們說它不是句子。這些規(guī)則成為我們判別句子結(jié)構(gòu)合法與否的依據(jù)，換句話說，這些規(guī)則看成是一種元語言，用它描述漢語。這里僅僅涉及漢語句子的結(jié)構(gòu)描述。其中一種描述元語言稱為文法。 7 英語句子 sentence – subject verbphrase object subject – This | Computers | I verbphrase – adverb verb | verb adverb – never verb – is | run | am | tell object – the noun | a noun | noun noun – university | world | cheese | lies This is a university. Computers run the world. I am the cheese. I never tell lies. 8 語言概述 語言是由句子組成的集合，是由一組符號所構(gòu)成的集合。 漢語 所有符合漢語語法的句子的全體 英語 所有符合英語語法的句子的全體 程序設(shè)計語言 所有該語言的程序的全體 每個句子構(gòu)成的規(guī)律 研究語言 每個句子的含義 每個句子和使用者的關(guān)系 9 研究程序設(shè)計語言 每個程序構(gòu)成的規(guī)律 每個程序的含義 每個程序和使用者的關(guān)系 語言研究的三個方面 語法 Syntax 語義 Semantics 語用 Pragmatics 10 語法 表示構(gòu)成語言句子的各個記號之間的組合規(guī)律 語義 表示各個記號的特定含義。（各個記號和記號所表示的對象之間的關(guān)系） 語用 表示在各個記號所出現(xiàn)的行為中，它們的來源、使用和影響。 11 每種語言具有兩個可識別的特性 ， 即語言的形式和該形式相關(guān)聯(lián)的意義 。 語言的實(shí)例若在語法上是正確的 ， 其相關(guān)聯(lián)的意義可以從兩個觀點(diǎn)來看 ， 其一是該句子的創(chuàng)立者所想要表示的意義 ， 另一是接收者所檢驗(yàn)到的意義 。 這兩個意義并非總是一樣的 ， 前者稱為語言的語義 ， 后者是其語用意義 。 幽默 、 雙關(guān)語和謎語就是利用這兩方面意義間的差異 。 12 如果不考慮語義和語用 ， 即只從語法這一側(cè)面來看語言 ， 這種意義下的語言稱作形式語言 。 形式語言抽象地定義為一個數(shù)學(xué)系統(tǒng) ?！?形式 ” 是指這樣的事實(shí)：語言的所有規(guī)則只以什麼符號串能出現(xiàn)的方式來陳述 。 形式語言理論是對符號串集合的表示法 、 結(jié)構(gòu)及其特性的研究 。 是程序設(shè)計語言語法分析研究的基礎(chǔ) 。 13 有關(guān)定義和記號 — 回 顧 符號：可以相互區(qū)別的記號（元素）。 字母表 ?：符號（元素）的非空有窮集合。 符號串：由字母表 ?中的符號組成的任何有窮序列稱為該字母表上的符號串。 ε (沒有 符號的符號串 )是 ?上的符號串 x是 ?上的符號串 ,a是 ?的元素 ,則 xa是 ?上的符號串 3. y是 ?上的符號串 ,當(dāng)且僅當(dāng)它可以由 1和 2導(dǎo)出。 例如： Σ ={a,b} ε ,a,b,aa,ab,aabba… 都 是 ?上的符號串 14 有關(guān)定義和記號 — 回 顧 符號串 s的頭（前綴）：移走符號串 s尾部的零個或多于零個符號得到的符號串 . 如： b是符號串 banana的一個前綴 . 符號串 s的尾（后綴）：刪去符號串 s頭部的零個或多于零個符號得到的符號串 . 如 :nana是符號串 banana的一個后綴 . 符號串 s的子串：從 s中刪去一個前綴和一個后綴得到的符號串 . 如 :ana是符號串 banana的一個子串 . 15 對于每個符號串 s， s和 ε 兩者 都 是符號串 s的前綴，后綴和子串。 符號串 s的真前綴，真后綴，真子串：任何非空符號串 x,相應(yīng)地，是 s的前綴，后綴或子串，并且 s ? x 符號串的運(yùn)算 符號串的長度：符號串中符號的個數(shù) .符號串 s的長度記為 |s|。 ε 的長度為 0 連接：符號串 x、 y的連接 ,是把 y的符號寫在 x的符號之后得到的符號串 xy 如 x=ab,y=cd 則 xy=abcd 有 ε a = aε 方冪：符號串自身連接 n次得到的符號串 an 定義為 aa… aa n個 a a1=a, a2=aa則 a0=ε 16 符號串集合：若集合 A中所有元素都是某字母表 ?上的符號串，則稱 A為字母表 ?上的符號串集合。 兩個符號串集合 A和 B的乘積定義為 AB =?xy|x?A且 y?B? 若 集合 A=?ab,cde? B = ?0,1? 則 AB =?ab1,ab0,cde0,cde1? 使用 ?* 表示 ?上的一切符號串（包括 ε ）組成的集合。 Σ *稱為 Σ 的閉包 。 ?上的 除 ε 外 的所有符號串組成的集合記為?+ 。 Σ +稱為 Σ 的正閉包 。 17 例： Σ ={a,b} Σ *={ε ,a,b,aa,ab,ba,bb,aaa,aab,… } Σ +={a,b,aa,ab,ba,bb,aaa,aab,… } . . . . . .}{ 2* ??????? ?. . . . . .}{ 32** ?????????????? ? ?18 有關(guān)定義和記號 語言 是由句子組成的集合，是由一組符號所構(gòu)成的集合。換言之 ,字母表 ?上 的一個語言是 ?上的一些符號串的集合 (字母表?上 的每個語言是 ?*的一個子集 )。 例如： 字母表 Σ ={a,b} ,Σ *={ε ,a,b,aa,ab,ba,bb,aaa,aab,… } 集合 {ab,aabb,aaabbb,… ,anbn,… } 或表示為 {w|w∈ Σ *且 w=anbn,n≥1} 為 字母表 ?上 的一個語言。 集合 {a,aa,aaa,… } 或 表示為 {w|w∈ Σ *且 w=an,n≥1} 為 字母表 ?上 的一個語言。 ?ε ?是一個語言。 ?即 ? ?是一個語言 。 19 給出語言 上 的有關(guān)運(yùn)算 設(shè) L是（ ?上的）一個語言 ,M是（ ?上的）一個語言 , 語言 L和 M的并，交，差，補(bǔ) 是一個語言。 語言 L和 M的并為 L?M， 是一個語言 : {w|w is in L or is in M} 如： L1 ={a,b,… y,z} M1 ={1,2… 8,9 } L1?M1={a,b,… y,z， 1,2… 8,9 } 語言 L和 M的連接 是一個語言，記 為 LM LM={st |s∈ L且 t∈ M} 如： L1M1 ={a1,b1,… y1,z1,a2,b2… a9… z9} 有 L ?ε ?= ?ε ?L=L。 L的 n次連接 Ln= LL...L 20 語言 上 的運(yùn)算 語言 L的 閉包 記 為 L*， L*= L0 ? L1 ? L2 ? ... L0= ?ε ? ， Ln= L Ln1= Ln1 L,n?1 語言 L的正 閉包 記 為 L+， L+= L1 ? L2 ? L3 ... L+= LL*= L*L L*= L+ ? ?ε ? 如： L1 ={a,b,… y,z} M1 ={1,2… 8,9 } （ L1?M1） ={a,b,… y,z， 1,2… 8,9 } （ L1?M1） *={a,b,… y,z， 1,2… 8,9 ，aa,1a,…xyz,6789st..} L1（ L1?M1） *={所有字母打頭的字母和數(shù)字符號串 } 21 文法和語言的形式定義 如何來描述一種語言？ 如果語言是有窮的（只含有有窮多個句子），可以將句子逐一列出來表示 如果語言是無窮的，找出語言的有窮表示。語言的有窮表示有兩個途經(jīng)：