第三章文法和語法[lly]3

第3章文法和語言;1、語言;研究程序設計語言及研究的三個方面： 每個程序構成的規律(語法 Syntax)每個程序的含義(語義 Semantics)每個程序和使用者的關系(語用 Pragmatics)

語言三個方面定義：語法 -- 表示構成語言句子的各個記號之間的組合規律語義 -- 表示按照各種表示方法所表示的各個記號的特定含義。(各個記號和記號所表示的對象之間的關系)語用 --表示在各個記號所出現的行為中，它們的來源、使用和影響。;以自然語言為例(用 EBNF 描述一種語言：);〈句子〉 ? 〈主語〉〈謂語〉 ? 〈代詞〉〈謂語〉 ?　我〈謂語〉 ?　我〈動詞〉〈直接賓語〉 ?　我是〈直接賓語〉 ?　我是〈名詞〉 ?　我是大學生思考： “?”的含義？“我大學生是” 與“大學生是王明”是句子?;3、程序設計語言與文法關系：一個程序設計語言是一個記號系統，如自然語言一樣，由語句組成，完整的定義應包含語法與語義兩個方面。語法規定了語句形成的規則，(哪些符號序列是合法的，而與其含義無關)；語義不僅要限定語法規則(靜態)，而且要表明程序要做什么(動態)。文法是闡述語法規則的工具，是形式語言理論基礎。

為語言的語法描述尋求工具工具要對程序設計語言給出精確無二義的語法描述。(嚴謹、簡潔、易讀)形式工具--形式語言抽象地定義為一個數學系統。“形式”是指這樣的事實：語言的所有規則只以什麼符號串能出現的方式來陳述。;字母表?：元素的非空有窮集合。(符號集)符號：字母表中的元素。;例如： Σ={0,1}ε,0,1,00,01,11,1001110等都是?上的符號串.;2)串的頭與尾如果 z = xy 是一符號串，那么：x 是 z 的頭，y 是 z 的尾；如果 x 非空，那么 y 是固有尾；如果 y 非空，那么 x 是固有頭。;3、符號串的運算1)符號串的長度：符號串中符號的個數.符號串s的長度記為|s|。 ε的長度為02)連接：符號串x、y的連接,是把y的符號寫在x的符號之后得到的符號串xy例： x=ST,y=abu 則 xy=STabu |x|=2,|y|=3,|xy|=5 εx = xε= x3)方冪：符號串x自身連接n次得到的符號串 xx…xx(n個x)定義為 x n x0=ε, x1=x, x2=xx, x3=xxx x=AB, 則 x0=ε, x1=AB, x2=ABAB, x3=ABABAB對于 n>0, x n = xxn-1 = xn-1x 4)符號串集合：若集合A中一切元素都是某字母表?上的符號串，則稱A為字母表?上的符號串集合。;Σ* = Σ0 ∪ Σ1 ∪ Σ2 … ∪ Σn …Σ+ = Σ1 ∪ Σ2 … ∪ Σn …Σ* = Σ0 ∪ Σ+Σ+ = ΣΣ* = Σ* ΣΣ+ = Σ* -{ε};1、規則(重寫規則、產生式或生成式)： 是形如α→β或α∷=β的(α，β)有序對，其中α是某字母表V的正閉包V+中的一個符號，β是V*中的一個符號。(α∈V+，β∈V* why?) α稱為規則的左部(或生成式的左部)。 β稱為規則的右部(或生成式的右部)。

例：〈句子〉::= 〈主語〉〈謂語〉〈主語〉::= 〈代詞〉|〈名詞〉〈代詞〉::= 你 | 我 | 他;2、文法G定義為四元組(VN，VT，P，S)元素說明：VN ：非終結符集VT ：終結符集P：產生式(規則)集合S：開始符號(識別符號)VN、VT 和 P 是非空有窮集。S 至少在一條規則中作為左部出現。VN∩VT= φ， S∈VNV=VN∪VT，稱為文法G的字母表(字匯表);例3.2 文法G=(VN，VT，P，S)VN ={標識符，字母，數字}VT ={a,b,c,…x,y,z,0,1,…,9}P={→ →→ →a,…, →z →0,…, →9 }S=

思考： C語言的標識符(變量命名)如何用文法定義？;文法習慣上只將產生式寫出。并有如下約定：第一條產生式的左部是開始符號用尖括號括起的是非終結符，否則為終結符。或者大寫字母表示非終結符，小寫字母表示終結符G可寫成G[S]，其中S是開始符號;3、推導的定義;例 文法G=(VN，VT，P，S)VN ={標識符，字母，數字}VT ={a,b,c,…x,y,z,0,1,…,9}P={→ →→