當前位置:首頁 » 編程軟體 » 編譯原理文法轉表達式

編譯原理文法轉表達式

發布時間: 2024-06-13 11:58:59

1. 什麼是文法(編譯原理)

【定義】

文法G定義為四元組(VN,VT,P,S)

其中 VN   :非終結符號(即語法變數)集

        VT   : 終結符號集

                   VN∩VT =Φ,令V= VN∪VT,V稱為文法G的字母表或字匯表。

        P  :產生式(α→β)集

        S :開始符號,且S∈VN ,S至少要在一條規則的左部出現。

【約定】

一般地,文法G的 四元組 不用全部給出 ,而只將產生式寫出。

約定:

    (1)第一條產生式的左部是開始符號

    (2)用尖括弧括起來的(或 大寫字母 )是非終結符號

    (3)不用尖括弧括起來(或 小寫字母 )是終結符號

    (4)還有一種習慣寫法,即 G[S] ,其中 S 是 開始符號 。

【舉例】

    例: G=(VN,VT,P,S)

           其中  VN={S},

           VT ={0,1},

           P={S→0S1,S→01}

           S是開始符號

2. 編譯原理文法

編譯原理文法的概念為:每一種自然語言或者是編程語言都需要文法來描述,文法相當於語言學的語義分析,即分析每一句話所表示的含義,編譯器需要利用文法來完成其語法分析和語義分析。

字母表是元素的非空有窮集合,字母表中的元素稱之為符號,因此,字母表也稱之為符號集。例如C語言中的字母表由字母、數字、關鍵字等組成。

符號串,就是由符號集中的元素組成的序列。例如,給定符號集a、b、c,那麼abc、abb、ac就是由該符號集組成的符號串。一個文法中,含有一個,或多個產生式,產生式,描述了將終結符集合和非終結符集合組合成串的方法。

3. 【編譯原理】構造下述文法G[S]的確定有限自動機,並給出該文法的語言的正規表達式 S->Aa|ε A->Aa|Sb|a

通過聯立方程組求正規表達式:
A = Aa|Sb|a = Aa|(Aa|ε)b|a= Aa+(Aa+ε)b+a=Aa+(Aab+b)+a=Aa+Aab+b+a=A(a+ab)+(b+a)
根據方程X=Xt+r 必有X=t*r解的論斷,可得A=(a+ab)*(b+a),進而可求得:
S = Aa|ε = Aa+ε = Aa = (a+ab)*(b+a)a = (a|ab)*(b|a)a
即文法的正規表達式為: (a|ab)*(b|a)a。
注意:以上求解的過程中「|」和「+」是等價的,都表示「或」的意思,它們的相互替換是為了描述的方便。

4. 編譯原理簡單文法歸約計算

編譯原理中的語法和文法是不一樣的,但卻融會貫通。
在計算機科學中,文法是編譯原理的基礎,是描述一門程序設計語言和實現其編譯器的方法。
文法分成四種類型,即0型、1型、2型和3型。這幾類文法的差別在於對產生式施加不同的限制。
形式語言,這種理論對計算機科學有著深刻的影響,特別是對程序設計語言的設計、編譯方法和計算復雜性等方面更有重大的作用。
多數程序設計語言的單詞的語法都能用正規文法或3型文法(3型文法G=(VN,VT,P,S)的P中的規則有兩種形式:一種是前面定義的形式,即:A→aB或A→a其中A,B∈VN ,a∈VT*,另一種形式是:A→Ba或A→a,前者稱為右線性文法,後者稱為左線性文法。正規文法所描述的是VT*上的正規集)來描述。
四個文法類的定義是逐漸增加限制的,因此每一種正規文法都是上下文無關的,每一種上下文無關文法都是上下文有關的,而每一種上下文有關文法都是0型文法。稱0型文法產生的語言為0型語言。上下文有關文法、上下文無關文法和正規文法產生的語言分別稱為上下文有關語言、上下文無關語言和正規語言。

5. 在編譯原理中: 文法S——>SS+|SS*|a能產生什麼語言,並驗證! 求高人指導!

為了使問題簡化,我們考慮文法S->ss+|a,考慮s->ss*時,只要把+換成*即可。
0層遞歸是,s->a,文法的語言是{a}。是後綴表達式。
1層以內遞歸時,文法語言是{a,aa+}。是後綴表達式。
2層以內遞歸時,文法語言是{a,aa+}.{a,aa+}.{+}。其中.表示連接,是後綴表達式。
依此類推,多少層的遞歸都是後綴表達式。
把表達式的+換成*後依然為後綴表達式。
下面證明文法產生的語言是所有的以a為變數,以+和*為運算符的後綴表達式。
因為每個表達式都對應一個常規的表達式(如1*2+3就是常規表達式),下面只需證明語言能產生的後綴表達式對應所有的常規表達式。當常規表達式只有一個運算符,對應aa+或aa*。當常規表達式有兩個運算符,可寫成(表達式1).{+|*}.(表達式2),因為表達式1和2都只含一個運算符,所以可以用語言表示,上述常規表達式可用後綴表達式(表達式1).(表達式2).{+l*}表示。所以不管常規表達式有多少個運算符,都可以由語言的後綴表達式對應。

6. (編譯原理) 求下述文法對應正規式: 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]+。

7. 編譯原理-文法定義

文法定義公式如下:

Chomsky 文法分類將文法分為四種,0型文法( PSG )、1型文法( CSG )、2型文法( CFG )和3型文法( RG )。

又被稱為無限制文法(Unrestricted Grammar), 或者短語結構文法(Phrase Structure Grammar)
定義: 對於產生式 α→β , α 至少包含一個非終結符。

為什麼要叫無限制文法,明明它要求產生式的左部必須包含一個非終結符。

又被稱為上下文有關文法(Context-Sensitive Grammar)
定義:對於產生式 α→β , |α| <= |β| , 僅僅 S→ε 除外

為什麼叫做上下文有關文法?

一般情況下,這種產生式的形式為 α1Aα2→α1βα2

又被稱為上下文無關文法(Context-Free Grammar)
定義:對任一產生式 α→β ,都有 α∈VN,β∈(VN∪VT)*

為什麼叫上下文無關文法?

又被稱為正則文法(Regular Grammar,RG),分為右線性(Right Linear)文法和左線性(Left Linear)文法。

定義: 對任一產生式 α→β ,都有 α∈VN,β最多兩個字元元素,如果有二個字元必須是(終結符+非終結符)的格式,如果是一個字元,那麼必須是終結符。

根據產生式右部非終結符位置不同,分為右線性文法和左線性文法。

可以看出,不同文法就是對產生式進行逐層的限制,所以各個文法是包含關系,即0型文法包含1型文法;1型文法又包含2型文法;2型文法最後包含3型文法。

8. 【編譯原理】第二章:語言和文法



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

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

產生式

可以簡寫為:

如上例中,

可以簡寫為:

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

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

推導的反過程稱為 歸約

如果 ,則稱 是 的一個 句型(sentential form )。

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


文法

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

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

中必須包含一個 非終結符


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

上下文有關文法不包含空產生式( )。


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

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

例:(右線性文法)

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

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

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

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

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

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

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

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

9. 編譯原理的文法是什麼

文法是描述語言規則的形式規則。實際上就是用一個四元組G=(VT,VN,S,P)定義的一個推理方式。其中VT是終結符,VN是非終結符,S是開始符號,P是一組產生規則。

熱點內容
免費的文件夾加密大師 發布:2024-07-23 03:44:44 瀏覽:451
3位密碼鎖密碼是多少 發布:2024-07-23 03:17:55 瀏覽:209
linuxandroid內核版本 發布:2024-07-23 02:37:24 瀏覽:73
緩存模型導出max 發布:2024-07-23 02:20:53 瀏覽:98
android進程回收 發布:2024-07-23 02:20:52 瀏覽:660
數組打亂php 發布:2024-07-23 02:20:52 瀏覽:66
西安php 發布:2024-07-23 02:16:05 瀏覽:213
無冬腳本 發布:2024-07-23 02:16:04 瀏覽:996
方舟伺服器推薦什麼模式 發布:2024-07-23 02:07:17 瀏覽:390
淘寶支付密碼怎麼改 發布:2024-07-23 02:01:37 瀏覽:927