二文法和语言PPT课件.ppt

第二章文法和语言2.1语言和文法的直观概念2.2符号和符号串2.3文法和语言的形式定义2.4文法的类型2.5上下文无关文法及其语法树2.6句型的分析2.1语言和文法的直观概念语义(semantics)分类:静态语义：一系列限定规则，确定哪些合乎语法的程序是合适的动态语义：表明程序要做什么描述工具:指称语义,操作语义等作用:检查类型匹配，变量作用域等文法的直观概念例:“我是大学生”是汉语的一个句子汉语句子的构成规则表示如下：〈句子〉∷=〈主语〉〈谓语〉〈主语〉∷=〈代词〉｜〈名词〉〈代词〉∷=我｜你｜他〈名词〉∷=王明｜大学生｜工人｜英语〈谓语〉∷=〈动词〉〈直接宾语〉〈动词〉∷=是｜学习〈直接宾语〉∷=〈代词〉｜〈名词〉例:“(34-3)*42”是一个表达式表达式的构成规则表示如下：Exp∷=ExpopExp|(Exp)|NumberOp∷=+|–|*由规则推导句子例如:句子“我是大学生”的推导过程如下：〈句子〉〈主语〉〈谓语〉〈代词〉〈谓语〉我〈谓语〉我〈动词〉〈直接宾语〉我是〈直接宾语〉我是〈名词〉我是大学生文法的作用严格定义句子的结构，是判断句子结构合法与否的依据用有穷的规则把无穷的句子集合描述出来2.2符号和符号串符号串定义:由字母表中的符号组成的任何有穷序列例：0,00,10是字母表∑={0‚1}上的符号串a,ab,aaca是Α={a‚b，c}上的符号串在符号串中，符号是有顺序的，顺序不同,代表不同的符号串，如:ab和ba不同不含任何符号的符号串称为空串，用ε表示注意:{ε}并不等于空集合{}符号串长度:符号串中含有符号的个数如:|abc|=3|ε|=0符号串的运算符号串的连接：设x、y是符号串,它们的连接是把y的符号写在x的符号之后得到的符号串xy例如x=ST，y=abu则xy=STabu显然εx=xε=x符号串的方幂：把符号串a自身连接n次得到的符号串an=aa…aa例如a1=aa2=aaa0=ε符号串集合：定义:若集合A中所有元素都是某字母表上的符号串，则称A为字母表上的符号串集合。符号串集合的乘积：符号串集合A和B的乘积定义为:AB={xy|x∈A且y∈B}，即AB是由A中的串x和B中的串y连接而成的串xy组成的集合。若集合A=ab,cdeB=0,1则AB=ab0,ab1,cde0,cde1显然{ε}A=A{ε}=A集合的闭包闭包集合Σ的闭包Σ*定义如下：Σ*=Σ0∪Σ1∪Σ2∪Σ3∪…例：设有字母表Σ={0，1}则Σ*=Σ0∪Σ1∪Σ2∪…={ε,0,1,00,01,10,11,000,…}即Σ*表示Σ上所有有穷长的串的集合。字母表上的一个语言是上的一些符号串的集合即是*的一个子集例如：Σ={a,b}Σ*={ε,a,b,aa,ab,ba,bb,aaa,aab,…}集合{ab,aabb,aaabbb,…,anbn,…}或{w|w∈Σ*且w=anbn,n≥1}为字母表上的一个语言。集合{a,aa,aaa,…}或{w|w∈Σ*且w=an,n≥1}为字母表上的一个语言ε是一个语言即是一个语言。2.3文法和语言的形式定义1．文法的定义说明:V=VN∪VT，V称为文法G的字母表P中产生式形如：α→β,其中α∈V+且至少含一个非终结符，β∈V*VN,VT和P是非空有穷集VN∩VT=φS是一个非终结符，且至少要在一条产生式的左部出现例1：文法G=(VN,VT,P,S)其中VN={S}，VT={0，1}，P={S->0S1,S->01}，开始符为S例2：文法G=(VN,VT,P,S)VN={标识符，字母，数字}，VT={a,b,c,…x,y,z,0,1,…,9}P={<标识符>→<字母>，<标识符>→<标识符><字母><标识符>→<标识符><数字>，<字母>→a,…,<字母>→z，<数字>→0,…,<数字>→9}，S=<标识符>2．文法的简化表示法3.推导(Derivation)与归约(Reduction)推导和归约若存在v=w0w1...wn=w,(n>0)则称v推导出w，或w归约到v,记为v=>+w若有v=>+w，或v=w，则记作v=>*w规范推导如果在推导的任何一步αβ，都是对α中的最左（最右）非终结符进行替换,则称这种推导为最左(最右)推导最右推导被称为规范推导例文法G：E→E+T|TT→T×F|FF→（E）|i“i+i×i”的推导过程如下：最左推导：E=>E+T=>T+T=>F+T=>i+T=>i+T×F=>i+F×F=>i+i×F=>i+i×i最右推导：E=>E+T=>E+T×F=>E+T×i=>E+F×i=>E+i×i=>T+i×i=>F+i×i=>i+i×i4．句型、句子、语言的定义提问语言的定义由文法G生成的语言记为L(G),它是文法G的一切句子的