编译原理课件第讲文法和语法

编译原理课件第讲文法和语法第1页，共63页，2023年，2月20日，星期二第一节

语言语言:是由句子组成的集合。

汉语---所有符合汉语语法的句子的全体英语---所有符合英语语法的句子的全体程序设计语言---所有该语言的程序的全体研究语言：每个句子构成的规律每个句子的含义每个句子和使用者的关系第2页，共63页，2023年，2月20日，星期二研究程序设计语言：

每个程序构成的规律每个程序的含义每个程序和使用者的关系语言研究的三个方面：

语法Syntax

语义Semantics

语用Pragmatics第3页，共63页，2023年，2月20日，星期二语法：

表示构成语言句子的各个记号之间的

组合规律

语义：表示按照各种表示方法所表示的各个记号的特定含义。（各个记号和记号所表示的对象之间的关系）

语用：表示在各个记号所出现的行为中，它们的来源、使用和影响。

第4页，共63页，2023年，2月20日，星期二第二节文法“我是大学生”是否是该语言的句子？〈句子〉::=〈主语〉〈谓语〉〈主语〉::=〈代词〉|〈名词〉〈代词〉::=你|我|他〈名词〉::=王明|大学生|工人|英语〈谓语〉::=〈动词〉〈直接宾语〉〈动词〉::=是|学习〈直接宾语〉::=〈代词〉|〈名词〉以自然语言为例，用EBNF(扩展的巴科斯范式)描述一种语言：第5页，共63页，2023年，2月20日，星期二〈句子〉〈主语〉〈谓语〉

①〈句子〉::=〈主语〉〈谓语〉〈主语〉::=〈代词〉|〈名词〉〈代词〉::=你|我|他〈名词〉::=王明|大学生|工人|英语〈谓语〉::=〈动词〉〈直接宾语〉〈动词〉::=是|学习〈直接宾语〉::=〈代词〉|〈名词〉

〈代词〉〈谓语〉②我〈谓语〉③我〈动词〉〈直接宾语〉⑤我是〈直接宾语〉⑥我是〈名词〉⑦我是大学生④第6页，共63页，2023年，2月20日，星期二〈句子〉::=〈主语〉〈谓语〉〈主语〉::=〈代词〉|〈名词〉〈代词〉::=你|我|他〈名词〉::=王明|大学生|工人|英语〈谓语〉::=〈动词〉〈直接宾语〉〈动词〉::=是|学习〈直接宾语〉::=〈代词〉|〈名词〉下列是否是句子?我大学生是 他是工程师大学生是王明第7页，共63页，2023年，2月20日，星期二事实上，使用文法作为工具，不仅为了严格定义句子的结构，也是为了用适当条数的规则把语言的全部句子描述出来。文法是以有穷的集合刻画无穷的集合的一个工具。第8页，共63页，2023年，2月20日，星期二第三节符号和符号串字母表：元素的非空有穷集合。（符号集）符号：字母表中的元素。例如：汉语的字母表中包括汉字、数字及标点符号等。PASCAL语言的字母表是由字母、数字、若干专用符号及BEGIN、IF之类的保留字组成。第9页，共63页，2023年，2月20日，星期二符号串：由字母表中的符号组成的任何有穷序列称为该字母表上的符号串。1.空符号串ε(没有符号的符号串)是上的符号串。2.若x是上的符号串，a是的元素，则xa和ax是上的符号串。3.

y是上的符号串,当且仅当它可以由1和2导出。

例如：Σ={a,b}

ε,a,b,aa,ab,aabba,…,都是上的符号串。第10页，共63页，2023年，2月20日，星期二例：Σ={0,1}

ε,0,1,00,01,11,1001110等都是上的符号串.例：Σ={a,b,c}上的符号串有：

a,b,c,ab,ba,aaca,acaa等.注意：符号串中的符号排列是有顺序的.可以用字母表示符号串，如：x=aaca第11页，共63页，2023年，2月20日，星期二如果z=xy是一符号串，那么：x是z的头(前缀)，y是z的尾(后缀)；如果x非空，那么y是固有尾；如果y非空，那么x是固有头。例：设z=abc,那么z的头是：ε,a,ab,abc（除abc外都是固有头）z的尾是：ε,c,bc,abc（除abc外都是固有尾）

第12页，共63页，2023年，2月20日，星期二几种表示法（x，z是符号串，t是符号）：z=x… x是符号串z的头z=…x x是符号串z的尾z=…x… x在符号串z中某处出现z=t…符号t是符号串z的第一个符号z=…t符号t是符号串z的最后一个符号第13页，共63页，2023年，2月20日，星期二符号串的运算符号串的长度：符号串中符号的个数。符号串s的长度记为|s|。ε的长度为0。连接：符号串x、y的连接,是把y的符号写在x的符号之后得到的符号串xy

例：x=ST，y=abu则xy=STabu

|x|=2，|y|=3，|xy|=5

εx=xε=x第14页，共63页，2023年，2月20日，星期二方幂符号串x自身连接n次得到的符号串xx…xx(n个x)表示为xn

x0=ε,x1=x,x2=xx，…，xn=xx…xx=AB,则x0=ε,x1=AB,x2=ABAB,x3=ABABAB对于n>0,xn=xxn-1=xn-1x

第15页，共63页，2023年，2月20日，星期二符号串集合：若集合A中一切元素都是某字母表上的符号串，则称A为字母表上的符号串集合。两个符号串集合A和B的乘积：定义为AB=xy|xA且yB

例：若，集合A=a,bB=c,d

则，AB=ac,ad,bc,bd

{ε}A=A{ε}=A(∵εx=xε=x)闭包：

使用*表示上的所有有穷长的串（包括ε）的集合。Σ*称为Σ的闭包。正闭包：

从*中除去ε得到的集合记为+。

Σ+称为Σ的正闭包。第16页，共63页，2023年，2月20日，星期二Σ*=Σ0∪Σ1∪Σ2…∪Σn∪

…Σ+=Σ1∪Σ2…∪Σn∪

…Σ*=Σ0∪Σ+Σ+=ΣΣ*=Σ*ΣΣ+=Σ*-{ε}例1：设Σ={0,1}，则：Σ*={ε，0，1，00，01，10，11，000，001，010，…}例2：设Σ={a,b}，则Σ*={ε，a，b，aa，ab，ba，bb，aaa，aab，…}Σ+={a，b，aa，ab，ba，bb，aaa，aab，…}第17页，共63页，2023年，2月20日，星期二第四节文法和语言的形式定义产生式（重写规则、规则或生成式），是形如α→β或α∷=β的（α，β）有序对，其中α是某字母表V的正闭包V+中的一个符号串，β是V*中的一个符号串。（α∈V+，β∈V*)α称为产生式的左部(或规则的左部)。

β称为产生式的右部(或规则的右部)。第18页，共63页，2023年，2月20日，星期二一、文法的定义文法G：定义为四元组（VN，VT，P，S），其中VN：非终结符集VT：终结符集P：产生式（规则）集合S：开始符号（起始符、识别符号）VN、VT

和P是非空有穷集。S至少在一条规则中作为左部出现。VN∩VT=φ，S∈VN，V=VN∪VT，称为文法G的字母表（字汇表）

注：有的参考书用（VT,VN,S,P）表示文法。第19页，共63页，2023年，2月20日，星期二例3.1文法G=（VN，VT，P，S） VN={S},VT={0,1} P={S→0S1,S→01} S为开始符号或写成：G[S]：S→0S1,S→01第20页，共63页，2023年，2月20日，星期二例3.2文法G=（VN，VT，P，S） VN={标识符，字母，数字}

VT={a，b，c，…，x，y，z，0，1，…，9} P={<标识符>→<字母>， <标识符>→<标识符><字母>， <标识符>→<标识符><数字>， <字母>→a，…，<字母>→z，

<数字>→0，…,<数字>→9}

S=<标识符>第21页，共63页，2023年，2月20日，星期二习惯上只将产生式写出。并有如下约定：

第一条产生式的左部是开始符号用尖括号括起的是非终结符，否则为终结符。或者大写字母表示非终结符，小写字母表示终结符G可写成G[S]，其中S是开始符号第22页，共63页，2023年，2月20日，星期二例3.3文法G=（VN，VT，P，S） VN={S},VT={0,1} P={S→0S1,S→01} S为开始符号可写成：

G[S]：S→0S1 S→01或写成：

G[S]：S→0S1│01

注：把“0S1”和“01”称为产生式S→0S1│01的候选式第23页，共63页，2023年，2月20日，星期二二、推导的定义直接推导“”α→β是文法G的产生式，γ,δ∈V*，若有v,w满足：v=γαδ,w=γβδ,则说：v（应用规则α→β）直接产生w或说：w是v的直接推导，或说：w直接归约到v，记作

vw例：G：S→0S1，S→01直接推导：0S10011

（v=0S1，w=0011，使用规则S→01，γ=0，δ=1）S0S1（v=S，w=0S1，使用规则S→0S1，γ=ε，δ=ε）

0S100S11

（v=0S1，w=00S11，使用规则S→0S1，γ=0，δ=1）第24页，共63页，2023年，2月20日，星期二例文法G=（VN，VT，P，S） VN={标识符，字母，数字}； VT={a,b,c,…x,y,z,0,1,…,9} P={<标识符>→<字母> <标识符>→<标识符><字母> <标识符>→<标识符><数字> <字母>→a,…,<字母>→z<数字>→0,…,<数字>→9}

S=<标识符>指出下面直接推导所使用的规则：<标识符>

<标识符><字母><标识符>

<字母><数字>

<字母><字母><数字>abc<数字>abc5第25页，共63页，2023年，2月20日，星期二例：G：S→0S1，S→010S100S11000S11100001111即0S100001111也记作0S100001111若存在v=w0w1...wn=w,(n>0)，则称v推导出（产生）w（推导长度为n），或称w归约v.记作vw。若有vw，或v=w，则记为vw+++*+**和注：包含0步推导；而不包含0步推导。*+推导第26页，共63页，2023年，2月20日，星期二例G:<标识符>→<字母> <标识符>→<标识符><字母> <标识符>→<标识符><数字> <字母>→a│b│…│z<数字>→0│1│…│9

<标识符><标识符><数字><字母><数字>x<数字>x1即：<标识符>x1也可记作：<标识符>x1+*第27页，共63页，2023年，2月20日，星期二句型设G[S]是一文法，如果符号串x是从开始符号推导出来的，即Sx，则称x是文法G[S]的句型。句子x仅由终结符号组成（即Sx，且x∈VT*），则称x是G[S]的句子。例：G：S→0S1，S→01S0S100S11000S11100001111三、文法的句型、句子的定义**第28页，共63页，2023年，2月20日，星期二四、语言的定义由文法G生成的语言记为L(G)，它是文法G的全部句子的集合:L(G)={x|Sx，且x∈VT*，其中S为文法的开始符号}文法描述的语言是该文法一切句子的集合。

例：G：S→0S1，S→01S0S100S11…

0n-1S1n-1

0n1nL(G)={0n1n|n≥1}*第29页，共63页，2023年，2月20日，星期二例3.3设G=(VN,VT,P,S),VN={S,B,E},VT={a,b,e}, P由下列产生式组成：（1）S→aSBE（2）S→aBE（3）EB→BE（4）aB→ab（5）bB→bb（6）bE→be（7）eE→eeS

an-1S(BE)n-1an(BE)nanBnEn…anbnen

L(G)={anbnen|n≥1}**第30页，共63页，2023年，2月20日，星期二五、文法的等价若L(G1)=L(G2)，则称文法G1和G2是等价的。

如文法G1[A]：A→0R与G2[S]：S→0S1等价

A→01S→01R→A1注：语言和文法的对应关系是一对多（1：n）的关系。第31页，共63页，2023年，2月20日，星期二第五节文法的类型通过对产生式施加不同的限制，Chomsky将文法分为四种类型（称为Chomsky文法）第32页，共63页，2023年，2月20日，星期二一、文法的类型0型文法：对任一产生式α→β，都有α∈(VN∪VT)+，且至少包含一非终结符，β∈(VN∪VT)*

1型文法：对任一产生式α→β，都有|β|≥|α|，仅仅S→ε除外

2型文法：对任一产生式α→β，都有α∈VN，β∈(VN∪VT)*

3型文法：任一产生式α→β的形式都为(1)A→aB或

A→a，其中A∈VN，B∈VN，a∈VT*(右线性文法)

或(2)A→Ba或

A→a，其中A∈VN，B∈VN，a∈VT*(左线性文法)第33页，共63页，2023年，2月20日，星期二1型文法：对任一产生式α→β，都有|β|≥|α|，仅仅S→ε除外上下文有关文法：α1Aα2→α1βα2(A在VN中，其他在V*中，β≠ε)2型文法：对任一产生式α→β，都有α∈VN，β∈(VN∪VT)*上下文无关文法：A→β(A在VN中，β在V*中，)3型文法也叫正规文法第34页，共63页，2023年，2月20日，星期二例：1型（上下文有关）文法文法G[S]： S→aSBE S→aBE EB→BE aB→ab bB→bb bE→be eE→ee第35页，共63页，2023年，2月20日，星期二例：2型（上下文无关）文法文法G[S]： S→aB|bA A→a|aS|bAA B→b|bS|aBB

例:3型文法G[S]：S→0A|1B|0 A→0A|1B|0S B→1B|1|0第36页，共63页，2023年，2月20日，星期二四种文法之间的关系是将产生式做进一步限制而定义的，他们之间的逐级“包含”关系2型文法1型文法0型文法3型文法第37页，共63页，2023年，2月20日，星期二二、文法和语言0型文法(PSG)产生的语言称为0型语言1型文法或上下文有关文法（CSG）产生的语言称为1型语言或上下文有关语言（CSL）2型文法或上下文无关文法（CFG）产生的语言称为2型语言或上下文无关语言（CFL）

3型文法或正则（正规）文法（RG）产生的语言称为3型语言或正则（正规）语言（RL）第38页，共63页，2023年，2月20日，星期二第六节上下文无关文法及其语法树上下文无关文法有足够的能力描述现今程序设计语言的语法结构算术表达式语句赋值语句条件语句读语句……第39页，共63页，2023年，2月20日，星期二算术表达式上下文无关文法表示：文法G=({E},{+,*,i,(,)},P,E） P: E→i E→E+E E→E*E E→(E)条件语句上下文无关文法表示<条件语句>→if<条件>then<语句>|

if<条件>then<语句>else<语句>第40页，共63页，2023年，2月20日，星期二一、上下文无关文法的语法树用于描述上下文无关文法的句型推导的直观方法设G=(VN,VT,P,S)为一cfg，若一棵树满足下列4个条件，则此树称作G的语法树(推导树)(派生树）：1.每个结点都有一个标记，此标记是V的一个符号2.根的标记是S3.若一结点n至少有一个它自己除外的子孙，并且有标记A，则肯定A∈VN4.如果结点n有标记A,其直接子孙结点从左到右的次序是n1，n2，…，nk，其标记分别为A1，A2，…，Ak，那么A→A1A2，…，Ak一定是P中的一个产生式第41页，共63页，2023年，2月20日，星期二例:G[S]: S→aAS A→SbA A→SS S→a A→ba

SaASSbAaaba句型aabbaa的语法树（推导树）叶子结点：树中没有子孙的结点。

从左到右读出推导树的叶子标记，所得的句型为推导树的结果。也把该推导树称为该句型的语法树。第42页，共63页，2023年，2月20日，星期二推导过程中施用产生式的顺序例:G[S]: S→aAS A→SbA A→SS S→a A→ba

SaASSbAaaba句型aabbaa的语法树（推导树）SaASaAaaSbAaaSbbaaaabbaaSaASaSbASaabASaabbaSaabbaaSaASaSbASaSbAaaabAaaabbaa第43页，共63页，2023年，2月20日，星期二最右（最左）推导：在推导的任何一步αβ，其中α、β是句型，都是对α中的最右（左）非终结符进行替换最右推导被称为规范推导。由规范推导所得的句型称为规范句型SaASaAaaSbAaaSbbaaaabbaaSaASaSbASaabASaabbaSaabbaaSaASaSbASaSbAaaabAaaabbaa例:G[S]: S→aAS A→SbA A→SS S→a A→ba第44页，共63页，2023年，2月20日，星期二一棵语法树表示了一个句型的种种可能的(但未必是所有的)不同推导过程，包括最左(最右)推导。但是，一个句型是否只对应唯一的一棵语法树呢?一个句型是否只有唯一的一个最左(最右)推导呢?第45页，共63页，2023年，2月20日，星期二例：G[E]:

E→i E→E+E E→E*E E→(E)

EE+EE*Eiii

EE*EiE+Eii句型i*i+i的两个不同的最左推导：推导1：EE+EE*E+Ei*E+Ei*i+Ei*i+i推导2：EE*Ei*Ei*E+Ei*i+Ei*i+i问题：一个句型是否对应唯一的一棵语法树？第46页，共63页，2023年，2月20日，星期二二、二义文法

若一个文法存在某个句子对应两棵不同的语法树，则称这个文法是二义的。

或者说，若一个文法存在某个句子有两个不同的最左（右）推导，则称这个文法是二义的。文法的二义性和语言的二义性是两个不同的概念。因为可能有两个不同的文法G和G′，其中G是二义的，但是却有L(G)=L(G′)，也就是说，这两个文法所产生的语言是相同的。产生某上下文无关语言的每一个文法都是二义的，则称此语言是先天二义的。第47页，共63页，2023年，2月20日，星期二判定任给的一个上下文无关文法是否二义，或它是否产生一个先天二义的上下文无关语言，这两个问题是递归不可解的。但可以为无二义性寻找一组充分条件。

二义文法改造为无二义文法G[E]:E→iG[E]：E→T|E+T E→E+ET→F|T*F E→E*EF→（E）|i E→(E)规定优先顺序和结合律对于一个程序设计语言来说，常常希望它的文法是无二义的，因为希望对它的每个语句的分析是唯一的。第48页，共63页，2023年，2月20日，星期二第七节句型的分析句型分析

就是识别一个符号串是否为某文法的句型，是某个推导的构造过程。在语言的编译实现中，把完成句型分析的程序称为分析程序或识别程序。分析算法又称识别算法。从左到右的分析算法，即总是从左到右地识别输入符号串，首先识别符号串中的最左符号，进而依次识别右边的一个符号。第49页，共63页，2023年，2月20日，星期二分析算法可分为：

自上而下分析法（推导）：

从文法的开始符号出发，反复使用各种产生式，寻找与输入符号匹配的推导。（从文法符号开始，将它做为语法树的根，向下逐步建立语法树，使语法树的结果正好是输入符号串）

自下而上分析法（归约）：

从输入符号串开始，逐步进行归约，直至归约到文法的开始符号。（从输入符号串开始，以它做为语法树的结果，自底向上的构造语法树）

两种方法反映了两种不同的语法树的构造过程第50页，共63页，2023年，2月20日，星期二一、自上而下的语法分析例：文法G：S→cAd

A→ab

A→a

识别输入串w=cabd是否为该文法的句子？

S S S c A d c A d ab推导过程：ScAdcabd第51页，共63页，2023年，2月20日，星期二二、自下而上的语法分析例：文法G：S→cAd

A→ab

A→a

识别输入串w=cabd是否该文法的句子

S A A cabd cabd cabd

归约过程：ScAdcabd第52页，共63页，2023年，2月20日，星期二自上而下的语法分析

(1)S→cAd(2)A→ab(3)

A→a

识别输入串w=cad是否为该文法的句子若ScAd后选择(2)扩展A，ScAdcabd那将会？

w的第二个符号可以与叶子结点a得以匹配，但第三个符号却不能与下一叶子结点d匹配？宣告分析失败（其意味着，识别程序不能为串cad构造语法树，即cad不是句子）-显然是错误的结论。导致失败的原因是在分析中对A的选择不是正确的。

ScAdab

这时应该回朔，把A为根的子树剪掉，扫描过的输入串中的a吐出来,再试探用产生式（3）第53页，共63页，2023年，2月20日，星期二自下而上的语法分析

(1)S→cAd(2)A→ab(3)A→a

识别输入串w=cabd是否为该文法的句子对串cabd的分析中，如果不是选择ab用产生式(2),而是选择a用产生式(3)将a归约到了A，那么在cAbd中无法找到一个可归约串了，最终就达不到归约到S的结果，因而也无从知道cabd是一个句子cabd

cAbd

a第54页，共63页，2023年，2月20日，星期二三、句型分析的有关问题1）如何选择使用哪个产生式进行推导？ 在自上而下的分析方法中，假定要被代换的最左非终结符号是V，且有n条规则：V→A1|A2|…|An，那