【正文】 第二章 形式語言概論 形式語言理論 ? 什么是語言？ ? “ 為相當(dāng)大地區(qū)的公眾所懂得并使用的 ‘ 話 ’ ，以及組成這些 ‘ 話 ’ 的方法的統(tǒng)一體 ” ? “ 某一字母表上符號串（句子）的集合 ” ? 定義仍需精確化 1） 字母表 2） 語法 3） 語義 形式語言理論 ? 由數(shù)學(xué)方法研究自然語言 (如英語 )和人工語言 (如程序語言 )之語法的理論 ,主要討論了語言和文法的數(shù)學(xué)機(jī)制以及語言和文法的分類 ? 應(yīng)用領(lǐng)域 (一 )形式語言理論 (二 )語言和文法的直觀概念 (三 )字母表、串、語言 (四 )文法和語言的形式定義 (五 )文法的類型 (六 )上下文無關(guān)文法及語法樹 (七 )句型的分析 (八 )有關(guān)文法實用中的一些說明 (一 )形式語言理論 (二 )語言和文法的直觀概念 (三 )字母表、串、語言 (四 )文法和語言的形式定義 (五 )文法的類型 (六 )上下文無關(guān)文法及語法樹 (七 )句型的分析 (八 )有關(guān)文法實用中的一些說明 (一 )形式語言理論 (二 )語言和文法的直觀概念 (三 )字母表、串、語言 (四 )文法和語言的形式定義 (五 )文法的類型 (六 )上下文無關(guān)文法及語法樹 (七 )句型的分析 (八 )有關(guān)文法實用中的一些說明 (二 )語言和文法的直觀概念 （引例） ? 我們從“產(chǎn)生語言”的角度出發(fā) ,討論文法和語言的形式定義 ? 語言生成 —— 指制定出有限條規(guī)則，借助它們產(chǎn)生的句子的集合 英語語言為例。并設(shè)每個句子都是“主 謂 賓”結(jié)構(gòu) ? 文法 —— 見右。其中，每個用 括起來的部分是所要定義語言中的一個語法實體（稱為語法單位、語法結(jié)構(gòu)、語法范疇、語法變量等）?！?::=”是用于定義語法結(jié)構(gòu)的符號，其含義（并讀作）“定義為” 。 文法 也稱為產(chǎn)生式 (Production) ① 句子 ::=主語短語 動詞短語 ② 主語短語 ::= the 名詞 ③ 動詞短語 ::=動詞 賓語短語 ④ 賓語短語 ::=冠詞 名詞 ⑤ 名詞 ::=monkey ⑥ 名詞 ::=banana ⑦ 動詞 ::=eat ⑧ 動詞 ::=has ⑨ 冠詞 ::=the ⑩ 冠詞 ::=a (二 )語言和文法的直觀概念 （引例） ? 推導(dǎo) (derivation)——從語言最大的一個 語法實體 （本例中是 句子 ）開始，反復(fù)用語法規(guī)則中 “ ::=” 右側(cè)的符號串取代其左側(cè)符號，直到所得的符號串中不再含有可被替換語法實體 。每次替換稱為一步（直接） 推導(dǎo) ，并用符號“ ?” 表示。 例如 ? 首先用規(guī)則①進(jìn)行第一步推導(dǎo)，可得到 主語短語 動詞短語 ，即 ? 句子 ? 主語短語 動詞短語 ? 所得符號串 主語短語 動詞短語 含有兩個 語法實體 ，可對其中任一個（例如對 動詞短語 ）進(jìn)行新的 推導(dǎo) ? 句子 ? 主語短語 動詞短語 ? ? 主語短語 動詞 賓語短語 ? 重復(fù)上述過程，可得到一個推導(dǎo)序列（見下頁）。 推導(dǎo) 所用 所得的符號串 步 規(guī)則 1 ① 句子 ? 主語短語 動詞短語 2 ③ ? 主語短語 動詞 賓語短語 3 ② ? the 名詞 動詞 賓語短語 4 ④ ? the 名詞 動詞 冠詞 名詞 5 ⑤ ? the monkey動詞 冠詞 名詞 6 ⑦ ? the monkey eat 冠詞 名詞 7 ⑩ ? the monkey eat a 名詞 8 ⑥ ? the monkey eat a banana 推導(dǎo)序列 推導(dǎo)長度 用語法規(guī)則進(jìn)行推導(dǎo) ? 從 句子 出發(fā)，經(jīng) 8步推導(dǎo) 得到一個英語句子 ,則稱前面的推導(dǎo)為 長度為 8的推導(dǎo) ? 若不關(guān)心推導(dǎo)的中間過程，可將從一符號串到另一符號串的推導(dǎo)用記號 ????????????名詞冠詞動詞句子步的推導(dǎo)記為例如上例中經(jīng)過表示monkeythe5,規(guī)則的簡化表示 ? 在前面的語法規(guī)則定義中，有些語法范疇（如 名詞 、 動詞 ）有若干條不同的規(guī)則來定義它，為簡明起見，我們可以將它們寫在同一個左部語法范疇下，將其定義值用符號 “ |”（ 讀作 ‘ 或 ’ ） 隔開。如 名詞 、 動詞 、 冠詞 的定義規(guī)則可簡記為 名詞 ::= monkey | banana 動詞 ::= eat | has 冠詞 ::= the | a 推導(dǎo) 所用 所得的符號串 步 規(guī)則 1 ① 句子 ? 主語短語 動詞短語 2 ③ ? 主語短語 動詞 賓語短語 3 ② ? the 名詞 動詞 賓語短語 4 ④ ? the 名詞 動詞 冠詞 名詞 5 ⑤ ? the monkey動詞 冠詞 名詞 6 ⑦ ? the monkey eat 冠詞 名詞 7 ⑩ ? the monkey eat a 名詞 8 ⑥ ? the monkey eat a banana 練習(xí)：請推導(dǎo) the banana eat a monkey 推導(dǎo)序列 語法規(guī)則及其產(chǎn)生的語言 ? 前面的語法規(guī)則可以產(chǎn)生 16個不同的句子， 由這 16個句子組成的集合，就是該規(guī)則所定義（或所產(chǎn)生）的 語言 ? 應(yīng)指出，所產(chǎn)生的句子中，有些句子的含義是 荒謬的（如 the banana eat a monkey和 the banana eat the banana等）。然而，若不考慮 語義 ，則我們就必須承認(rèn)它們是語法上 合法 的句子。 (二 )語言和文法的直觀概念 1. 程序設(shè)計語言的定義 語言是一個記號系統(tǒng)。 ? 漢語 符合漢語語法的句子的全體 ? 英語 符合英語語法的句子的全體 ? 程序設(shè)計語言 該語言的程序的全體 程序設(shè)計語言由語法和語義定義： 語法：定義每個程序構(gòu)成的規(guī)則 語義：定義每個程序的意義 程序設(shè)計語言包括 :語法 和 語義 ?語法 (syntax) ?定義 : 是一組規(guī)則，用它可以形成和產(chǎn)生一個合適的程序 ?描述工具 :文法 ?作用 : 定義什么樣的符號序列是合法的，與符號的含義無關(guān)。 ?語義 (semantics) ?分類 : 靜態(tài)語義：一系列限定規(guī)則，確定哪些合乎語法的程序是合適的 動態(tài)語義：表明程序要做什么 ?描述工具 : 指稱語義 ,操作語義等 ?作用 : 檢查類型匹配，變量作用域等 2.