一、編譯過(guò)程與T形圖

1.編譯過(guò)程

從宏觀上講就是由高級(jí)語(yǔ)言生成機(jī)器碼的過(guò)程。

2.T形圖

二、自動(dòng)機(jī)基礎(chǔ)

1.文法定義：G=(VT,VN,P,S)

字母表：有窮符號(hào)集合。
乘積：連接。
正閉包與克林閉包：克林閉包多了一個(gè)空串。(所有不同長(zhǎng)度的字符串組成的集合)
G=(VT,VN,P,S)

• VT：終結(jié)符，a,b,c,id…
• VN：非終結(jié)符，通常用來(lái)描述終結(jié)符,E,T…
• P：產(chǎn)生式集合，描述將終結(jié)符和非終結(jié)符組合成串的方法。
• S：開(kāi)始符號(hào)，表示的是該文法中最大的語(yǔ)法成分。

2.推導(dǎo)與規(guī)約

+表示經(jīng)過(guò)正數(shù)次推導(dǎo)，*表示經(jīng)過(guò)若干次推導(dǎo)(多了一個(gè)0次)。

3.句型與句子

不包含非終結(jié)符的是句子，包含的是句型，句子是一個(gè)特殊的句型。

4.語(yǔ)言

由文法開(kāi)始符號(hào)推導(dǎo)出所有的句子構(gòu)成的集合稱(chēng)為該文法生成的語(yǔ)言。

5.文法分類(lèi)

是通過(guò)對(duì)產(chǎn)生式內(nèi)容的限制來(lái)劃分的。

(1)0型文法

無(wú)限制文法，a->b

，a中至少有一個(gè)非終結(jié)符。

(2)1型文法(上下文有關(guān)語(yǔ)言)

a->b

a中至少一個(gè)非終結(jié)符
且|a|<=|b|

(3)2型文法(上下文無(wú)關(guān)文法)

a->b

a中至少一個(gè)非終結(jié)符
|a|<=|b|
a只能是非終結(jié)符

(4)3型文法

a->b

a中至少一個(gè)非終結(jié)符
|a|<=|b|
a只能是非終結(jié)符
右線性：(a->w)||(a->wB) 左線性：(a->w)||(a->Bw)

(5)四種文法關(guān)系

6.上下文無(wú)關(guān)文法(CFG)分析樹(shù)

我們只對(duì)2型文法做研究。

(1)建樹(shù)規(guī)則

根節(jié)點(diǎn)符號(hào)為文法開(kāi)始符號(hào)。
子樹(shù)根節(jié)點(diǎn)為產(chǎn)生式左側(cè)，子節(jié)點(diǎn)從左到右構(gòu)成產(chǎn)生式右側(cè)。
葉節(jié)點(diǎn)既可以是終結(jié)符，也可以是非終結(jié)符。

(2)衍生概念

邊緣：從左到右排列葉子節(jié)點(diǎn)，得到符號(hào)串稱(chēng)為這棵樹(shù)的邊緣。
短語(yǔ)：分析樹(shù)中的每一個(gè)子樹(shù)的邊緣稱(chēng)為該句型的一個(gè)短語(yǔ)。
直接短語(yǔ)：子樹(shù)只有父子兩代節(jié)點(diǎn)，它的邊緣為一個(gè)直接短語(yǔ)。

7.二義性文法

形成多棵分析樹(shù)的文法是二義性文法，我們要避免。有一個(gè)充分條件，如果文法滿(mǎn)足，則為一個(gè)二義性文法。