第三章文法和语法[lly]3.pptVIP

第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|。 ε的长度为0 2）连接：符号串x、y的连接,是把y的符号写在x的符号之后得到的符号串xy例： x=ST,y=abu 则 xy=STabu |x|=2,|y|=3,|xy|=5 εx = xε= x 3）方幂：符号串x自身连接n次得到的符号串 xx…xx(n个x)定义为 x n x0=ε, x1=x, x2=xx, x3=xxx x=AB, 则 x0=ε, x1=AB, x2=ABAB, x3=ABABAB 对于 n0, 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∈VN V=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={标识符→字母 标识符→标识符字母 标识符→标识符数字 字母→a,…, 字母→z 数字→0,…, 数字→9