《编译原理》课程简介 (5).pdf

编译原理 COMPILATION PRINCIPLE第二章 高级语言及其语法描述2.2文法的形式化定义和分类文法形式化定义n文法定义成一个四元组G=(VN,VT,S,P)pVN:非空有限的非终结符集；pVT:非空有限的终结符集；pS:开始符号；pP:产生式集合。p其中，VN VT=，S VNpP中产生式一般形式为:A|，其中 A VN，,（VN VT）*例1v 文法G=(VN,VT,S,P)，其中VN=S，VT=0，1，P=S0S1，S01。v 这里，非终结符集中只含一个元素S；终结符集由两个元素0和1组成；有两条产生式；开始符号是S。v 文法G=(VN,VT,S,P)，其中VN=S，VT=0，1，P=S0S1，S01。G=(S,A，a,b，P，S)其中P：SaAb Aab AaAb A G：SaAb Aab AaAb A GS：Aab AaAb A S aAb GS：Aab|aAb|SaAb 文法的分类n对产生式施加不同的限制得到不同类型的文法p0型（无限制文法）:G=(VN,VT,S,P)规则形式：;(VNVT)+,(VN VT)*且中至少含有一个非终结符 p1型（上下文有关）:规则 有 1|,其中=1A2,=12;A VN,(VN VT)+,1,2 (VN VT)*.规则形式：1A 2 12;p2型（上下文无关）:规则形式：A,A VN，(VN VT)+p3型（右线性和正规文法）:规则形式:AB或A（右线性）A,B VN,(VT)*。v左线性文法p规则形式:AB或A（左线性）A,B VN,(VT)*.v正规文法p规则形式:AB或A 其中A,B VN,VT，如果S P，且S不能出现在任何产生式右边p正规文法中只能出现单个终结符，右线性文法中可能出现若干个终结符组成的串 v2型文法扩充p规A,A VN，(VN VT)*p允许有空产生式：An四个文法类的定义是逐渐增加限制的，因此每一种正规文法都是上下文无关的，每一种上下文无关文法都是上下文有关的，而每一种上下文有关文法都是0型文法。n称0型文法产生的语言为0型语言。上下文有关文法、上下文无关文法和正规文法产生的语言分别称为上下文有关语言、上下文无关语言和正规语言。n现今大多数高级程序设计语言采用上下文无关文法来描述其语法已经足够了。文法举例n文法G=(S,A,B,a,b,c,d,e,S,P),其中，P=S abcA|edB,AbeB,B d p文法G是右线性文法p也是正规文法 n其中,VN=S，X，Y，Z VT=x，y，z P=S xSYZ|xYZ，xYxy，yYyy，yZyz，ZYYZ，zZzz v例1 1型文法G=(VN,VT,P,S)n其中,VN=S，T VT=a，b，c，d P=S aTd，TbT|cT|b|c v例2 2型文法G7=(VN,VT,P,S)n其中,VN=B VT=(，)P=B（B）|BB|（）v例3 2型文法G8=(VN,VT,P,B)n其中,VN=S VT=0，1 P=S 0S1，S 01 v例4 1型文法G9=(VN,VT,P,S)n用文法描述下面的语言：“所有以0开头，后接零个或多个10组成的符号串的集合”v例5左线性文法,G11S:S S10|0 2右线性文法,G10S:S 0A A10A|1正线性文法,G12S:S 0B|0 B1S 3|编译原理