高級(jí)語言及其文法-資料下載頁
2024-10-23 23:45本頁面
【導(dǎo)讀】是人與人的通訊工具。計(jì)算機(jī)系統(tǒng)間、人機(jī)間通訊工具。數(shù)學(xué)語言（符號(hào)）：嚴(yán)格、準(zhǔn)確-形式化。高度的抽象，嚴(yán)格的理論基礎(chǔ)和方便的計(jì)。call過程名(參數(shù)表). 子組成的集合就是該文法產(chǎn)生的語言?？肆衷?951年到1956年間，從識(shí)別語言的。角度研究語言，給出了語言的另一種描述?？肆质窃谘芯可窠?jīng)細(xì)胞中，建立了自動(dòng)機(jī)，他用這種自動(dòng)機(jī)。1959年，Chomsky通過深入研究，將他本人的研究成果。20世紀(jì)50年代，人們用巴科斯范式（BackusNour. 這一成功，使得形式語言在20世紀(jì)60年。代得到了大力的發(fā)展。計(jì)算思維能力的培養(yǎng)，主要是由基礎(chǔ)理論系列課程實(shí)。它們構(gòu)成的是一個(gè)梯級(jí)訓(xùn)練系統(tǒng)。之為該字母表上的符號(hào)串,也稱作"字"。定義1設(shè)∑1、∑2是兩個(gè)字母表，∑1與∑2的乘積。{0,1}*={ε，0，1，00，01，11，000，
【正文】 a2,a1+ a2 *F, a2 *F a1, a2, a3, a2 * a3 a1+ a2 *a3 E E + T T F a1 T * F F a2 a3 ?a1+a2 *a3 短語 例 短語與分析樹 (文法 E→E+E|E*E|(E)|id ） E E + E id E E * id id 一棵子樹的葉子！ 二義性文法與先天二義性語言 ? 對(duì)同一句子存在兩棵語法分析樹 ? 在理論上不可判定 E E * E id E E + id id E E + E E E id * id id 1. 描述一個(gè)句子的文法不是唯一的； 2. 對(duì)于一個(gè)句子的分析應(yīng)是唯一的。 考慮表達(dá)式下面的文法 G[E],其產(chǎn)生式如下： E?E+E?E*E? (E) ? a 對(duì)于句子 a+a*a, 有如下兩個(gè)最左推導(dǎo)： E?E+E ?a+E ?a+E*E ?a+a*E ?a+a*a E ?E*E ?E+E*E ?a+E*E ?a+a*E ?a+a*a 文法的二義性 E?E+E ?a+E ?a+E*E ?a+a*E ?a+a*a E ?E*E?E+E*E ?a+E*E?a+a*E ?a+a*a E E + E E * E a a a E E * E + E E a a a 最左推導(dǎo) E?E+E ?E+E*E ?E+E*a ?E+a*a ?a+a*a E ?E*E?E*a ?E+E*a?E+a*a ?a+a*a E E + E E * E a a a E E * E + E E a a a 最右推導(dǎo) 如果一個(gè)文法的句子存在兩棵分析樹 ,那么 ,該句子是二義性的。如果一個(gè)文法包含二義性的句子 ,則稱這個(gè)文法是二義性的 。 否則，該 文法是無二義性的。幾點(diǎn)說明： 1 . 一般來說，程序語言存在無二義性文法， 對(duì)于表達(dá)式來說，文法（ 2 .1）是二義性的。對(duì)于條件語句，經(jīng)常使用二義性文法描述它： S? if expr then S ?if expr then S else S ? other 二義性的句子 : if e1 then if e2 then s1 else s2 二義性（歧義性， ambiquity)的定義 下面是 S?matched_s ? unmatched_s matched_s ?if expr then matched_s else matched_s ?other unmatched_s ?if expr then S ? if expr then matched_s else unmatched_s 它顯然比較復(fù)雜，因此： 2. 在能駕馭的情況下，使用 二義性文法 。 描述 if語句的無二義性文法的產(chǎn)生式 3. 對(duì)于任意一個(gè)上下文無關(guān)文法，不存在一個(gè)算法，判定它是無二義性的；但能給出一組充分條件，滿足這組充分條件的文法是無二義性的。 4. 存在先天二義性語言。例如， ?aibicj?i,j?1?? ?aibjcj?i,j?1? 存在一個(gè)二義性的句子 akbkck。 (抽象 )語法樹與分析樹不同 (語法 )分析樹 E E + id E + E E id id (抽象 )語法樹 + id + id id 文法的構(gòu)造 ? 明確描述對(duì)象 ── 語言 ? 合法的語言結(jié)構(gòu) ? 確定基本符號(hào)集Ｖ T ? 引入非終結(jié)符 ? 各種語法成分的結(jié)構(gòu) ? 定義句子的組成規(guī)則 ? BNF范式或產(chǎn)生式 文法舉例 ? {x|x是長(zhǎng)度為偶數(shù)的 0、 1串 } S→00S|01S|10S|11S|ε ? {0 m 1 n |m,n≥ 1} —— RL S→0S|0A A→1A|1 ? {0 n 1 n |n≥ 1} —— CFL S→0S1|01 ? {ww |w∈{a,b} +} —— PSL S→aCAE|bCBE Aa→aA Ab→bA AE→aRE RE→D aR→Ra bR→Rb CR→aCA|bCB Ba→aB Bb→bB BE→bRE aR→Ra bR→Rb CR→aCA|bCB aD→Da bD→Db ED→ε 例 27： {w|w為十進(jìn)制數(shù) } D →N| N →1|2|3|4|5|6|7|8|9 N →N0|N1|N2|N3|N4|N5|N6|N7|N8|N9 T → 1|2|3|4|5|6|7|8|9 T →0T|1T|2T|3T|4T|5T|6T|7T|8T|9T D →0||| 無用產(chǎn)生式與無用符號(hào) E → T | E + T | E T T → F | T * F | T / F F → ( E ) | id E → E | H + T T → FH | TQ+PF | EQF M → ( E ) | id 單一產(chǎn)生式 、 派生不出終極符號(hào)行 (H、 Q、 P)、從開始符號(hào)無法派生出來 (M) 值得注意的問題 ? 文法描述 ? 描述句子的組成規(guī)則 ， 不涉及語義 ? 文法正確不能保證語義正確（例） ? 明確目標(biāo) ? 要描述語言的結(jié)構(gòu) ? 確認(rèn)基本符號(hào)集 ? 合理引入非終結(jié)符（語義明確） 本章小結(jié)： ? 幾個(gè)基本概念 ? 文法是語言的一種有窮描述 ， 它嚴(yán)格 、準(zhǔn)確 、 簡(jiǎn)潔 。 ? 文法的形式定義 ? 句型 、 句子 、 語言 ? 文法的分類 ? ＣＦＧ的分析樹 習(xí)題 ? P174～ 175習(xí)題 ～ ? 1) 參照 ，寫出表達(dá)式 id*(id+id)*id的生成過程 (最左派生、最右派生 ) ? 2) 給定文法如下： ? E → T | E + T | E T ? T → F | T * F | T / F ? F → ( E ) | id ? 畫出表達(dá)式 id*(id+id)+id 的分析樹 ? 3) 判斷上題的文法屬于哪個(gè)類型的文法 ？ 為什么 ？
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1