编译原理—第3章文法和语法ppt

1、第第3 3章章文法和语言文法和语言教学要求：本章是编译原理课程的理论基教学要求：本章是编译原理课程的理论基础，要求理解文法、语言、规范推导、规础，要求理解文法、语言、规范推导、规范归约和短语、简单短语、句柄的基本概范归约和短语、简单短语、句柄的基本概念；掌握语言的求解方法、文法的二义性念；掌握语言的求解方法、文法的二义性的判断方法及句型的分析方法。的判断方法及句型的分析方法。教学重点：上下文无关文法，语言定义教学重点：上下文无关文法，语言定义 一、语言一、语言 语言是由句子组成的集合，是由一组记号语言是由句子组成的集合，是由一组记号所构成的集合。所构成的集合。汉语汉语-所有符合汉语语法的句子的

2、全体所有符合汉语语法的句子的全体英语英语-所有符合英语语法的句子的全体所有符合英语语法的句子的全体程序设计语言程序设计语言-所有该语言的程序的全体所有该语言的程序的全体“我是大学生我是大学生”是否是该语言的句子？是否是该语言的句子？句子句子:=:=主语谓语主语谓语主语主语:=:=代词代词| |名词名词代词代词:= := 你你 | | 我我 | | 他他名词名词:= := 王明王明 | | 大学生大学生 | | 工人工人 | | 英语英语谓语谓语:=:=动词直接宾语动词直接宾语动词动词:= := 是是 | | 学习学习直接宾语直接宾语:=:=代词代词| |名词名词二、文法二、文法“:=”与与“”

3、等价，表示为等价，表示为“由由什么组成什么组成”或或“定义为定义为”句子句子 主语谓语主语谓语 代词谓语代词谓语 我谓语我谓语 我动词直接宾语我动词直接宾语 我是直接宾语我是直接宾语 我是名词我是名词 我是大学生我是大学生句子句子:=:=主语谓语主语谓语主语主语:=:=代词代词| |名词名词代词代词:= := 你你 | | 我我 | | 他他名词名词:= := 王明王明 | | 大学生大学生 | | 工人工人 | | 英语英语谓语谓语:=:=动词直接宾语动词直接宾语动词动词:= := 是是 | | 学习学习直接宾语直接宾语:=:=代词代词| |名词名词语法变量（在形式语法变量（在形式语言中又称

4、语言中又称“非终非终结符结符”）单词符号（在形单词符号（在形式语言中又称式语言中又称“终结符号终结符号”)三、符号和符号串三、符号和符号串1 1、字母表和符号串、字母表和符号串字母表：符号的非空有限集字母表：符号的非空有限集 例：例： = = a a，b b，cc符号：字母表中的元素符号：字母表中的元素 例：例： a a，b b，c c符号串：符号的有穷序列符号串：符号的有穷序列 例：例：a, aa, ac, abca, aa, ac, abc，.空符号串：无任何符号的符号串空符号串：无任何符号的符号串( ()符号串集合：由符号串构成的集合。符号串集合：由符号串构成的集合。2 2、符号串的运算

5、、符号串的运算符号串的长度符号串的长度：符号串中符号的个数：符号串中符号的个数. .符号串符号串s s的长度的长度记为记为| |s|s|。 的长度为的长度为0 0符号串的连接符号串的连接：符号串：符号串x x、y y的连接的连接, ,是把是把y y的符号写在的符号写在x x的符号之后得到的符号串的符号之后得到的符号串xyxy例例 x=ST,y=abu x=ST,y=abu 则则 xy=STabuxy=STabu |x|=2,|y|=3,|xy|=5 |x|=2,|y|=3,|xy|=5 x = x= x x = x= x方幂方幂：符号串：符号串x x自身连接自身连接n n次得到的符号串次得到的

6、符号串 xxxx(nxxxx(n个个x)x)定义为定义为 x xn n x x0 0=, x=, x1 1=x, x=x, x2 2=xx, x=xx, x3 3=xxx=xxxx=AB, x=AB, 则则 x x0 0=, x=, x1 1=AB, x=AB, x2 2=ABAB, x=ABAB, x3 3=ABABAB=ABABAB对于对于 n0, xn0, xn n = xx= xxn-1 n-1 = x= xn-1n-1x x 3 3、符号串集合、符号串集合 若集合若集合A A中一切元素都是某字母表中一切元素都是某字母表 上的符号串，上的符号串，则称则称A A为字母表为字母表 上的符号

7、串集合。上的符号串集合。 两个符号串集合两个符号串集合A A和和B B的乘积定义为的乘积定义为 若集合若集合A=A= a,ba,b B=B= c,dc,d 则则 AB=AB= ac,ad,bc,bdac,ad,bc,bd (x=x=x)(x=x=x) 使用使用 * *表示表示 上的所有有穷长的串（包括上的所有有穷长的串（包括）的集合。的集合。* *称为称为的的。 从从 * *中除去中除去得到的集合记为得到的集合记为 + + 。 + +称为称为的的。* = 0 1 2 n + = 1 2 n * = 0 + = * = *+ = * -设设=0,1，则则* =, 0, 1, 00, 01, 10

8、, 11, 000, 001, 010,设设=a,b=a,b，则则 * *=,a,b,aa,ab,ba,bb,aaa,aab,=,a,b,aa,ab,ba,bb,aaa,aab, + +=a,b,aa,ab,ba,bb,aaa,aab,=a,b,aa,ab,ba,bb,aaa,aab,四、文法和语言的形式定义四、文法和语言的形式定义1 1、文法的形式定义、文法的形式定义1 1）规则（重写规则、产生式或生成式）：是）规则（重写规则、产生式或生成式）：是一个有序对（一个有序对（，）。）。记为记为或或=，其中其中VV+ +，VV* * 。 称为规则的左部称为规则的左部( (或生成式的左部或生成式的左

9、部) )。 称为规则的右部称为规则的右部( (或生成式的右部或生成式的右部) )。2 2）文法）文法GSGS：文法为文法为（V VN N，V VT T，P P，S S） V VN N ：非终结符集非终结符集 V VT T ：终结符集终结符集 P P：产生式（规则）集合产生式（规则）集合 S S：开始符号（识别符号）开始符号（识别符号）V VN N、V VT T 和和 P P 是非空有穷集。是非空有穷集。S S 至少在一条规则至少在一条规则中作为左部出现。中作为左部出现。V VN NVVT T=， SV SVN NV=VV=VN NVVT T，称为文法称为文法G G的字母表（字汇表）的字母表（字

10、汇表） 例例: : 文法文法G=G=（V VN N，V VT T，P P，S S）V VN N = S , V = S , VT T = 0, 1 = 0, 1 P= S0S1, S01 P= S0S1, S01 S S为开始符号为开始符号例例: : 文法文法G=G=（V VN N，V VT T，P P，S S）V VN N = =标识符，字母，数字标识符，字母，数字 V VT T =a,b,c,x,y,z,0,1,9 =a,b,c,x,y,z,0,1,9P=P= a, a, z z 0, 0, 99S=S= 习惯上只将产生式写出。并有如下约定：习惯上只将产生式写出。并有如下约定：第一条产生式

11、的左部是开始符号第一条产生式的左部是开始符号用尖括号括起的是非终结符，否则为终结用尖括号括起的是非终结符，否则为终结符。或者大写字母表示非终结符，小写字符。或者大写字母表示非终结符，小写字母表示终结符母表示终结符G G可写成可写成GSGS，其中其中S S是开始符号是开始符号 例例:文法文法G=（VN，VT，P，S）VN = S , VT = 0, 1 P= S0S1, S01 S为开始符号为开始符号 可写成：可写成： G：S0S1 S01 或写成：或写成： GS：S0S1 S01五、推导的定义五、推导的定义 1 1）直接推导）直接推导“” 是文法是文法G G的产生式，的产生式，,V,V* *，

12、若将，若将作用于作用于 v=v=得到得到 w=,w=,则则记作记作 v vw w，读作读作v v（应用规则应用规则）直接产生直接产生w w（w w是是v v的的或或w w到到v v）例：例：G G：S0S1S0S1，S01S01直接推导：直接推导：0 0S1S100110011（v=0S1v=0S1，w=0011w=0011，使用规则使用规则S01S01，=0=0，=1=1）S S0S10S1（v=Sv=S，w=0S1w=0S1，使用规则使用规则S0S1S0S1，= =，= =）0 0S1S100S1100S11（v=0S1v=0S1，w=00S11w=00S11，使用规则使用规则S0S1S0

13、S1，=0=0，=1=1）例例 文法文法G=（VN，VT，P，S）VN =标识符，字母，数字标识符，字母，数字VT =a,b,c,x,y,z,0,1,9P= a, z z 0,0,99S=指出下面直接推导所使用的规则：指出下面直接推导所使用的规则： abcabc abc5abc52）长度为长度为n的推导（有限次推导）的推导（有限次推导） 若存在若存在v =w0 w1 . wn=w, (n0)， 则称则称v出出w（或或w到到v）. 记作记作 v w。3）若有若有v w，或或v=w， 则记为则记为v w+*例：例：G G： S0S1 S0S1， S01 S010S10S100S1100S11000

14、S111000S11100001111 00001111 即即 0S1 000011110S1 00001111也记作也记作 0S1 000011110S1 00001111+*1 1）句型）句型 设设GS是一文法是一文法，如果符号串如果符号串x是从是从识别符号识别符号推推导出来的，即导出来的，即S x，则称则称x是文法是文法GS的句型。的句型。*例：例：G G： S0S1， S01S 0S1 00S11 000S111 00001111*2 2）句子）句子x仅由仅由终结符号终结符号组成组成（即即S x，且且xVVT T* *），），则称则称x是是GS的句子的句子。3 3）语言）语言 由文法由

15、文法G G产生的所有句子组成的集合叫做文法产生的所有句子组成的集合叫做文法G G所成描述的语言，记为所成描述的语言，记为L(G)L(G)。 例：例：G G： S0S1， S01 L(G)=0n1n|n1 注：产生式中含有递归式，产生的句子是无穷的注：产生式中含有递归式，产生的句子是无穷的*L(G)=x|S x，其中其中S为文法的开始符号为文法的开始符号，且且x VVT T* * 例例: :文法文法GS：（1）SdAdAB（2）AaA（3）Aaa（4）BBBb（5）BL（G）=?G G生成的每个串都在生成的每个串都在L(G)L(G)中中L(G)L(G)中的每个串确实能被中的每个串确实能被G G生

16、成生成例：构造生成语言例：构造生成语言L= 的文的文法。法。分析：分析：n n1 1，所以必须用递归规则。所以必须用递归规则。a a和和b b的的个数个数 一样多，但一样多，但c c的个数不同，所以将生成的个数不同，所以将生成含含 a,b a,b的部分与生成含的部分与生成含e e的部分分开，的部分分开，A A生成生成 abab，B B生成生成e.e. GZ:ZAB GZ:ZAB AaAb|ab AaAb|ab BeB| BeB|0, 1|inebainn4)4)文法的等价文法的等价 若若L L（G G1 1）=L=L（G G2 2），），则称文法则称文法G G1 1和和G G2 2是等价的。是

17、等价的。如文法如文法G G1 1AA：A0R A0R 与与 G G2 2SS：S0S1 S0S1 等价等价 A01 S01A01 S01 RA1 RA1七、文法的类型七、文法的类型 （1）0型文法型文法(短语文法短语文法)：对任一产生式对任一产生式，都有都有(V(VN NVVT T) )+ +， (V (VN NVVT T) )* * （2 2）1 1型文法型文法( (上下文有关文法上下文有关文法) )： 对任一产生式对任一产生式，都有都有| |， 仅仅仅仅 SS除除外。即外。即1 1AA2 21 12 2( (A A在在V VN N中中，其他在其他在V V* *中中，) )（3 3）2 2型

18、文法型文法（上下文无关文法上下文无关文法）： 对任一产生式对任一产生式，都有都有VVN N ， (V (VN NVVT T) )* * 即即AA( (A A在在V VN N中中，在在V V* *中中，) )（4 4）3 3型文法型文法（正规文法正规文法）：）：任一产生式任一产生式的形式都的形式都为为AaBAaB或或AaAa，其中其中AVAVN N ，BVBVN N ，aVaVT T 例：例：1 1型（上下文有关）文法型（上下文有关）文法 文法文法GS：SaSBESaBEEBBEaBabbBbbbEbeeEee 例：例：2 2型（上下文无关）文法型（上下文无关）文法 文法文法GS： SaB|bA

19、aB|bAAa|aS|bAAa|aS|bAABb|bS|aBBb|bS|aBB 文法文法GS： S0A|1B|00A|1B|0A0A|1B|0S0A|1B|0SB1B|1|01B|1|0 例：定义标识符的例：定义标识符的3 3型（正规）文法型（正规）文法 文法文法GI：I lT lTI l lT lT lTT dT dTT l lT d d文法和语言文法和语言 0 0型文法产生的语言称为型文法产生的语言称为0 0型语言型语言 1 1型文法或上下文有关文法（型文法或上下文有关文法（ CSG CSG ）产生的语产生的语言称为言称为1 1型语言或上下文有关语言（型语言或上下文有关语言（CSLCSL）

20、 2 2型文法或上下文无关文法（型文法或上下文无关文法（ CFG CFG ）产生的语产生的语言称为言称为2 2型语言或上下文无关语言（型语言或上下文无关语言（ CFL CFL ） 3 3型文法或正则（正规）文法（型文法或正则（正规）文法（ RG RG ）产生的语产生的语言称为言称为3 3型语言或正则（正规）语言（型语言或正则（正规）语言（ RL RL ）八、上下文无关文法及其语法树八、上下文无关文法及其语法树 上下文无关文法有足够的能力描述现今程上下文无关文法有足够的能力描述现今程序设计语言的语法结构。序设计语言的语法结构。 算术表达式算术表达式 语句语句 赋值语句赋值语句 条件语句条件语句

21、循环语句循环语句 用于描述上下文无关文法的用于描述上下文无关文法的句型推导句型推导的的直观方法直观方法 例例: : GS:SaASASbAASSSaAba S a A S S b A a a b a句型句型aabbaa的语法树（推导树）的语法树（推导树）叶子结点：树中没有子孙的结点。叶子结点：树中没有子孙的结点。从左到右读出推导树的叶子标记，所得的句从左到右读出推导树的叶子标记，所得的句型为推导树的结果。也把该推导树称为该句型为推导树的结果。也把该推导树称为该句型的语法树。型的语法树。推导过程中施用产生式的推导过程中施用产生式的顺序顺序 例例: GS:SaASASbAASSSaAba S a

22、A S S b A a a b a句型句型aabbaa的语法树（推导树）的语法树（推导树）SaASaAaaSbAaaSbbaaaabbaa在推导的任何一步在推导的任何一步，其中其中、是句型，是句型，都是对都是对中的最左（右）非终结符进行替换。中的最左（右）非终结符进行替换。 最右推导被称为最右推导被称为。 由规范推导所得的句型称为由规范推导所得的句型称为SaASaAaaSbAaaSbbaaaabbaa（最右推导最右推导）SaASaSbASaabASaabbaSaabbaa（最左推导最左推导）SaASaSbASaSbAaaabAaaabbaa 例例: GS:SaASASbAASS Sa Aba问

23、题：一个句型是否对应唯一的一棵语法树？问题：一个句型是否对应唯一的一棵语法树？ 例：例：GE:GE:E iE iE E+EE E+EE EE E* *E EE (E)E (E) E E E + E E + E E E * * E i E i i i i i E E E E * * E E i E + E i E + E i i i i句型句型 i*i+i 的两个不同的最左推导的两个不同的最左推导：推导推导2：E E*E i*E i*E+E i*i+E i*i+i推导推导1：E E+E E*E+E i*E+E i*i+E i*i+i3 3、二义文法、二义文法若一个文法存在若一个文法存在某个某个句

24、子对应两棵不同的语法句子对应两棵不同的语法树，则称这个文法是树，则称这个文法是二义二义的。的。或者，若一个文法存在或者，若一个文法存在某个某个句子有两个不同的句子有两个不同的最左（右）推导，则称这个最左（右）推导，则称这个文法文法是是二义二义的。的。产生某上下文无关语言的每一个文法都是二义产生某上下文无关语言的每一个文法都是二义的，则称此的，则称此语言语言是是先天二义先天二义的。的。排除文法二义性的两种方法：排除文法二义性的两种方法：（1 1）在语义上加些限制（如优先顺序和结）在语义上加些限制（如优先顺序和结合律）。合律）。（2 2）重构无二义性的文法。）重构无二义性的文法。GE: E IGE

25、: E I E E+E E E+E E EE E* *E E E (E) E (E)GE: E T|E+TGE: E T|E+T T F|T T F|T* *F F F F （E E）|i|i 练习：有文法练习：有文法GN： NSE|E S SD|D E 0|2|4|6|8|10 D 0|1|2|3|4|5|6|7|8|9（1）证明此文法有二义性证明此文法有二义性（2）此文法描述的语言是什么？）此文法描述的语言是什么？（3）试写出另一文法，其产生的语言和）试写出另一文法，其产生的语言和GN产产生的语言等价且是无二义性的。生的语言等价且是无二义性的。八、句型的分析八、句型的分析就是识别一个符号串

26、是否为某文法的就是识别一个符号串是否为某文法的句型，是某个推导的构造过程。句型，是某个推导的构造过程。在语言的编译实现中，把完成句型分析的程序在语言的编译实现中，把完成句型分析的程序称为称为或或。分析算法又称。分析算法又称识别识别算法算法。从左到右的分析算法从左到右的分析算法，即总是从左到右地识别，即总是从左到右地识别输入符号串，首先识别符号串中的最左符号，输入符号串，首先识别符号串中的最左符号，进而依次识别右边的一个符号。进而依次识别右边的一个符号。1、自上而下的语法分析：从文法的开始符号出发，、自上而下的语法分析：从文法的开始符号出发，反复使用各种产生式，寻找与输入符号串匹配的推反复使用各

27、种产生式，寻找与输入符号串匹配的推导。导。 例：文法例：文法G：S cAd A ab A a识别输入串识别输入串 w = cabd 是否该文法的句子是否该文法的句子SSScAdcAd a b推导过程推导过程：cabdcAd S2、自下而上的语法分析自下而上的语法分析：从输入符号串开始，逐从输入符号串开始，逐步进行归约，直至归约到文法的开始符号。步进行归约，直至归约到文法的开始符号。 例：文法例：文法G：S cAd A ab A a识别输入串识别输入串 w = cabd 是否该文法的句子是否该文法的句子SAA c a b d c a b d c a b d 规约过程规约过程：cabdcAd S3

28、 3、句型分析的有关问题、句型分析的有关问题1 1）如何选择使用哪个产生式进行推导？）如何选择使用哪个产生式进行推导？假定要被代换的最左非终结符号是假定要被代换的最左非终结符号是V V，且有且有n n条条规则：规则：VA1|A2|AnVA1|A2|An，那么如何确定用哪个那么如何确定用哪个右部去替代右部去替代V V？2 2）如何识别可归约的串？如何识别可归约的串？在自下而上的分析方法中，在分析程序工作的在自下而上的分析方法中，在分析程序工作的每一步，都是从当前串中选择一个子串，将它每一步，都是从当前串中选择一个子串，将它归约到某个非终结符号，该子串称为归约到某个非终结符号，该子串称为“可归约可归约串串”（“4 4、短语、直接短语、句柄的定义：、短语、直接短语、句柄的定义：文法文法GS，是是G的一个句型的一个句型，如果如果： S A且且A 则称则称是句型是句型相对于非终结符相对于非终结符A的的。若有若有A 则称则称是句型是句型相对于规则相对于规则A的的。一个句型的一个句型的最左直接短语最左直