形式語言基礎

形式語言基礎1第1頁，課件共143頁，創(chuàng)作于2023年2月第二章形式語言基礎知識§2.1引言一、形式語言提出二、語言描述方法§2.2用文法生成法對語言進行描述一、巴科斯范式二、語法和語義三、語法樹§2.3形式語言基本概念和術語一、元語言二、符號和符號串三、產(chǎn)生式（規(guī)則）四、文法

五、推導和歸約六、句型和句子七、語言

八、遞歸文法九、短語和簡單短語十、最左推導和最右推導十一、文法二義性

§2.4語法分析初步

一、自頂向下語法分析二、自底向上語法分析

§2.5文法和語言分類

一、文法分類二、文法和自動機三、壓縮過文法

§2.6文法其他表示法

一、擴充巴科斯范式二、語法圖

2第2頁，課件共143頁，創(chuàng)作于2023年2月第二章形式語言基礎知識§2.1引言一、形式語言提出二、語言描述方法§2.2用文法生成法對語言進行描述一、巴科斯范式二、語法和語義三、語法樹§2.3形式語言基本概念和術語一、元語言二、符號和符號串三、產(chǎn)生式（規(guī)則）四、文法

五、推導和歸約六、句型和句子七、語言

八、遞歸文法九、短語和簡單短語十、最左推導和最右推導十一、文法二義性

§2.4語法分析初步

一、自頂向下語法分析二、自底向上語法分析

§2.5文法和語言分類

一、文法分類二、文法和自動機三、壓縮過文法

§2.6文法其他表示法

一、擴充巴科斯范式二、語法圖

3第3頁，課件共143頁，創(chuàng)作于2023年2月第二章形式語言基礎知識§2.1引言

一、形式語言提出

二、語言描述方法

4第4頁，課件共143頁，創(chuàng)作于2023年2月第二章形式語言基礎知識§2.1引言

一、形式語言提出

二、語言描述方法

5第5頁，課件共143頁，創(chuàng)作于2023年2月§2.1引言

一、形式語言提出

形式語言是研究符號的語言，它僅考慮符號間的關系，不考慮含義即用數(shù)學方法（主要是代數(shù)方法）對語言進行形式化描述。一開始，我們介紹了什么是語言，那是非形式描述，是人們交流思想的工具，從語言學本身來說也是一門古老的科學，但是在很早以前人們就用數(shù)學方法開始對語言學進行研究。

1847年，俄國數(shù)學家布拉庫夫斯基就用概率論進行語法詞源及語言歷史比較研究。

1904年，波蘭語言學家指出，語言學家不僅要掌握初等數(shù)學而且還要掌握高等數(shù)學。

1931年，俄國數(shù)學家就用概率論研究俄語元音字母和輔音字母序列。特別是1946年電子計算機問世以來更加促使數(shù)學和語言學結合研究。6第6頁，課件共143頁，創(chuàng)作于2023年2月

1956年N.Chomsky(喬姆斯基）在研究自然語言過程中提出一種文法數(shù)學模型，為形式語言理論打下了基礎。7第7頁，課件共143頁，創(chuàng)作于2023年2月數(shù)學家Kleene（克林）在研究神經(jīng)細胞時建立了自動機模型，使用該模型來識別一個語言。

控制部件輸入文件存儲輸出8第8頁，課件共143頁，創(chuàng)作于2023年2月喬姆斯基1959將形式語言的研究成果和自動機的研究成果結合形式語言與自動機理論正式誕生，成為計算機科學理論一個重要分支，迅速在計算機科學技術領域的得到了應用。9第9頁，課件共143頁，創(chuàng)作于2023年2月

形式語言理論研究的對象不僅是自然語言，也有人工語言（包括計算機編程的高級語言）。喬姆斯基的形式語言理論得到了多重驗證，于是才為語言學界和計算機科學界所折服，

“引發(fā)了語言學中的伽利略式的科學革命的開端”10第10頁，課件共143頁，創(chuàng)作于2023年2月第二章形式語言基礎知識§2.1引言

一、形式語言提出

二、語言描述方法

11第11頁，課件共143頁，創(chuàng)作于2023年2月§2.1引言

二、語言描述方法無論是自然語言或者是程序設計語言，都是由許多句子組成，當然這些句子是由本語言字母表上符號并按照一定規(guī)則組成的符號串。對一個語言的描述，就是如何刻畫一個語言中哪些句子是屬于該語言的句子，哪些句子是不屬于該語言的句子。我們可以用三種方法來描述語言，枚舉法、文法生成法和自動機識別法。

1.枚舉法：如果一個語言僅含有有限個句子，就可以采用枚舉法來描述此語言，即把語言中全部句子一一列舉出來即可。然而，絕大多數(shù)重要語言都有無窮多個語句，因此枚舉法顯然失效。

12第12頁，課件共143頁，創(chuàng)作于2023年2月

2.文法生成法：就是用有限個規(guī)則來產(chǎn)生出語言中無限個句子，這種規(guī)則集合稱文法。

3.自動機識別法：用自動機對語言中的句子進行識別，自動機是描述離散變量的一個系統(tǒng)（數(shù)學模型），因在形式語言中稱為識別器，也可看成是一個識別程序。不同語言對應不同自動機，對應某個語言的自動機能接受該語言句子，否則不接受。

下面我們著重討論用文法生成法來描述語言。13第13頁，課件共143頁，創(chuàng)作于2023年2月第二章形式語言基礎知識§2.1引言一、形式語言提出二、語言描述方法§2.2用文法生成法對語言進行描述一、巴科斯范式二、語法和語義三、語法樹§2.3形式語言基本概念和術語一、元語言二、符號和符號串三、產(chǎn)生式（規(guī)則）四、文法

五、推導和歸約六、句型和句子七、語言

八、遞歸文法九、短語和簡單短語十、最左推導和最右推導十一、文法二義性

§2.4語法分析初步

一、自頂向下語法分析二、自底向上語法分析

§2.5文法和語言分類

一、文法分類二、文法和自動機三、壓縮過文法

§2.6文法其他表示法

一、擴充巴科斯范式二、語法圖

14第14頁，課件共143頁，創(chuàng)作于2023年2月第二章形式語言基礎知識§2.2用文法生成法對語言進行描述

一、巴科斯范式二、語法和語義

1.語法

2.語義三、語法樹

15第15頁，課件共143頁，創(chuàng)作于2023年2月第二章形式語言基礎知識§2.2用文法生成法對語言進行描述

一、巴科斯范式二、語法和語義

1.語法

2.語義三、語法樹

16第16頁，課件共143頁，創(chuàng)作于2023年2月§2.2用文法生成法對語言進行描述

一、巴科斯范式

巴科斯范式BNF--BackusNormalFormThebigelephantatethepeanut.(大象吃花生）

Thelittleboyranquickly.(小男孩跑得快）

Themanhasapig.(這人有一只豬）以上都是符合英語語法規(guī)則的句子，即它們是在英語語法規(guī)則中成立的句子。如何描述一個給定的句子在給定規(guī)則下是否成立呢？我們以“∷=”符號(或“→”符號)表示定義為，以“|”符號表示“或”，以“〈〉”符號表示語法實體(語法單位)，這些符號是元語言符號，那么上面敘述<句子>的語法規(guī)則可寫為：17第17頁，課件共143頁，創(chuàng)作于2023年2月①〈句子〉∷=〈主語〉〈謂語〉②〈主語〉∷=<冠詞><形容詞>〈名詞〉③〈冠詞〉∷=the④<形容詞>∷=big⑤〈謂語〉∷=〈動詞〉〈賓語〉⑥〈動詞〉∷=ate⑦〈賓語〉∷=〈冠詞〉〈名詞〉⑧〈名詞〉∷=elephant|peanut我們把這種描述語法規(guī)則方法稱巴科斯范式，也稱巴科斯--瑙爾范式(BackusNormalForm)，簡稱BNF。根據(jù)以上規(guī)則，可以推導出句子Thebigelephantatethepeanut.過程如下：18第18頁，課件共143頁，創(chuàng)作于2023年2月步驟推導所用規(guī)則1<句子><主語>〈謂語〉①2<冠詞>〈形容詞〉〈名詞〉〈謂語〉②3the〈形容詞〉〈名詞〉〈謂語〉③4thebig〈名詞〉〈謂語〉④5thebigelephant〈謂語〉⑧6thebigelephant〈動詞〉<賓語>⑤7thebigelephantate<賓語>⑥8thebigelephantate〈冠詞〉<名詞>⑦9thebigelephantatethe<名詞>③10thebigelephantatethepeanut⑧可見句子thebigelephantatethepeanut成立。當然我們還可以推導出其它的句子，如thebigpeanutatetheelephant，在這里，我們只考慮句子的語法，而不考慮句子的語義。19第19頁，課件共143頁，創(chuàng)作于2023年2月巴科斯范式是描述語法規(guī)則一種表示方法,它是由巴科斯為了在ALGOL60報告中來描述ALGOL語言首先提出的。采用這種形式體系方式定義語法規(guī)則,可以用簡潔的公式把各種語法規(guī)則嚴格而清晰描述出來。例如,在高級語言中大家所熟知的〈標識符〉這種語法成分,它用巴科斯范式描述為:〈標識符〉∷=〈字母〉|〈標識符〉〈字母〉|〈標識符〉〈數(shù)字〉而〈字母〉∷=A|B|C|D|…|Z〈數(shù)字〉∷=0|1|2|…|9

這樣便刻畫出了〈標識符〉是以字母開始的一串字母和數(shù)字任意組合這種特點。20第20頁，課件共143頁，創(chuàng)作于2023年2月用巴科斯范式描述語言能給研究問題帶來很大方便。如下面9個句子都是正確的：①Weran②Heran③Iran④Weate⑤Heate⑥Iate⑦Wesat⑧Hesat⑨Isat如果我們用巴科斯范式來描述上面9個句子只要幾條規(guī)則就行了。①〈句子〉∷=〈主語〉〈謂語〉②〈主語〉∷=We|He|I③〈謂語〉∷=ran|ate|sat可見，如果一個語言有無窮多個句子，那么用上述規(guī)則來描述更有實際意義.它用一組規(guī)則來代替枚舉法，用有窮來描述無限。21第21頁，課件共143頁，創(chuàng)作于2023年2月第二章形式語言基礎知識§2.2用文法生成法對語言進行描述

一、巴科斯范式二、語法和語義

1.語法

2.語義三、語法樹

22第22頁，課件共143頁，創(chuàng)作于2023年2月第二章形式語言基礎知識§2.2用文法生成法對語言進行描述

一、巴科斯范式二、語法和語義

1.語法

2.語義三、語法樹

23第23頁，課件共143頁，創(chuàng)作于2023年2月§2.2用文法生成法對語言進行描述二、語法和語義

1.語法

用類似巴科斯范式來描述某種語言，稱為該語言的語法（也稱文法）。

實際上語法是在字母表上構造句子的一組規(guī)則。對于自然語言就是造句的規(guī)則；對于程序設計語言就是書寫程序規(guī)則。24第24頁，課件共143頁，創(chuàng)作于2023年2月第二章形式語言基礎知識§2.2用文法生成法對語言進行描述

一、巴科斯范式二、語法和語義

1.語法

2.語義三、語法樹

25第25頁，課件共143頁，創(chuàng)作于2023年2月§2.2用文法生成法對語言進行描述

二、語法和語義

2.語義

語義是按照語法規(guī)則所構成結構的含義。對于自然語言，語義是所要表達的意思；對于程序設計語言，語義是一個程序所要完成工作，或者某個語法成分的含義。顯然，一個句子語法上正確不等于語義上也是正確的。例如，“人吃石頭”在語法上是正確，在語義上是荒謬的。在PASCAL語言中，標識符以字母開頭是語法，而標識符使用必須加以說明則是語義。對于語法目前研究比較成熟，可以進行形式描述，但對語義的描述還沒能形式化，還得借助于自然語言。

26第26頁，課件共143頁，創(chuàng)作于2023年2月編譯程序如何將源程序變成目標程序？第一：就是語法分析，看源程序是否符合該語言的語法關系第二：就是語義分析，根據(jù)該語言語義生成目標代碼這是兩個核心問題。27第27頁，課件共143頁，創(chuàng)作于2023年2月第二章形式語言基礎知識§2.2用文法生成法對語言進行描述

一、巴科斯范式二、語法和語義

1.語法

2.語義三、語法樹

28第28頁，課件共143頁，創(chuàng)作于2023年2月§2.2用文法生成法對語言進行描述

三、語法樹

除了上面可以根據(jù)語言語法規(guī)則來推導出句子，還可以用圖解形式來表示。以圖解（樹）形式來描述句子語法結構關系，稱語法樹。

29第29頁，課件共143頁，創(chuàng)作于2023年2月

句子themanhasabook

①〈句子〉∷=〈主語〉〈謂語〉②〈主語〉∷=<冠詞><形容詞>〈名詞〉③〈冠詞〉∷=the④<形容詞>∷=big⑤〈謂語〉∷=〈動詞〉〈賓語〉⑥〈動詞〉∷=ate⑦〈賓語〉∷=〈冠詞〉〈名詞〉⑧〈名詞〉∷=elephant|peanut30第30頁，課件共143頁，創(chuàng)作于2023年2月

句子themanhasabook

①〈句子〉∷=〈主語〉〈謂語〉②〈主語〉∷=<冠詞><形容詞>〈名詞〉|

<冠詞>〈名詞〉③〈冠詞〉∷=the|a④<形容詞>∷=big⑤〈謂語〉∷=〈動詞〉〈賓語〉⑥〈動詞〉∷=ate|has⑦〈賓語〉∷=〈冠詞〉〈名詞〉⑧〈名詞〉∷=elephant|peanut|man|book31第31頁，課件共143頁，創(chuàng)作于2023年2月

句子themanhasabook

的推導過程及對應的語法樹<句子>32第32頁，課件共143頁，創(chuàng)作于2023年2月三、語法樹除了上面可以根據(jù)語言語法規(guī)則來推導出句子，還可以用圖解形式來表示。以圖解（樹）形式來描述句子語法結構關系，稱語法樹。

（句子themanhasabook的推導過程及對應的語法樹）<句子><主語><謂語>33第33頁，課件共143頁，創(chuàng)作于2023年2月三、語法樹除了上面可以根據(jù)語言語法規(guī)則來推導出句子，還可以用圖解形式來表示。以圖解（樹）形式來描述句子語法結構關系，稱語法樹。

（句子themanhasabook的推導過程及對應的語法樹）<句子><主語><謂語><名詞><冠詞>34第34頁，課件共143頁，創(chuàng)作于2023年2月三、語法樹除了上面可以根據(jù)語言語法規(guī)則來推導出句子，還可以用圖解形式來表示。以圖解（樹）形式來描述句子語法結構關系，稱語法樹。

（句子themanhasabook的推導過程及對應的語法樹）<句子><主語><謂語><名詞>the<冠詞>35第35頁，課件共143頁，創(chuàng)作于2023年2月三、語法樹除了上面可以根據(jù)語言語法規(guī)則來推導出句子，還可以用圖解形式來表示。以圖解（樹）形式來描述句子語法結構關系，稱語法樹。

（句子themanhasabook的推導過程及對應的語法樹）<句子><主語><謂語><名詞>manthe<冠詞>36第36頁，課件共143頁，創(chuàng)作于2023年2月三、語法樹除了上面可以根據(jù)語言語法規(guī)則來推導出句子，還可以用圖解形式來表示。以圖解（樹）形式來描述句子語法結構關系，稱語法樹。

（句子themanhasabook的推導過程及對應的語法樹）<句子><主語><謂語><名詞><動詞><賓語>manthe<冠詞>37第37頁，課件共143頁，創(chuàng)作于2023年2月三、語法樹除了上面可以根據(jù)語言語法規(guī)則來推導出句子，還可以用圖解形式來表示。以圖解（樹）形式來描述句子語法結構關系，稱語法樹。

（句子themanhasabook的推導過程及對應的語法樹）<句子><主語><謂語><名詞><動詞><賓語>manhasthe<冠詞>38第38頁，課件共143頁，創(chuàng)作于2023年2月三、語法樹除了上面可以根據(jù)語言語法規(guī)則來推導出句子，還可以用圖解形式來表示。以圖解（樹）形式來描述句子語法結構關系，稱語法樹。

（句子themanhasabook的推導過程及對應的語法樹）<句子><主語><謂語><名詞><動詞><賓語>manhas<名詞><冠詞>the<冠詞>39第39頁，課件共143頁，創(chuàng)作于2023年2月三、語法樹除了上面可以根據(jù)語言語法規(guī)則來推導出句子，還可以用圖解形式來表示。以圖解（樹）形式來描述句子語法結構關系，稱語法樹。

（句子themanhasabook的推導過程及對應的語法樹）<句子><主語><謂語>the<名詞><動詞><賓語>manhas<名詞><冠詞>a<冠詞>40第40頁，課件共143頁，創(chuàng)作于2023年2月三、語法樹除了上面可以根據(jù)語言語法規(guī)則來推導出句子，還可以用圖解形式來表示。以圖解（樹）形式來描述句子語法結構關系，稱語法樹。

（句子themanhasabook的推導過程及對應的語法樹）<句子><主語><謂語><名詞><動詞><賓語>manhas<名詞><冠詞>abookthe<冠詞>其中：<句子>稱為語法樹根帶<>和不帶<>的都稱為語法樹的結點一個結點以及向下射出部分稱為子樹沒有向下射出部分的結點稱為末端結點41第41頁，課件共143頁，創(chuàng)作于2023年2月第二章形式語言基礎知識§2.1引言一、形式語言提出二、語言描述方法§2.2用文法生成法對語言進行描述一、巴科斯范式二、語法和語義三、語法樹§2.3形式語言基本概念和術語一、元語言二、符號和符號串三、產(chǎn)生式（規(guī)則）四、文法

五、推導和歸約六、句型和句子七、語言

八、遞歸文法九、短語和簡單短語十、最左推導和最右推導十一、文法二義性

§2.4語法分析初步

一、自頂向下語法分析二、自底向上語法分析

§2.5文法和語言分類

一、文法分類二、文法和自動機三、壓縮過文法

§2.6文法其他表示法

一、擴充巴科斯范式二、語法圖

42第42頁，課件共143頁，創(chuàng)作于2023年2月第二章形式語言基礎知識§2.3形式語言基本概念和術語

一、元語言

1.元語言

2.元語言變量

二、符號和符號串

1.字母表

2.符號串

3.行集合

4.關于行集合V*上幾種運算

三、產(chǎn)生式（規(guī)則）

1.定義

2.字匯表

四、文法

五、推導和歸約

六、句型和句子七、語言八、遞歸文法

1.定義

2.說明

九、短語和簡單短語

1.短語和簡單短語

2.柄短

3.再談語法樹

十、最左推導和最右推導

十一、文法二義性

1.定義

2.文法二義性消除

3.幾點說明43第43頁，課件共143頁，創(chuàng)作于2023年2月第二章形式語言基礎知識§2.3形式語言基本概念和術語

一、元語言

1.元語言

2.元語言變量

二、符號和符號串

1.字母表

2.符號串

3.行集合

4.關于行集合V*上幾種運算

三、產(chǎn)生式（規(guī)則）

1.定義

2.字匯表

四、文法五、推導和歸約

六、句型和句子

七、語言八、遞歸文法

1.定義

2.說明

九、短語和簡單短語

1.短語和簡單短語

2.柄短

3.再談語法樹

十、最左推導和最右推導

十一、文法二義性

1.定義

2.文法二義性消除

3.幾點說明44第44頁，課件共143頁，創(chuàng)作于2023年2月第二章形式語言基礎知識§2.3形式語言基本概念和術語

一、元語言

1.元語言

2.元語言變量

二、符號和符號串

1.字母表

2.符號串

3.行集合

4.關于行集合V*上幾種運算

三、產(chǎn)生式（規(guī)則）

1.定義

2.字匯表

四、文法五、推導和歸約

六、句型和句子

七、語言八、遞歸文法

1.定義

2.說明

九、短語和簡單短語

1.短語和簡單短語

2.柄短

3.再談語法樹

十、最左推導和最右推導

十一、文法二義性

1.定義

2.文法二義性消除

3.幾點說明45第45頁，課件共143頁，創(chuàng)作于2023年2月§2.3形式語言基本概念和術語

一、元語言

1.元語言下面給大家介紹一些與編譯有關的形式語言基本概念和術語。用來描述其它語言的語言，稱元語言。而被描述語言稱對象語言。

例如：英語教科中，英語是對象語言，漢語是元語言。元語言與被描述語言可以是相同的，也可以是不同的。

46第46頁，課件共143頁，創(chuàng)作于2023年2月第二章形式語言基礎知識§2.3形式語言基本概念和術語

一、元語言

1.元語言

2.元語言變量

二、符號和符號串

1.字母表

2.符號串

3.行集合

4.關于行集合V*上幾種運算

三、產(chǎn)生式（規(guī)則）

1.定義

2.字匯表

四、文法五、推導和歸約

六、句型和句子

七、語言八、遞歸文法

1.定義

2.說明

九、短語和簡單短語

1.短語和簡單短語

2.柄短語

3.再談語法樹

十、最左推導和最右推導

十一、文法二義性

1.定義

2.文法二義性消除

3.幾點說明47第47頁，課件共143頁，創(chuàng)作于2023年2月§2.3形式語言基本概念和術語

一、元語言

2.元語言變量

元語言的詞匯稱為元語言的變量(或元語言的符號)。例如：在上一節(jié)中描述句子，我們用了<句子><主語><謂語><賓語>等，這些符號的引入完全是為了描述英語句子thebigelephantatethepeanut.而這些引入符號并未出現(xiàn)在句子中，對于這種用尖括號括起來的詞匯就是元語言變量或語法單位。48第48頁，課件共143頁，創(chuàng)作于2023年2月第二章形式語言基礎知識§2.3形式語言基本概念和術語

一、元語言

1.元語言

2.元語言變量

二、符號和符號串

1.字母表

2.符號串

3.行集合

4.關于行集合V*上幾種運算

三、產(chǎn)生式（規(guī)則）

1.定義

2.字匯表

四、文法五、推導和歸約

六、句型和句子

七、語言八、遞歸文法

1.定義

2.說明

九、短語和簡單短語

1.短語和簡單短語

2.柄短語

3.再談語法樹

十、最左推導和最右推導

十一、文法二義性

1.定義

2.文法二義性消除

3.幾點說明49第49頁，課件共143頁，創(chuàng)作于2023年2月第二章形式語言基礎知識§2.3形式語言基本概念和術語

一、元語言

1.元語言

2.元語言變量

二、符號和符號串

1.字母表

2.符號串

3.行集合

4.關于行集合V*上幾種運算

三、產(chǎn)生式（規(guī)則）

1.定義

2.字匯表

四、文法五、推導和歸約

六、句型和句子

七、語言八、遞歸文法

1.定義

2.說明

九、短語和簡單短語

1.短語和簡單短語

2.柄短語

3.再談語法樹

十、最左推導和最右推導

十一、文法二義性

1.定義

2.文法二義性消除

3.幾點說明50第50頁，課件共143頁，創(chuàng)作于2023年2月§2.3形式語言基本概念和術語

二、符號和符號串

1.字母表

有限個元素的非空集合稱字母表，也稱符號集。它是組成一個語言最基本的成分。字母表中元素稱符號。習慣上用V、Σ或其它大寫字母表示。例如V={a,b,c}，V={α,β…ω}等都是字母表。|V|表示字母表中符號的個數(shù)。對于不同程序設計語言有不同字母表。例如，機器語言字母表={0,1}，

PASCAL語言的字母表由字母、數(shù)字以及一些特殊符號，如+，-，*，/，·，(，)，=，…等組成。

注意：在一個語言中不能出現(xiàn)字母表以外的符號。51第51頁，課件共143頁，創(chuàng)作于2023年2月第二章形式語言基礎知識§2.3形式語言基本概念和術語

一、元語言

1.元語言

2.元語言變量

二、符號和符號串

1.字母表

2.符號串

3.行集合

4.關于行集合V*上幾種運算

三、產(chǎn)生式（規(guī)則）

1.定義

2.字匯表

四、文法五、推導和歸約

六、句型和句子

七、語言八、遞歸文法

1.定義

2.說明

九、短語和簡單短語

1.短語和簡單短語

2.柄短語

3.再談語法樹

十、最左推導和最右推導

十一、文法二義性

1.定義

2.文法二義性消除

3.幾點說明52第52頁，課件共143頁，創(chuàng)作于2023年2月§2.3形式語言基本概念和術語

二、符號和符號串

2.符號串

（1）定義

符號串是字母表中的符號所組成的任何有窮序列(有時也稱為符號行或字)

例如：設V={a,b,c},則符號串有

a,b,c,aa,ab,ac,ba,abc…

又如：設V={0,1},則符號串有

0，1，00，01，10，11，000…

由上例可以看出，符號串與符號組成順序有關，如符號串a(chǎn)b不同于ba，符號串01不同于10，今后我們常用t,u,v,…x,y,z等小寫字母表示符號串。

（2）空符號串

不包含任何符號的符號串稱為空符號串，記為ε。

（3）符號串長度

符號串中所含符號個數(shù)稱為該符號串的長度，設符號串為x，則用|x|來表示x的長度。例如：x=abc，則|x|=3,顯然,|ε|=0。53第53頁，課件共143頁，創(chuàng)作于2023年2月§2.3形式語言基本概念和術語

二、符號和符號串關于符號串的幾種運算

（1）符號串的聯(lián)結設有符號串x和y，則它們的聯(lián)結xy是將符號串y直接拼接在符號串x之后，即

x=x1x2x3…xm,y=y1y2y3…yn則

xy

=x1x2x3…xmy1y2y3…yn

顯然εx=x，xε=x

（2）符號串的方冪

設有符號串x,則x的n次聯(lián)結稱為x的n次方冪

則x0=ε，x1=x，x2=xx，x3=xxx，…xn=xx…x(n個）如x=abc則x0=ε,x1=abc,x2=abcabcx3=abcabcabc

54第54頁，課件共143頁，創(chuàng)作于2023年2月§2.3形式語言基本概念和術語

二、符號和符號串關于符號串的幾種運算

（3）符號串的頭、尾、子串

設有符號串x,把x的尾部去掉若干符號（包括0個符號）之后所余下部分稱為x的頭設有符號串x,把x的頭部去掉若干符號（包括0個符號）之后所余下部分稱為x的尾若x的頭（尾）不是x本身，則稱x的真頭（尾）

從一個符號串中刪去一個頭和尾后所余下的部分稱為此符號串的子串，如果刪去的頭和尾不同時為ε，則該子串是真子串。如x=abcx的頭：abc、ab、a、ε55第55頁，課件共143頁，創(chuàng)作于2023年2月第二章形式語言基礎知識§2.3形式語言基本概念和術語

一、元語言

1.元語言

2.元語言變量

二、符號和符號串

1.字母表

2.符號串

3.行集合

4.關于行集合V*上幾種運算

三、產(chǎn)生式（規(guī)則）

1.定義

2.字匯表

四、文法五、推導和歸約

六、句型和句子

七、語言八、遞歸文法

1.定義

2.說明

九、短語和簡單短語

1.短語和簡單短語

2.柄短語

3.再談語法樹

十、最左推導和最右推導

十一、文法二義性

1.定義

2.文法二義性消除

3.幾點說明56第56頁，課件共143頁，創(chuàng)作于2023年2月§2.3形式語言基本概念和術語

二、符號和符號串

3.行集合

符號串集合：若集合A中的一切元素都是字母表上符號串，則稱A為該字母表上的符號串集合。用大寫字母A、B、C……來表示字母表上符號串集合。例如：設V={0，1},則符號串集合

A={ε，0，1，01}B={0，11，00，111}

對于符號串集合不可能窮盡一切元素時，可以用集合中符號串所應滿足的條件來刻畫一個符號串集合，即{x|x滿足條件C}:例如：{x|x全由1組成}57第57頁，課件共143頁，創(chuàng)作于2023年2月§2.3形式語言基本概念和術語

二、符號和符號串

3.行集合

字母表V上各種長度符號串構成行集合，記為V*，不包括空符號串的集合記為V+

即V*={x|x是V上符號串且包括空符號串}V+={x|x是V上符號串且不包括空符號串}V+=V*-{ε}

如：V={a,b}，則

V*={ε,a,b,aa,ab,ba,bb,aaa,…bbb,…}V+={a,b,aa,ab,ba,bb,aaa,…bbb,…}58第58頁，課件共143頁，創(chuàng)作于2023年2月第二章形式語言基礎知識§2.3形式語言基本概念和術語

一、元語言

1.元語言

2.元語言變量

二、符號和符號串

1.字母表

2.符號串

3.行集合

4.關于行集合V*上幾種運算

三、產(chǎn)生式（規(guī)則）

1.定義

2.字匯表

四、文法五、推導和歸約

六、句型和句子

七、語言八、遞歸文法

1.定義

2.說明

九、短語和簡單短語

1.短語和簡單短語

2.柄短

3.再談語法樹

十、最左推導和最右推導

十一、文法二義性

1.定義

2.文法二義性消除

3.幾點說明59第59頁，課件共143頁，創(chuàng)作于2023年2月§2.3形式語言基本概念和術語

二、符號和符號串

4.關于行集合V*上幾種運算

（1）符號串的聯(lián)結設有符號串x和y，則它們的聯(lián)結xy是將符號串y直接拼接在符號串x之后，即

x=x1x2x3…xm,y=y1y2y3…yn則

xy

=x1x2x3…xmy1y2y3…yn

顯然εx=x，xε=x

60第60頁，課件共143頁，創(chuàng)作于2023年2月（2）符號串集合乘積設A和B為兩個符號串集合，并包含于V*，則A和B的乘積定義為

AB={xy|x∈A且y∈B}由此定義，乘積AB是滿足x∈A且y∈B的所有符號串xy所組成的集合。如：V={0，1}V*={ε,0,1,00,01,10,11,000,001，010，011，100,101…}A={0，101}B={10，11，110}則AB={010，011，0110，10110，10111，101110}

61第61頁，課件共143頁，創(chuàng)作于2023年2月符號串是字母表中的符號所組成的任何有窮序列空符號串：εεx=x，xε=x

若集合A中的一切元素都是字母表上符號串，則稱A為該字母表上的符號串集合空集：ΦΦA=AΦ=Φ含有空符號串的集合：{ε}

{ε}A=A{ε}=A

62第62頁，課件共143頁，創(chuàng)作于2023年2月（3）符號串的方冪

設有符號串x∈V*,則x的n次聯(lián)結稱為x的n次方冪

則x0=ε，x1=x，x2=xx，x3=xxx，…xn=xx…x(n個）如x=abc則x0=ε,x1=abc,x2=abcabcx3=abcabcabc（4）符號串集合的方冪設符號串集合AV*則A0={ε},A1=A,A2=AA,A3=AAA,…An=AAA…A(n個）如：設A={a,b}，則A0={ε},A1={a,b}，A2={a,b}{a,b}={aa,ab,ba,bb}A3={aaa,aab,aba,abb,baa,bab,bba,bbb}∩63第63頁，課件共143頁，創(chuàng)作于2023年2月(5)符號串集合的閉包和正閉包

設A為符號串集合，則A的正閉包定義為

A+=A1∪A2∪…∪An∪…

符號串集合A的閉包定義為

A*=A0∪A+={ε}∪A+

如A={a,b}則A+={a,b}∪{aa,ab,ba,bb}∪…={a,b,aa,ab,ba,bb,aaa,…,bbb,…}A*={ε,a,b,aa,ab,ba,bb,aaa,…bbb,…}我們可以證明：A+=AA*=A*AAA*=A（A0∪A1∪A2∪…An∪…

）

=A1∪A2∪…An∪…

=A+64第64頁，課件共143頁，創(chuàng)作于2023年2月第二章形式語言基礎知識§2.3形式語言基本概念和術語

一、元語言

1.元語言

2.元語言變量

二、符號和符號串

1.字母表

2.符號串

3.行集合

4.關于行集合V*上幾種運算

三、產(chǎn)生式（規(guī)則）

1.定義

2.字匯表

四、文法五、推導和歸約

六、句型和句子

七、語言八、遞歸文法

1.定義

2.說明

九、短語和簡單短語

1.短語和簡單短語

2.柄短語

3.再談語法樹

十、最左推導和最右推導

十一、文法二義性

1.定義

2.文法二義性消除

3.幾點說明65第65頁，課件共143頁，創(chuàng)作于2023年2月第二章形式語言基礎知識§2.3形式語言基本概念和術語

一、元語言

1.元語言

2.元語言變量

二、符號和符號串

1.字母表

2.符號串

3.行集合

4.關于行集合V*上幾種運算

三、產(chǎn)生式（規(guī)則）

1.定義

2.字匯表

四、文法五、推導和歸約

六、句型和句子

七、語言八、遞歸文法

1.定義

2.說明

九、短語和簡單短語

1.短語和簡單短語

2.柄短

3.再談語法樹

十、最左推導和最右推導

十一、文法二義性

1.定義

2.文法二義性消除

3.幾點說明66第66頁，課件共143頁，創(chuàng)作于2023年2月§2.3形式語言基本概念和術語三、產(chǎn)生式（規(guī)則）

1.定義

產(chǎn)生式(規(guī)則)就是一個符號與另一個符號串的有序偶

(U,x),通常記為

U→x或U∷=x

其中：U是符號,x是有限非空符號串。U稱為規(guī)則的左部,x

稱為規(guī)則的右部如果U→x1，U→x2，U→x3，…，U→xn

可以寫成U→x1|x2|…|xn,并稱xi是U的一個候選式。67第67頁，課件共143頁，創(chuàng)作于2023年2月第二章形式語言基礎知識§2.3形式語言基本概念和術語

一、元語言

1.元語言

2.元語言變量

二、符號和符號串

1.字母表

2.符號串

3.行集合

4.關于行集合V*上幾種運算

三、產(chǎn)生式（規(guī)則）

1.定義

2.字匯表

四、文法五、推導和歸約

六、句型和句子

七、語言八、遞歸文法

1.定義

2.說明

九、短語和簡單短語

1.短語和簡單短語

2.柄短語

3.再談語法樹

十、最左推導和最右推導

十一、文法二義性

1.定義

2.文法二義性消除

3.幾點說明68第68頁，課件共143頁，創(chuàng)作于2023年2月§2.3形式語言基本概念和術語三、產(chǎn)生式（規(guī)則）

2.字匯表

（1）定義用于規(guī)則左部和右部中所有符號形成集合為字匯表，

記為V。

69第69頁，課件共143頁，創(chuàng)作于2023年2月又如：在PASCAL中，對標識符的定義規(guī)則為：〈標識符〉∷=<字母>|<標識符><字母>|<標識符><數(shù)字>〈字母〉∷=a|b|…|z〈數(shù)字〉∷=0|1|…|9（2）分類

1）非終結符號

出現(xiàn)在規(guī)則左部,且能派生出符號或符號串的那些符號稱為非終結符,也稱語法實體或語法單位,它們的全體構成一個非終結符的集合,記為VN2）終結符

規(guī)則中不屬于VN的那些符號,稱為終結符,它們的全體組成終結符的集合,記為VT

。終結符一般出現(xiàn)在規(guī)則的右部。顯然,V=VN∪VT,VN∩VT=?由此得：VN={〈字母〉,〈數(shù)字〉,〈標識符〉}VT={a,b,…,z,0,1,…9}70第70頁，課件共143頁，創(chuàng)作于2023年2月例如：有產(chǎn)生式:S∷=0S1S∷=01

則VN={}VT={}V={}例如：有產(chǎn)生式:S∷=0S1S∷=01

則VN={S}VT={0,1}V={S,0,1}71第71頁，課件共143頁，創(chuàng)作于2023年2月第二章形式語言基礎知識§2.3形式語言基本概念和術語

一、元語言

1.元語言

2.元語言變量

二、符號和符號串

1.字母表

2.符號串

3.行集合

4.關于行集合V*上幾種運算

三、產(chǎn)生式（規(guī)則）

1.定義

2.字匯表

四、文法五、推導和歸約

六、句型和句子

七、語言八、遞歸文法

1.定義

2.說明

九、短語和簡單短語

1.短語和簡單短語

2.柄短

3.再談語法樹

十、最左推導和最右推導

十一、文法二義性

1.定義

2.文法二義性消除

3.幾點說明72第72頁，課件共143頁，創(chuàng)作于2023年2月§2.3形式語言基本概念和術語

四、文法為研究方便，下面給出文法的形式定義定義：文法是規(guī)則的有窮集合,形式定義為四元組形式為

G=(VN,VT,P,Z)其中：VN是非終結符集合,

VT是終結符集合,

P代表產(chǎn)生式集,

Z∈VN是文法G開始符號,也稱識別符號,它至少要在一條產(chǎn)生式左部出現(xiàn)。文法G通常記為G［Z］。73第73頁，課件共143頁，創(chuàng)作于2023年2月§2.3形式語言基本概念和術語

四、文法對于前面例子中用8條文法規(guī)則來描述英語句子,其文法可表示為

G=(VN,VT,P,〈句子〉)其中:VN={<句子>，<主語>，<謂語>，<賓語>，<冠詞>，<動詞>，<形容詞>,<名詞>}VT={the,big,elephant,peanut,ate}P是前述8條規(guī)則Z=〈句子〉①〈句子〉∷=〈主語〉〈謂語〉②〈主語〉∷=<冠詞><形容詞>〈名詞〉③〈冠詞〉∷=the④<形容詞>∷=big⑤〈謂語〉∷=〈動詞〉〈賓語〉⑥〈動詞〉∷=ate⑦〈賓語〉∷=〈冠詞〉〈名詞〉⑧〈名詞〉∷=elephant|peanut74第74頁，課件共143頁，創(chuàng)作于2023年2月又例如：標識符文法可定義如下:G［Z］=(VN,VT,P,Z)VN={〈字母〉,〈數(shù)字〉,〈標識符〉}VT={a,b,…,z,0,1,…9}P由下列規(guī)則組成:〈標識符〉∷=<字母>|<標識符><字母>|<標識符><數(shù)字>〈字母〉∷=a|b|…|z〈數(shù)字〉∷=0|1|…|9Z=〈標識符〉75第75頁，課件共143頁，創(chuàng)作于2023年2月第二章形式語言基礎知識§2.3形式語言基本概念和術語

一、元語言

1.元語言

2.元語言變量

二、符號和符號串

1.字母表

2.符號串

3.行集合

4.關于行集合V*上幾種運算

三、產(chǎn)生式（規(guī)則）

1.定義

2.字匯表

四、文法

五、推導和歸約

六、句型和句子

七、語言八、遞歸文法

1.定義

2.說明

九、短語和簡單短語

1.短語和簡單短語

2.柄短

3.再談語法樹

十、最左推導和最右推導

十一、文法二義性

1.定義

2.文法二義性消除

3.幾點說明76第76頁，課件共143頁，創(chuàng)作于2023年2月§2.3形式語言基本概念和術語

五、推導和歸約定義1

設G為一個文法，U∷=u是G中一個規(guī)則，x和y是V*上符號串，使得

v=xUy與w=xuy則稱符號串v直接推導出符號串w，或稱w直接歸約到v，并把w叫做v直接派生式，記作vw

注意三點：1）v，w是兩個不同符號串

2）有一規(guī)則U∷=u3）直接推導vw

若x=y=ε，則v=xUy=U，w=xuy=u

可見vw即Uu說明一個規(guī)則就是一個直接推導例如〈句子〉直接推導到<主語><謂語>，而<主語><謂語>直接歸約到<句子>。

77第77頁，課件共143頁，創(chuàng)作于2023年2月例如:

G=(VN,VT,P,Z)VN={S},VT={0,1}P:S∷=0S1S∷=01Z=S

令v=xSy,w=x01y,因S

∷=01(U∷=u)

即vwxSyx01y

若x=y=ε則S01(一個規(guī)則就是一個直接推導)同樣S

∷=0S1

v=00S11，w=000S111Uu

即vw00S11

000S11178第78頁，課件共143頁，創(chuàng)作于2023年2月又如：標識符文法定義如下:G［Z］=(VN,VT,P,Z)VN={〈字母〉,〈數(shù)字〉,〈標識符〉}VT={a,b,…,z,0,1,…9}P由下列規(guī)則組成:

〈標識符〉∷=<字母>|<標識符><字母>|<標識符><數(shù)字>

〈字母〉∷=a|b|…|z〈數(shù)字〉∷=0|1|…|9Z=〈標識符〉則有：〈標識符〉<標識符><字母>

<標識符>a

從v出發(fā)應用規(guī)則U∷=u,把v=xUy中U替換為右部u,即v直接推導到w,這時長度可能增加,至少不會縮小:|w|≥|v|。從w出發(fā)應用規(guī)則U∷=u,把w=xuy中u替換為左部U,即w直接歸約為v,這時長度可能縮小,至少不會變長:|v|≤|w|。

79第79頁，課件共143頁，創(chuàng)作于2023年2月定義2

設u0,u1,u2,…,un均為V*上符號串,若w是v經(jīng)過一系列直接推導得到的,即

v=u0

u1

u2

…

un-1

un=w(n>0)則稱v推導到w,或稱w歸約到v,記作

v+w稱這個直接推導序列為長度為n的推導。如果v+w或者v=w(表示0步推導),則記作

v*w稱v廣義推導到w或稱w廣義歸約到v。

顯然,直接推導的長度為1,推導

+的長度≥1,而廣義推導

*的長度≥0例如在前面的例子中,因S∷=0S1

S∷=01

0S100S11000S11100001111所以0S1+00001111(n=3)80第80頁，課件共143頁，創(chuàng)作于2023年2月例2.16設有文法G［〈整數(shù)〉］:(1)<整數(shù)>∷=<數(shù)字串>(2)<數(shù)字串>∷=<數(shù)字串><數(shù)字>(3)<數(shù)字串>∷=<數(shù)字>(4)<數(shù)字>∷=0(5)<數(shù)字>∷=1(6)<數(shù)字>∷=2(7)<數(shù)字>∷=3(8)<數(shù)字>∷=4(9)<數(shù)字>∷=5(10)<數(shù)字>∷=6(11)<數(shù)字>∷=7(12)<數(shù)字>∷=8(13)<數(shù)字>∷=9VwXUyxuyε〈整數(shù)〉εε〈數(shù)字串〉ε規(guī)則1ε<數(shù)字串>εε<數(shù)字串><數(shù)字>ε規(guī)則2ε<數(shù)字串><數(shù)字>ε〈數(shù)字〉〈數(shù)字〉規(guī)則3ε〈數(shù)字〉〈數(shù)字〉ε2〈數(shù)字〉規(guī)則62〈數(shù)字〉ε23ε規(guī)則7由此建立下列推導:<整數(shù)><數(shù)字串><數(shù)字串><數(shù)字><數(shù)字><數(shù)字>2<數(shù)字>23因此,<整數(shù)>+23,其推導長度為5。顯而易見,在推導時,任意地選取規(guī)則(4)到(13),就可以推導得到任意整數(shù)。81第81頁，課件共143頁，創(chuàng)作于2023年2月第二章形式語言基礎知識§2.3形式語言基本概念和術語

一、元語言

1.元語言

2.元語言變量

二、符號和符號串

1.字母表

2.符號串

3.行集合

4.關于行集合V*上幾種運算

三、產(chǎn)生式（規(guī)則）

1.定義

2.字匯表

四、文法五、推導和歸約

六、句型和句子

七、語言八、遞歸文法

1.定義

2.說明

九、短語和簡單短語

1.短語和簡單短語

2.柄短語

3.再談語法樹

十、最左推導和最右推導

十一、文法二義性

1.定義

2.文法二義性消除

3.幾點說明82第82頁，課件共143頁，創(chuàng)作于2023年2月§2.3形式語言基本概念和術語

六、句型和句子在上述推導過程中產(chǎn)生了一系列的符號串，它們或全由終結符組成（如：23），或全由非終結符組成（如：<數(shù)字串>，<數(shù)字串><數(shù)字>，<數(shù)字><數(shù)字>），或由終結符和非終結符混合組成（如：2<數(shù)字>）。為了區(qū)別這些組成不同的符號串，我們引入句型和句子兩個概念。定義：設G［Z］是一文法,若符號串x是由識別符Z推導而得,即

Z*xx∈V*則稱符號串x為該文法G的一個句型。如果一個句型x僅由終結符組成,即

Z*xx∈VT*則稱句型x為該文法一個句子。例如在例2.16中,〈整數(shù)〉,〈數(shù)字〉〈數(shù)字〉,2〈數(shù)字〉,23等都是文法G[<整數(shù)>]的句型，其中僅23是句子。

可見：句子一定是句型，而句型未必是句子。一個正確的源程序是句子。83第83頁，課件共143頁，創(chuàng)作于2023年2月第二章形式語言基礎知識§2.3形式語言基本概念和術語

一、元語言

1.元語言

2.元語言變量

二、符號和符號串

1.字母表

2.符號串

3.行集合

4.關于行集合V*上幾種運算

三、產(chǎn)生式（規(guī)則）

1.定義

2.字匯表

四、文法五、推導和歸約

六、句型和句子

七、語言八、遞歸文法

1.定義

2.說明

九、短語和簡單短語

1.短語和簡單短語

2.柄短語

3.再談語法樹

十、最左推導和最右推導

十一、文法二義性

1.定義

2.文法二義性消除

3.幾點說明84第84頁，課件共143頁，創(chuàng)作于2023年2月§2.3形式語言基本概念和術語

七、語言設G［Z］為一文法,由該文法所產(chǎn)生的一切