语言分析基础小.ppt
1,第二章 语言分析基础,2,语言分析基础,文法和语言概述字母表和符号串文法和语言的形式定义文法的类型上下文无关文法及其语法树句型的分析有关文法实用中的说明,3,语言是由句子组成的集合，是由一组符号所构成的集合 字母表上的一个语言是上的一些符号串的集合 字母表上的每个语言是*的一个子集,2.3 文法和语言的形式定义,文法是对语言结构的定义与描述。（或称为“语法”）。,:=“=”:=“+”|“*”:=“(”“)”|,4,1.语法规则：我们通过建立一组规则，来描述句子的语法结构。规定用“:=”或“=”或“-”表示“由组成”。,:=:=|:=你|我|他:=王民|大学生|工人|英语:=:=是|学习:=|,2.3 文法和语言的形式定义,5,2.由规则推导句子：有了一组规则之后，可以按照一定的方式用它们去推导或产生句子。推导方法：从一个要识别的符号开始推导，即用相应规则的右部来替代规则的左部，每次仅用一条规则去进行推导。,=这种推导一直进行下去，直到所有带的符号都由终结符号替代为止。,2.3 文法和语言的形式定义,6,=,=,=我,=我,=我是,=我是,=我是大学生,:=:=|:=你|我|他:=王民|大学生|工人|英语:=:=是|学习:=|,推导方法：从一个要识别的符号开始推导，即用相应规则的右部来替代规则的左部，每次仅用一条规则去进行推导。,2.3 文法和语言的形式定义,我是大学生,7,例：有一英语句子：The big elephant ate the peanut:=:=:=the:=big:=elephant:=:=ate:=:=peanut,2.3 文法和语言的形式定义,8,:=:=:=the:=big:=elephant|peanut:=:=ate:=,=,=,=the,=the big,=the big elephant,=the big elephant,=the big elephant ate,=the big elephant ate,=the big elephant ate the,=the big elephant ate the peanut,2.3 文法和语言的形式定义,The big elephant ate the peanut,9,上述推导可写成=the big elephant ate the peanut,+,说明：(1)有若干语法成分同时存在时，我们总是从最左的语法成分进行推导，这称之为最左推导，类似有最右推导（规范推导）。(2)从一组规则可推出不同的句子，如以上规则还可推出“大象吃象”、“大花生吃象”、“大花生吃花生”等句子，它们在语法上都正确，但在语义上都不正确。,所谓文法是在形式上对句子结构的定义与描述，而未涉及语义问题。,2.3 文法和语言的形式定义,10,文法 GS=（VN，VT，P，S）VN：有穷非空的非终结符号集 VT：有穷非空的终结符号集，且VNVT=P：有穷非空产生式或规则的集合 S：开始符号（识别符号）SVN，S至少要在 一条规则中作为左部出现。,文法的形式定义,2.3 文法和语言的形式定义,11,终结符号(T)语言不可再分的基本符号，通常是一个语言的字母表。非终结符号(N)也称语法变量，它代表语法实体或语法范畴。,2.3 文法和语言的形式定义,VN VT称为文法的字母表，一般用V表示。,:或(VN VT)+且至少有一个非终结符，而(VN VT)*,例：Pa1，Pa2，Pan 缩写成：Pa1a2an,文法开始符号(S)一个特殊的非终结符，它就是语言的目标。规则(也称产生式或生成规则)是定义语法实体的一种书写规则。,12,例：G=（VN，VT，P，S）VN=S,VT=0,1,P=S0S1,S01，S为开始符号。,例：G=（VN，VT，P，S）VN=，VT=a,b,c,x,y,z,0,1,9 P=a,z 0,9 S=,2.3 文法和语言的形式定义,13,G=(VN,VT,S,P)，其中:VN=表达式VT=+,*,(,),iS=表达式P=表达式表达式+表达式 表达式表达式*表达式 表达式(表达式)表达式i,例：程序语言中只含+、*和（）运算的算术表达式，用i表示变量或常数，其文法可以表示为：,2.3 文法和语言的形式定义,14,产生式左边符号构成集合VN，且 S VN,VN：代表程序的语法成份，如“表达式”，它不会出现在程序中。VT：会出现在程序中，如 i+i,2.3 文法和语言的形式定义,15,终结符：一般用小写字母表示，如a、b、i 非终结符：一般用大写字母表示，如S、W、A 文法开始符S：第一条产生式的左部，或写成GS,2.3 文法和语言的形式定义,16,终结符集是输入字符集，它是构成单词的最基本元素,终结符集是经词法分析识别后的单词集，如变量i,运算符+、*和分界符(、)，它们被视为语法分析中最基本元素。,描述词法规则的文法,GS：SL|SL|SD La|b|z D0|1|9,2.3 文法和语言的形式定义,17,文法的表示方法:,3.语法图,2.EBNF(扩展的巴科斯范式),元符号：,:=,|,(,),1.BNF(巴科斯范式),元符号：,:=,|,2.3 文法和语言的形式定义,18,形式语言理论可以证明以下两点：（1）L(G)G1，G2，Gn；（2）G L（G）；已知语言，构造文法，无形式化方法，更多是凭经验；已知文法，求语言，通过推导。,2.3 文法和语言的形式定义,文法应满足两点要求：语言的所有的句子都能由文法的开始符号推导得到；由开始符号推导出来的所有终结符号串都是语言的句子。,注意：一种语言可由不同的文法产生，但一个文法描述的语言却是唯一的！,19,一般采用“凑规则”的方法来构造语言的文法，步骤如下：1.找出语言的若干典型句子；2.分析句子的特点；3.根据句子的特点凑规则；4.得到文法；5.检查文法。,2.3 文法和语言的形式定义,已知语言，构造文法,20,例：abna|n1,构造其文法,若n0，如何？,G1S：SaBa,B|bBG2S：SaBa,B|Bb,分组练习：anbn|n1，构造其文法,2.3 文法和语言的形式定义,已知语言，求文法,GS：S aSb|ab,GS:SaSB|ab aBab bBbb,GS：S AB A a|aAB B b,21,2.3 文法和语言的形式定义,练习1：构造标识符的文法（以字母开头的字母数字串）：,(1)为“标识符”构造文法规则：标识符字母|字母字母数字串 在构造过程中引入非终结符：字母（L），字母数字串（S）(ILLS)(2)对引入的非终结符进一步构造文法规则，此步反复。L：AZ，az(L a|b|z|A|B|Z)D：09(D 0|1|9)S:(L|D),(L|D)(L|D),(L|D)(L|D)(L|D),S,S,故：S(L|D)|(L|D)S,最后：GI:I L|LS,S(L|D)|(L|D)S,22,练习2：构造无符号整数的文法：,2.3 文法和语言的形式定义,G：|0|1|2|3|9,练习3：构造只含+、-、*、/、（）运算的算术表达式，用i表示变量或常数，构造其文法：,表达式(表达式)|表达式OP表达式OP+|-|*|/表达式 i,23,例：GS S:=aSb|ab求其所产生的语言。,若S:=aSb|，如何？,练习：GS S:=bA A:=aA|a,练习：GS S:=AB A:=aA|a B:=bB|b,2.2 文法和语言的形式定义,已知文法，求语言,24,2.3 文法和语言的形式定义,练习：文法G=(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 ee,S aSBE aaSBEBE aaaSBEBEBE aaaSBBEBEE aaaSBBBEEE aaaaBEBBBEEE aaaaBBEBBEEE aaaaBBBEBEEE aaaaBBBBEEEE aaaabBBBEEEE aaaabbBBEEEE aaaabbbBEEEE aaaabbbbEEEE aaaabbbbeEEE aaaabbbbeeEE aaaabbbbeeeE aaaabbbbeeee a4b4e4 同理：S anbnen,L(G)=anbnen|n1,25,如果是文法G=(VT，VN，S，P)的一个产生式，V*，有符号串x，y满足：x=，y=,则：称y是x的直接推导，也可以说，y直接归约到x，记作x y。,直接推导：用产生式的右部替换产生式的左部直接归约：用产生式的左部替换产生式的右部的过程,推导的形式定义,2.3 文法和语言的形式定义,26,2.3 文法和语言的形式定义,推导示例:,表达式 i+i*i 的推导如下：E E+E E+E*E E+E*i E+i*i i+i*i,表达式文法GE：E(E)|E+E|E*E Ei,G：S0S1 S01,0S1 00S1100S11 000S111000S111 00001111S 0S1,27,1 1 0,(5),=,(1),(3),(4),(2),当符号串已没有非终结符号时，推导就必须终止。因为终结符不可能出现在规则左部。,例：G：（1）（2）（3）（4）0|1|2|3|9,=,=,=,=,2.3 文法和语言的形式定义,28,语言是由文法开始符号推导出来的终结符号串组成的集合；文法GS所产生的所有句子的集合。,句子是所有终结符号组成的句型,语言的形式定义,2.3 文法和语言的形式定义,29,GE：EE+E|E*E|(E)|i,句型：E+EE+E*EE+E*iE+i*i,句子：i+ii*ii+i*i(i+i)*i,2.3 文法和语言的形式定义,句型、句子、语言示例：,L(G)=0n1n|n1,G：S0S1|01 S 0S1 00S11 000S111 00001111 G的句型：S,0S1,00S11,000S111,00001111 G的句子：01，0011，000111，00001111，,30,例：构造一个文法，使其描述的语言是无符号整数,GS：SSD|D D0|1|2|3|4|5|6|7|8|9,GS S L L L D|D D 0|1|2|3|4|5|6|7|8|9,定义：G和G是两个不同的文法，若 L(G)=L(G),则：G和G为等价文法。,2.3 文法和语言的形式定义,等价文法,文法等价是从语法上讲的，而不是语义上的等价；即：从两个文法得到的语言的句子在组成结构上是等价的，而含义上不一定等价。,31,给定x,G,求x L(G)?,x,算法1,算法2,x L(G)?,G,y,n,出错处理,停机,编译感兴趣的问题,2.3 文法和语言的形式定义,32,1.递归规则：规则右部有与左部相同的符号 左递归规则：AA 右递归规则：A A 自嵌入递归规则：A A,2.递归文法：含有递归规则的文法，为直接递归文法,ABaBAb,2.3 文法和语言的形式定义,递归文法,33,递归文法的优点：可用有穷条规则，定义无穷语言,例：对于前面给出的无符号整数的文法是有递归文法，用 12条规则就可以定义出所有的无符号整数。,!,GS：SSD|D D0|1|2|3|4|5|6|7|8|9,2.3 文法和语言的形式定义,若不用递归文法，那将要用多少条规则呢？,34,左递归文法的缺点：不能用自顶向下的方法来进行语法分析。,会造成死循环（后面将详细论述）,GE：Ei+I|i*I|(i+i)*i,该文法所描述的语言为L(G)=i+i,i*i,(i+i)*i，无法表示无穷的表达式语言。,2.3 文法和语言的形式定义,
