編譯原理演示文稿2.ppt

《編譯原理演示文稿2.ppt》由會員上傳分享，免費在線閱讀，更多相關內(nèi)容在行業(yè)資料-天天文庫。

1、第二章文法和語言2.1文法的基本概念一個程序設計語言是一個記號系統(tǒng)，如自然語言一樣，它的完整的定義應包括語法和語義兩方面。所謂一個語言的語法是指一組規(guī)則，用它可以形成和產(chǎn)生一個合適的程序，目前在程序設計語言的識別中廣泛使用的是上下文無關的文法。在這理主要介紹文法和語言的概念。例：設有文法：<句子>→<主語><謂語><主語>→<冠詞><形容詞><名詞><冠詞>→the<形容詞>→big<謂語>→<動詞><直接賓語><動詞>→ate

2、caught<直接賓語>→<冠詞><名詞><名詞>→mouse

3、cat則：<句子>=><主語

4、><謂語>=><冠詞><形容詞><名詞><謂語>=>the<形容詞><名詞><謂語>=>thebig<名詞><謂語>=>thebigcat<謂語>=>thebigcat<動詞><直接賓語>=>thebigcatate<直接賓語>=>thebigcatate<冠詞><名詞>=>thebigcatatethe<名詞>=>thebigcatatethemouse2.1.1符號和符號串定義2.1字母表是有窮非空集合。用Σ表示。例：無符號二進制數(shù)的字母表為{0，1}C語言的字母表為字母、數(shù)字和若干專用符號組成的符號集定義2.2符號

5、串是由字母表中的符號組成的有窮序列，又稱字符串、串。例：a,b,c,ba,bbac,caacb,···等都是字母表{a,b,c}上的符號串定義2.3不包含任何字符串的空符號串用ε表示定義2.4符號串x的長度，即符號串x中的字符用

6、x

7、表示(讀作x的長度)例：

8、abc

9、=3

10、a

11、=1

12、ε

13、=0定義2.5設非空符號串u=xvy,其中v≠ε,則稱v為u的子串,若

14、u

15、>

16、v

17、則稱v為u的真子串定義2.6如果z=xy是一個符號串，則x是z和頭，而y是z的尾。如果x是非空的，那么y是固有尾；同樣如果y非空，那么x是固有頭。例：設z

18、=abc，那么z的頭是ε,a，ab，abc。除abc外，其它都是固有頭。z的尾是ε,c，bc，abc。z的固有尾是ε,c，bc定義2.7設x、y是同一字母表上的兩個符號串，把y的符號寫在X的符號之后得到的符號串，稱為的連接。記為xy例：x=ab，y=wabu則z=xy=abywabu顯然：

19、x

20、+

21、y

22、=

23、z

24、εx=xε=x定義2.8設x是符號串，把x自身連接n次得到符號串z,即z=xx···xx(n個x)，稱為符號串x的方冪,記為z=xn例：x0=εx1=xx2=xxx3=xxx···定義2.9符號串集合若集合A中的一

25、切元素都是其字母表上的符號串，則稱A為該字母表上的符號串集合。注意：ε、{ε}和Φ（表示空集）的區(qū)別定義2.10兩個符號串集合A和B的乘積AB定義為：AB={xy

26、x∈A且y∈B}例：設A={a,bc}，B=｛b,c,da｝則集合AB={ab,ac,ada,bcb,bcc,bcda｝。注意：由于εx=xε=x因此{ε}A=A{ε}=A，但ΦA=AΦ=Φ則：A0={ε}A1=AA2=AAAn=An-1A=AAn-1（n>0）顯然：Σ1是字母表中的所有單個字符組成的字符串Σ2是所有由字母表中二個的字符組成的字符串Σ3是所有由

27、字母表中三個的字符組成的字符串Σn是所有由字母表中長度為n的字符串集合定義2.11A的閉包A*=A0∪A1∪A2∪···A的正閉包A+=A1∪A2∪A3∪···顯然A+=AA*=A*AA*=A0∪A+由于一個字母表上的正閉包包含了該字母表中的符號所能組成的一切符號串，而語言是該字母表上的某些符號串的集合，因此，某個字母表上的語言是這個字母表上的正閉包的子集，而且通常是真子集。例：若Σ={0,1},則Σ*=｛ε,0,1，00,01，10,11,000，001，010,···｝例：令L={A,B,C,···,Z,a,b,··

28、·,z},D={0,1,···9}1.L∪D2.LD3.L44.L(L∪D)*5.D+6.D+∪L*則分別代表什么集合？1.字母或數(shù)字（包括ε）的集合2.由字母開頭后面跟一個數(shù)字的集合3.由４個字母組成的字符串的集合4.由字母開頭后面是字母數(shù)字（可省略）的集合5.數(shù)字串集合6.數(shù)字串和字母串集合（包括ε）約定：當對符號串z=xy的頭感興趣而對其余部分不感興趣時，可以采用省略寫法：z=x···；如果只是為了強調(diào)x在符號串z中的某處出現(xiàn)，則可表示為:z=···x···；如果只是為了強調(diào)x在符號串z中的末尾出現(xiàn)，則可表示為:z

29、=···x；2.1.2文法和語言的形式定義語言是字母表上的某些符號串集合，在這集合中的每個符號串都是按一定規(guī)則生成的。其規(guī)則最常用的是重寫規(guī)則（又稱產(chǎn)生式或生成式），它是形如α→β或α：：=β（α，β）的有序對，（讀作α定義為β），其中α稱為規(guī)則的左部，β稱為規(guī)則的右部。定義2.12文法G定義為四元組（Vn,Vt，P