高級語言及其文法(編輯修改稿)
2024-11-28 23:45 本頁面
【文章內(nèi)容簡介】 的一個(gè)出現(xiàn) 。 β∈( Ｖ T∪ Ｖ N)*。 α 稱為產(chǎn)生式 α → β的 左部 (Left Part)， β 稱為產(chǎn)生式 α → β 的 右部(Right Part)。 產(chǎn)生式定義各個(gè)語法成分的結(jié)構(gòu) （ 組成規(guī)則 ） 例 21 算術(shù)表達(dá)式的文法 ? 遞歸定義 —— 中綴表示 ? 標(biāo)識(shí)符 (id)（ 常數(shù)、變量）是表達(dá)式 (E)； ? 表達(dá)式加一個(gè)表達(dá)式是表達(dá)式； ? 表達(dá)式減一個(gè)表達(dá)式是表達(dá)式； ? 表達(dá)式乘一個(gè)表達(dá)式是表達(dá)式； ? 表達(dá)式除一個(gè)表達(dá)式是表達(dá)式； ? 表達(dá)式加上括號后是表達(dá)式； 例 21 算術(shù)表達(dá)式的文法 ? 考慮簡單算術(shù)表達(dá)式組成的語言 ? G =({id， +， *， (， )}， {E}， P， E) ? P: E→E + E ? E→E * E ? E→( E ) ? E→id ? 約定：只寫產(chǎn)生式 ? 簡寫 ? E → E + E | E * E | ( E ) | id （ ） 產(chǎn)生式的簡寫 ?對一組有相同左部的產(chǎn)生式 α→β 1， α→β 2… ， α→β n 可以簡單地記為： α→β 1|β 2|… |β n 讀作： α 定義為或者 β 1， 或者 β 2， … ，或者 β n。 并且稱它們?yōu)?α 產(chǎn)生式。 β 1，β 2， … ， β n稱為 候選式 (Candidate)。 基于產(chǎn)生式的變換 推導(dǎo)或歸約 ? E → E + E | E * E | ( E ) | id ? E由第一個(gè)候選式可以變成 E+E ? E+E中的第一個(gè) E由第二個(gè)候選式可以變成 E*E， 從而 E+E變成 E*E+E ? 根據(jù)第 4個(gè)候選式， E*E+E中的 E都可以變成 id: ? E*E+E 變成 id*E+E ? id*E+E變成 id*E+id ? id*E+id變成 id*id+id ? 也就是說，根據(jù)第 4個(gè)候選式， E*E+E經(jīng) 3步變換變成 id*id+id 直接推導(dǎo)與歸約 ? 根據(jù)產(chǎn)生式對符號串進(jìn)行變換的過程 ? Ａ → γ 是文法Ｇ的一個(gè)產(chǎn)生式， ? 且 α 、 β∈ （ Ｖ T∪ Ｖ N） *， ? 稱 α Ａ β 直接推導(dǎo) /派生 (Derive)出 αγβ ，也稱 αγβ 直接歸約 (Reduce)為 α Ａ β 。 ? 記為 α Ａ β ?αγβ ? 例： ? id + E?id + E * E （多步）推導(dǎo) ? α 0?α 1?α 2 ?… ?α n ? 記為 α 0?n α n (恰用 n步 ) ? α 0?+ α n （ 至少一步） ? α 0?* α n （ 若干步 :零步或多步） 推導(dǎo) /歸約舉例 E ? E + E （ 1） 串中含有變量 ? ? id + E （ 4） 串中含有變量 ? ? id + E * E （ 2） 串中含有變量 ? ? id + id * E （ 4） 串中含有變量 ? ? id + id * id （ 4） 串中沒有變量 ? 到此串中已經(jīng)沒有（語法）變量了，不能再推導(dǎo)了 ? E→E + E ? E→E * E ? E→( E ) ? E→id 句型與句子 ? E ?5 id + id * id ? 句子 :如果 S ?* x， 且 x∈ Ｖ T* ， 則稱 x是G產(chǎn)生的一個(gè) 句子 (Sentence) ? E ? E + E ?E + E * E ? E ?4 id + id * E ? 句型 :如果 S?*α ， α∈( Ｖ T∪ Ｖ N)*則稱 α是 G產(chǎn)生的一個(gè) 句型 (Sentential Form) 文法 G產(chǎn)生的語言 Ｌ (Ｇ )＝ {x｜ Ｓ ?* x and x∈ Ｖ T*} ?文法 E→E+E|E*E|(E)|id 可以派生出多少個(gè)句子？ ?文法 G的作用 —— 語言的有窮描述 ?以有限的規(guī)則描述無限的語言現(xiàn)象 ?有限： ?產(chǎn)生式集合、終結(jié)符集合、非終結(jié)符集合 ?無限： ?可以導(dǎo)出無窮多個(gè)句子（ L也可是有窮） id+id*id的不同推導(dǎo) E→E+E|E*E|(E)|id E ? E+E ? id+E ? id+E*E ? id+id*E ? id+id*id E ? E+E ? E+E*E ? E+E*id ? E+id*id ? id+id*id E ? E*E ? E+E*E ? E+id*E ? id+id*E ? id+id*id 不做限制 句型 (sentential Form) （ 歸約） E ?* id+id*id 施于最 右 變量 右句型 /規(guī)范句型 (canonical ~) (最左 /規(guī)范歸約 ) E ?+ id+id*id 施于最 左 變量 左句型 (left~) （ 最右歸約） E?5 id+id*id 最左推導(dǎo)與最右推導(dǎo) ?最左推導(dǎo) (Leftmost Derivation) ?每次推導(dǎo)都施加在句型的最左邊的語法變量上。 —— 與最右歸約對應(yīng) ?最右推導(dǎo) (Rightmost Derivation) ?每次推導(dǎo)都施加在句型的最右邊的語法變量上。 —— 與最左歸約（規(guī)范規(guī)約）對應(yīng)的規(guī)范 (Canonical)句型 短語 (Phrase) ?什么叫短語？ ? 如果 Ｓ ?* α Ａ β and A ?+γ ， 則稱 γ是句型 αγβ 的相對于變量 A的短語 ? 如果 Ｓ ?* α Ａ β and A ?γ ， 則稱 γ是句型 αγβ 的相對于變量 A的直接短語 ?最左直接短語叫做句柄 (Handle) 例： (直接 )短語 E?E+T ?T+T ?F+T ?(E)+T ?(E+T)+T ?(E+T)+T ?(T+T)+T ?(F+T)+T ?(id+T)+T ?(a+T*F)+T ?(a+F*F)+T ?(a+b*F)+T ?(a+b*c)+T ?(a+b*c)+F ?(a+b*c)+d E→E+T|T T→T* F|F F→( E )| id 句柄 (Handle)： 最左直接短語 ?E→E+T|T ?T→T* F|F ?F→( E )| id E?E+T ?T+T ?F+T ?(E)+T
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1