编译原理2.3.1-3_4-文法直观概念-形式定义.ppt

2.3程序语言的语法描述,2.3.1上下文无关文法2.3.2语法分析树与二义性2.3.3形式语言鸟瞰,2.3.1上下文无关文法,一、文法引入二、符号和符号串三、文法的直观概念四、文法和语言的形式定义,三、文法的直观概念,采用EBNF来表示英语中一种句子的构成规则:=wolf|goat|rabbit|tiger=the|a|an=gray|red=will=eat|like,补充例,用规则产生句子.(推导)使用一条规则,把左边的部分替换成右边的部分。用规则判别句子的合法性,：方括号表示其内的成分为任选项,判断一个符号串是否为语法上正确的,运用规则,把左边的部分替换成右边的部分,如果可以推导出(产生)该符号串,则该符号串是正确的句子可以图示化表示这种推导,得到语法分析树参考p27做练习:画出Thegraywolfwilleatthegoat.的语法树,有关文法概念的给出,=wolf|goat|rabbit|tiger,产生式,产生式,产生式,非终结符,终结符,开始符号(识别符号),文法G:一组非终结符,一组终结符,一个开始符号,一组产生式,终结符,终结符是组成语言的基本符号,不可再分割，不能由其它文法符号定义词法规则终结符是字母,数字,其他合法符号语法规则从语法分析的角度,终结符指单词符号,基本字,标识符,常数,算符,界符等,非终结符,非终结符:语法成分,语法短语，语法单位，语法变量，语法范畴，语法实体非终结符可由其它文法符号定义。不是用户自己写的非终结符给语言强加了一种层次结构每个非终结符表示一定符号串的集合,开始符号(识别符号),开始符号是我们最终感兴趣的语法范畴是文法最终要定义的语法结构,四、文法和语言的形式定义,产生式(规则)文法直接推导,直接归约推导,归约句型,句子语言文法等价(补充)最左推导,最右推导,1.文法,(a)文法的形式定义:G=(VT，VN，P，S)VNVT=V:文法符号的集合(文法G的字母表)V=VNVT(补充)语言LVT*,终结符号集合,非终结符号集合,产生式集合,开始符号,2.产生式,重写规则、产生式、生成式aproductionrule、arewritingrule有序对(，)(书上A)=：规则的左部V+：规则的右部V*,产生式可以递归,产生式左部的符号可以在右部出现.例:表达式的定义EiEE+EEE*EE(E),p28,(b)文法举例,文法G=(VN，VT，P，S)，VN=S，VT=0，1，P=S0S1，S01,补充例文法1,补充例文法2,文法G=(VN，VT，P，S)，VN=标识符，字母，数字，VT=a,b,c,，x,y,z,0,1,，9P=标识符字母标识符标识符字母标识符标识符数字字母a字母b字母z数字0数字1数字9S=标识符,(c)文法的写法,VNA,B,C,VTa,b,c,1,2,3,V,G=(S,A，a,b，P，S)，PSaAb，Aab，AaAb，A,补充:文法的写法1,VN,VT,G=(S,A，a,b，P，S)，P：SaAb，Aab，AaAb，A,补充:文法的写法2,G：SaAb，Aab，AaAb，A,GS：Aab，AaAb，A，SaAb,补充:文法的写法3,开始符号:第一条产生式的左部,开始符号,A1，A2，An缩写为：A1|2|n,GS：Aab|aAb|，SaAb,补充:文法的写法4,候选式,思考题,文法的形式定义对编译器有何作用?如何用文法阐明语言的语法?一个上下文无关文法如何定义语言?29举例G:EE+E|E*E|(E)|iEE+EE+ii+i从E到i+i的一个推导证明i+i是上述文法定义的一个表达式,3.直接推导,直接归约,文法G=(VT，VN，P，S)是一产生式,v=，w=即:vww是v的直接推导，v直接推出w,w直接归约到v,补充定义,A直接推出即:A,仅当A是一个产生式,且,V*,书上定义p29,思考题,是否正确?,直接推导举例,G1:S0S1S01G2:标识符字母标识符标识符字母标识符标识符数字字母a|b|z|A|B|Z数字0|1|9,4.推导出,归约到,序列12n称为1到n的一个推导或1推导出n,等价于:=或,推导举例,G1:S0S1S01G2:标识符字母标识符标识符字母标识符标识符数字字母a|b|z|A|B|Z数字0|1|9,5.句型,句子,设文法GS,如果S,V*称是文法GS的句型。若仅由终结符号组成,VT*称为GS的句子。例:G1:S0S1|01,判断对错,句子一定是句型。从识别符号推导出的所有符号串都是句型从识别符号推导出的所有由终结符组成的符号串都是句子。由终结符组成的字符串不一定是文法的句子。,6.语言L(G),L(G)=|S，且VT*L(G)=|S，且VT*,判断对错：语言是文法G从开始符号出发，推导出的所有句子的集合。2.语言是文法G所有句子的集合。,文法和语言题型,给文法,写语言给语言,写文法,文法和语言举例,G1:S0S1S01L(G1)=0n1n|n1,补充例文法和语言1,补充例文法和语言2,G=(VN，VT，P，S)，VN=S,B,E，VT=a,b,e，P:(1)SaSBE(2)SaBE(3)EBBE(4)aBab(5)bBbb(6)bEbe(7)eEee,L(G)=anbnen|n1,例2.1G1:SbA,AaA|aL(G1)=ban|n1,文法和语言举例p30,例2.2G2:SAB,AaA|a,BbB|bL(G2)=ambn|m,n1,例2.3构造一个文法G3,使L(G3)=anbn|n1G3:SaSb|ab,请写出描述以下语言的文法,L(G1)=anban|n1G1:SaAa,AaAa,AbL2=anbam|n,m1G2:SaS,SaB,BbC,CaC,Ca,补充,