【正文】 〉 ?我是大學(xué)生 6 “我是大學(xué)生 ” 的構(gòu)成符合上述規(guī)則，而 “ 我大學(xué)生是 ” 不符合上述規(guī)則，我們說它不是句子。這里僅僅涉及漢語句子的結(jié)構(gòu)描述。 7 英語句子 sentence – subject verbphrase object subject – This | Computers | I verbphrase – adverb verb | verb adverb – never verb – is | run | am | tell object – the noun | a noun | noun noun – university | world | cheese | lies This is a university. Computers run the world. I am the cheese. I never tell lies. 8 語言概述 語言是由句子組成的集合，是由一組符號(hào)所構(gòu)成的集合。（各個(gè)記號(hào)和記號(hào)所表示的對(duì)象之間的關(guān)系） 語用 表示在各個(gè)記號(hào)所出現(xiàn)的行為中，它們的來源、使用和影響。 語言的實(shí)例若在語法上是正確的 ， 其相關(guān)聯(lián)的意義可以從兩個(gè)觀點(diǎn)來看 ， 其一是該句子的創(chuàng)立者所想要表示的意義 ， 另一是接收者所檢驗(yàn)到的意義 。 幽默 、 雙關(guān)語和謎語就是利用這兩方面意義間的差異 。 形式語言抽象地定義為一個(gè)數(shù)學(xué)系統(tǒng) 。 形式語言理論是對(duì)符號(hào)串集合的表示法 、 結(jié)構(gòu)及其特性的研究 。 13 有關(guān)定義和記號(hào) — 回 顧 符號(hào)：可以相互區(qū)別的記號(hào)（元素）。 符號(hào)串：由字母表 ?中的符號(hào)組成的任何有窮序列稱為該字母表上的符號(hào)串。 例如： Σ ={a,b} ε ,a,b,aa,ab,aabba… 都 是 ?上的符號(hào)串 14 有關(guān)定義和記號(hào) — 回 顧 符號(hào)串 s的頭（前綴）：移走符號(hào)串 s尾部的零個(gè)或多于零個(gè)符號(hào)得到的符號(hào)串 . 如： b是符號(hào)串 banana的一個(gè)前綴 . 符號(hào)串 s的尾（后綴）：刪去符號(hào)串 s頭部的零個(gè)或多于零個(gè)符號(hào)得到的符號(hào)串 . 如 :nana是符號(hào)串 banana的一個(gè)后綴 . 符號(hào)串 s的子串：從 s中刪去一個(gè)前綴和一個(gè)后綴得到的符號(hào)串 . 如 :ana是符號(hào)串 banana的一個(gè)子串 . 15 對(duì)于每個(gè)符號(hào)串 s， s和 ε 兩者 都 是符號(hào)串 s的前綴，后綴和子串。 ε 的長度為 0 連接：符號(hào)串 x、 y的連接 ,是把 y的符號(hào)寫在 x的符號(hào)之后得到的符號(hào)串 xy 如 x=ab,y=cd 則 xy=abcd 有 ε a = aε 方冪：符號(hào)串自身連接 n次得到的符號(hào)串 an 定義為 aa… aa n個(gè) a a1=a, a2=aa則 a0=ε 16 符號(hào)串集合：若集合 A中所有元素都是某字母表 ?上的符號(hào)串，則稱 A為字母表 ?上的符號(hào)串集合。 Σ *稱為 Σ 的閉包 。 Σ +稱為 Σ 的正閉包 。換言之 ,字母表 ?上 的一個(gè)語言是 ?上的一些符號(hào)串的集合 (字母表?上 的每個(gè)語言是 ?*的一個(gè)子集 )。 集合 {a,aa,aaa,… } 或 表示為 {w|w∈ Σ *且 w=an,n≥1} 為 字母表 ?上 的一個(gè)語言。 ?即 ? ?是一個(gè)語言 。 語言 L和 M的并為 L?M， 是一個(gè)語言 : {w|w is in L or is in M} 如： L1 ={a,b,… y,z} M1 ={1,2… 8,9 } L1?M1={a,b,… y,z， 1,2… 8,9 } 語言 L和 M的連接 是一個(gè)語言，記 為 LM LM={st |s∈ L且 t∈ M} 如： L1M1 ={a1,b1,… y1,z1,a2,b2… a9… z9} 有 L ?ε ?= ?ε ?L=L。語言的有窮表示有兩個(gè)途經(jīng)： 生成方式 （文法）：語言中的每個(gè)句子可以用嚴(yán)格定義的規(guī)則來構(gòu)造。） 22 文法即是生成方式描述語言的：語言中的每個(gè)句子可以用嚴(yán)格定義的規(guī)則來構(gòu)造 .下面給出文法的定義 .進(jìn)而在 文法的定義的基礎(chǔ)上 ,給出 推導(dǎo)的概念 ,句型、句子和語言的定義 . 23 定義 文法 G定義為四元組 (VN， VT， P， S )其中 VN為非終結(jié)符號(hào) (或語法實(shí)體，或變量 )集； VT為終結(jié)符號(hào)集； P為產(chǎn)生式 (也稱規(guī)則 )的集合； VN， VT和 P是 非空有窮集。 VN和 VT不含公共的元素，即 VN ∩ VT = φ 用 V表示 VN ∪ VT ，稱為文法 G的字母表或字匯表 規(guī)則 ，也稱 重寫規(guī)則 、 產(chǎn)生式 或 生成式 ，是形如α→ β或 α∷ =β的 (α， β)有序?qū)?，其?α是字母表 V的正閉包 V+中的一個(gè)符號(hào)， β是 V*中的一個(gè)符號(hào)。 24 Define a grammar A grammar G is defined as a 4tuple (VN， VT， P， S ) VN is a set of nonterminals VT is a set of terminals P is a set of productions， each production consists of a left side,an arrow(or ‘::=‘),and a right side S is a designation of one of the nonterminals as the start symbol V =VN ∪ VT is the alphabet of G 25 文法的定義 例 文法 G=（ VN， VT， P， S） VN = { S }, VT ={ 0, 1 } P={ S→ 0S1, S→ 01 } S為開始符號(hào) 例 文法 G=（ VN， VT， P， S） VN ={標(biāo)識(shí)符，字母，數(shù)字 } VT ={a,b,c,…x,y,z,0,1,…,9} P={標(biāo)識(shí)符 → 字母 標(biāo)識(shí)符 → 標(biāo)識(shí)符 字母 標(biāo)識(shí)符 → 標(biāo)識(shí)符 數(shù)字 字母 → a,…, 字母 →z 數(shù)字 →0, … , 數(shù)字 →9 } S=標(biāo)識(shí)符 27 文法的寫法 1 G： S→aA b A→ab A→aA b A→ ε 2 G[S]： A→ab A→aA b A→ ε S→aS b 3 G[S]： A→ab |aA b |ε S→aS b 元 符號(hào) : → ∷= | 習(xí)慣表示 大寫字母：終結(jié)符 小寫字母：非終結(jié)符 S – AB A – Ax | y B – z 29 推導(dǎo)的定義 直接推導(dǎo) “ ?” α → β 是文法 G的產(chǎn)生式，若有 v,w滿足：v=γ α δ ,w= γβδ, 其中 γ ∈V *,δ ∈V * 則稱 v直接 推導(dǎo) 到 w,記作 v ? w 也稱 w直接 歸約 到 v 例： G： S→ 0S1， S→ 01 0S1 ?00S11 00S11 ?000S111 000S111 ?00001111 S ?0S1 30 程序 ?分程序 . 分程序 . ? 變量說明部分 語句 . VAR標(biāo)識(shí)符 。BEGIN READ(標(biāo)識(shí)符 ) END. 31 推導(dǎo)的定義 若存在 v ?w0 ?w1 ?... ?wn=w,(n0) 則記為 v =+ w， v推導(dǎo)出 w，或 w歸約到 v 若有 v =+ w，或 v=w， 則記為 v =* w 32 例： G： S→ 0S1， S→ 01 0S1 ?00S11 00S11 ?000S111 000S111 ?00001111 S ?0S1 ?00S11 ?000S111 ?00001111 S =+ 00001111 S =* S 00S11 =* 00S11 33 What are Derivations Derivation is a way that a grammar defines a language .In the process of derivation a production is treated as a rewriting rule in which the nonterminal on the left side is replaced by the string on the right side of the production A production u – v is used by replacing an occurrence of u by v . Formally, if we apply a production p ??P to a string of symbols w in V to yield a new string of symbols z in V, we say that z derived from w using p, written as follows: w =p z . We also use: w = z z derives from w (production unspecified) w =* z z derives from w using zero or more productions w =+ z z derives from w using one or more productions 34 句型、句子的定義 句型 有文法 G，若 S =* x，則稱 x是文法 G的句型。 例： G： S→ 0S1， S→ 01 S ?0S1 ?00S11 ?000S111 ?00001111 G的句型 S,0S1 ,00S11 ,000S111,00001111 G的句子 00001111, 01 35 例： G[E]： E→E+T|T T→T*F|F F→(E)|a E?E+T ?T+T ?F+T ?a+T ?a+T*F ?a+F*F ?a+a*F ?a+a*a 句子：用符號(hào) a， +， *， (和 )構(gòu)成的算術(shù)表達(dá)式 36 文法，語言的定義 由文法 G生成的語言記為 L(G),它是文法 G的一切句子的集合 : L(G)={x|S =* x，其中 S為文法的開始符號(hào)，且 x ∈V T*} 例： G： S→ 0S1， S→ 01 L(G)={0n1n|n≥ 1} 例 文法 G[S]： （ 1） S→ aSBE （ 2） S→ aBE （ 3） EB→ BE （ 4） aB→ ab （ 5） bB→ bb （ 6） bE→