资源描述：
《形式语言概述.ppt》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。
1、第七章 句法结构模式识别形式语言概述文法推断句法分析自动机理论误差校正句法分析§7-1形式语言概述一、基本概念1、字母表：与所研究的问题有关的符号集合。例：V1={A,B,C,D},V2={a,b,c,d}2、句子(链)：由字母表中的符号所组成的有限长度的符号串。3、句子(链)的长度：所包含的符号数目。例:
2、a3b3c3
3、=94、语言：由字母表中的符号组成的句子集合，用L表示。例：字母表V={a,b}L1={ab,aab,abab}有限语言L2={anbm
4、n,m=0,1,2….}无限语言5、文法：在一种语言中，构成句子所必须
5、遵循的规则的集合，用G表示。L(G)表示由文法G构成的语言。6、V*:由字母表V中的符号组成的所有句子的集合，包括空句子λ在内。例：V*＝{λ,01,001}7、V＋:不包括空句子在内的句子集合，即V＋＝V*－(λ)8、VT:终止符，不能再分割的最简基元的集合，用小写字母表示。VT={a,b,c}9、VN:非终止符，由基元组成的子模式和句子的集合。用大写字母表示。VN={A,B,C}VT，VN的关系：VT∩VN=Φ(空集)VT∪VN=V（全部字母表）10、产生式(再写规则)P：存在于终止符和非终止符间的关系式。例：α→β，α∈VN，β∈VN
6、,VT.11、文法的数学定义：它是一个四元式，由四个参数构成。G={VN,VT,P,S}二.短语结构文法1.0型文法（无限制）设文法G=(VN,VT,P,S)VN：非终止符，用大写字母表示VT：终止符，用小写字符表示P：产生式S：起始符产生式P：α→β，其中α∈V+，β∈V*α，β无任何限制(V+不包括空格,V*包括空格)例：0型文法G=(VN,VT,P,S)VN={S,A,B}VP={a,b,c}P:①S→aAbc②Ab→bA③Ac→Bbcc④bB→Bb⑤aB→aaA⑥aB→λ(空格)S→Aabc→abAc→abBbcc→aBbbcc→b
7、bcc此文法可以产生：X=anbn+2cn+2n≥0X
8、n=0=bbcc由0型文法产生的语言称为0型语言。2.1型文法（上下文有关文法）设文法G=(VN,VT,P,S)产生式P：α1Aα2→α1βα2其中A∈VN，β∈V+,α1,α2∈V*
9、α1Aα2
10、≤
11、α1βα2
12、,或
13、A
14、≤
15、B
16、由上下文有关文法构成的语言称为上下文有关语言，用L(G1)表示，G1：上下文有关文法①②③④⑥例：G=(VN,VT,P,S)VN={S,B,C}VT={a,b,c}P:①S→aSBC②CB→BC③S→abC④bB→bb⑤bC→bc⑥cC→ccλ1Sλ2→λ1
17、aSBCλ2,bBλ→bbλ对于S→aSBC∵α1=λ,α2=λ,A=S,B=aSBC,并且
18、S
19、<
20、aSBC
21、∴符合1型文法规则对于bB→bb∵α1=b,α2=λ,A=B,B=b,并且
22、B
23、≤
24、b
25、∴也符合1型文法规则产生式都符合1型文法的要求S→aSBC→aabCBC→abbBCC→aabbCC→aabbcC→aabbcc∴X=a2b2c2此文法G可产生的语言：L(G)={anbncn
26、n=1,2...}假设基元语言L(G)可以描述不同的三角型X=abcX=a2b2c2abc①②③④⑥⑤abcccbbaa2.2型文法（上下文无关文法）设
27、文法G=(VN,VT,P,S)产生式P：A→β其中A∈VN（且是单个的非终止符)β∈V+(可以是终止符，非终止符，不能是空格)对产生式的限制比较严格由上下文无关文法构成的语言称为上下文无关语言。例：文法G=(VN,VT,P,S)VN={S,B,C}VT={a,b}P:①S→aB②S→bA③A→a④A→aS⑤A→bAA⑥B→b⑦B→bS⑧B→aBBaB→abS→abaB→ababSabbA→abbabA→baS→baaB→baabbabA→baba例：G=(VN,VT,P,S)VN={S,T,F}VT={a,+,*,(,)}P:①S→S+T②
28、S→T③T→T*F④T→F⑤F→(S)⑥F→aS→S+T→T+T→F+T→a+T→a+T*F→a+F*F→a+a*F→a+a*a①⑦③④③⑥⑥①①②②②①②④⑥⑥⑥③④两种方法替换非终止符：①最左推导：每次替换都是先从最左边的非终止符开始，例如上边的例子。我们经常采用最左推导。②最右推导：每次替换都是先从最右边的非终止符开始，例如：S→S+T→S+F→S+a→T+a→F+a→a+a3.3型文法（有限状态文法）文法G=(VN,VT,P,S)产生式P：A→aB或A→a，（对产生式限制最严格）其中A,B∈VN（且是单个字符），a∈VT(且是单个字
29、符)由3型文法产生的语言成为3型语言。例：文法G=({S,A},{0,1},P,S)P:①S→0A②A→0A③A→1S→0A→00A→000A→0001L(G)={0n1
30、n=1
