编译原理第4讲.ppt

1、编译原理第4讲 语法分析(1),贾西平 Email: ,2,内容提纲,基本概念 形式语言分类 正规表达式与上下文无关文法,3,内容提纲,基本概念 形式语言分类 正规表达式与上下文无关文法,4,基本概念,1. 字母表：元素的有穷非空集合。 2.字符 (或符号)：字母表中的每个元素。 不同的语言可以有不同的字母表，例如英文的字母表中26个字母、数字及标点符号等。 PASCAL语言的字母表是由字母、数字、若干专用符号组成。 字母表也称为符号集。,5,基本概念(续),3. 字符串(或字): 字母表中的字符组成的任何有穷序列。例如00 11 10 是字母表 =0，1上的符号串. 字母表A=a,b,c上的

2、一些符号串有：a,b,c,ab,aaca等。 在字符串中，字符的顺序是很重要的，字符串ab就不同于ba,abca和aabc也不同。字符串STR表示“由字符S、T和R，并按此顺序组成.,6,语言,语言：对字母表来说，*上的任意一个子集都称为上的一个语言，记为L(L *) 句子：语言L的每一个字符串称为该语言的一个语句或句子。 例：字母表0，1上的语言 0，1 00，11 0，1，00，11 0，1，00，11，01，10 00，11* 01，10*,7,文法,文法：描述语言的语法结构的形式规则。 文法被用来精确而无歧义地描述语言句子的构成方式. 文法描述语言的时候不考虑语言的含义。,8,文法的形

3、式定义,文法通常表示成四元组G=(VT，VN，S，)，其中: (1)VT为终结符号集，是一个非空有限集，它的每个元素称为终结符号； (2)VN为非终结符集，也是一个非空有限集，其每个元素称为非终结符号，且有VTVN=； (3)S为一文法开始符，是一个特殊的非终结符号，即SVN； (4)是产生式的非空有限集,9,文法的形式定义,终结符号：组成该语言的最基本的符号，不可再分,如保留字、标识符等。 非终结符号：表示一些语法成分，可以推导出其他的语法成分,表示一定符号串的集合，是一个类，如表达式。 开始符号：规则中的一个特殊的非终结符号，语言中的句子都从它开始推导,如程序、句子 产生式：定义语法成分的

4、规则,10,产生式,产生式，也称产生规则或规则，是定义语法实体的一种书写规则。 每个产生式是一序偶(，)，通常写作或:=，读作“是”或“定义为”。 为产生式的左部，为右部 、是由终结符和非终结符组成的符号串 (VTVN)+且至少有一个非终结符 (VTVN)*。,11,产生式的书写,可将有相同左部的产生式合并为一个 例： P1 P2 Pn 可缩写成 P12n 每个i(i=1,2,n)称为P的一个候选式 直竖“”读为“或”，与“”一样是用来描述文法的元语言符号(即不属于的字符)。,12,例：构造产生标识符的文法,解 标识符是以字母开头的字母数字串，用L表示“字母”类非终结符，用D表示“数字”类非终

5、结符，而用T表示“字母或数字”类非终结符，则有： Labz D019 TLD 如果用S表示“字母数字串”类，则T是一字母或数字，ST也是字母数字串，即有STST 产生式STST是一种左递归形式，由它可以产生一串T。,13,例：构造产生标识符的文法（续）,作为“标识符”的非终结符I，它或者是一单个字母，或者为一字母后跟字母数字串，即 ILLS 因此，产生标识符的文法GI为： G=(a,b,z,0,9,I,S,T,L,D,I,) : ILLS STST TLD Labz D019,14,例3.2,写一文法，使其语言是奇数集合，但不允许出现以0打头的奇数。,解根据题意，可以将奇数划分为如图所示的三个

6、部分： 最高位允许出现19，用非终结符B表示； 中间部分可以出现任意多位数字09，每一位用非终结符D表示； 最低位只允许出现1、3、5、7、9等奇数，用A表示。,15,例3.2,由于中间部分可出现任意位，所以另引入了一个非终结符M，它包括最高位和中间位部分。假定开始符为N，则可得到文法GN为： G=(0,1,9,N,A,M,B,D,N,) :NAMA /*一位数字多位数字*/ MBMD /*仅两位数字(无中间位)多于两位数字*/ A13579 B123456789 D0B,16,推导,直接推导：又称一步推导(用 符号=表示),就是用某条规则的右部去替换该规则的左部 推导: 连续使用直接推导,得

7、到的连续序列称为一个推导。,17,直接推导,设文法G=(VT,VN,S,)且、(VTVN)*，如果存在产生式A(VTVN)*)，则称A可直接推出，即 A = “=”表示直接推导出，是应用产生规则进行推导的记号。 “=”与“”不同，“”是产生式中的定义记号 直接推导是对文法符号串A中的非终结符A用相应的产生式A的右部来替换，从而得到。,18,通常，用 表示：从1出发，经过一步或若干步，可以推出n。,用 表示：从1出发，经过0步或若干步，可以推出n。,所以 ： 即 或,推导符号,19,表达式推导,例如，对下面的文法GE： EE+EE*E(E)i (3.1) 唯一的非终结符E可以看成是代表一类算术表

8、达式。 可以从E出发进行一系列的推导，如表达式i+i*i的推导如下： E =E+E =E+E*E = E+E*i =E+i*i =i+i*i,注意： 每步推导，只能将某个产生式的左部用其右部替换。,20,例 : G =( i, +, *, (, ) , E , E, P) (1.1) P： E E+E | E*E | (E) | i 表达式(i)和(i+i)*i的推导：,E (E) (i)E E*E (E)*E (E + E)*E (i + E)*E (i + i)*E (i + i)*i,E E 0步推导 E (i + i)*i 6步推导 E (i + i)*i 6步推导 E (E) 直接推

9、导,表达式推导,21,句型：设(s)是一文法，如果符号串x是从开始符号推导出来的，即有s=x,则称x是文法G(s)的一个句型。 即: 任何由开始符推导出来的符号串都是句型。 句子：若x仅由终结符号组成，则称x为G(S)的句子,*,练习： 文法G：SaAcB | Bd AAaB | c BbScA | b 写出句型aAcbBdcc和句子acabcbbdcc的推导过程。,22,文法G产生的语言,定义：文法GS所产生的所有句子构成的集合，记为L(G) L(G)=|S=,其中S为文法的开始符号，Vt*,+,23,文法G产生的语言,例 考虑文法G1: 它定义了什么语言。,S bA A aA|a,推导过程

10、 ：S=bA =ba S=bA =baA=baa . S=bA =baA= =baa,归纳得： L(G1) = ban | n1,24,文法G产生的语言,练习：文法S( a,b,c, A,B,S ,S, P) S Ac|aB A ab B bc写出(G)的全部元素,答案：L(G) = abc,25,文法G产生的语言,例：考虑文法G2: 它定义的语言是：,S AB A aA|a B bB|b,L(G2) = ambn |m,n1,26,内容提纲,基本概念 形式语言分类 正规表达式与上下文无关文法,27,形式语言分类,Chomsky把文法分成四种类型：0，1，2，3型 它们都由四部分组成，但对产生

11、式的限制有所不同。,28,0型文法,如果文法G的每一个产生式具有下列形式： 其中，V*VNV*(注：V=VNVT)，即至少含有一个非终结符；V*； 则称文法G为0型文法或短语文法，记为PSG。 0型文法相应的语言称为0型语言或称递归可枚举集 它的识别系统是图灵(Turing)机。,29,1型文法,文法G的每一个产生式，均在0型文法的基础上增加了字符长度上满足限制条件，则称文法G为1型文法或上下文有关文法，记为CSG。 1型文法相应的语言称为1型语言或上下文有关语言，它的识别系统是线性界限自动机。 1型文法的另一种定义方法：文法G的每一个产生式具有下列形式：A其中，、V*，AVN，V+； A必须

12、在、的上下文环境中才能被所替换。,30,2型文法,文法G的每一个产生式具有下列形式：A其中，AVN，V*，则称文法G为2型文法或上下文无关文法，记为CFG。 2型文法相应的语言称为2型语言或上下文无关语言，它的识别系统是下推自动机。,31,3型文法,文法G的每个产生式具有下列形式：Aa或AaB其中，A、BVN，aVT*则文法G称为3型文法、正规文法或右线性文法，记为RG 3型文法相应的语言为3型语言或正规语言，它的识别系统是有限自动机。 3型文法还可以呈左线性形式：Aa或ABa,32,四类文法的关系与区别,从0型文法到3型文法逐渐增加限制 13型文法都属于0型文法 2、3型文法均属于1型文法

13、3型文法属于2型文法。 四类文法的区别如下： (1) 1型文法中不允许有形如“A”的产生式存在，而2、3型文法允许； (2) 0、1型文法的产生式左部含有终结符或两个以上的非终结符，而2型和3型文法的产生式左部只允许是单个的非终结符号。,33,语言的层次,这四种语言可被4种自动机识别： 0型图灵机 1型线性界限自动机 2型下推自动机 3型有限自动机,从外到内，四种文法对产生式的限制越来越多，语言的描述能力越来越弱,34,例3.3,试判断下列产生式集所对应的文法类型和产生的语言： (1)SACaB (2)SaSBC (3)SAc (4)SaS CaaaC SaBCSSc SaA CBDB CBD

14、BAab AbA CBE DBDCAaAb AbB aDDa DCBCBcB ADAC aBab Bc aEEa bBbb AE bCbc cCcc,35,解 由四类文法的定义与区别可知，14分别为03型文法。 (1) 该0型文法产生的0型语言为L0(G)=a2nn0。例如：当n=2时，句子a22= aaaa ,36,(2) 该1型文法产生的1型语言为L1(G)=anbncnn1。例如，当n=2时，句子a2b2c2=aabbcc是通过下列推导得到的：,37,(3) 该2型文法产生的2型语言为L2(G)=anbncmm、n1。例如当n=2、m=3时，句子a2 b2 c3=aabbccc是通过下列

15、推导得到的：,38,(4) 该3型文法产生的3型语言为L3(G)=ambnckm、n、k1。例如当m=2、n=3、k=4时，句子a2b3c4=aabbbcccc是通过下列推导得到的：,39,几点说明,由例3.3可知： anbncnn1 anbncmm、n1 ambnckm、n、k1 对文法规则定义形式的限制虽然加强了，但相应的语言反而更大了 不能主观认定文法限制越大则语言越小 下述结论是不成立的： 3型语言 2型语言 1型语言 0型语言,40,几点说明,在编译方法中： 常用3型文法描述高级程序语言的词法部分，然后用有限自动机FA来识别高级语言的单词； 用2型文法描述高级语言的语法部分，然后用下

16、推自动机PDA来识别高级语言的各种语法成分。,41,图32 例3.4的DFA,解 为了构造字母表=a,b上同时只有奇数个a和奇数个b的所有字符串的正规表达式，画出如图32所示的DFA， 即由开始符S出发，经过奇数个a到达状态A，或经过奇数个b到达状态B。再由状态A出发，经过奇数个b到达状态C(终态)；同样，由状态B出发，经过奇数个a到达终态C。,例3.4 给出字母表=a,b上的同时只有奇数个a和奇数个b的所有字符串集合的正规文法。,42,例3.4,由图32可直接得到正规文法GS如下： GS: SaAbB AaSbCb BbSaCa CbAaB,43,内容提纲,基本概念 形式语言分类 正规表达式与上下文无关文法,44,正规表达式与上下文无关文法,正规表达式所描述的语言结构均可以用上下文无关文法描述，反之则不一定。 由正规表达式构造上下文无关文法的一种方法如下： (1) 构造正规表达式的NFA； (2) 若0为初始状态，则A0为开始符号； (3) 如果存在映射关系f(i, a)= j，则定义产生式Ai aAj； (4) 如果存在映射关系f(i, )= j，则定义产生式 Ai Aj； (5) 若i为终态，则定义产生式Ai 。,45,例3.5,用上下文无关文法描述正规表达式(ab)*abb。,解 首先构造识别正规表达式(ab)*abb的NFA M如图 由构造上下文无关文法的方法