詞法分析與語(yǔ)法分析區(qū)別

• 詞法分析：字母是元素，組成字符串，記號(hào)的集合，線性結(jié)構(gòu)
• 語(yǔ)法分析：記號(hào)是元素，組成句子，句子的集合，樹(shù)結(jié)構(gòu)

詞法：構(gòu)詞規(guī)則和詞法分析（識(shí)別輸入序列）

語(yǔ)法：語(yǔ)法規(guī)則（上下文無(wú)關(guān)文法）和語(yǔ)法分析（下推自動(dòng)機(jī)，自上而下，自下而上分析等）

錯(cuò)誤處理方面的區(qū)別：

• 語(yǔ)法錯(cuò)誤：常見(jiàn)，方便診斷。
• 語(yǔ)義錯(cuò)誤：較難診斷。

上下文無(wú)關(guān)文法（CFG）

CFG是一個(gè)四元組G =（N，T，P，S），其中

1. N是非終結(jié)符（Nonterminals）的有限集合；
2. T是終結(jié)符（Terminals）的有限集合，且N∩T=Φ；
3. P是產(chǎn)生式（Productions）的有限集合，形如：A→α，其中A∈N（左部），α∈(N∪T)*（右部），若α=ε，則稱A→ε為空產(chǎn)生式（也可以記為A →）；
4. S是非終結(jié)符，稱為文法的開(kāi)始符號(hào)（Start symbol）。

產(chǎn)生式集表示

• 文法開(kāi)始符號(hào)S是第一個(gè)產(chǎn)生式的左部；
• N是可以出現(xiàn)在產(chǎn)生式左邊符號(hào)的記號(hào)集合；
• T是絕不出現(xiàn)在產(chǎn)生式左邊符號(hào)的記號(hào)集合；

產(chǎn)生式表示也稱為巴克斯范式，→用::=表示

產(chǎn)生式縮寫

左部非終結(jié)符相同可合并，右部是所有原來(lái)右部的或運(yùn)算（并），用|連接，注意，右部的每一個(gè)候選項(xiàng)具有平等的權(quán)利。

產(chǎn)生語(yǔ)言的基本方式-推導(dǎo)

從開(kāi)始符號(hào)開(kāi)始，反復(fù)使用產(chǎn)生式，得到終結(jié)符序列。

直接推導(dǎo)記作：αAβ=>αγβ。零步或多步推導(dǎo)，記為：α1=*>αn，其中α1=αn的情況為零步推導(dǎo)。若α1≠αn，即推導(dǎo)過(guò)程中至少使用一次產(chǎn)生式，則稱此過(guò)程為至少一步推導(dǎo)，記為：α1=+>αn。

上下文無(wú)關(guān)語(yǔ)言

由CFG G所產(chǎn)生的語(yǔ)言L(G)被定義為:
L(G) = { ω┃S=+>ω and ω∈T* }，
L(G)稱為上下文無(wú)關(guān)語(yǔ)言(Context FreeLanguage, CFL)，
ω稱為句子。 
若S=*>α，α∈(N∪T)*，則稱α為G的一個(gè)句型

最左推導(dǎo)產(chǎn)生左句型，最右推導(dǎo)產(chǎn)生右句型，最右推導(dǎo)也稱為規(guī)范推導(dǎo)。

分析樹(shù)

根由開(kāi)始符號(hào)標(biāo)記，葉子由終結(jié)符，非終結(jié)符，或ε標(biāo)記，內(nèi)部節(jié)點(diǎn)由一個(gè)非終結(jié)符標(biāo)記。父節(jié)點(diǎn)A->孩子節(jié)點(diǎn)XYZ...是一個(gè)產(chǎn)生式。若A→ε，則標(biāo)記為A的結(jié)點(diǎn)可以僅有一個(gè)標(biāo)記為ε的孩子。

葉子從左到右構(gòu)成句型，若僅由終結(jié)符標(biāo)記則構(gòu)成一個(gè)句子。

最左推導(dǎo)與最右推導(dǎo)的分析樹(shù)可能不同。

語(yǔ)法樹(shù)

根與內(nèi)部節(jié)點(diǎn)由表達(dá)式中的操作符標(biāo)記；葉子由表達(dá)式中的操作數(shù)標(biāo)記；用于改變運(yùn)算優(yōu)先級(jí)和結(jié)合性的括弧，被隱含在語(yǔ)法樹(shù)的結(jié)構(gòu)中。

分析樹(shù)與語(yǔ)法樹(shù)的區(qū)別

• 分析樹(shù)的內(nèi)部節(jié)點(diǎn)是非終結(jié)符；
• 語(yǔ)法樹(shù)的內(nèi)部節(jié)點(diǎn)是操作符（運(yùn)算符）；
• 或者說(shuō)語(yǔ)法樹(shù)中省略了反映分析過(guò)程的非終結(jié)符

二義性及其消除

二義性

一個(gè)句子可能對(duì)應(yīng)多顆分析樹(shù)，則該文法就是二義性的。

文法二義不一定所產(chǎn)生的語(yǔ)言二義。

消除二義性

1. 改寫。優(yōu)先級(jí)高的離開(kāi)始符號(hào)遠(yuǎn)，遞歸非終結(jié)符在終結(jié)符左邊，運(yùn)算具有左結(jié)合性，否則具有右結(jié)合性。
2. 規(guī)定符號(hào)的優(yōu)先級(jí)和結(jié)合性。

正規(guī)式到CFG的轉(zhuǎn)換

正規(guī)式描述的語(yǔ)言結(jié)構(gòu)均可用CFG描述，反之不一定。（CFG樹(shù)形結(jié)構(gòu)，正規(guī)式線性結(jié)構(gòu)，簡(jiǎn)單的可以用復(fù)雜的表示）

從正規(guī)式到CFG的轉(zhuǎn)換：

1. 構(gòu)造NFA，用a-->b的方式描述NFA.
2. 按照經(jīng)驗(yàn)描述。