文章目錄
-
- 一、上下文無關文法 設計 示例
- 二、上下文無關文法 的歧義性
- 三、Chomsky 範式
- 四、上下文無關文法 轉為 Chomsky 範式
- 五、上下文無關文法 轉為 Chomsky 範式 示例
一、上下文無關文法 設計 示例
1 . 上下文無關文法 設計要求 : 設計一個文法 , 使用該文法生成語言
w
w
w , 該
w
w
w 語言的字元串的開始和結尾的字元是相同的 ;
2 . 設計方法 : 非确定性優先自動機 ( NFA ) 識别某語言 , 将 NFA 轉為 确定性優先自動機 ( DFA ) , 然後将 DFA 轉為 上下文無關文法 ;
3 . 文法設計要求分析 :
-
-
開始字元 要麼是
0 , 要麼就是
1
1
1 ;
-
如果開始字元是
0 , 對應的結尾字元也是
0 ;
-
如果開始字元是
1
1
1 , 對應的結尾字元也是
1
1
1 ;
4 . 初始狀态
S
S
S 規則 : 上述文法描述轉為規則 如下 , 其中
S
S
S 為初始狀态 ;
S
→
S
′
∣
1
S
′
1
S \to 0S'0 | 1S'1
S→0S′0∣1S′1
5 .
S
′
S'
S′ 規則 :
S
′
S'
S′ 表示中間的字元串 , 這個
S
′
S'
S′ 字元串可以是任意字元串 , 根據下面的規則可以生成任意的
,
1
0,1
0,1 組成的字元串 ;
S
′
→
S
′
∣
1
S
′
∣
ε
S' \to 0S' | 1S' | \varepsilon
S′→0S′∣1S′∣ε
二、上下文無關文法 的歧義性
給出如下上下文無關文法 ( CFG ) :
E
x
p
r
e
s
s
i
o
n
→
E
x
p
r
e
s
s
i
o
n
+
E
x
p
r
e
s
s
i
o
n
∣
E
x
p
r
e
s
s
i
o
n
×
E
x
p
r
e
s
s
i
o
n
∣
E
x
p
r
e
s
s
i
o
n
∣
a
Expression \to Expression + Expression | Expression \times Expression | Expression | a
Expression→Expression+Expression∣Expression×Expression∣Expression∣a
文法的含義是 :
-
-
E
x
p
r
e
s
s
i
o
n
Expression
Expression 可以被
E
x
p
r
e
s
s
i
o
n
+
E
x
p
r
e
s
s
i
o
n
Expression + Expression
Expression+Expression 替換 ;
-
E
x
p
r
e
s
s
i
o
n
Expression
Expression 可以被
E
x
p
r
e
s
s
i
o
n
×
E
x
p
r
e
s
s
i
o
n
Expression \times Expression
Expression×Expression 替換 ;
-
E
x
p
r
e
s
s
i
o
n
Expression
Expression 可以被
E
x
p
r
e
s
s
i
o
n
Expression
Expression 替換 ;
-
E
x
p
r
e
s
s
i
o
n
Expression
Expression 可以被
a
a
a 替換 ;
1 . 文法的有歧義性 : 同樣的一個字元串 , 可以有不同的文法分析樹 ;
① 文法分析樹 1 :
2 . 在上述的 文法分析樹中 , 加法優先級高于乘法 , 這是錯誤的分析 ;
② 文法分析樹 2 :
在上述的 文法分析樹中 , 乘法優先級高于加法 , 這是正确的分析 ;
3 . 文法歧義性分析 : 上述文法中是無法區分 加法 和 乘法的優先級的 , 是以這裡得到兩個完全不一緻得我文法分析樹 , 那麼該文法是有歧義的 ;
4 . 與代數表達式文法對比 : 之前講的代數表達式是好的文法 , 乘法 和 加法的優先級 也展現出來 , 乘法優先級高于加法 , 括号的優先級高于乘法 ;
① 代數表達式文法 :
-
-
E
x
p
r
e
s
s
i
o
n
→
E
x
p
r
e
s
s
i
o
n
+
T
e
r
m
∣
T
e
r
m
Expression \to Expression + Term \quad | \quad Term
Expression→Expression+Term∣Term
-
T
e
r
m
→
T
e
r
m
×
F
a
c
t
o
r
∣
F
a
c
t
o
r
Term \to Term \times Factor \quad | \quad Factor
Term→Term×Factor∣Factor
-
F
a
c
t
o
r
→
E
x
p
r
e
s
s
i
o
n
∣
a
Factor \to Expression \quad | \quad a
Factor→Expression∣a
② 代數表達式文法分析樹 : 這個文法分析樹是唯一的 , 沒有其它的形式 , 該文法是沒有歧義的 ;
③ 有歧義的文法 : 在本節的文法中 , 無法區分 加法 和 乘法的優先級 , 該文法是有歧義的 ;
5 . 總結 : 如果文法有歧義 , 那麼中間的字元串有歧義 ; 沒有算法 可以判定 上下文無關文法 是否有歧義 ; 有些文法天生就是有歧義的 , 但可以通過某種方法去掉文法中的歧義性 ;
三、Chomsky 範式
1 . Chomsky 範式 : 上下文無關文法中的任何規則都是如下格式 ;
①
A
→
B
C
A \to BC
A→BC :
A
A
A 是 變元 ,
B
,
C
B,C
B,C 也是變元 ;
②
A
→
a
A \to a
A→a :
A
A
A 是 變元 ,
a
a
a 是常元 ,
A
A
A 可以被終端字元替換 ;
③
B
,
C
B ,C
B,C 變元要求 :
B
,
C
B, C
B,C 變元一定不能是開始變元 ;
④
S
→
ε
S \to \varepsilon
S→ε :
S
S
S 開始變元可以為空 ;
⑤ 不能出現
變
元
→
變
元
變元 \to 變元
變元→變元 單個變元 到 單個變元不允許出現 ;
2 .
S
→
ε
S \to \varepsilon
S→ε 規則 說明 :
① 語言包含空字元串 : 如果上下文無關文法包含空字元串時 , 一定需要
S
→
ε
S \to \varepsilon
S→ε 規則 ;
② 語言不包含空字元串 : 如果上下文無關文法不包含空字元串時 , 一定不需要
S
→
ε
S \to \varepsilon
S→ε 規則 ;
③ 規則總結 : 該規則決定 上下文無關文法 所生成的語言 是否包含 空字元串 , 如果包含必須要這個規則 , 如果不包含空字元串一定不要這個規則 ;
四、上下文無關文法 轉為 Chomsky 範式
Chomsky 範式規則 的 上下文無關文法 生成的語言 的文法分析樹 除葉子節點之外 都 是二叉樹 , 葉子節點 與 上一層都是 一對一的節點 ;
任何 上下文無關文法 , 都可以找到一個 Chomsky 範式 與其等價 ;
任何 上下文無關文法 的文法分析樹 都可以進行修剪 , 修剪後的樹都是二叉樹 ;
上下文無關文法 轉為 Chomsky 範式 步驟 :
1 . 添加開始變元及規則 : 添加一個新的開始變元
S
S_0
S0 , 以及配套的規則
S
→
S
S_0 \to S
S0→S ,
S
S
S 是舊的開始變元 ;
① 目的 : 添加開始變元的目的是 開始變元 永遠出現在左邊 ;
② Chomsky 範式 中 , 開始變元始終在規則的左邊 , 不允許開始變元在規則的右側 ;
③ 對應 Chomsky 範式 規則 :
A
→
B
C
A \to BC
A→BC 規則 ,
A
A
A 是 變元 ,
B
,
C
B,C
B,C 也是變元 , 并且
B
,
C
B,C
B,C 不允許是開始變元 ;
2 . 消除所有的
ε
\varepsilon
ε 規則 : 消除所有從 變元 到 空字元 的規則 ;
3 . 消除所有的
A
→
B
A \to B
A→B 規則 : 消除所有從 單個變元 到 單個變元的 單條規則 , 允許從 單個變元 到 多個變元或常元 ;
如
A
→
B
A \to B
A→B 是需要删除的 ,
A
→
B
S
A \to BS
A→BS 可以保留 ;
五、上下文無關文法 轉為 Chomsky 範式 示例
将 上下文無關文法
G
6
G6
G6 轉為 Chomsky 範式 :
-
-
S
→
A
S
A
∣
a
B
S \to ASA | aB
S→ASA∣aB
-
A
→
B
∣
S
A \to B|S
A→B∣S
-
B
→
b
∣
ε
B \to b|\varepsilon
B→b∣ε
轉換過程如下 :
1 . 添加新的開始變元 :
S
S_0
S0 , 舊的開始變元
S
S
S 就不是開始變元了 ;
目前的文法格式如下 :
-
-
S
→
S
S_0 \to S
S0→S
-
S
→
A
S
A
∣
a
B
S \to ASA | aB
S→ASA∣aB
-
A
→
B
∣
S
A \to B|S
A→B∣S
-
B
→
b
∣
ε
B \to b|\varepsilon
B→b∣ε
2 . 消除
ε
\varepsilon
ε 規則 :
消除
ε
\varepsilon
ε 規則 原則 : 假設有規則
C
→
ε
C \to \varepsilon
C→ε ,
D
→
u
C
v
D \to uCv
D→uCv , 如果要删除
ε
\varepsilon
ε 規則 , 需要實作 消除前後具有 相同的替換效果 , 将規則改為
D
→
u
v
D \to uv
D→uv 即可删除
ε
\varepsilon
ε 相關規則 ;
( 消除前後 , 替換效果必須一緻 )
3 . 消除
B
→
b
∣
ε
B \to b|\varepsilon
B→b∣ε 中的
ε
\varepsilon
ε : 會影響
S
→
A
S
A
∣
a
B
S \to ASA | aB
S→ASA∣aB 和
A
→
B
∣
S
A \to B|S
A→B∣S 兩條規則中涉及到了
B
B
B 變元 , 消除的原則是 " 消除前後 , 替換效果必須一緻 " ;
3.1 .
S
→
A
S
A
∣
a
B
S \to ASA | aB
S→ASA∣aB 規則消除
ε
\varepsilon
ε 分析 : 這裡讨論 消除
B
→
b
∣
ε
B \to b|\varepsilon
B→b∣ε 規則中的
B
→
ε
B \to \varepsilon
B→ε 規則 對
a
B
aB
aB 的影響 ;
① 消除
B
→
ε
B \to \varepsilon
B→ε 規則前分析 : 使用
B
→
b
∣
ε
B \to b|\varepsilon
B→b∣ε 規則 對
a
B
aB
aB 進行替換 有兩種情況 , 分别是
a
b
ab
ab ,
a
a
a , 兩種情況 ;
② 消除
B
→
ε
B \to \varepsilon
B→ε 規則後分析 : 如果要消除
B
→
ε
B \to \varepsilon
B→ε 規則 , 那麼消除後的規則是
B
→
b
B \to b
B→b , 使用
B
→
b
B \to b
B→b 規則對
a
B
aB
aB 進行替換 , 其替換 結果必須是
a
b
ab
ab ,
a
a
a , 兩種情況 ;
分析
a
b
ab
ab ,
a
a
a 兩種結果 :
-
-
a
B
aB
aB 使用
B
→
b
B \to b
B→b 規則替換 , 可以得到
a
b
ab
ab ;
-
a
a
a 替換結果無法擷取 , 此時需要在
a
B
aB
aB 的平級 , 再次添加
a
a
a 即可達到上述效果 ;
a
B
aB
aB 最終修改方案 : 将
a
B
aB
aB 改為
a
B
∣
a
aB|a
aB∣a , 使用
B
→
b
B \to b
B→b 規則替換
a
B
∣
a
aB|a
aB∣a 的結果是
a
b
ab
ab ,
a
a
a , 與上述消除
B
→
ε
B \to \varepsilon
B→ε 規則 前的結果一緻 ;
③
S
→
A
S
A
∣
a
B
S \to ASA | aB
S→ASA∣aB 規則對應的消除
B
→
ε
B \to \varepsilon
B→ε 規則後的結果為
S
→
A
S
A
∣
a
B
∣
a
S \to ASA | aB | a
S→ASA∣aB∣a
④ 目前的文法格式如下 : 注意 還沒有讨論
A
→
B
∣
S
A \to B|S
A→B∣S 規則中的
B
B
B ,
B
→
b
∣
ε
B \to b|\varepsilon
B→b∣ε 規則中的
ε
\varepsilon
ε 還不能删除 ;
-
-
S
→
S
S_0 \to S
S0→S
-
S
→
A
S
A
∣
a
B
∣
a
S \to ASA | aB | a
S→ASA∣aB∣a
-
A
→
B
∣
S
A \to B|S
A→B∣S : 注意此時該規則不完善 , 還沒有删除
ε
\varepsilon
ε ;
-
B
→
b
B \to b
B→b
3.2 .
A
→
B
∣
S
A \to B|S
A→B∣S 規則消除
ε
\varepsilon
ε 分析 : 這裡讨論 消除
B
→
b
∣
ε
B \to b|\varepsilon
B→b∣ε 規則中的
B
→
ε
B \to \varepsilon
B→ε 規則 對
B
B
B 的影響 ;
① 消除
B
→
ε
B \to \varepsilon
B→ε 規則前分析 : 使用
B
→
b
∣
ε
B \to b|\varepsilon
B→b∣ε 規則 對
B
B
B 進行替換 有兩種情況 , 分别是
b
b
b ,
ε
\varepsilon
ε , 兩種情況 ;
② 消除
B
→
ε
B \to \varepsilon
B→ε 規則後分析 : 如果要消除
B
→
ε
B \to \varepsilon
B→ε 規則 , 那麼消除後的規則是
B
→
b
B \to b
B→b , 使用
B
→
b
B \to b
B→b 規則對
B
B
B 進行替換 , 其替換 結果必須是
b
b
b ,
ε
\varepsilon
ε , 兩種情況 ;
分析
b
b
b ,
ε
\varepsilon
ε 兩種結果 :
-
-
B
B
B 使用
B
→
b
B \to b
B→b 規則替換 , 可以得到
b
b
b ;
-
ε
\varepsilon
ε 替換結果無法擷取 , 此時需要在
B
B
B 的平級 , 再次添加
ε
\varepsilon
ε 即可達到上述效果 ;
B
B
B 最終修改方案 : 将
B
B
B 改為
B
∣
ε
B|\varepsilon
B∣ε , 使用
B
→
b
B \to b
B→b 規則替換
B
∣
ε
B|\varepsilon
B∣ε 的結果是
b
b
b ,
ε
\varepsilon
ε , 與上述消除
B
→
ε
B \to \varepsilon
B→ε 規則 前的結果一緻 ;
③
A
→
B
∣
S
A \to B|S
A→B∣S 規則對應的消除
B
→
ε
B \to \varepsilon
B→ε 規則後的結果為
A
→
B
∣
ε
∣
S
A \to B| \varepsilon|S
A→B∣ε∣S
④ 目前的文法格式如下 : 注意 還沒有讨論
A
→
B
∣
S
A \to B|S
A→B∣S 規則中的
B
B
B ,
B
→
b
∣
ε
B \to b|\varepsilon
B→b∣ε 規則中的
ε
\varepsilon
ε 還不能删除 ;
-
-
S
→
S
S_0 \to S
S0→S
-
S
→
A
S
A
∣
a
B
∣
a
S \to ASA | aB | a
S→ASA∣aB∣a
-
A
→
B
∣
ε
∣
S
A \to B| \varepsilon |S
A→B∣ε∣S
-
B
→
b
B \to b
B→b
4 . 消除
A
→
B
∣
ε
∣
S
A \to B| \varepsilon |S
A→B∣ε∣S 中的
ε
\varepsilon
ε : 會影響
S
→
A
S
A
∣
a
B
∣
a
S \to ASA | aB | a
S→ASA∣aB∣a 規則中涉及到了
A
A
A 變元 , 消除的原則是 " 消除前後 , 替換效果必須一緻 " ;
① 消除
A
S
A
ASA
ASA 中的
ε
\varepsilon
ε , 添加以下項即可 :
-
-
第一個
A
A
A 通過
ε
\varepsilon
ε 代替 : 添加
S
A
SA
SA 項 ;
-
第二個
A
A
A 通過
ε
\varepsilon
ε 代替 : 添加
A
S
AS
AS 項 ;
-
兩個
A
A
A 都通過
ε
\varepsilon
ε 代替 : 是
S
S
S , 可以不同寫 ,
S
→
S
S \to S
S→S 沒啥意義 ;
②
S
→
A
S
A
∣
a
B
∣
a
S \to ASA | aB | a
S→ASA∣aB∣a 規則對應的消除
A
→
ε
A \to \varepsilon
A→ε 規則後的結果為 :
S
→
A
S
A
∣
A
S
∣
S
A
∣
a
B
∣
a
S \to ASA | AS | SA | aB | a
S→ASA∣AS∣SA∣aB∣a
③ 目前的文法格式如下 :
-
-
S
→
S
S_0 \to S
S0→S
-
S
→
A
S
A
∣
A
S
∣
S
A
∣
a
B
∣
a
S \to ASA | AS | SA | aB | a
S→ASA∣AS∣SA∣aB∣a
-
A
→
B
∣
S
A \to B| S
A→B∣S
-
B
→
b
B \to b
B→b
5 . 消除
A
→
B
A \to B
A→B 規則 :
假設要消除
C
→
D
C \to D
C→D 規則 : 如果文法中有
D
→
W
D \to W
D→W 規則 , 那麼如果消除
C
→
D
C \to D
C→D , 需要将
C
→
W
C \to W
C→W 展現出來 ;
消除
A
→
B
A \to B
A→B 規則 , 檢查
B
B
B 出現在規則左邊的情況 , 這裡有
B
→
b
B \to b
B→b 規則 , 需要 添加
A
→
b
A\to b
A→b 規則後 , 即可删除
A
→
B
A \to B
A→B 規則 ;
删除前規則 :
-
-
S
→
S
S_0 \to S
S0→S
-
S
→
A
S
A
∣
A
S
∣
S
A
∣
a
B
∣
a
S \to ASA | AS | SA | aB | a
S→ASA∣AS∣SA∣aB∣a
-
A
→
B
∣
S
A \to B| S
A→B∣S
-
B
→
b
B \to b
B→b
删除後規則如下 :
-
-
S
→
S
S_0 \to S
S0→S
-
S
→
A
S
A
∣
A
S
∣
S
A
∣
a
B
∣
a
S \to ASA | AS | SA | aB | a
S→ASA∣AS∣SA∣aB∣a
-
A
→
b
∣
S
A \to b| S
A→b∣S
6 . 消除
A
→
S
A \to S
A→S 規則 :
① 消除
A
→
S
A \to S
A→S 規則 , 檢查
S
S
S 出現在規則左邊的情況 , 這裡有
S
→
A
S
A
∣
A
S
∣
S
A
∣
a
B
∣
a
S \to ASA | AS | SA | aB | a
S→ASA∣AS∣SA∣aB∣a 規則 , 需要 添加
A
→
A
S
A
∣
A
S
∣
S
A
∣
a
B
∣
a
A\to ASA | AS | SA | aB | a
A→ASA∣AS∣SA∣aB∣a 規則後 , 即可删除
A
→
S
A \to S
A→S 規則 ;
② 删除前規則 :
-
-
S
→
S
S_0 \to S
S0→S
-
S
→
A
S
A
∣
A
S
∣
S
A
∣
a
B
∣
a
S \to ASA | AS | SA | aB | a
S→ASA∣AS∣SA∣aB∣a
-
A
→
b
∣
S
A \to b | S
A→b∣S
③ 删除後規則如下 :
-
-
S
→
S
S_0 \to S
S0→S
-
S
→
A
S
A
∣
A
S
∣
S
A
∣
a
B
∣
a
S \to ASA | AS | SA | aB | a
S→ASA∣AS∣SA∣aB∣a
-
A
→
b
∣
A
S
A
∣
A
S
∣
S
A
∣
a
B
∣
a
A \to b| ASA | AS | SA | aB | a
A→b∣ASA∣AS∣SA∣aB∣a
7 . 分解規則 :
① 分解示例 :
S
→
A
S
A
S \to ASA
S→ASA 可以分解為
S
→
R
S \to R
S→R ,
R
→
S
A
R \to SA
R→SA
② 分解前的規則 :
-
-
S
→
S
S_0 \to S
S0→S
-
S
→
A
S
A
∣
A
S
∣
S
A
∣
a
B
∣
a
S \to ASA | AS | SA | aB | a
S→ASA∣AS∣SA∣aB∣a
-
A
→
b
∣
A
S
A
∣
A
S
∣
S
A
∣
a
B
∣
a
A \to b| ASA | AS | SA | aB | a
A→b∣ASA∣AS∣SA∣aB∣a
③ 分解後的規則 :
-
S
→
S
S_0 \to S
S0→S
-
-
S
→
R
S \to R
S→R
-
R
→
S
A
R \to SA
R→SA
-
S
→
A
S
S \to AS
S→AS
-
S
→
S
A
S \to SA
S→SA
-
S
→
a
B
S \to aB
S→aB
-
S
→
a
S \to a
S→a
-
-
A
→
b
A \to b
A→b
-
A
→
R
A \to R
A→R
-
A
→
S
A
A \to SA
A→SA
-
A
→
A
S
A \to AS
A→AS
-
A
→
S
A
A \to SA
A→SA
-
A
→
a
B
A \to aB
A→aB
-
A
→
a
A \to a
A→a