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

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.产生式(规则)2.文法3.直接推导,直接归约4.推导,归约5.句型,句子6.语言7.文法等价(补充)8.最左推导,最右推导1.文法(a)文法的形式定义:G=(VT，VN，P，S)VN∩VT=φV:文法符号的集合(文法G的字母表)V=VN∪VT(补充)•语言LVT*终结符号集合非终结符号集合产生式集合开始符号2.产生式•重写规则、产生式、生成式aproductionrule、arewritingrule•有序对(α，β)•α→β(书上A→α)•α∷=β•α：规则的左部α∈V+•β：规则的右部β∈V*产生式可以递归•产生式左部的符号可以在右部出现.•例:表达式的定义E→iE→E+EE→E*EE→(E)p28(b)文法举例文法G=(VN，VT，P，S)，VN={S}，VT={0，1}，P={S→0S1，S→01}补充例文法1补充例文法2文法G=(VN，VT，P，S)，VN={标识符，字母，数字}，VT={a,b,c,…，x,y,z,0,1,…，9}P={〈标识符〉→〈字母〉〈标识符〉→〈标识符〉〈字母〉〈标识符〉→〈标识符〉〈数字〉〈字母〉→a〈字母〉→b…〈字母〉→z〈数字〉→0〈数字〉→1…〈数字〉→9}S=〈标识符〉(c)文法的写法•VN–A,B,C…,表达式,程序•VT–a,b,c,…,1,2,3,…•V–,,…G=({S,A}，{a,b}，P，S)，P＝{S→aAb，A→ab，A→aAb，A→ε}补充:文法的写法1VNVTG=({S,A}，{a,b}，P，S)，P：S→aAb，A→ab，A→aAb，A→ε补充:文法的写法2G：S→aAb，A→ab，A→aAb，A→εG[S]：A→ab，A→aAb，A→ε，S→aAb补充:文法的写法3开始符号:第一条产生式的左部开始符号A→α1，A→α2，…A→αn缩写为：A→α1|α2|…|αnG[S]：A→ab|aAb|ε，S→aAb补充:文法的写法4候选式思考题•文法的形式定义对编译器有何作用?•如何用文法阐明语言的语法?•一个上下文无关文法如何定义语言?29•举例G:E→E+E|E*E|(E)|iEE+EE+ii+i从E到i+i的一个推导证明i+i是上述文法定义的一个表达式3.直接推导,直接归约•文法G=(VT，VN，P，S)α→β是一产生式,v=γαδ，w=γβδ即:vww是v的直接推导，v直接推出w,w直接归约到v•γαδγβδ补充定义αAβ直接推出αγβ即:αAβαγβ,仅当A→γ是一个产生式,且α,β∈V*书上定义p29思考题•αα是否正确?直接推导举例G1:S→0S1S→01G2:〈标识符〉→〈字母〉〈标识符〉→〈标识符〉〈字母〉〈标识符〉→〈标识符〉〈数字〉〈字母〉→a|b|…|z|A|B|…|Z〈数字〉→0|1|…|94.推导出,归约到序列α1α2…αn称为α1到αn的一个推导或α1推导出αnn≥2一步或多步α1αn＋n≥1零步或多步α1αn*αβ等价于:α=β或αβ*＋推导举例G1:S→0S1S→01G2:〈标识符〉→〈字母〉〈标识符〉→〈标识符〉〈字母〉〈标识符〉→〈标识符〉〈数字〉〈字母〉→a|b|…|z|A|B|…|Z〈数字〉→0|1|…|95.句型,句子设文法G[S],如果Sα,α∈V*称α是文法G[S]的句型。若α仅由终结符号组成,α∈VT*称α为G[S]的句子。•例:G1:S→0S1|01*判断对错1.句子一定是句型。2.从识别符号推导出的所有符号串都是句型3.从识别符号推导出的所有由终结符组成的符号串都是句子。4.由终结符组成的字符串不一定是文法的句子。√√√√6.语言L(G)L(G)={α|Sα，且α∈VT*}L(G)={α|Sα，且α∈VT*}判断对错：1.语言是文法G从开始符号出发，推导出的所有句子的集合。2.语言是文法G所有句子的集合。*+√√文法和语言题型•给文法,写语言•给语言,写文法文法和语言举例G1:S→0S1S→01L(G1)={0n1n|n≥1}补充例文法和语言1补充例文法和语言2G=(VN，VT，P，S)，VN={S,B,E}，VT={a,b,e}，P:(1)S→aSBE(2)S→aBE(3)EB→BE(4)aB→ab(5)bB→bb(6)bE→be(7)eE→eeL(G)=｛anbnen|n≥1｝例2.1G1:S→bA,A→aA|aL(G1)={ban|n≥1}文法和语言举例p30例2.2G2:S→AB,A→aA|a,B→bB|bL(G2)={ambn|m,n≥1}例2.3构造一个文法G3,使L(G3)={anbn|n≥1}G3:S→aSb|ab请写出描述以下语言的文法•L(G1)={anban|n≥1}G1:S→aAa,A→aAa,A→b•L2={anbam|n,m≥1}G2:S→aS,S→aB,B→bC,C→aC,C→a补充7.文法等价(补充)•若L(G1)=L(G2)，则称文法G1和G2等价。等价•G[A]:A→0RA→01R→A1•G[S]:S→0S1S→018.最左推导,最右推导例G2:S→AB,A→aA|a,B→bB|b写出句子aabb的最左推导和最右推导序列符号辨析→::=|*+