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