資源描述：
《編譯原理第2章 編譯基礎(chǔ).ppt》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫(kù)。
1、第二章編譯基礎(chǔ)1§2.0概述對(duì)程序設(shè)計(jì)語(yǔ)言的描述是從語(yǔ)法、語(yǔ)義和語(yǔ)用三個(gè)因素來(lái)考慮。語(yǔ)法是對(duì)語(yǔ)言結(jié)構(gòu)的定義。語(yǔ)用則是從使用的角度去描述語(yǔ)言。語(yǔ)義是描述了語(yǔ)言的含義。2§2.0概述例如賦值語(yǔ)句s＝2*3.1416*r的非形式化的描述為：語(yǔ)法：賦值語(yǔ)句由一個(gè)變量，后隨一個(gè)賦值號(hào)“＝”，再在其后面跟一個(gè)表達(dá)式構(gòu)成。語(yǔ)義：首先計(jì)算語(yǔ)句右部表達(dá)式的值，然后把所得結(jié)果送給左部變量中。語(yǔ)用：賦值語(yǔ)句可用來(lái)計(jì)算和保存表達(dá)式的值。這種非形式化的描述,不夠清晰和準(zhǔn)確,為了精確定義和描述程序設(shè)計(jì)語(yǔ)言,需采用形式化的方法。3形式化方法：是用一整套帶有嚴(yán)格規(guī)定的符號(hào)體系來(lái)描述問(wèn)
2、題的方法?！?.1符號(hào)表一．符號(hào)串與字母表1．字母表：元素的非空有窮集合。兩含義：①字母表中至少包含一個(gè)元素。②字母表中元素可以是字母、數(shù)字或其它符號(hào)。例如：∑={a,b,c}42.符號(hào)（字符）：字母表中元素。3.符號(hào)串：用字母表中的符號(hào)組成的任何有窮序列，也稱字。例如：a,ab,bba,acab,…注意：①符號(hào)串中符號(hào)的順序是很重要的。②不包含任何符號(hào)的符號(hào)串稱空串，記為ε。
3、ε
4、=0③一個(gè)字母表上全部符號(hào)的集合是無(wú)窮的。54.符號(hào)串的前綴、后綴以及子串：設(shè)x是一符號(hào)串，例如：x=abc符號(hào)串的前綴：從x的尾部刪除若干個(gè)（>=0）符號(hào)后所余下的部分。
5、例如：ε，a，ab，abc符號(hào)串的后綴：從x的頭部刪除若干個(gè)（>=0）符號(hào)后所余下的部分。例如：ε，c，bc，abc子串：從x中刪除前綴和后綴之后所余下的部分。例如：ε，a，b，ab，bc，abc6二.符號(hào)串的運(yùn)算1．符號(hào)串的連接：設(shè)x，y是符號(hào)串，則串xy稱為它們的連接。例如：設(shè)x=myy=computerxy=mycomputeryx=computermy注意：對(duì)任意xXε=εX=X2．集合的和與乘積：設(shè)A，B是符號(hào)串的集合，則：A∪B={ω
6、ω∈A或ω∈B}AB={xy
7、x∈A且y∈B}例如：設(shè)A={a,b}B={c,d}則：A∪B={a,b,c
8、,d}AB={ac,ad,bc,bd}注意：Φ∪A=A∪Φ=AΦA(chǔ)=AΦ=Φ{ε}A=A{ε}=AΦ={}≠{ε}73.符號(hào)串的冪運(yùn)算：若x是符號(hào)串，則x0=ε,x1=x,x2=xx,…例如：設(shè)x=abc則：x0=ε,x1=abc,x2=abcabc,…4.集合的冪運(yùn)算：若A是符號(hào)串的集合，則A0={ε},A1=A,A2=AA,…例如：設(shè)A={a,b}則：A0={ε},A1={a,b},A2={aa,ab,ba,bb},…5.集合的A＋(正閉包)和A*（自反傳遞閉包）:設(shè)A為任一集合，則：A＋=A1∪A2∪A3∪…∪An∪…（A上所有符號(hào)串所組成的集合
9、）A*=A0∪A＋={ε}∪A＋例如：設(shè)A={a,b,c}A＋={a,b,c,aa,ab,ac,ba,bb,bc,…}A*={ε,a,b,c,aa,ab,ac,ba,bb,bc,…}8§2.2文法和語(yǔ)言的形式定義一．形式語(yǔ)言：是一字母表上按某種規(guī)則構(gòu)成的所有符號(hào)串的集合。反之，任一字母表上符號(hào)串的集合均可定義為一個(gè)形式語(yǔ)言。二．形式語(yǔ)言的描述：（三種方法）1．當(dāng)語(yǔ)言為有窮集合時(shí)，用枚舉法。例如：設(shè)有字母表A={a,b,c}則：L1={a,b}L2={a,aa,ab,ac}L3={c,cc}92．用文法描述語(yǔ)言例如：設(shè)有字母表∑={0，1}∑+={0，1
10、，00，01，11，10，000，100，…}用A表示∑+，A→0（定義為，生成，導(dǎo)出）用產(chǎn)生式表示∑+：A→0A→1A→A0A→A13．用自動(dòng)機(jī)識(shí)別語(yǔ)言：構(gòu)造一種裝置來(lái)識(shí)別語(yǔ)言，它可以判斷某符號(hào)串是否是該語(yǔ)言的句子。例如：1100→→是（接收）11ab→→不是（不接收）自動(dòng)機(jī)10三．文法的形式定義1．規(guī)則（產(chǎn)生式）：是一個(gè)符號(hào)與一個(gè)符號(hào)串的有序?qū)Γˋ，α），通常寫(xiě)作：A→α或A∷=α2．非終結(jié)符與終結(jié)符：非終結(jié)符：出現(xiàn)在規(guī)則左部能派生出符號(hào)或符號(hào)串的那些符號(hào)。通常用大寫(xiě)字母表示。終結(jié)符：是組成語(yǔ)言不可再分的基本符號(hào)，通常用小寫(xiě)字母表示。113．文法的
11、形式定義：是規(guī)則的非空有窮集合，通常定義為四元組：G[S]=（Vn，Vt，P，S）其中：Vn：規(guī)則中非終結(jié)符的集合。Vn={A}Vt：規(guī)則中終結(jié)符的集合。Vt={0，1}P：文法規(guī)則式的集合。P:A→0A→1A→A0A→A1S：文法的開(kāi)始符號(hào)（識(shí)別符號(hào)）由它開(kāi)始識(shí)別我們所定義的語(yǔ)言。S=A例1例2例3例4例5繼續(xù)12例1．設(shè)有字母表∑={a，b}，請(qǐng)為語(yǔ)言L={a2n,b2n
12、n>=1}設(shè)計(jì)一個(gè)文法。首先分析語(yǔ)言中串的結(jié)構(gòu)特征：L={aa,bb,aaaa,bbbb,…}（偶數(shù)個(gè)a或偶數(shù)個(gè)b組成）G[S]=（Vn，Vt，P，S）其中：Vn={A,B,D}
13、Vt={a，b}P:A→aa
14、aaB
15、bb
16、bbDB→aa
17、aaBD→bb
18、bbDS=A易錯(cuò)：
