編譯原理2

1. (編譯原理) 求下述文法對應正規式： S->0A|1B A->1S|1 B->0S|0

一、簡單的推導思路
1、該文法的對應正規式為：[01|10]+
2、推導：
（1）首先，展開產生式S，可知S要麼以0開頭，要麼以1開頭；
（2）如果S按產生式S->0A展開，則S必以01開頭，因為通過產生式A->1S|1可知，A必定是以1開頭的；
（3）如果S按產生式S->1B展開，則S必以10開頭，因為產生式B必定以0開頭；
（4）綜上，可知，S是以01或10開頭的非終結符號；
（5）當A以產生式A->1展開或 B以B->0展開時，S將推導結束；
（6）當A以產生式A->1S展開或 B以B->0S展開時，產生式中的非終結符號S將重復（1）-（3）的推導步驟；
（7）綜上所述，該文法的對應正規式為：[01|10]+。

二、聯立方程組求解
假設非終結符號S、A、B都分別代表一個正規式，則正規文法的產生式集合所代表的就是關於正規式S、A、B的一個方程組。
我們將文法「|」符號替換為正規式「+」符號，可得，
S=0A+1B=0(1S+1)+1(0S+0)=01(S+ε)+10(S+ε)=(01+10)(S+ε)=(01+10)S+(01+10)。
根據方程X=rX+t有形如X=r*t的解論斷，可得，
S=(01+10)*(01+10)=[01|10]+。

2. 編譯原理中，形式語言里怎麼區分2型文法與3型文法

二型文法如下:
S->Ac
S->Sc
A->ab
A->aAb
三型文法如下:
S->aS
A->bA
B->cB
B->c
A->Bb
A、2型文法是上下文無關文法，表現在產生式上就是產生式的左部只有一個非終結符；3型文法從廣義上講包括左線形文法、右線形文法和正規文法 。
B、左線形文法產生式的右部要麼沒有非終結符，如果有非終結符也只能有一個，且必須位於產生式右部的最左端。
C、右線形文法產生式的右部要麼沒有非終結符，如果有非終結符也只能有一個，且必須位於產生式右部的最右端 。
D、正規文法是右線形文法的一個子集，其產生式右部只有三種情況：
1）空串
2）只有一個終結符
3）只有一個終結符後接一個非終結符
E、所有的3型文法都是2型文法。

3. 【編譯原理】第二章：語言和文法

上述文法 表示，該文法由終結符集合 ，非終結符集合 ，產生式集合 ，以及開始符號 構成。
而產生式 表示，一個表達式（Expression） ，可以由一個標識符（Identifier） 、或者兩個表達式由加號 或乘號 連接、或者另一個表達式用括弧包裹（ ）構成。

約定 ：在不引起歧義的情況下，可以只寫產生式。如以上文法可以簡寫為：

產生式

可以簡寫為：

如上例中，

可以簡寫為：

給定文法 ，如果有 ，那麼可以將符號串 重寫 為 ，記作 ，這個過程稱為 推導 。
如上例中， 可以推導出 或 或 等等。

如果 ，
可以記作 ，則稱為 經過n步推導出 ，記作 。

推導的反過程稱為 歸約 。

如果 ，則稱 是 的一個 句型（sentential form ）。

由文法 的開始符號 推導出的所有句子構成的集合稱為 文法G生成的語言 ，記作 。
即：

例
文法

表示什麼呢？
代表小寫字母；
代表數字；
表示若干個字母和數字構成的字元串；
說明 是一個字母、或者是字母開頭的字元串。
那麼這個文法表示的即是，以字母開頭的、非空的字元串，即標識符的構成方式。

並、連接、冪、克林閉包、正閉包。
如上例表示為：

中必須包含一個 非終結符 。

產生式一般形式：
即上式中只有當上下文滿足 與 時，才能進行從 到 的推導。

上下文有關文法不包含空產生式（ ）。

產生式的一般形式：
即產生式左邊都是非終結符。

右線性文法 ：
左線性文法 ：
以上都成為正則文法。
即產生式的右側只能有一個終結符，且所有終結符只能在同一側。

例：（右線性文法）

以上文法滿足右線性文法。
以上文法生成一個以字母開頭的字母數字串（標識符）。
以上文法等價於 上下文無關文法 ：

正則文法能描述程序設計語言中的多數單詞。

正則文法能描述程序設計語言中的多數單詞，但不能表示句子構造，所以用到最多的是CFG。

根節點 表示文法開始符號S；
內部節點 表示對產生式 的應用；該節點的標號是產生式左部，子節點從左到右表示了產生式的右部；
葉節點 （又稱邊緣）既可以是非終結符也可以是終結符。

給定一個句型，其分析樹的每一棵子樹的邊緣稱為該句型的一個 短語 。
如果子樹高度為2，那麼這棵子樹的邊緣稱為該句型的一個 直接短語 。

直接短語一定是某產生式的右部，但反之不一定。

如果一個文法可以為某個句子生成 多棵分析樹 ，則稱這個文法是 二義性的 。

二義性原因：多個if只有一個else；
消岐規則：每個else只與最近的if匹配。

4. 璁＄畻鏈虹戝︿笡涔β風紪璇戝師鐞嗗唴瀹圭畝浠

璁＄畻鏈虹戝﹂嗗煙鏈変竴鏈澶囧彈鎺ㄥ磭鐨勮憲浣溾斺斻婄紪璇戝師鐞(鏈縐戞暀瀛︾増絎2鐗)銆嬨傝繖鏈涔︾粡榪囩簿蹇冩敼緙栵紝鐩歌緝浜庣涓鐗堬紝鍐呭規洿鍔犵簿鐐間笖瀹炵敤鎬ф洿寮猴紝瀹冩洿鍔犺創鍚堟垜鍥介珮鏍¤＄畻鏈轟笓涓氱殑鏁欏﹂渶奼傘備綔涓烘湰縐戠敓緙栬瘧鍘熺悊璇劇▼鐨勭悊鎯蟲暀鏉愶紝鏃犺烘槸瀵逛笓涓氬︾敓榪樻槸鐮旂┒浜哄憳錛岄兘鍏鋒湁鏋侀珮鐨勫弬鑰冧環鍊箋

琚瑾変負鈥滈緳涔︹濈殑銆婄紪璇戝師鐞(鏈縐戞暀瀛︾増絎2鐗)銆嬭嚜1986騫撮棶涓栦互鏉ワ紝涓鐩村彈鍒板叏鐞冪煡鍚嶅﹀簻鐨勯潚鐫愶紝濡傚摜浼︽瘮浜氬ぇ瀛︺佹柉鍧︾忓ぇ瀛︺佸搱浣涘ぇ瀛﹀拰鏅鏋楁柉欏垮ぇ瀛︾瓑錛屽畠浠閮藉皢姝や功浣滀負緙栬瘧鍘熺悊璇劇▼鐨勯栭夋暀鏉愩傚湪涓鍥斤紝璇ヤ功瀵歸珮絳夋暀鑲查嗗煙灝ゅ叾浜х敓浜嗘繁榪滃獎鍝嶏紝鎺ㄥ姩浜嗙紪璇戞妧鏈鐨勬暀瀛﹀拰鐮旂┒銆

鍦ㄧ浜岀増涓錛屼綔鑰呭瑰悇絝犺妭榪涜屼簡鍏ㄩ潰鐨勬洿鏂幫紝浠ュ弽鏄犺繃鍘20澶氬勾杞浠跺伐紼嬨佺▼搴忚捐¤璦鍜岃＄畻鏈轟綋緋葷粨鏋勯嗗煙鐨勮繘姝ワ紝濡備綍褰卞搷浜嗙紪璇戞妧鏈銆傛柊鐗堟繁鍏ヨ茶В浜嗙紪璇戝櫒鐨勮捐★紝騫剁潃閲嶅睍紺轟簡緙栬瘧鎶鏈鍦ㄨ蔣浠跺紑鍙戜腑鐨勫箍娉涘簲鐢ㄣ傛瘡涓絝犺妭閮介厤浠ヤ赴瀵岀殑涔犻橈紝鏂逛究瀛︾敓榪涜屽疄璺電粌涔狅紝鍚屾椂鎻愪緵浜嗗厖瓚崇殑鍙傝冩枃鐚渚涜繘涓姝ュ︿範銆

閽堝瑰浗鍐呯殑鏁欏﹂渶奼傦紝鏂扮増銆婄紪璇戝師鐞(鏈縐戞暀瀛︾増絎2鐗)銆嬪垹鍑忎簡閮ㄥ垎楂樼駭鍐呭癸紝淇濈暀浜嗗熀紜鐭ヨ瘑錛屾棬鍦ㄦ彁渚涗竴涓鏇翠負閫傚悎璁＄畻鏈哄強鐩稿叧涓撲笟鏈縐戠敓瀛︿範鐨勬暀鏉愶紝甯鍔╀粬浠寤虹珛璧峰潥瀹炵殑緙栬瘧鍘熺悊鍩虹銆

5. 編譯原理 2型文法一定是1型文法嗎 不是一種包含關系嗎

2型文法一定是1型文法嗎？--是的，一定是，3型文法一定是2型的，2型一定是1型的，1型一定是0型的。
只不過考試時候需要最准確的回答，如果考試問一個文法G1（是2型的），你回答0型，1型，2型都沒錯，但是回答2型才是最准確的，單選也是，需要回答2型，復選題的話你就得選 0型、1型、2型了。