【正文】 x的 方冪。 12 ?符號串中符號的個數(shù)。 ? 如 :ana是符號串 banana的一個子串 . ? 對于每個符號串 s， s和 ε 兩者 都 是符號串 s的前綴，后綴和子串。 ? 如： b是符號串 banana的一個前綴 . ? 符號串 s的尾（后綴）：刪去符號串 s頭部的零個或多于零個符號得到的符號串。即：設(shè) L是（ ∑上的）一個語言 ,M是（ ∑上的）一個語言，則語言 L和 M的并，交，差，補(bǔ)是一個語言。 ? ε (沒有 符號的符號串 )是 ?上的符號串 ? x是 ?上的符號串 ,a是 ?的元素 ,則 xa是 ?上的符號串 ? 3. y是 ?上的符號串 ,當(dāng)且僅當(dāng)它可以由 1和 2導(dǎo)出。 ? 字母表（ ?） ：符號（元素）的非空有窮集合。其中一種描述元語言稱為文法。這些規(guī)則成為我們判別句子結(jié)構(gòu)合法與否的依據(jù)，換句話說，這些規(guī)則看成是一種元語言，用它描述漢語。比如，選取了 〈 主語 〉 ，并采用規(guī)則 〈 主語 〉 ∷ =〈 代詞 〉 ， ? 那么得到： 〈 主語 〉〈 謂語 〉 ? 〈 代詞 〉〈 謂語 〉 ， 重復(fù)做下去。語法只是定義什么樣的符號序列是合法的，與這些符號的含義毫無關(guān)系 ?闡明語法的一個工具是文法，這是形式語言理論的基本概念之一。所謂一個語言的語法是指一組規(guī)則，用它可以形成和產(chǎn)生一個合適的程序?！靶问健笔侵高@樣的事實(shí)：語言的所有規(guī)則只以什麼符號串能出現(xiàn)的方式來陳述。1 編譯原理 文法和語言 華東交通大學(xué) 軟件學(xué)院網(wǎng)絡(luò)工程教研室 萬仲保 Tel:7046821 13907097766 Email: 2 第三章 文法和語言 ?本章目的 ? 為語言的語法描述尋求工具 ? 工具要對程序設(shè)計語言給出精確無二義的語法描述。（嚴(yán)謹(jǐn)、簡潔、易讀） ?形式工具 形式語言抽象地定義為一個數(shù)學(xué)系統(tǒng)。 3 ? 文法的直觀概念 ? 符號和符號串 ? 文法和語言的形式定義 ? 文法的類型 ? 上下文無關(guān)文法及其語法樹 ? 句型分析 ? 實(shí)用說明 第三章 文法和語言 4 文法的直觀概念 ?一個程序設(shè)計語言是一個記號系統(tǒng)，如同自然語言一樣，它的完整的定義應(yīng)包括語法和語義兩個方面。目前廣泛使用的手段是上下文無關(guān)文法，即用上下文無關(guān)文法作為程序設(shè)計語言語法的描述工具。 ?示例： 漢語句子的描述 ?語言概述 5 漢語句子的描述 ?語法規(guī)則定義 ?字符串的判斷 6 語法規(guī)則定義 〈 句子 〉 ∷ =〈 主語 〉〈 謂語 〉 〈 主語 〉 ∷ =〈 代詞 〉 ｜ 〈 名詞 〉 〈 代詞 〉 ∷ =我 ｜ 你 ｜ 他 〈 名詞 〉 ∷ =王明 ｜ 大學(xué)生 ｜ 工人 ｜ 英語 〈 謂語 〉 ∷ =〈 動詞 〉〈 直接賓語 〉 〈 動詞 〉 ∷ =是 ｜ 學(xué)習(xí) 〈 直接賓語 〉 ∷ =〈 代詞 〉 ｜ 〈 名詞 〉 7 字符串的判斷 ? 有了一組規(guī)則以后，按照如下方式用它們導(dǎo)出句子：開始去找 ∷ =左端的帶有 〈 句子 〉 的規(guī)則并把它由 ∷ =右端的符號串代替，這個動作表示成： ? 〈 句子 〉 ? 〈 主語 〉〈 謂語 〉 ， ? 然后在得到的串 〈 主語 〉〈 謂語 〉 中，選取 〈 主語 〉 或 〈 謂語 〉 ，再用相應(yīng)規(guī)則的 ∷ =右端代替之。 ? 句子： “ 我是大學(xué)生 ” 的全部動作過程是： ? 〈 句子 〉 ?〈 主語 〉〈 謂語 〉 ? 〈 代詞 〉〈 謂語 〉 ? ?我 〈 謂語 〉 ?我 〈 動詞 〉〈 直接賓語 〉 ? ? 我是 〈 直接賓語 〉 ?我是 〈 名詞 〉 ?我是大學(xué)生 8 字符串的判斷 ?“我是大學(xué)生 ” 的構(gòu)成符合上述規(guī)則，而“ 我大學(xué)生是 ” 不符合上述規(guī)則，我們說它不是句子。這里僅僅涉及漢語句子的結(jié)構(gòu)描述。 9 符號和符號串 ?定義： ? 符號：可以相互區(qū)別的記號（元素）。 ? 符號串：由字母表 ?中的符號組成的任何有窮序列稱為該字母表上的符號串。 ? 例如： Σ ={a,b} ? ε ,a,b,aa,ab,aabba… 都 是 ?上的符號串 ?符號串的運(yùn)算 10 符號串的運(yùn)算 ?既然將語言定義為一個集合，那么有關(guān)集合的運(yùn)算也適合語言。 ? 符號串的頭、尾、子串 ? 符號串的長度 ? 符號串的連接 ? 符號串的方冪 ? 符號串的集合 11 符號串的頭、尾、子串 ? 符號串 s的頭（前綴）：移走符號串 s尾部的零個或多于零個符號得到的符號串。 ? 如 :nana是符號串 banana的一個后綴 . ? 符號串 s的子串：從 s中刪去一個前綴和一個后綴得到的符號串。 ? 符號串 s的真前綴，真后綴，真子串：任何非空符號串 x,相應(yīng)地，是 s的前綴，后綴或子串，并且 s ? x。 ?符號串 s的長度記為 |s|。寫作 z=an ?示例： ? a1=a, a2=aa ? a0=ε 15 符號串集合 ?若集合 A中所有元素都是某字母表 ?上的符號串，則稱 A為字母表 ?上的符號串集合。 Σ *稱為 Σ 的閉包 。 Σ +稱為 Σ的正閉包 。 ?漢語 所有符合漢語語法的句子的全體 ?英語 所有符合英語語法的句子的全體 ? 每個句子構(gòu)成的規(guī)律 ?語言研究 每個句子的含義 ? 每個句子和使用者的關(guān)系 每個程序構(gòu)成的規(guī)律 ?研究程序設(shè)計語言 每個程序的含義 每個程序和使用者的關(guān)系 語法 Syntax ? 語言研究的三個方面 語義 Semantics 語用 Pragmatics 18 程序設(shè)計語言 ?研究程序設(shè)計語言 每個程序構(gòu)成的規(guī)律 每個程序的含義 每個程序和使用者的關(guān)系 ?語言研究的三個方面 語法 Syntax 語義 Semantics 語用 Pragmatics 19 語言研究的三個方面 ?語法 表示構(gòu)成語言句子的各個記號之間的組合規(guī)律 ?語義 表示各個記號的特定含義。 ?每種語言具有兩個可識別的特性 ， 即語言的形式和該形式相關(guān)聯(lián)的意義 。 這兩個意義并非總是一樣的 ， 前者稱為語言的語義 ， 后者是其語用意義 。 2