4.文法和語言總結與梳理

• 2019 年 10 月 3 日
• 筆記

1. 梳理第二章的內容，寫一篇理解與總結。

       第二章 文法和語言

  1.文法:闡明語法的一個工具,也可以說是以有窮的集合刻畫無窮的集合的一個工具。

   語言:程式設計語言。

  2.符號、字母表和符號串

  基本符號:可以相互區別的基本元素,如字母,數字,標點符號。

  字母表:基本符號的非空有窮集合,常用Z表示。例: 2={0,1), Z-{a, b, c, ..., xy, z}

  符號串:由字母表中的符號構成的任何有窮序列稱為符號串。符號串中的符號是有順序的。

  3.產生式

  生成方式(文法) :語言中的每個句子可以用嚴格定義的規則來構造。

  4.推導

  用文法定義語言的中心思想是:從文法的開始符號出發,反覆使用合適規則,對非終結符施行替換和展開。

  最左(最右)推導:在推導的任何一步a=>b，其中a、b是句型,都是對a中的最左(右)非終結符進行替換，最右推導被稱為規範推導。

  5.文法類型

 （1）0型文法：無限制文法、短語文法，α->β，α中至少含一個非終結符。

 （2）1型文法（CSG）：上下文有關文法，α->β滿足|α|<=|β|，對於產生式α1Aα2->α1βα2，用β替換A時，只能在上下文為α1和α2時才能進行。這裡的|β|表示的是β的長度。同理|α|表示的是α的長度。

注意：雖然要求|β|>=|α|，但有一特例：α→ε也滿足1型文法。

 （3）2型文法（CFG）：上下文無關文法，A->β，其中左邊必須有且僅有一個非終結符，當用β替換A時，與A的上下文環境無關。

如Ab->Bab雖然符合1型文法要求,但不符合2型文法要求，因為其α=Ab，而Ab不是一個非終結符。

 （4）3型文法（RG）：也稱為正則文法。它應該滿足以下條件①左邊必須只有一個字元，且必須是非終結符。②右邊最多只能有兩個字元，且當只有兩個字元時必須是一個為終結符而另一個為非終極符；當右邊只有一個字元時，此字元必須為終結符。

   上下文無關文法的句型推導直觀工具：推導樹--語法樹。

  6.句型分析

  句型分析就是識別一個符號串是否為某文法的句型,是某個推導的構造過程。

  分析演算法可分為:自上而下分析法：從文法的開始符號出發,反覆使用文法的產生式，尋找與輸入符號串匹配的推導。自下而上分析法：從輸入符號串開始,逐步進行歸約，直至歸約到文法的開始符號。兩種方法反映了兩種不同的語法樹的構造過程。

  語法樹子樹分析法:

  短語:任意一顆子樹的葉子結點從左至右順序排列的字元串(按給定句型排除) 。

  直接短語:只有父子兩層的子樹的葉子結點從左至右順序排列的字元串。

  句柄:最左最下的只有父子兩層的子樹的葉子結點從左至右順手排列的字元串。

  文法的二義性和語言的二義性：

　若一個文法存在某個句子對應兩棵不同的語法樹，則稱這個文法是二義的或者，若一個文法存在某個句子有兩個不同的最左（右）推導，則稱這個文法是二義的判定任給的一個上下文無關文法是否二義，或它是否產生一個先天二義的上下文無關語言，這兩個問題是遞歸不可解的，但可以為無二義性尋找一組充分條件文法的二義性和語言的二義性是不同的概念。

  通過這個月老師的授課，還有做練習和作業學習了編譯原理的文法與語言，學習的概念：文法，推導，直接推導,最左(右)推導,產生式,句型,短語,直接短語,句柄語法樹,規範推導,二義文法等 。熟悉4種文法的定義、文法的構造和文法的推導。掌握語法樹的構造和最左(右)推導;熟悉二義文法、二義性的證明;掌握句型分析

2. 嘗試寫出PL/0 語言的文法。（或者你認為比較好的語言規則）

整數n  n :: =0| 1 | 2 | ..... | 9 

標識符i   i :: =a|b|c|……|y|z|A|B|C|……|Y|Z （<字母> | {<字母> | <數字 >}）

表達式e  e::= [+|-] <項> { <加減運算符> <項> }

條件語句  ::= if<條件>then<語句>

賦值語句  ::= <標識符id> := <表達式>

複合語句  ::= begin <語句> {;<語句>} end

函數  ::= <類型說明><函數名><複合語句>

程式  ::= [<常量說明部分>] [<變數說明部分>] [<過程說明部分>] <語句>

...