編譯原理-第2章-文法和語言的基本知識課件

第2章文法和語言的基本知識本章是編譯原理課程的理論基礎(chǔ)，要求掌握形式語言的基本術(shù)語和概念,重點(diǎn)掌握短語、直接短語、句柄、素短語、規(guī)范推導(dǎo)、規(guī)范歸約。掌握文法和語言的定義，文法的二義性與遞歸性的判斷方法及句型的分析方法，文法分類。熟練使用文法定義程序設(shè)計(jì)語言的單詞和語法成分。對形式語言的理論有一個(gè)初步認(rèn)識。教學(xué)目標(biāo)Monday,December19,2022第2章文法和語言的基本知識本章是編譯原理課程的理論基礎(chǔ)，要12.1字母表和符號串的基本概念2.2文法和語言的形式定義2.3句型的分析2.4文法和語言的分類教學(xué)內(nèi)容Monday,December19,20222.1字母表和符號串的基本概念教學(xué)內(nèi)容Sunday,De2程序設(shè)計(jì)語言是一種形式語言，與自然語言既有相似的性質(zhì)又有本質(zhì)的不同。最主要的區(qū)別是：形式語言的規(guī)則簡單、嚴(yán)格、無例外、無二義性。編譯程序的正確轉(zhuǎn)換建立在對程序設(shè)計(jì)語言的精確定義和描述基礎(chǔ)上。語法——文法是描述語言語法的形式規(guī)則語義——語言中各語句的含義語用——從使用者的角度對語言的描述Monday,December19,2022程序設(shè)計(jì)語言是一種形式語言，與自然語言既有相似的性質(zhì)又有本質(zhì)3字母表：符號的非空有限集例：={0，1}

2.1字母表和符號串符號：字母表中的元素例：0，1符號串：由字母表中的符號組成的任何有窮序列例：0,1,01,10,011，..空符號串：無任何符號的符號串，用ε表示

C語言的字母表

A＝{a,b,…,0,1,…,9,+,－,×,_/,(,),=…if,else,for...}不對如={if,else,for,while}符號就是字符，對嗎？Monday,December19,2022字母表：符號的非空有限集例：={0，1}2.1字母4符號串的前綴和后綴:從符號串s的尾部刪去若干個(gè)(包括0個(gè))符號之后所余下的部分稱為s的前綴ε，0，01及011都是符號串011的前綴ε，1，11及011都是符號串011的后綴符號串集合：若集合A中的一切元素都是某字母表上的符號串，則稱A為該字母表上的符號串集合。例：={a，b，c}A={a,aa,ac}Monday,December19,2022符號串的前綴和后綴:ε，0，01及011都是5符號串的運(yùn)算符號串x和y的連接:是把y的符號寫在x的符號之后得到的符號串xy

例如x=00，y=11，則xy=0011對于任意一個(gè)符號串s，有εs=sε=s符號串的連接運(yùn)算Monday,December19,2022符號串的運(yùn)算符號串x和y的連接:是把y的符號寫在x的符號之后6符號串自身連接n次得到的符號串sn定義為ss…ss，包括n個(gè)s，稱為符號串的冪運(yùn)算

s0=ε，s1=s，s2=ss，……設(shè)s=01，則s0=εs1=01s2=0101……符號串的冪運(yùn)算Monday,December19,2022符號串自身連接n次得到的符號串sn定義為ss…ss，包7設(shè)A、B為符號串集合，則A和B的乘積定義為：AB＝{xy|x∈A,y∈B}例如，A＝{a,b}，B={c,d}則AB=符號串集合的乘積{ac,ad,bc,bd}

Monday,December19,2022設(shè)A、B為符號串集合，則A和B的乘積定義為：AB＝{xy8有符號串集合A，定義A0={ε},A1=A,A2=AA,A3=AAA,……An＝An-1A=AAn-1，n>0例如，A＝{0,1}，則A0=A1=A2=A3=符號串集合的冪運(yùn)算{ε}{0,1}{00,01,10,11}{000,001,010,011,100,101,110,111}Monday,December19,2022有符號串集合A，定義A0={ε},A1=A,9設(shè)A是符號串集合，定義

A＋＝A1∪A2∪A3∪……∪An∪…… 稱為集合A的正閉包。

A*＝A0∪A＋

稱為集合A的閉包。例：A={x,y}A＋＝？

A*＝？{x,y,xx,xy,yx,yy,xxx,xxy,xyx,xyy,……}

A1

A2

A3{ε,x,y,xx,xy,yx,yy,xxx,xxy,xyx,xyy,……}

A0A1

A2

A3符號串集合的閉包運(yùn)算Monday,December19,2022設(shè)A是符號串集合，定義例：A={x,y}{x,10Σ的閉包*表示上的一切符號串（包括ε）組成的集合Σ的正閉包+表示上的除ε外的所有符號串組成的集合例：Σ={a,b}Σ*={ε,a,b,aa,ab,ba,bb,aaa,aab,…}Σ+={a,b,aa,ab,ba,bb,aaa,aab,…}

Monday,December19,2022Σ的閉包*例：Σ={a,b}Sunday,Decembe11若A為某語言的字母表

A＝{a,b,…,0,1,…,9,+,－,×,_/,(,),=…if,else,for...}B為單詞集B={if,else,for,……,<標(biāo)識符>,<常量>,……}則BA*。語言的句子是定義在B上的符號串。若令C為句子集合，則CB*,程序C為什么對符號、符號串、符號串集合以及它們的運(yùn)算感興趣？Monday,December19,2022若A為某語言的字母表為什么對符號、符號串、符號串集合以及它們12語言是由句子組成的集合，是由一組符號所構(gòu)成的集合字母表上的一個(gè)語言是上的一些符號串的集合字母表上的每個(gè)語言是*的一個(gè)子集

集合{a,aa,aaa,…} 或表示為{w|w∈Σ*且w=an,n≥1}為字母表上的一個(gè)語言例如：字母表Σ={a,b},Σ*={ε,a,b,aa,ab,ba,bb,aaa,aab,…}

集合{ab,aabb,aaabbb,…,anbn,…}或表示為{w|w∈Σ*且w=anbn,n≥1}為字母表上的一個(gè)語言Monday,December19,2022語言是由句子組成的集合，是由一組符號所構(gòu)成的集合集合{a,a132.2文法和語言的形式定義文法是對語言結(jié)構(gòu)的定義與描述。（或稱為“語法”）。<賦值語句>::=<標(biāo)識符>“=”<表達(dá)式><表達(dá)式>::=<表達(dá)式>“+”<表達(dá)式>

|

<表達(dá)式>“*”<表達(dá)式><表達(dá)式>::=“(”<表達(dá)式>“)”|

<標(biāo)識符>

|

<整數(shù)>

|

<實(shí)數(shù)>

Monday,December19,20222.2文法和語言的形式定義文法是對語言結(jié)構(gòu)的定義與描述。14文法的直觀概念：以漢語中的“我是大學(xué)生”為例。采用BNF來表示漢語句子的構(gòu)成規(guī)則為：〈句子〉：：=〈主語〉〈謂語〉〈主語〉：：=〈代詞〉|〈名詞〉〈代詞〉：：=我|你|他〈名詞〉：：=王明|大學(xué)生|工人|英語〈謂語〉：：=〈動(dòng)詞〉〈直接賓語〉〈動(dòng)詞〉：：=是|學(xué)習(xí)〈直接賓語〉：：=〈代詞〉|〈名詞〉根據(jù)上述規(guī)則，“我是大學(xué)生”的構(gòu)成符合上述規(guī)則，而“我大學(xué)生是”不符合，我們說它不是句子。這些規(guī)則成為我們判別句子結(jié)構(gòu)合法與否的依據(jù)。換句話說，這些規(guī)則看成是一種元語言，用它描述漢語。這種的語言描述成為文法。

文法的四部分①一組終結(jié)符號（語言的基本符號）②一組非終結(jié)符號（語法單位）③一個(gè)開始符號（一個(gè)特殊的非終結(jié)符號，最感興趣的語法單位）④一組規(guī)則（也稱產(chǎn)生式或產(chǎn)生規(guī)則）Monday,December19,2022文法的直觀概念：以漢語中的“我是大學(xué)生”為例。采用BNF來15文法的形式定義：P10的定義1.1例2-1，文法G=（，，P，S）是描述標(biāo)識符的文法，則其中：={標(biāo)識符，字母，數(shù)字}

={a,b,c….x,y,z,0,1,2,3…9}P={<標(biāo)識符><字母>|<標(biāo)識符><字母>|<標(biāo)識符><數(shù)字><字母>a|b|c|….|z<數(shù)字>0|1|2|….|9}S=<標(biāo)識符>Monday,December19,2022文法的形式定義：P10的定義1.1Sunday,Decem16賦值語句標(biāo)識符表達(dá)式表達(dá)式表達(dá)式表達(dá)式標(biāo)識符整數(shù)標(biāo)識符表達(dá)式y(tǒng)=x+r*6y=x+r*6Monday,December19,2022賦值語句標(biāo)識符表達(dá)式表達(dá)式表達(dá)式表達(dá)式標(biāo)識符整數(shù)標(biāo)識符表達(dá)式17例：有一句子：“我是大學(xué)生”。這是一個(gè)在語法、語義上都正確定句子，該句子的結(jié)構(gòu)（稱為語法結(jié)構(gòu)）是由它的語法決定的。在本例中它為“主謂結(jié)構(gòu)”。如何定義句子的合法性？有窮語言：只需逐一列舉句子無窮語言：使用文法定義句子的結(jié)構(gòu)，用適當(dāng)條數(shù)的規(guī)則把語言的全部句子描述出來。文法是以有窮的集合刻劃無窮的集合的工具。文法的非形式定義Monday,December19,2022例：有一句子：“我是大學(xué)生”。這是一個(gè)18

1.語法規(guī)則：我們通過建立一組規(guī)則，來描述句子的語法結(jié)構(gòu)。規(guī)定用“::=”表示“由……組成”。<句子>::=<主語><謂語><主語>::=<代詞>|<名詞><代詞>::=你|我|他<名詞>::=王民|大學(xué)生|工人|英語<謂語>::=<動(dòng)詞><直接賓語><動(dòng)詞>::=是|學(xué)習(xí)<直接賓語>::=<代詞>|<名詞>文法的BNF表示Monday,December19,20221.語法規(guī)則：我們通過建立一組規(guī)則，來描述句子的語法結(jié)構(gòu)192.由規(guī)則推導(dǎo)句子：有了一組規(guī)則之后，可以按照一定的方式用它們?nèi)ネ茖?dǎo)或產(chǎn)生句子。推導(dǎo)方法：從一個(gè)要識別的符號開始推導(dǎo)，即用相應(yīng)規(guī)則的右部來替代規(guī)則的左部，每次僅用一條規(guī)則去進(jìn)行推導(dǎo)。<句子>=><主語><謂語><主語><謂語>=><代詞><謂語> …………這種推導(dǎo)一直進(jìn)行下去，直到所有帶<>的符號都由終結(jié)符號替代為止。Monday,December19,20222.由規(guī)則推導(dǎo)句子：有了一組規(guī)則之后，可以按照一定的方式<句20<句子>=><主語><謂語>=><代詞><謂語>=>我<謂語>=>我<動(dòng)詞><直接賓語>=>我是<直接賓語>=>我是<名詞>=>我是大學(xué)生<句子>::=<主語><謂語><主語>::=<代詞>|<名詞><代詞>::=你|我|他<名詞>::=王民|大學(xué)生|工人|英語<謂語>::=<動(dòng)詞><直接賓語><動(dòng)詞>::=是|學(xué)習(xí)<直接賓語>::=<代詞>|<名詞>推導(dǎo)方法：從一個(gè)要識別的符號開始推導(dǎo)，即用相應(yīng)規(guī)則的右部來替代規(guī)則的左部，每次僅用一條規(guī)則去進(jìn)行推導(dǎo)。Monday,December19,2022<句子>=><主語><謂語>=><代詞><謂語>21例：有一英語句子：Thebigelephantatethepeanut.<句子>::=<主語><謂語><主語>::=<冠詞><形容詞><名詞><冠詞>::=the<形容詞>::=big<名詞>::=elephant<謂語>::=<動(dòng)詞><賓語><動(dòng)詞>::=ate<賓語>::=<冠詞><名詞><名詞>::=peanutMonday,December19,2022例：有一英語句子：Thebigelephantate22<句子>=><主語><謂語>=><冠詞><形容詞><名詞><謂語>=>the<形容詞><名詞><謂語>=>thebig<名詞><謂語>=>thebigelephant<謂語>=>thebigelephant<動(dòng)詞><賓語>=>thebigelephantate<賓語>=>thebigelephantate<冠詞><名詞>=>thebigelephantatethe<名詞>=>thebigelephantatethepeanut<句子>::=<主語><謂語><主語>::=<冠詞><形容詞><名詞><冠詞>::=the<形容詞>::=big<名詞>::=elephant|peanut<謂語>::=<動(dòng)詞><賓語><動(dòng)詞>::=ate<賓語>::=<冠詞><名詞>Monday,December19,2022<句子>=><主語><謂語>=><冠詞><形容詞>23上述推導(dǎo)可寫成<句子>=>thebigelephantatethepeanut+說明：(1)有若干語法成分同時(shí)存在時(shí)，我們總是從最左的語法成分進(jìn)行推導(dǎo)，這稱之為最左推導(dǎo)，類似的有最右推導(dǎo)（一般推導(dǎo)）。(2)從一組規(guī)則可推出不同的句子，如以上規(guī)則還可推出“大象吃象”、“大花生吃象”、“大花生吃花生”等句子，它們在語法上都正確，但在語義上都不正確。所謂文法是在形式上對句子結(jié)構(gòu)的定義與描述，而未涉及語義問題。Monday,December19,2022上述推導(dǎo)可寫成<句子>=>thebigelephan24例2-3，利用例2-2中的文法，推導(dǎo)出文法的句子012：最左推導(dǎo)：N

=>S=>SD=>SDD=>DDD=>0DD=>01D=>012最右推導(dǎo)：N=>S=>SD=>S2=>SD2=>S12=>D12=>012在這里，NS為長度為1的推導(dǎo)，NSD為長度為2的推導(dǎo)N012為長度為7的推導(dǎo)。其中，對于NS來說，S是N的直接推導(dǎo)，或N是S的直接歸約。一些規(guī)定：=>推導(dǎo)=>規(guī)范推導(dǎo)長度大于零的推導(dǎo)長度可為零的推導(dǎo)長度為n的推導(dǎo)

NSSSD|DD0|1|2…|9Monday,December19,2022例2-3，利用例2-2中的文法，推導(dǎo)出文法的句子012：N25課堂作業(yè)：設(shè)有文法G[S]：S→a|ε|（T）T→T，S|S請給出句子（a,(a,a))的最左、最右推導(dǎo)。其最左推導(dǎo)為：S=>（T）=>（T，S）=>（S，S）=>（a，（T））=>（a，（T，S））=>（a，（S，S））=>（a，（a，S））=>（a，（a，a））其最右推導(dǎo)為：S=>（T）=>（T，S）=>（T，（T））=>（T，（T，S））=>（T，（T，a））=>（T，（S，a））=>（T，（a，a））=>（S，（a，a））=>（a，（a，a））=>（a，S）Monday,December19,2022課堂作業(yè)：其最左推導(dǎo)為：S=>（T）=>（T，S）=>（S26文法G[S]=（VN，VT，P，S） VN：非終結(jié)符號集 VT：終結(jié)符號集 P：產(chǎn)生式或規(guī)則的集合S：開始符號（識別符號）S∈VN，S至少要在一條規(guī)則中作為左部出現(xiàn)V＝VN∪VT稱為文法的字母表補(bǔ):規(guī)則的定義α::β或αβα∈V+且至少有一個(gè)非終結(jié)符，而β∈(VN∪VT)*

文法的形式定義Monday,December19,2022文法G[S]=（VN，VT，P，S）V＝VN∪VT補(bǔ):規(guī)27G=(VT,VN,S,P)，其中:VN={表達(dá)式}VT={+,*,(,),i}S=〈表達(dá)式〉P={〈表達(dá)式〉→〈表達(dá)式〉+〈表達(dá)式〉〈表達(dá)式〉→〈表達(dá)式〉*〈表達(dá)式〉〈表達(dá)式〉→(〈表達(dá)式〉)〈表達(dá)式〉→i}【例2.1】程序語言中只含+、*運(yùn)算的算術(shù)表達(dá)式，用i表示變量或常數(shù)，其文法可以表示為：

描述了表達(dá)式的語法規(guī)則Monday,December19,2022G=(VT,VN,S,P)，其中:【例2.1】程序語28幾點(diǎn)說明：產(chǎn)生式左邊符號構(gòu)成集合VN，且S∈VN給定一個(gè)文法，實(shí)際只需給出產(chǎn)生式集合，并指定識別符號G[表達(dá)式]:〈表達(dá)式〉→〈表達(dá)式〉+〈表達(dá)式〉〈表達(dá)式〉→〈表達(dá)式〉*〈表達(dá)式〉〈表達(dá)式〉→(〈表達(dá)式〉)〈表達(dá)式〉→iVN：代表程序的語法成份，如“＜表達(dá)式＞”，它不會(huì)出現(xiàn)在程序中VT：會(huì)出現(xiàn)在程序中，如i+iMonday,December19,2022幾點(diǎn)說明：產(chǎn)生式左邊符號構(gòu)成集合VN，且S∈VN給定29有些產(chǎn)生式具有相同的左部，可以和在一起G[E]：E→E+E|E*E|(E)|i

Monday,December19,2022有些產(chǎn)生式具有相同的左部，可以和在一起G[E]：Sunday30G[S]：S→L|SL|SDL→a|b|…|zD→0|1|…|9【例2.2】某種語言的標(biāo)識符是以字母開頭的字母數(shù)字串，如果用L表示<字母>，D表示<數(shù)字>，用S表示字母數(shù)字串描述了標(biāo)識符的詞法規(guī)則Monday,December19,2022G[S]：【例2.2】某種語言的標(biāo)識符是以字母開頭的字母數(shù)字31例：無符號整數(shù)的文法：G[<無符號整數(shù)>]<無符號整數(shù)>→<數(shù)字串><數(shù)字串>→<數(shù)字串><數(shù)字>|<數(shù)字><數(shù)字>→0|1|2|3|……|9描述了無符號整數(shù)的詞法規(guī)則Monday,December19,2022例：無符號整數(shù)的文法：描述了無符號整數(shù)的詞法規(guī)則Sunda32說明：終結(jié)符集是輸入字符集，它是構(gòu)成單詞的最基本元素終結(jié)符集是經(jīng)詞法分析識別后的單詞集，如變量i,運(yùn)算符+、*和分界符(、)，它們被視為語法分析中最基本元素描述語法規(guī)則的文法G[E]：E→E+E|E*E|(E)|i

描述詞法規(guī)則的文法G[S]：S→L|SL|SDL→a|b|…|zD→0|1|…|9Monday,December19,2022說明：終結(jié)符集是輸入字符集，它是構(gòu)成單詞的最基本元素終結(jié)符集33文法的表示方法3.語法圖2.EBNF：擴(kuò)充的BNF的元符號：<,>,::=,|,{,},[,](,)

字母

字母數(shù)字

數(shù)字

標(biāo)識符無符號整數(shù)1.BNF的元符號：<,>,::=,|Monday,December19,2022文法的表示方法3.語法圖2.EBNF：擴(kuò)充的BNF的元符34推導(dǎo)的形式定義如果α→β是文法G=(VT，VN，S，P)的一個(gè)產(chǎn)生式，γ，δ∈V*，有符號串x，y滿足x=γαδ，y=γβδ,xy則稱y是x的直接推導(dǎo)，也可以說，y直接歸約到x，記作xy。直接推導(dǎo)：用產(chǎn)生式的右部替換產(chǎn)生式的左部直接歸約：用產(chǎn)生式的左部替換產(chǎn)生式的右部的過程例：xSSDLDaDa1=yG[S]：S→L|SL|SDL→a|b|…|zD→0|1|…|9Monday,December19,2022推導(dǎo)的形式定義如果α→β是文法G=(VT，VN，S，P)的一35S=>SD,使用規(guī)則S→SD，其中γ=δ=ε；SD=>LD,使用規(guī)則S→L，其中γ=ε,δ=D；LD=>aD,使用規(guī)則L→a，其中γ=ε,δ=D；aD=>a1,使用規(guī)則D→1，其中γ=a,δ=ε。G[S]：S→L|SL|SDL→a|b|…|zD→0|1|…|9根據(jù)文法和推導(dǎo)的定義，可推出終結(jié)符號串如果α→β是文法G=(VT，VN，S，P)的一個(gè)產(chǎn)生式，γ，δ∈V*，有符號串x，y滿足x=γαδ，y=γβδ,xy則稱y是x的直接推導(dǎo)，也可以說，y直接歸約到x，記作xy。Monday,December19,2022S=>SD,使用規(guī)則S→SD，其中γ=δ=ε；G[S]36<無符號整數(shù)><數(shù)字串><數(shù)字串><數(shù)字><數(shù)字><數(shù)字>1<數(shù)字>10(6)==>==>(1)==>(3)(5)==>==>(2)當(dāng)符號串已沒有非終結(jié)符號時(shí)，推導(dǎo)就必須終止。因?yàn)榻K結(jié)符不可能出現(xiàn)在規(guī)則左部，所以將在規(guī)則左部出現(xiàn)的符號稱為非終結(jié)符號。例如：G[<無符號整數(shù)>](1)<無符號整數(shù)>→<數(shù)字串>(2)<數(shù)字串>→<數(shù)字串><數(shù)字>(3)<數(shù)字串>→<數(shù)字>(4)<數(shù)字>→0|1|2|3|……|9Monday,December19,2022<無符號整數(shù)><數(shù)字串>37如果存在直接推導(dǎo)序列：xy0y1y2…yn=y則稱這個(gè)序列是一個(gè)從x至y的長度為n（n>0）的推導(dǎo)，或稱y歸約到x，記作xy。若有xy，或x=y，則記作xy。＋=>

＋=>

*=>

例：xSSDLDaDa1=yG[S]：S→L|SL|SDL→a|b|…|zD→0|1|…|9＋=>

記作xy或記作xy*=>

例：xSSDLDaDa1=yG[S]：S→L|SL|SDL→a|b|…|zD→0|1|…|9＋=>

記作xy或記作xy*=>

Monday,December19,2022如果存在直接推導(dǎo)序列：＋＋*例：xSSD38文法G[S] （1）句型：x是句型

Sα,且α∈V*； （2）句子：x是句子

Sα,且α,∈VT*； （3）語言：L（G[S]）={α|α∈VT*,Sα}；++文法G[S]所產(chǎn)生的所有句子的集合*句子是所有終結(jié)符號組成的句型語言的形式定義G[E]：E→E+E|E*E|(E)|i

句型：E+EE+E*EE+E*iE+i*i句子：i+ii*ii+i*i(i+i)*iMonday,December19,2022文法G[S]++文法G[S]所產(chǎn)生的*句子是所有終結(jié)符39形式語言理論可以證明以下兩點(diǎn)：

（1）G→L（G）；

（2）L(G)→G1，G2，……，Gn；已知文法，求語言，通過推導(dǎo)；已知語言，構(gòu)造文法，無形式化方法，更多是憑經(jīng)驗(yàn)Monday,December19,2022形式語言理論可以證明以下兩點(diǎn)：Sunday,Dece40例：G[S]S::=aSb|ab求其所產(chǎn)生的語言。若S::=aSb|ε，如何？L(G[S])={anbn|n≥1}L(G[S])={anbn|n≥0}已知文法，求語言，通過推導(dǎo)課堂練習(xí)1：G[S]S::=bAA::=aA|aL(G[S])={ban|n≥1}課堂練習(xí)2：G[S]S::=ABA::=aA|aB::=bB|bL(G[S])={ambn|m,n≥1}Monday,December19,2022例：G[S]若S::=aSb|ε，如何？L(G[S41例：{abna|n≥1},構(gòu)造其文法定義.G和G’是兩個(gè)不同的文法，若L(G)=L(G’),則G和G’為等價(jià)文法。若n≥0，如何？課堂練習(xí)3：{anbnci|n≥1,i≥0},構(gòu)造其文法

G[S]：S→ABA→aAb|abB→cB|εG1[S]：S→aBa, B→b|bBG2[S]：S→aBa, B→b|BbG1[S]：S→aBa, B→ε|bBG2[S]：S→aBa, B→ε|BbMonday,December19,2022例：{abna|n≥1},構(gòu)造其文法42例：構(gòu)造一個(gè)文法，使其描述的語言是無符號整數(shù)。G[S]：S→SD|DD→0|1|2|3|4|5|6|7|8|9G[<無符號整數(shù)>]<無符號整數(shù)>→<數(shù)字串><數(shù)字串>→<數(shù)字串><數(shù)字>|<數(shù)字><數(shù)字>→0|1|2|3|……|9Monday,December19,2022例：構(gòu)造一個(gè)文法，使其描述的語言是無符號整數(shù)。G[S]：G43編譯感興趣的問題是:給定x,G,求xL(G)?x算法1算法2xL(G)?Gyn出錯(cuò)處理停機(jī)<賦值語句>∷=<標(biāo)識符>=<表達(dá)式>Monday,December19,2022編譯感興趣的問題是:給定x,G,求xL(G)?x441.遞歸規(guī)則：規(guī)則右部有與左部相同的符號 左遞歸規(guī)則：A→A…右遞歸規(guī)則：A→…A自嵌入遞歸規(guī)則：A→…A…遞歸文法2.遞歸文法：含有遞歸規(guī)則的文法，為直接遞歸文法A→BaB→Ab

G[S]：S→L|SL|SDL→a|b|…|zD→0|1|…|9間接遞歸文法Monday,December19,20221.遞歸規(guī)則：規(guī)則右部有與左部相同的符號遞歸文法2.遞歸文法45遞歸文法的優(yōu)點(diǎn)：可用有窮條規(guī)則，定義無窮語言例：對于前面給出的無符號整數(shù)的文法是有遞歸文法，用12條規(guī)則就可以定義出所有的無符號整數(shù)。若不用遞歸文法，那將要用多少條規(guī)則呢？!G[S]：S→SD|DD→0|1|2|3|4|5|6|7|8|9Monday,December19,2022遞歸文法的優(yōu)點(diǎn)：可用有窮條規(guī)則，定義無窮語言例：對于前46左遞歸文法的缺點(diǎn)：不能用自頂向下的方法來進(jìn)行語法分析會(huì)造成死循環(huán)（后面將詳細(xì)論述）G[E]：E→i+i|i*i|(i+i)*i該文法所描述的語言為L(G)={i+i,i*i,(i+i)*i}，無法表示無窮的表達(dá)式語言Monday,December19,2022左遞歸文法的缺點(diǎn)：不能用自頂向下的方法來進(jìn)行語法分析會(huì)造成死472.3句型的分析句型的分析：是指識別輸入的符號串是否為某一文法的句型(或句子)的過程對于同一個(gè)句型或句子，可以通過不同的推導(dǎo)序列推導(dǎo)出來，這是因?yàn)樵谕茖?dǎo)過程中所選擇的非終結(jié)符的次序不同

G[E]：E→E+E|E*E|(E)|ii+i*i的推導(dǎo)序列有哪些？

Monday,December19,20222.3句型的分析句型的分析：是指識別輸入的符號串是否為某48最左(右)推導(dǎo)指對于一個(gè)推導(dǎo)序列中的每一直接推導(dǎo)，被替換的總是當(dāng)前符號串中的最左(右)非終結(jié)符號。最右推導(dǎo)也稱為規(guī)范推導(dǎo)。規(guī)范推導(dǎo)的逆過程，稱為最左歸約，也稱為規(guī)范歸約。用最左推導(dǎo)所推導(dǎo)出的句型稱為最左句型用最右推導(dǎo)所推導(dǎo)出的句型稱為最右句型，通常稱為規(guī)范句型規(guī)范推導(dǎo)與規(guī)范歸約Monday,December19,2022最左(右)推導(dǎo)指對于一個(gè)推導(dǎo)序列中的每一直接推導(dǎo)，被替換的總49賦值語句標(biāo)識符表達(dá)式表達(dá)式表達(dá)式表達(dá)式標(biāo)識符整數(shù)標(biāo)識符表達(dá)式y(tǒng)=x+r*6語法分析的結(jié)果-----語法樹語法樹與文法的二義性Monday,December19,2022賦值語句標(biāo)識符表達(dá)式表達(dá)式表達(dá)式表達(dá)式標(biāo)識符整數(shù)標(biāo)識符表達(dá)式501.語法樹：描述一個(gè)句子的語法結(jié)構(gòu)<句子><主語><謂語><冠詞><形容詞><名詞><動(dòng)詞><賓語><冠詞><名詞>Thebigelephantatethepeanut語法成分（非終結(jié)符）單詞符號（終結(jié)符號)Monday,December19,20221.語法樹：描述一個(gè)句子的語法結(jié)構(gòu)<句子><主語><謂語><51語法樹：句子結(jié)構(gòu)的圖示表示法，它是一種有向圖，由結(jié)點(diǎn)和有向邊組成。

結(jié)點(diǎn)：符號 根結(jié)點(diǎn)：識別符號 中間結(jié)點(diǎn)：非終結(jié)符 葉結(jié)點(diǎn)：終結(jié)符或非終結(jié)符

有向邊：表示結(jié)點(diǎn)間的派生關(guān)系

SUVabcdMonday,December19,2022語法樹：句子結(jié)構(gòu)的圖示表示法，它是一種有向圖，由 結(jié)點(diǎn)：符52句型推導(dǎo)過程<==>句型語法樹的生長過程 由推導(dǎo)構(gòu)造語法樹1從識別符號開始，逐步建立推導(dǎo)序列。由根結(jié)點(diǎn)開始，自上而下建立語法樹。Monday,December19,2022句型推導(dǎo)過程<==>句型語法樹的生長過程 由推導(dǎo)構(gòu)造語法53例：G[<無符號整數(shù)>] 句型10[<無符號整數(shù)>]<無符號整數(shù)><數(shù)字串><數(shù)字串>==><數(shù)字串><數(shù)字><數(shù)字串><數(shù)字>==>0<數(shù)字串>0==><數(shù)字><數(shù)字>0==>110==>規(guī)范推導(dǎo)Monday,December19,2022例：G[<無符號整數(shù)>] 句型10[<無符號整數(shù)>]<無符號54 由語法樹構(gòu)造推導(dǎo)2自下而上地修剪子樹的末端結(jié)點(diǎn)，直至把整棵樹剪掉（留根），每剪一次對應(yīng)一次規(guī)約。從句型開始，自右向左地逐步進(jìn)行規(guī)約，建立推導(dǎo)序列。Monday,December19,2022 由語法樹構(gòu)造推導(dǎo)2自下而上地修剪子樹的末端結(jié)點(diǎn)，直至把55[<無符號整數(shù)>]<數(shù)字串><數(shù)字><數(shù)字串><數(shù)字>01<無符號整數(shù)>==><數(shù)字串><數(shù)字>==><數(shù)字串>0==>10<數(shù)字>0==><數(shù)字串>==>規(guī)范規(guī)約與規(guī)范推導(dǎo)互為逆過程Monday,December19,2022[<無符號整數(shù)>]<數(shù)字串><數(shù)字><數(shù)字串><數(shù)字>01<56課堂練習(xí)：對于句子i＋i*i，給出兩種不同的規(guī)范推導(dǎo)，并畫出語法樹定義:若一個(gè)文法的某句子存在兩個(gè)不同的最右(最左)推導(dǎo)，則該文法是二義性的，否則是無二義性的。2.文法的二義性G[E]：E→E+E|E*E|(E)|i

Monday,December19,2022課堂練習(xí)：定義:若一個(gè)文法的某句子存在兩個(gè)不同的最右(最左)57EEE+EE*iiiEEE*EE+iii這兩種不同的推導(dǎo)對應(yīng)了兩種不同的語法樹(1)E==>E+E==>E+E*E==>E+E*i==>E+i*i==>i＋i*i(2)E==>E*E==>E*i==>E+E*i==>E+i*i==>i＋i*iMonday,December19,2022EEE+EE*iiiEEE*EE+iii這兩種不同的推導(dǎo)對應(yīng)58若文法是二義性的，則在編譯時(shí)就會(huì)產(chǎn)生不確定性文法的二義性是不可判定的，即不可能構(gòu)造出一個(gè)算法，通過有限步驟來判定任一文法是否有二義性?？梢圆捎脙煞N途徑來解決文法的二義性問題1不改變文法中原有的規(guī)則，僅加進(jìn)一些語法的非形式規(guī)定。規(guī)定“*”運(yùn)算優(yōu)先級高于“+”運(yùn)算，且服從左結(jié)合改寫文法，把排除二義性的規(guī)則合并到原有文法中2Monday,December19,2022若文法是二義性的，則在編譯時(shí)就會(huì)產(chǎn)生不確定性可以采用兩種途徑59EiET+TF*iFTFi例:算術(shù)表達(dá)式的文法E::=E+T|TT::=T*F|FF::=(E)|iG[E]：E→E+E|E*E|(E)|i

Monday,December19,2022EiET+TF*iFTFi例:算術(shù)表達(dá)式的文法E::=60短語與句柄P18定義：設(shè)G[<S>]是一個(gè)文法，并設(shè)w=xuy是該文法的一個(gè)句型。若<S>*x<U>y且<U>+u，則稱u為句型w=xuy對非終結(jié)符<U>的一個(gè)短語。若<S>*x<U>y且<U>u，則稱u為句型w=xuy相對于非終結(jié)符<U>的一個(gè)簡單(直接）短語。任何一個(gè)句型的最左簡單短語稱為柄短語（句柄）。含有終結(jié)符的短語，并且不存在也具有這種性質(zhì)真子串的短語稱為素短語。P72Monday,December19,2022短語與句柄P18定義：設(shè)G[<S>]是一個(gè)文法，并設(shè)w=61例：表達(dá)式文法G[<E>]：<E>→<E>+<T>|<T> <T>→<T>*<F>|<F> <F>→(<E>)|i對句型i*(<E>)的推導(dǎo)為： <E><T><T>*<F><F>*<F>i*<F>i*(<E>)Monday,December19,2022例：表達(dá)式文法G[<E>]：Sunday,Decembe62對應(yīng)的推導(dǎo)樹為：表達(dá)式文法G[<E>]：<E>→<E>+<T>|<T><T>→<T>*<F>|<F><F>→(<E>)|iMonday,December19,2022對應(yīng)的推導(dǎo)樹為：表達(dá)式文法G[<E>]：Sunday,D63語法樹與短語使用推導(dǎo)樹計(jì)算句型（句子）的短語簡單、明了推導(dǎo)<S>*x<U>y <U>+u等價(jià)于： 等價(jià)于： <S> <U> x<U>y uMonday,December19,2022語法樹與短語使用推導(dǎo)樹計(jì)算句型（句子）的短語簡單、明了Sun64因此稱u是句型xuy(對<U>)的一個(gè)短語等價(jià)于： <S> x<U>y u以為子樹根的葉結(jié)點(diǎn)的全體<U>Monday,December19,2022因此稱u是句型xuy(對<U>)的一個(gè)短語以為子樹65若子樹高度為1，則u還是直接短語，最左直接短語為句柄。若u是含有終結(jié)符的最小的短語，則為素短語，句型最左邊的素短語稱為最左素短語（P72）。例：上例的文法G[<E>]和句型i*(<E>)容易從推導(dǎo)樹中看出：短語：i,i*(<E>),(<E>)直接短語：i，(<E>)句柄（左直接短語）：i素短語：i，(<E>)最左素短語：iMonday,December19,2022若子樹高度為1，則u還是直接短語，最左直接短語為句柄。若u66例，找出針對左邊文法的句型T+T*F+a的所有短語、簡單短語(直接短語)、素短語和句柄。此句型對應(yīng)的分析樹為：EE+TE+TTT*FFa短語：直接短語：句柄：E→E+TE→TT→T*FT→FF→（E）F→aTT*FT+T*FT+T*F+aaTT*FaT素短語：T*Fa最左素短語：T*FMonday,December19,2022例，找出針對左邊文法的句型T+T*F+a的所有短語、簡單短語67課堂練習(xí)設(shè)有文法G[E]如下：E→E+T|E-T|TT→T*F|T/F|FF→（E）|id請給出句型（F+id)-T*(E-T)的所有短語、簡單短語和句柄。EE-TTF（E）E+TTFFidT*F（E）E-T短語有：FidF+id(F+id)E-T（E-T）T*（E-T）（F+id)-T*(E-T)直接短語有：F,id,E-T句柄有：F素短語：idE-T最左素短語：idMonday,December19,2022課堂練習(xí)設(shè)有文法G[E]如下：EE-TTF（E）E+TTFF682.4文法和語言的分類

形式語言(喬姆斯基)：通過抽象，對語言進(jìn)行形式化描述用一組數(shù)學(xué)符號和規(guī)則來描述的語言稱為形式語言*的任何子集稱作上的形式語言L（G[S]）={α|α∈VT*,Sα}+由文法定義語言文法和語言分類：0型、1型、2型、3型這幾類文法的差別在于對產(chǎn)生式施加不同的限制。Monday,December19,20222.4文法和語言的分類形式語言(喬姆斯基)：通過抽69 0型語言：L00型文法稱為無約束短語結(jié)構(gòu)文法。規(guī)則的左部和右部都可以是符號串，一個(gè)短語可以產(chǎn)生另一個(gè)短語。 0型：P：α::=β 其中α∈V*且至少含有一個(gè)非終結(jié)符，β∈V*Monday,December19,2022 0型語言：L00型文法稱為無約束短語結(jié)構(gòu)文法。規(guī)則700型文法G[S]:S→ABS|ABAB→BAA→0B→1L(G[S])={x|x是由n個(gè)01或10組成的二進(jìn)制數(shù)字串，n≥1}該文法產(chǎn)生的語言為Monday,December19,20220型文法L(G[S])={x|x是由n個(gè)01或10組成的二進(jìn)71S→ACaBCa→aaCCB→DBaB→Ba CB→E

aD→DaAD→ACaE→EaAE→ε例：0型文法G[S]：Monday,December19,2022S→ACaB例：0型Sunday,December18,72 1型文法：P：αAβ::=αγβ 其中A∈VN，α，β∈V*，γ∈V＋

注意：規(guī)則的左邊的字符串長度≤右邊字符串長度1型語言：L1稱為上下文敏感或上下文有關(guān)。也即只有在α、β這樣的上下文中才能把A改寫為γMonday,December19,2022 1型文法：1型語言：L1稱為上73S→aSBES→aBEBE→bEaB→ab bB→bb bE→beeE→ee例：1型（上下文有關(guān)）文法G[S]：S→ACaBCa→aaCCB→DBaB→Ba CB→E

aD→DaAD→ACaE→EaAE→ε例：0型文法G[S]：Monday,December19,2022S→aSBE例：1型（上下文有關(guān)）文法G[S]：S→ACaB74 2型：P：A::=β 其中A∈VN， β∈V*2型語言：L2稱為上下文無關(guān)文法。也即把A改寫為β時(shí)，不必考慮上下文。Monday,December19,2022 2型：P：A::=β2型語75例：2型（上下文無關(guān)）文法

文法G[S]： S→AB A→BS|0 B→SA|1S→εMonday,December19,2022例：2型（上下文無關(guān)）文法Sunday,December762型（上下文無關(guān)）文法

文法G[S]： S→0A|1BA→1S|1B→0S|0該文法產(chǎn)生的語言為：L(G[S])={anbn|n≥1}Monday,December19,20222型（上下文無關(guān)）文法該文法產(chǎn)生的語言為：L(G[S])={77（右線性）

P：A:=a 或A::=aB其中A、B∈VNa∈VT 3型語言：L3又稱正則語言.3型文法稱為正則文法。它是對2型文法進(jìn)行進(jìn)一步限制。左線性和右線性文法是相互等價(jià)的

注意：每個(gè)產(chǎn)生式右邊至少有一個(gè)終結(jié)符出現(xiàn)（左線性）

P：A:=a 或A::=Ba其中A、B∈VNa∈VT 3型文法：Monday,December19,2022（右線性） 3型語言：L3又稱正則語言78G[S]： S→0A|1B|0 A→0A|1B|0S B→1B|1|0G[I]： I→lT I→l T→lT

T→dT

T→l

T→d

例：3型文法Monday,December19,2022G[S]： G[I]： I→lT例：3型文法Sunday793型文法(正則文法)

G[S]：S→0A|1B|0 A→0A|1B|0S B→1B|1|02型（上下文無關(guān)）文法G[S]：S→BAA→1S|1B→0S|01型（上下文有關(guān)）文法G[S]：S→aSBES→aBEBE→bEaB→ab bB→bb bE→beeE→ee0型文法G[S]：S→ACaBCB→E

Ca→aaCaD→DaCB→DBAD→ACaB→Ba aE→EaMonday,December19,20223型文法(正則文法) 2型（上下文無關(guān)）文法1型（上下文有80有關(guān)文法的實(shí)用限制1、若文法中有如U::=U的規(guī)則，則這就是有害規(guī)則，它會(huì)引起二義性，而無任何用處。例如存在U::=U，U::=a|b,則有兩棵語法樹：UaUUa文法中不能含有有害規(guī)則和多余規(guī)則Monday,December19,2022有關(guān)文法的實(shí)用限制1、若文法中有如U::=U的規(guī)則，則這就812、多余規(guī)則：（1）某條規(guī)則U::=u的左部非終結(jié)符U（U不是識別符號），不在任何其他規(guī)則右部出現(xiàn)，即所有的推導(dǎo)始終不會(huì)用到此規(guī)則。（2）在推導(dǎo)句子的過程中，一旦使用了該規(guī)則，將推不出任何終結(jié)符號串。即該規(guī)則中含有推不出任何終結(jié)符號串的非終結(jié)符。例如給定G[S]，若其中關(guān)于U的規(guī)則只有如下一條： U::=xUy該規(guī)則是多余規(guī)則。若還有U::=a，則此規(guī)則并非多余若某文法中無有害規(guī)則或多余規(guī)則，則稱該文法是壓縮過的。Monday,December19,20222、多余規(guī)則：例如給定G[S]，若其中關(guān)于U的規(guī)則82根據(jù)上述討論，L0L1L2L30型文法可以產(chǎn)生L0、L1、L2、L3，但2型文法只能產(chǎn)生L2，不能產(chǎn)生L1?！取取?型文法1型文法0型文法3型文法四種文法之間的逐級“包含”關(guān)系Monday,December19,2022根據(jù)上述討論，L0L1L2L3∪∪∪2型文832型文法（不確定的下推自動(dòng)機(jī)）1型文法（不確定的界限自動(dòng)機(jī)）0型文法（圖靈機(jī)）3型文法（有限自動(dòng)機(jī)）形式語言與自動(dòng)機(jī)Monday,December19,20222型文法（不確定的下推自動(dòng)機(jī)）1型文法（不確定的界限自動(dòng)機(jī)）84圖靈機(jī)Monday,December19,2022圖靈機(jī)Sunday,December18,2022852.5PL/0編譯程序概述PL/0編譯程序pcode解釋程序PL/0源程序pcode代碼PASCAL語言的子集，功能簡單，結(jié)構(gòu)清晰，可讀性強(qiáng)，具備了一般高級語言的必備部分Monday,December19,20222.5PL/0編譯程序概述PL/0編譯程序pcode解釋程86PL/0語言的功能（1）賦值語句；（2）語句串，即begin…end語句；（3）條件語句，即if語句；（4）循環(huán)語句，即while語句；（5）過程調(diào)用語句，即call語句；（6）輸入語句，即read語句；（7）輸出語句，即write語句。語句類型Monday,December19,2022PL/0語言的功能（1）賦值語句；語句類型Sunday,D87（1）常量說明（全局）（2）變量說明；（3）過程說明。說明類型數(shù)據(jù)類型整型Monday,December19,2022（1）常量說明（全局）說明類型數(shù)據(jù)類型整型Sunday,D88標(biāo)識符（字母開始的字母數(shù)字串）的有效長度是10數(shù)字最多為14位過程無參，可嵌套（最多三層）定義，可遞歸調(diào)用變量的作用域同PASCAL13個(gè)保留字：if,then,while,do,read,write,call,begin,end,const,var,procedure,oddMonday,December19,2022標(biāo)識符（字母開始的字母數(shù)字串）的有效長度是10Sunday,89PL/0程序示例consta=10;varb,c;procedurep;beginc:=b+aend;beginread(b);whileb#0dobegincallp;write(2*c);read(b)endend.不區(qū)分大小寫Monday,December19,2022PL/0程序示例consta=10;不區(qū)分大小寫Sund90EBNF在此基礎(chǔ)上又增加了三種元符號，約定如下：{}表示其內(nèi)語法成分可以重復(fù)例如：A→Aα|β，可改寫為：A→{α}β。[]表示方括號內(nèi)的成分為任選項(xiàng)；例如：A→αβ|α，可改寫為：A→α[β]。()例如：A→αβ1|αβ2|…|αβn，可改寫為：A→α(β1|β2|…|βn)PL/0語言的文法Monday,December19,2022EBNF在此基礎(chǔ)上又增加了三種元符號，約定如下：PL/0語言91<整數(shù)>∷=[+|-]<數(shù)字>{<數(shù)字>}

<數(shù)字>∷=0|1|2|3|4|5|6|7|8|9<整數(shù)>∷=[+|-]<非零數(shù)字>{<數(shù)字>}|0<非零數(shù)字>∷=1|2|3|4|5|6|7|8|9<數(shù)字>∷=0|1|2|3|4|5|6|7|8|9EBNF示例Monday,December19,2022<整數(shù)>∷=[+|-]<數(shù)字>{<數(shù)字>}

<數(shù)字>∷=0|92PL/0語言文法的EBNF表示

〈程序〉∷=〈分程序〉.

〈分程序〉∷=[〈常量說明部分〉][〈變量說明部分〉][〈過程說明部分〉]〈語句〉

〈常量說明部分〉∷=CONST〈常量定義部分〉{，〈常量定義〉}；

〈無符號整數(shù)〉∷=〈數(shù)字〉{〈數(shù)字〉}

〈變量說明部分〉∷=VAR〈標(biāo)識符〉{，〈標(biāo)識符〉}；

〈標(biāo)識符〉∷=〈字母〉{〈字母〉|〈數(shù)字〉}

……Monday,December19,2022PL/0語言文法的EBNF表示

〈程序〉∷=〈分程序〉.

〈93語句constidentnumber=,;varident，procedureident分程序分程序;;;分程序.程序語法圖Monday,December19,2022語句constidentnumber=,;varident，94PL/0程序示例－－改錯(cuò)vara,b,c;beginread(a,b);c=100if(a>0)then{b=b+1;write(b);}elsewrite(c);write(a,b,c);end.Monday,December19,2022PL/0程序示例－－改錯(cuò)vara,b,c;Sunday,95語法語義分析程序詞法分析程序表格管理程序出錯(cuò)處理程序代碼生成程序PL/0源程序目標(biāo)程序PL/0編譯程序的總體設(shè)計(jì)讀單詞生成目標(biāo)代碼核心一遍掃描方式Monday,December19,2022語法語義分析程序詞法分析程序出錯(cuò)處理程序代碼生成程序PL/096編譯程序總體流程圖Monday,December19,2022編譯程序總體流程圖Sunday,December18,97內(nèi)容：符號串和符號串集合的運(yùn)算、文法和語言的定義幾個(gè)重要概念：規(guī)范推導(dǎo)、規(guī)范歸約、遞歸文法、文法的二義性、短語、直接短語、句柄、素短語文法的BNF、EBNF、語法圖表示文法和語言的分類重點(diǎn)：在理解基本概念的基礎(chǔ)上根據(jù)給定的語言寫出文法、根據(jù)給定的文法確定語言判斷文法的二義性難點(diǎn)：關(guān)于文法和語言的概念是形式語言的理論基礎(chǔ)，形式語言抽象地定義為一個(gè)數(shù)學(xué)系統(tǒng)“形式”是指：語言的所有規(guī)則以符號串的方式來描述。文法就是這樣一個(gè)工具推導(dǎo)，文法與語言的相互轉(zhuǎn)換小結(jié)Monday,December19,2022內(nèi)容：小結(jié)Sunday,December18,202298自測2（做在書上），習(xí)題2、5、9作業(yè)題Monday,December19,2022自測2（做在書上），習(xí)題2、5、9作業(yè)題Sunday,De99第2章文法和語言的基本知識本章是編譯原理課程的理論基礎(chǔ)，要求掌握形式語言的基本術(shù)語和概念,重點(diǎn)掌握短語、直接短語、句柄、素短語、規(guī)范推導(dǎo)、規(guī)范歸約。掌握文法和語言的定義，文法的二義性與遞歸性的判斷方法及句型的分析方法，文法分類。熟練使用文法定義程序設(shè)計(jì)語言的單詞和語法成分。對形式語言的理論有一個(gè)初步認(rèn)識。教學(xué)目標(biāo)Monday,December19,2022第2章文法和語言的基本知識本章是編譯原理課程的理論基礎(chǔ)，要1002.1字母表和符號串的基本概念2.2文法和語言的形式定義2.3句型的分析2.4文法和語言的分類教學(xué)內(nèi)容Monday,December19,20222.1字母表和符號串的基本概念教學(xué)內(nèi)容Sunday,De101程序設(shè)計(jì)語言是一種形式語言，與自然語言既有相似的性質(zhì)又有本質(zhì)的不同。最主要的區(qū)別是：形式語言的規(guī)則簡單、嚴(yán)格、無例外、無二義性。編譯程序的正確轉(zhuǎn)換建立在對程序設(shè)計(jì)語言的精確定義和描述基礎(chǔ)上。語法——文法是描述語言語法的形式規(guī)則語義——語言中各語句的含義語用——從使用者的角度對語言的描述Monday,December19,2022程序設(shè)計(jì)語言是一種形式語言，與自然語言既有相似的性質(zhì)又有本質(zhì)102字母表：符號的非空有限集例：={0，1}

2.1字母表和符號串符號：字母表中的元素例：0，1符號串：由字母表中的符號組成的任何有窮序列例：0,1,01,10,011，..空符號串：無任何符號的符號串，用ε表示

C語言的字母表

A＝{a,b,…,0,1,…,9,+,－,×,_/,(,),=…if,else,for...}不對如={if,else,for,while}符號就是字符，對嗎？Monday,December19,2022字母表：符號的非空有限集例：={0，1}2.1字母103符號串的前綴和后綴:從符號串s的尾部刪去若干個(gè)(包括0個(gè))符號之后所余下的部分稱為s的前綴ε，0，01及011都是符號串011的前綴ε，1，11及011都是符號串011的后綴符號串集合：若集合A中的一切元素都是某字母表上的符號串，則稱A為該字母表上的符號串集合。例：={a，b，c}A={a,aa,ac}Monday,December19,2022符號串的前綴和后綴:ε，0，01及011都是104符號串的運(yùn)算符號串x和y的連接:是把y的符號寫在x的符號之后得到的符號串xy

例如x=00，y=11，則xy=0011對于任意一個(gè)符號串s，有εs=sε=s符號串的連接運(yùn)算Monday,December19,2022符號串的運(yùn)算符號串x和y的連接:是把y的符號寫在x的符號之后105符號串自身連接n次得到的符號串sn定義為ss…ss，包括n個(gè)s，稱為符號串的冪運(yùn)算

s0=ε，s1=s，s2=ss，……設(shè)s=01，則s0=εs1=01s2=0101……符號串的冪運(yùn)算Monday,December19,2022符號串自身連接n次得到的符號串sn定義為ss…ss，包106設(shè)A、B為符號串集合，則A和B的乘積定義為：AB＝{xy|x∈A,y∈B}例如，A＝{a,b}，B={c,d}則AB=符號串集合的乘積{ac,ad,bc,bd}

Monday,December19,2022設(shè)A、B為符號串集合，則A和B的乘積定義為：AB＝{xy107有符號串集合A，定義A0={ε},A1=A,A2=AA,A3=AAA,……An＝An-1A=AAn-1，n>0例如，A＝{0,1}，則A0=A1=A2=A3=符號串集合的冪運(yùn)算{ε}{0,1}{00,01,10,11}{000,001,010,011,100,101,110,111}Monday,December19,2022有符號串集合A，定義A0={ε},A1=A,108設(shè)A是符號串集合，定義

A＋＝A1∪A2∪A3∪……∪An∪…… 稱為集合A的正閉包。

A*＝A0∪A＋

稱為集合A的閉包。例：A={x,y}A＋＝？

A*＝？{x,y,xx,xy,yx,yy,xxx,xxy,xyx,xyy,……}

A1

A2

A3{ε,x,y,xx,xy,yx,yy,xxx,xxy,xyx,xyy,……}

A0A1

A2

A3符號串集合的閉包運(yùn)算Monday,December19,2022設(shè)A是符號串集合，定義例：A={x,y}{x,109Σ的閉包*表示上的一切符號串（包括ε）組成的集合Σ的正閉包+表示上的除ε外的所有符號串組成的集合例：Σ={a,b}Σ*={ε,a,b,aa,ab,ba,bb,aaa,aab,…}Σ+={a,b,aa,ab,ba,bb,aaa,aab,…}

Monday,December19,2022Σ的閉包*例：Σ={a,b}Sunday,Decembe110若A為某語言的字母表

A＝{a,b,…,0,1,…,9,+,－,×,_/,(,),=…if,else,for...}B為單詞集B={if,else,for,……,<標(biāo)識符>,<常量>,……}則BA*。語言的句子是定義在B上的符號串。若令C為句子集合，則CB*,程序C為什么對符號、符號串、符號串集合以及它們的運(yùn)算感興趣？Monday,December19,2022若A為某語言的字母表為什么對符號、符號串、符號串集合以及它們111語言是由句子組成的集合，是由一組符號所構(gòu)成的集合字母表上的一個(gè)語言是上的一些符號串的集合字母表上的每個(gè)語言是*的一個(gè)子集

集合{a,aa,aaa,…} 或表示為{w|w∈Σ*且w=an,n≥1}為字母表上的一個(gè)語言例如：字母表Σ={a,b},Σ*={ε,a,b,aa,ab,ba,bb,aaa,aab,…}

集合{ab,aabb,aaabbb,…,anbn,…}或表示為{w|w∈Σ*且w=anbn,n≥1}為字母表上的一個(gè)語言Monday,December19,2022語言是由句子組成的集合，是由一組符號所構(gòu)成的集合集合{a,a1122.2文法和語言的形式定義文法是對語言結(jié)構(gòu)的定義與描述。（或稱為“語法”）。<賦值語句>::=<標(biāo)識符>“=”<表達(dá)式><表達(dá)式>::=<表達(dá)式>“+”<表達(dá)式>

|

<表達(dá)式>“*”<表達(dá)式><表達(dá)式>::=“(”<表達(dá)式>“)”|

<標(biāo)識符>

|

<整數(shù)>

|

<實(shí)數(shù)>

Monday,December19,20222.2文法和語言的形式定義文法是對語言結(jié)構(gòu)的定義與描述。113文法的直觀概念：以漢語中的“我是大學(xué)生”為例。采用BNF來表示漢語句子的構(gòu)成規(guī)則為：〈句子〉：：=〈主語〉〈謂語〉〈主語〉：：=〈代詞〉|〈名詞〉〈代詞〉：：=我|你|他〈名詞〉：：=王明|大學(xué)生|工人|英語〈謂語〉：：=〈動(dòng)詞〉〈直接賓語〉〈動(dòng)詞〉：：=是|學(xué)習(xí)〈直接賓語〉：：=〈代詞〉|〈名詞〉根據(jù)上述規(guī)則，“我是大學(xué)生”的構(gòu)成符合上述規(guī)則，而“我大學(xué)生是”不符合，我們說它不是句子。這些規(guī)則成為我們判別句子結(jié)構(gòu)合法與否的依據(jù)。換句話