上下文无关语法
直觀的理解,V變元指代一類事物,如V指代動詞,那么T總結符就是一系列具體動作,初始符就是文化最開始,未發(fā)生任何變化時的樣子.
產生式麻,就是動詞到具體動作的映射過程
? 上下文無關文法是形式化描述語言的又一種工具;
? 它表示語言的能力強于有窮自動機和正則表達式, 但也有無法它表示的語言;
? 基本思想是用變量表示串的集合;
? 遞歸的使用變量去定義變量, 因此善于表示嵌套的結構, 比如匹配的括號等;
? 變量之間僅使用了“連接”, 同一變量的不同定義使用了“并”.
字符使用的一般約定
? 終結符: 0, 1, . . . , a, b, . . .
? 終結符串: . . . ,w, x, y, z
? 非終結符: S, A,B, . . .
? 終結符或非終結符: . . . ,X, Y,Z
? 終結符或非終結符組成的串: α, β, γ, . . .
歸約和派生
從字符串到文法變元的分析過程, 稱為遞歸推理(recursive inference) 或歸約(reduction) ;
從文法變元到字符串的分析過程, 稱為推導或派生(derivation).
? 歸約: 自底向上(bottom up), 由產生式的體向頭的分析
? 派生: 自頂向下(top down), 由產生式的頭向體分析
最左派生和最右派生
為限制派生的隨意性, 要求只替換符號串中最左邊變元的派生過程, 稱為最左派生(left-most derivation),
只替換最右的, 稱為最右派生(right-most derivation).
文法的語言
上下文無關是指在文法派生的每一步αAβ ? αγβ, 符號串γ 僅根據A 的產生式派生, 而無需依賴A 的上下文α 和β.
文法的等價性
如果有兩個文法CFG G1 和CFG G2, 滿足L(G1) = L(G2), 則稱G1 和G2 是等價的.
句型
? 只含有終結符的句型, 也稱為G 的句子(sentence)
? 而L(G) 就是文法G 全部的句子
文法設計舉例
至少包含xx, 則先將xx寫出來, 再用其他變元插入進行變化
將CFG 變?yōu)檎齽t表達式直接用P進行迭代
例4是相等的情況,不相等的情況,只需要相等情況C + 獨自情況A,B即可
思考n < m的情況: 先寫出相等,再加上偏移的字符
推薦解2. 當要求0,1相等,沒有位置要求,則先將1,0 列出來,再插縫,注意0,1順序的不同
先寫出i = 2j的情況,再加上偏移,注意偏移的寫法
語法分析樹
派生或歸約的過程可以表示成樹形結構.
語法樹和派生是等價的
語法樹唯一確定最左(右) 派生
文法和語言的歧義性
定義. 如果CFG G 使某些符號串有兩棵不同的語法分析樹, 則稱文法G 是歧義(ambiguity)的.
有些文法的歧義性, 可以通過重新設計文法來消除.
定義同樣的語言可以有多個文法, 如果CFL L 的所有文法都是歧義的, 那么稱語言L是固有歧義(Inherent Ambiguity) 的.
文法的化簡與范式
以不改變語言為前提, 化簡文法和限制文法的格式
文法的化簡
消除無用符號(useless symbols): 對文法定義語言沒有貢獻的符號
消除ε 產生式(ε-productions): A → ε (得到語言L ? {ε})
消除單元產生式(unit productions): A → B
無用符號, 從文法開始符號派生到終結符串的過程中用不到; ε-產生式, 除了空串ε 自身,
沒有貢獻語言中其他的串; 單元產生式, 僅僅增加了推導(或歸約) 的步驟. 這三者對語言的定
義都沒有實質的作用.
消除無用符號
可達就是S可到達的變元
產生就是可以派生到全部為終結符的串的變元
計算“產生的”符號集
每個T 中的符號都是產生的;
A → α ∈ P 且α 中符號都是產生的, 則A 是產生的
計算“可達的”符號集
符號S 是可達的;
A → α ∈ P 且A 是可達的, 則α 中符號都是可達的.
注意
? 先尋找并消除全部非“產生的”符號
? 再尋找并消除全部非“可達的”符號
? 否則可能消除不完整
消除ε-產生式
定義. 文法中形如A → ε 的產生式稱為ε-產生式.
如果變元A ?? ε, 稱A 是可空的.
確定“可空變元”
如果A → ε, 則A 是可空的;
如果B → α 且α 中的每個符號都是可空的, 則B 是可空的.
消除單元產生式
如果有A ?? B, 則稱[A,B] 為單元對.
單源產生式,即該產生式對應一個變元,而不是組合
A ==> B是單源產生式, A ==>BC不是單源產生式
同時注意,消除的只是 A ==> B,而不是B. 產生式B ==> … 依然成立
消除單元產生式
刪除全部形為A → B 的單元產生式;
對每個單元對[A,B], 將B 的產生式復制給A.
限制文法格式
將任意形式的文法轉換為:
喬姆斯基范式(CNF, Chomsky Normal Form)
格雷巴赫范式(GNF, Greibach Normal Form)
喬姆斯基范式
定理21 (喬姆斯基范式CNF). 每個不帶ε 的CFL 都可以由這樣的CFG G 定義, G 中每個產生式的形式都為
A → BC 或A → a (這里的A, B 和C 是變元, a 是終結符.)
喬姆斯基, 要么兩個大人(兩個變元), 要么是一個小孩(終結符)
反正成人不能單身
CFG 轉為CNF 的方法
將終結符封裝成變元
將一系列變元變成2個級聯(lián)的形式
格雷巴赫范式
定理22 (格雷巴赫范式GNF). 每個不帶ε 的CFL 都可以由這樣的CFG G 定義, G 中每個產生式的形式都為
A → aα (其中A 是變元, a 是終結符, α 是零或多個變元的串.)
GNF就是一個小孩一個大人(可以沒有), 兩個成人不能在一起,在一起必須有小孩在前面
間接左遞歸可以理解為循環(huán)引用
上下文無關語法的性質
上下文無關語言的泵引理
找到中間一個大小為N的塊,增減其兩端的字符,其任符合上下文無關語法
對比
找到前面一個大小為N的塊,任意增減其末尾字符, 其仍然屬于正則表達式
定理 34. 如果有 Σ 上的 CFL L 和代換 s, 且每個 a ∈ Σ 的 s(a) 都是 CFL, 那么 s(L) 也是
CFL.
定理 35. 上下文無關語言在并, 連接, 閉包, 正閉包, 同態(tài)下封閉.
定理 36. 如果 L 是 CFL, 那么 L R 也是 CFL.
CFL 對交運算不封閉
CFL 對補運算不封閉
定理 38. 若 L 是 CFL 且 R 是正則語言, 則 L ∩ R 是 CFL
根據上下文無關語言的性質判斷一個語言是否是上下文無關的
總結
- 上一篇: SAP Spartacus如何为不同的e
- 下一篇: VBA控制菜单栏上的菜单(如页面设置、打