考研復(fù)試六選四課件編譯原理文法

文法--1/6文法及其形式定義文法：所謂文法就是描述語言的語法結(jié)構(gòu)的形式規(guī)則。任何一個(gè)文法都可以表示為一個(gè)四元組G=(VT,VN,S,

)VT是一個(gè)非空的有限集合，它的每個(gè)元素稱為終結(jié)符號(hào)。

VN是一個(gè)非空的有限集合，它的每個(gè)元素稱為非終結(jié)符號(hào)。

VT∩VN=φ

S是一個(gè)特殊的非終結(jié)符號(hào)，稱為文法的開始符號(hào)。

是一個(gè)非空的有限集合，它的每個(gè)元素稱為產(chǎn)生式。產(chǎn)生式的形式為：

“

”表示“定義為”（或“由……組成”）

、

(VT∪VN)*

，

左部相同的產(chǎn)生式1、

2、……、

n可以縮寫

1|

2|……|

n“|”

表示“或”，每個(gè)

i(i=1,2,…,n)稱為

的一個(gè)候選式文法--2/6文法的分類

根據(jù)對(duì)產(chǎn)生式施加的限制不同，定義了四類文法和

相應(yīng)的四種形式語言類。文法類型產(chǎn)生式形式的限制文法產(chǎn)生的語言類

0型文法其中

,

(VT∪VN)*，|

|

0，

0型語言

中至少有一個(gè)非終結(jié)符號(hào)

1型文法，即

1型語言，即上下文有關(guān)文法

,

滿足0型文法的要求，并且

上下文有關(guān)語言|

|

|

|

2型文法，即A

2型語言，即上下文無關(guān)文法其中A

VN，

(VT∪VN)*

上下文無關(guān)語言

3型文法，即A

a或A

aB（右線性），或3型語言，即正規(guī)文法A

a或A

Ba（左線性）正規(guī)語言

（線性文法）其中A,B

VN，a

VT∪{

}文法--3/6上下文無關(guān)文法及相應(yīng)的語言所定義的語法單位(或稱語法實(shí)體)完全獨(dú)立于這種語法單位可能出現(xiàn)的上下文環(huán)境現(xiàn)有程序設(shè)計(jì)語言中，許多語法單位的結(jié)構(gòu)可以用上下文無關(guān)文法來描述。例：描述算術(shù)表達(dá)式的文法G：

G=({i,+,-,*,/,(,)},{<表達(dá)式>,<項(xiàng)>,<因子>},<表達(dá)式>,)其中

：<表達(dá)式>

<表達(dá)式>+<項(xiàng)>|<表達(dá)式>-<項(xiàng)>|<項(xiàng)><項(xiàng)>

<項(xiàng)>*<因子>|<項(xiàng)>/<因子>|<因子><因子>

(<表達(dá)式>)|i語言L(G)是所有包括加、減、乘、除四則運(yùn)算的算術(shù)表達(dá)式的集合。文法--4/6如果用“::=”代替“

”，這組產(chǎn)生式可以寫為：<表達(dá)式>::=<表達(dá)式>+<項(xiàng)>|<表達(dá)式>-<項(xiàng)>|<項(xiàng)><項(xiàng)>::=<項(xiàng)>*<因子>|<項(xiàng)>/<因子>|<因子><因子>::=(<表達(dá)式>)|i元符號(hào)：::=表示“定義為”或“由……組成”<……>表示非終結(jié)符號(hào)|表示“或”BNF（Backus-NormalForm）表示法

文法--5/6文法書寫約定終結(jié)符號(hào)次序靠前的小寫字母，如：a、b、c運(yùn)算符號(hào)，如：+、-、*、/各種標(biāo)點(diǎn)符號(hào)，如：括號(hào)、逗號(hào)、冒號(hào)、等于號(hào)數(shù)字1、2、…、9黑體字符串，如：id、begin、if、then非終結(jié)符號(hào)次序靠前的大寫字母，如：A、B、C大寫字母S常用作文法的開始符號(hào)小寫的斜體符號(hào)串，如：expr、term、factor、stmt文法--6/6終結(jié)符號(hào)串次序靠后的小寫字母，如：u、v、…