第二章程式语言的语法.ppt
《第二章程式语言的语法.ppt》由会员分享,可在线阅读,更多相关《第二章程式语言的语法.ppt(43页珍藏版)》请在三一文库上搜索。
1、1,第二章 程式語言的語法,陳維魁 博士 .tw 儒林圖書公司,2,大綱,基本定義 文法四要素 文法的分類 正規文法分類 B.N.F. 文法 剖析樹,模擬兩可的文法 懸置else問題 描述程式語言語法的方式 語意的描述 精選習題,3,基本定義,字元集 一組有限符號的集合稱之為字元 集 字元集有二類 ASCII Code Set EBCDIC Code Set,4,ascii table,5,基本定義,ASCII Code Set American Standard Code for Information Interchange 的縮寫 標準的 ASCII Code 有7個位元 可表示 27
2、= 128 種不同的字元 一般使用在 IBM PC 及Apple II上 現今使用的 ASCII Code 已經擴充為8個位 元,稱之為 ASCII-8,6,基本定義,EBCDIC Code Set Extended Binary Code Decimal Interchange Code 的縮寫 標準的EBCDIC Code有8個位元 可表示 28=256 種不同的字元 一般使用在IBM 360及FACOM機器上,7,基本定義,字串(String) 定義 S=t1t2.tn, ti T 其中 T 為字元集 S 是由 T 中的字元所組成的一串列 n=4 則 S 可能為 abcd,ABCD,AE
3、FG 等等 字串的長度 設 S=t1t2.tn則 S 的長度可表為S=n S 的長度為 n,8,基本定義,字串的連接 設 p 與 q 為二字串且 p=m1m2mu ,q=n1n2nv pq=m1m2.mun1n2.nv 表示二字串的連接且pq=u+v pq 字串的長度為 u+v,9,基本定義,空字串 通常以 “” 表示空字串,且=0, 有時空字串也可以 “”表示,10,基本定義,T 由 T 中的字元所組成任意長度 的字串的集合 實例 假設 T=p,q 則 =,p,q,pp,qq,pq,qp,pppp.,11,基本定義,語言 (Language) 若 L 為一語言,則 L 是 的一組子集合(su
4、bset) 實例 假設 T=p,q 則 L 可為 p,pq,qp,.或 ppp,qqq,pqp,qpq,. 等等 只要是 的子集合即可,12,基本定義,語言的乘積(product) L1 與 L2 的乘積 L1L2=aba L1,b L2 範例 L1=p,q L2=m,n,mn,nm L1L2=pm,pn,pmn,pnm,qm,qn, qmn,qnm,13,基本定義,語言 L 的次方 (Power) 定義 Lo= Ln=LLn-1 範例 假設 L=p,pq,q L0= , L1=L,L2=LL,.,14,基本定義,L*的定義 L* 又稱“Kleene Closure of L” L 做任意次乘
5、積(product) 的集合 L*=L0L1L2.Ln.,15,基本定義,L+ 的定義 又稱為“Transitive Closure of L” L+=L1L2L3.Ln.,16,文法四要素,T 終端符號 表示不能再以其他符號來替代 N 非終端符號 表示可以再以其他符號來替代 而N與T須具以下的關係:NT=,17,文法四要素,S starting symbol 起始符號 從事文法推演之步驟由S開始 P production rule 文法產生規則,18,文法的分類,Type 0 無任何限制 Type 1 Context sensitive grammar Type 2 Context free
6、 grammar Type 3 正規文法 (regular grammar),19,正規文法分類,右線性正規文法 right linear regular grammar 文法產生規需滿足 AuB or A u,其中 A,BN,u T 左線性正規文法 left linear regular grammar 文法產生規則需滿足 uAB or A u,其中 A,BN,u T,20,B.N.F. 文法,B.N.F. grammar Backus Naur Form grammar type 2 grammar context-free grammar,21,B.N.F.文法符號,“:=” 表示“定義
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 第二 章程 语言 语法
链接地址:https://www.31doc.com/p-2581845.html