寫在前面：
前幾篇博客中說到的詞法分析伞芹，做的是從 【x+y → id+id】 的工作，也就是要將源代碼變成一個記號流蝉娜。語法分析唱较，就是要通過為這個記號流序列（在“龍書”中，該序列被稱為“詞法單元序列”）構(gòu)造一棵語法分析樹召川，構(gòu)造該樹的方式就是“推導(dǎo)”（事實(shí)上南缓，分析樹其實(shí)是推導(dǎo)的圖形化表示）。
若能夠進(jìn)行這樣的推導(dǎo)： E=>E+E=>id+E=>id+id荧呐，即由 E 推出了 id+id汉形，與從詞法分析器那里得到的 id+id 相同，則說明語法結(jié)構(gòu)正確倍阐。
CFG 概述及其四元組表示
CFG 是什么概疆？CFG 是描述語言語法的工具，CFG 通過推導(dǎo)的方式產(chǎn)生語言峰搪。我們使用這個工具來對定義我們的語法岔冀，然后可以使用一些算法來基于它構(gòu)造我們想要的詞法分析器！這個分析器能夠?qū)⑽覀兊挠浱柫鳂?gòu)造為合法的語法樹概耻。
類似于我們在這里學(xué)過的很多其他東西使套，CFG 也一樣可以使用四元組表示：
CFG G=(N, T, P, S)
該四元組中的 N、T鞠柄、P 都是集合侦高，分別是 非終結(jié)符（Nonterminals）、終結(jié)符（Terminals）春锋、產(chǎn)生式（Productions） 的集合矫膨。S（Start Symbol） 是文法的開始符號，是一個特殊的非終結(jié)符期奔。
其中：
- N 和 T 沒有交集侧馅；
- P 的形式是 A→a，A∈N呐萌，a∈(N∪T)*（終結(jié)符或非終結(jié)符組成的一個串）馁痴，箭頭左側(cè)的被稱為左部，右側(cè)的被稱為右部
例子：簡單的算術(shù)表達(dá)式的 CFG 表示：
產(chǎn)生式中的 “ → ” 讀作“定義為” / “導(dǎo)出為”肺孤，例如 “ E→E+E ” 讀作 “E 導(dǎo)出為 E+E”罗晕，其表示 “算術(shù)表達(dá)式定義為兩個算術(shù)表達(dá)式相加”济欢。
注意，CFG 一旦定義完成小渊，語法也隨之定義完成了法褥。因此，對于一個句子的合法性檢查酬屉，就要根據(jù)我們定義的 CFG 來做半等。比如，如果按照上面這個例子的語法定義來看呐萨，“- - - - - id” 就是一個合法的句子杀饵，而 “ id - id ” 卻不合法。若想要其合法谬擦，我們需要在產(chǎn)生式中追加 “ E→ E - E ” 切距。
產(chǎn)生式集合表示 CFG
然而，用四元組來表示 CFG 還是太麻煩惨远，因此大佬們提出了這樣一個簡化的表達(dá)方式——只寫產(chǎn)生式集合谜悟，然后其他的部分我們可以通過一些預(yù)先約定好的規(guī)定來通過產(chǎn)生式集合求出來。這樣一來锨络，我們就可以省略很多東西了赌躺，就像下面這個：
P: E → E + E (1)
E → E * E (2)
E → (E) (3)
E → -E (4)
E → id (4)
使用該表示方法的前提是文法本身沒有錯誤（似乎是廢話？）羡儿。我們做預(yù)先約定好的規(guī)定如下：
CFG 的開始符號 S 礼患，是第一個產(chǎn)生式的左部——這就把四元組的最后一項(xiàng) S 定義出來了；
N 是可以出現(xiàn)在產(chǎn)生式左邊符號的集合——這就把四元組的第一項(xiàng) N（非終結(jié)符） 定義出來了掠归；
-
T 是絕不出現(xiàn)在產(chǎn)生式左邊的符號集合——這就把四元組第二項(xiàng) P 定義出來了缅叠。 注意，是只在右面出現(xiàn)的虏冻。像下面這種情況：
E -> ID ID -> ab盡管上面的 ID 在第一行出現(xiàn)在了右邊肤粱，到第二行卻出現(xiàn)在左邊，因此 ID 也是非終結(jié)符厨相。在且僅在產(chǎn)生式右面的符號领曼，才能叫作終結(jié)符。
因此蛮穿，只要我們寫出來 P 庶骄，整個四元組就都定義出來了——因?yàn)樗脑M中的其他三元都可以根據(jù)定義來從 P 中分類找出來
其實(shí)也可以寫得更簡單——就是用 | （或）符號來連接各個產(chǎn)生式，以省略多余的 E
比如：
E → E+E
|E*E
|(E)
|-E
|id
或
E → E+E|E*E|(E)|-E|id
這種產(chǎn)生式表示也被稱為“巴克斯范式”（BNF, Backus Naur Form）践磅，其中 → 用 ::= 表示单刁。
這種書寫方法中，每個右部的權(quán)利是相同的府适，因?yàn)楫?dāng)我們說 “ a 或 b ” 時羔飞，并沒有同時表達(dá)出來 “ a 重要還是 b 重要 ”的意思肺樟，我們也不能簡單地因?yàn)?a 在 b 的前面而推斷 a 比 b 更重要。這里的“權(quán)利”與文法的二義性有關(guān)逻淌。
終結(jié)符與非終結(jié)符還可以用下面的不同寫法進(jìn)行區(qū)分：
- 大小寫區(qū)分： E → id
- 用雙引號區(qū)分：E → "id" E → E "+" E
- 用尖括號區(qū)分：E → <E> + <E>
CFG么伯，用推導(dǎo)，產(chǎn)生語言
推導(dǎo)卡儒，實(shí)際上就是得到 CFG 所定義的語言的過程蹦狂。
回憶正規(guī)式——寫正規(guī)式的時候，就已經(jīng)有“產(chǎn)生”的含義在里面了
在正規(guī)式的定義中朋贬，我們可以說
a|b是一個正規(guī)式，它表示的正規(guī)集是：a表示的語言和b表示的語言取并集
——注意看這句話——正規(guī)式表示正規(guī)集窜骄，正規(guī)集是兩個語言的并集锦募，那么也就是說正規(guī)式表示語言的集合。我們已經(jīng)在定義正規(guī)式的時候把語言定義出來了邻遏！
正規(guī)式定義的時候糠亩，正規(guī)集這個語言就已經(jīng)隨之定義完了；但是在定義 CFG 的時候准验，我們可沒有說“CFG產(chǎn)生的語言”這類的話赎线，也就是說在我們寫下 CFG 時，這個語言并沒有被隨 CFG 定義出來糊饱。
因此垂寥，我們要單獨(dú)考慮怎么定義語言——語言，可以由 CFG 通過推導(dǎo)產(chǎn)生另锋，我們通過推導(dǎo)得到 CFG 所定義的語言滞项。
通俗地講，產(chǎn)生式產(chǎn)生語言的過程夭坪，就是從 S 開始文判，對產(chǎn)生式左部的非終結(jié)符反復(fù)地使用產(chǎn)生式：將產(chǎn)生式左部的非終結(jié)符替換為右部的文法序列（用 => 表示展開產(chǎn)生式），直到得到一個終結(jié)符序列室梅。
利用產(chǎn)生式產(chǎn)生句子戏仓。左側(cè)是產(chǎn)生式，產(chǎn)生式定義語法亡鼠。右側(cè)是根據(jù)左側(cè)的規(guī)則進(jìn)行的幾步推導(dǎo)過程赏殃。右邊這幾行式子的每一行推導(dǎo)符號右側(cè)的符號序列就叫做“文法符號序列”。
直接推導(dǎo)
推導(dǎo)拆宛，就是把非終結(jié)符按照產(chǎn)生式一步步換成終結(jié)符的過程嗓奢。
利用產(chǎn)生式產(chǎn)生句子的過程中，將產(chǎn)生式 A → γ 的右部代替文法符號序列 αAβ 中的 A 得到 αγβ 的過程浑厚，稱 αAβ 直接推導(dǎo)出 αγβ 股耽，記作 αAβ => αγβ
若對于任意文法符號序列 α1, α2, ...αn根盒，均有 α1=>α2=>...=>αn，則稱此過程為零步或多步推導(dǎo)物蝙，記為 α1=*>αn炎滞，當(dāng) α1=αn 時稱為零步推導(dǎo)。
若α1≠αn诬乞，即推導(dǎo)過程中至少使用一次產(chǎn)生式册赛，則稱此過程為 至少一步推導(dǎo)，記作 α1=+>αn
說白了震嫉。森瘪。根據(jù)產(chǎn)生式所描述的規(guī)則進(jìn)行代入替換，這里分清楚兩種箭頭就行了：→描述推導(dǎo)可以使用的規(guī)則票堵，=>描述推導(dǎo)的過程扼睬。
推導(dǎo)有自反性（對任意的 α，都有 α=>α）和傳遞性（若 α=>β悴势， β=>γ窗宇， 則 α=>γ）。
推導(dǎo)特纤，是一種二元關(guān)系
一個元素如果和它自己滿足該二元關(guān)系军俊，那么它就是自反的
即 aRa
由 CFG 產(chǎn)生語言
由 CFG G 產(chǎn)生的語言 L(G) 定義為：
-
L(G) = {ω | S=+> ω and ω∈ T* }
其中：
- S=+>ω：開始符號 S 經(jīng)過至少一步推導(dǎo)，能夠推出 ω
- ω∈ T*：ω 是由終結(jié)符組成的一個串
上面這兩條合在一起捧存，就可以保證我們能基于這套規(guī)則來從開始符號推出詞法分析器給我們的那個終結(jié)符串粪躬。基于此推出來的集合昔穴，就是語法規(guī)則所描述的語言短蜕。
該 L(G) 被稱為 上下文無關(guān)語言（Context Free Language，CFL）傻咖，ω 被稱為句子朋魔。
-
若 S=+>α ，α∈(N∪T)*卿操，則稱 α 為 G 的一個句型
其中：
- α∈(N∪T)*：推導(dǎo)過程中的 α 時終結(jié)符和非終結(jié)符組成的一個串警检。
- 句型可含終結(jié)符、非終結(jié)符害淤。而句子只能包含終結(jié)符扇雕，句子是句型的特例。
（句型窥摄，是句子的模型镶奉，有句子的結(jié)構(gòu)和特征，是句子的半成品）
在推導(dǎo)的過程中，若每次直接推導(dǎo)均替換句型中最左邊的非終結(jié)符哨苛，則稱為最左推導(dǎo)鸽凶。由最左推導(dǎo)產(chǎn)生的句型被稱為左句型。
右句型與之對稱建峭，最右推導(dǎo)也被稱為規(guī)范推導(dǎo)
例如：E => E+E => E+id // 規(guī)范推導(dǎo)
在玻侥？為啥從右往左叫規(guī)范？憑什么歧視左亿蒸？
其實(shí)這個和語法分析的方式有關(guān)凑兰。有兩種語法分析方式，分別是最左推導(dǎo)的自上而下方式和最右推導(dǎo)的自下而上方式边锁。前者雖然與人的思考方式類似姑食，但其實(shí)際的語法分析能力是比較差的，因此實(shí)際應(yīng)用中主要從下向上構(gòu)造語法樹茅坛。
下圖是自下而上構(gòu)造分析樹矢门，推導(dǎo)方式是自下而上。
總結(jié)一下這些奇奇怪怪的東西
推導(dǎo)灰蛙，就是得到 CFG 所定義的語言的過程。語言是一個集合隔躲，集合中的任何一個元素都是一個句子。推導(dǎo)過程中得到的串叫做句型，句型可以包含終結(jié)符和非終結(jié)符捞魁。
- 語言赠群，是以【從開始符號進(jìn)行至少一步推導(dǎo)得到的】終結(jié)符串為元素的集合；
- 推導(dǎo)浑吟，是 CFG 推導(dǎo)得到語言的過程笙纤，CFG 中的核心就是產(chǎn)生式；
- 產(chǎn)生式组力，是用于描述非終結(jié)符替換規(guī)則的式子省容；
- 分析語法，需要構(gòu)造語法分析樹燎字；
- “自上而下”腥椒、“自下而上” 都是語法分析的方式；
