编译程序的组织 (5).ppt

《编译程序的组织 (5).ppt》由会员分享，可在线阅读，更多相关《编译程序的组织 (5).ppt（13页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、1定义1文法G定义为四元组（Vn，VT，P，S）。其中：Vn：非终结符号(或语法实体，或变量)集；VT：终结符号集；P：产生式(也称规则)的集合；S：识别符号或开始符号。Vn，VT和P是非空有穷集P：或=V+，V*S：必须出现在某个产生式的左部2.2 文法和语言的形式定义2G句子=（Vn，VT，P，S）Vn=句子主语谓语代词、名词动词直接宾语VT=我、你、他、王明、大学生、工人、英语、是、学习P=句子=主语谓语主语=代词|名词代词=我|你|他名词=王明|大学生|工人|英语谓语=动词直接宾语动词=是|学习直接宾语=代词|名词3例 文法G=(Vn，VT，P，S)，其中 Vn=S，VT=0，1，P=

2、S0S1，S01。这里，非终结符集中只含一个元素S；终结符集由两个元素0和1组成；有两条产生式；开始符号是S。一般约定，第一条产生式的左部是识别符号；用尖括号括起来的是非终结符号，不用尖括号括起来的是终结符号，或者用大写字母表示非终结符号，小写字母表示终结符号。另外也有一种习惯写法，将G写成GS，其中S是识别符号.文法G还可以写成：G：S0S1 S01或 GS：S0S1 S014例文法 G=(Vn，VT，P，S)其中 Vn=标识符，字母，数字 S=标识符 VT=a,b,c,，x,y,z,0,1,，9P=标识符字母 标识符标识符字母 标识符标识符数字 字母a 字母b 字母z 数字0 数字1 数字

3、9字母a|b|c|z数字0|1|2|3|4|5|6|7|8|95一个文法的几种写法G=(S,A，a,b，P，S)其中P：SaAbAabAaAbAGS：AabAaAbASaAbGS：Aab|aAb|SaAbG：SaAbAabAaAbA6定义2推导如是文法G=(Vn，VT，P，S)的规则(或说是P中的一产生式)，和是V*中的任意符号，若有符号串v，w满足：v=，w=则说v(应用规则)直接产生w，或者说，w是v的直接推导，也可以说，w直接归约到v，记作v=w7例文法 G=(Vn，VT，P，S)其中Vn=标识符，字母，数字VT=a,b,c,，x,y,z,0,1,，9P=|a|b|c|z0|1|2|3|

4、4|5|6|7|8|9 S=标识符直接推导：直接推导：abcabc5,8定义3 如果存在直接推导的序列：v=w0 w1 w2 wn=w,(n0)则称v推导出(产生)w(推导长度为n)，或称w归约到v。记作v w。定义4 若有v w，或v=w，则记作v w。9例1 的文法：GS：S-0S1 S01 V=0S1 w=00001111 V=0S1=00S11=000S111=00001111;0S1=*00001111 例2文法：G标识符：P=标识符字母|标识符字母|标识符数字字母a|b|c|z数字0|1|2|3|4|5|6|7|8|9 V=W=ab1V=1=1=b1=b1=ab1记作=+ab1 或

5、=*ab110例：G：S0S1，S01定义5 设GS是一文法，如果符号串x是从识别符号推导出来的，即有S x，则称x是文法GS的句型。若x仅由终结符号组成，即S x，xVT*，则称x为GS的句子。S 0S100S11000000111.111.11例：GE：EE+T|TTT*F|FF（E）|aa+a*aEE+TT+TF+Ta+Ta+T*Fa+F*Fa+a*F12定义6文法G所产生的语言定义为集合x|Sx，其中S为文法识别符号，且xVT*。可用L(G)表示该集合。例：G：S0S1，S01第一，符号串x可从识别符号推出，也即x是句型。第二，x仅由终结符号组成，即x是文法G的句子。也就是说，文法描述的语言是该文法一切句子的集合。S 0S100S11000000111.111.L（G）=0n1n|n113文法的等价:若L（G1）=L（G2），则称文法G1和G2是等价的。