编译原理-第3章文法和语法

第3章 文法和语言教学要求：本章是编译原理课程的理论基础，要求理解文法、语言、规范推导、规范归约和短语、简单短语、句柄的基本概念；掌握语言的求解方法、文法的二义性的判断方法及句型的分析方法。教学重点：上下文无关文法，语言定义

一、语言语言是由句子组成的集合，是由一组记号所构成的集合。汉语--所有符合汉语语法的句子的全体英语--所有符合英语语法的句子的全体程序设计语言--所有该语言的程序的全体“我是大学生”是否是该语言的句子？〈句子〉::=〈主语〉〈谓语〉〈主语〉::=〈代词〉|〈名词〉〈代词〉::=你|我|他〈名词〉::=王明|大学生|工人|英语〈谓语〉::=〈动词〉〈直接宾语〉〈动词〉::=是|学习〈直接宾语〉::=〈代词〉|〈名词〉二、文法一种语言描述工具，用来定义句子的结构，用有限的规则把语言的全部句子描述出来，是以有穷的集合刻划无穷的集合的工具。“::=”与“→”等价，表示为“由什么组成”或“定义为”〈句子〉〈主语〉〈谓语〉

〈代词〉〈谓语〉

我〈谓语〉

我〈动词〉〈直接宾语〉

我是〈直接宾语〉

我是〈名词〉

我是大学生〈句子〉::=〈主语〉〈谓语〉〈主语〉::=〈代词〉|〈名词〉〈代词〉::=你|我|他〈名词〉::=王明|大学生|工人|英语〈谓语〉::=〈动词〉〈直接宾语〉〈动词〉::=是|学习〈直接宾语〉::=〈代词〉|〈名词〉语法变量（在形式语言中又称“非终结符”）单词符号（在形式语言中又称“终结符号”)三、符号和符号串例如：汉语的字母表中包括汉字、数字及标点符号等。C语言的字母表是由字母、数字、若干专用符号及IF、FOR之类的保留字组成。1、字母表和符号串字母表：符号的非空有限集例：={a，b，c}符号：字母表中的元素例：a，b，c符号串：符号的有穷序列例：a,aa,ac,abc，..空符号串：无任何符号的符号串(ε)符号串集合：由符号串构成的集合。2、符号串的运算符号串的长度：符号串中符号的个数.符号串s的长度记为|s|。ε的长度为0符号串的连接：符号串x、y的连接,是把y的符号写在x的符号之后得到的符号串xy

例x=ST,y=abu则xy=STabu

|x|=2,|y|=3,|xy|=5εx=xε=x方幂：符号串x自身连接n次得到的符号串

xx…xx(n个x)定义为

xnx0=ε,x1=x,x2=xx,x3=xxxx=AB,则

x0=ε,x1=AB,x2=ABAB,x3=ABABAB对于

n>0,xn=xxn-1=xn-1x

3、符号串集合

若集合A中一切元素都是某字母表上的符号串，则称A为字母表上的符号串集合。两个符号串集合A和B的乘积定义为

AB=xy|xA且yB若集合A=a,bB=c,d则AB=ac,ad,bc,bd{ε}A=A{ε}=A(∵εx=xε=x)使用*表示上的所有有穷长的串（包括ε）的集合。Σ*称为Σ的闭包。从*中除去ε得到的集合记为+。

Σ+称为Σ的正闭包。Σ*=Σ0∪Σ1∪Σ2…∪Σn…Σ+=Σ1∪Σ2…∪Σn…Σ*=Σ0∪Σ+Σ+=ΣΣ*=Σ*ΣΣ+=Σ*-{ε}例：设Σ={0,1}，则Σ*={ε,0,1,00,01,10,11,000,001,010,…}例：设Σ={a,b}，则Σ*={ε,a,b,aa,ab,ba,bb,aaa,aab,…}Σ+={a,b,aa,ab,ba,bb,aaa,aab,…}四、文法和语言的形式定义1、文法的形式定义1）规则（重写规则、产生式或生成式）：是一个有序对（α，β）。记为α→β或α∷=β，其中α∈V+，β∈V*。α称为规则的左部(或生成式的左部)。β称为规则的右部(或生成式的右部)。2）文法G[S]：文法为四元组（VN，VT，P，S）VN：非终结符集VT：终结符集P：产生式（规则）集合S：开始符号（识别符号）VN、VT

和P是非空有穷集。S至少在一条规则中作为左部出现。VN∩VT=φ，S∈VNV=VN∪VT，称为文法G的字母表（字汇表）例:文法G=（VN，VT，P，S） VN={S},VT={0,1} P={S→0S1,S→01} S为开始符号例:文法G=（VN，VT，P，S） VN={标识符，字母，数字}

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

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

S=<标识符>习惯上只将产生式写出。并有如下约定：第一条产生式的左部是开始符号用尖括号括起的是非终结符，否则为终结符。或者大写字母表示非终结符，小写字母表示终结符G可写成G[S]，其中S是开始符号例:文法G=（VN，VT，P，S） VN={S},VT={0,1} P={S→0S1,S→01} S为开始符号可写成：

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

G[S]：S→0S1 S→01

Mini_C介绍

Mini_C语言是在C语言的基础上定义的一种语言（C语言的子集），它的文法定义如下：1<程序>::=MAIN()<语句块>2<语句块>::={<变量声明列表><语句串>}|{语句串}3<变量声明列表>::=<变量声明列表><变量声明>|<变量声明>4<变量声明>::=<变量类型><ID>;5<变量类型>::=int|char|real6<语句串>::=<语句>;|<语句串><语句>;7<语句>::=<赋值语句>|<条件语句>|<循环语句>8<赋值语句>::=<ID>=<算术表达式>9<条件语句>::=if(<条件>)<语句块>|if(<条件>)<语句块>else<语句块>10<循环语句>::=<while语句>|<for语句>

11<while语句>::=while(<条件>)<语句块>12<for语句>::=for(<赋值语句>;<条件>;<算术表达式>)<语句块>13<条件>::=<算术表达式><关系运算符><算术表达式>14<关系运算符>::=>|>=|<|<=|==|!=15<算术表达式>::=<算术表达式>+<项>|<算术表达式>-<项>|<项>五、推导的定义1）直接推导“”α→β是文法G的产生式，γ,δ∈V*，若将α→β作用于v=γαδ得到w=γβδ,则记作

vw，读作v（应用规则α→β）直接产生w（w是v的直接推导或w直接归约到v）例：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）例文法G=（VN，VT，P，S） VN={标识符，字母，数字}

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

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

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

<字母><字母><数字>abc<数字>abc52）长度为n的推导（有限次推导）

若存在v=w0w1...wn=w,(n>0)，

则称v推导出w（或w归约到v）.记作

vw。3）若有vw，或v=w，则记为vw++*例：G：S→0S1，S→010S100S11000S11100001111即0S100001111也记作0S100001111+*六、文法的句型、句子的定义1）句型设G[S]是一文法，如果符号串x是从识别符号推导出来的，即Sx，则称x是文法G[S]的句型。*例：G：S→0S1，S→01S0S100S11000S11100001111*2）句子x仅由终结符号组成（即Sx，且x∈VT*），则称x是G[S]的句子。3）语言由文法G产生的所有句子组成的集合叫做文法G所成描述的语言，记为L(G)。

例：G：S→0S1，S→01L(G)={0n1n|n≥1}

注：产生式中含有递归式，产生的句子是无穷的*L(G)={x|Sx，其中S为文法的开始符号，且x∈VT*}例:文法G[S]： （1）S→dAB （2）A→aA （3）A→a （4）B→Bb （5）B→ε

L（G）=?G生成的每个串都在L(G)中L(G)中的每个串确实能被G生成例：构造生成语言L=的文法。分析：n≧1，所以必须用递归规则。a和b的个数一样多，但c的个数不同，所以将生成含a,b的部分与生成含e的部分分开，A生成ab，B生成e.G[Z]:Z→ABA→aAb|abB→eB|ε≧≧4)文法的等价若L（G1）=L（G2），则称文法G1和G2是等价的。

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

A→01S→01R→A1七、文法的类型（1）0型文法(短语文法)：对任一产生式α→β，都有α∈(VN∪VT)+，β∈(VN∪VT)*

（2）1型文法(上下文有关文法)：

对任一产生式α→β，都有|β|≥|α|，仅仅

S→ε除外。即α1Aα2→α1βα2(A在VN中，其他在V*中，β≠ε)（3）2型文法（上下文无关文法）：对任一产生式α→β，都有α∈VN，β∈(VN∪VT)*

即A→β(A在VN中，β在V*中，)（4）3型文法（正规文法）：任一产生式α→β的形式都为A→aB或A→a，其中A∈VN，B∈VN，a∈VT例：1型（上下文有关）文法

文法G[S]： S→aSBE S→aBE EB→BE aB→ab bB→bb bE→be eE→ee例：2型（上下文无关）文法

文法G[S]： S→aB|bA A→a|aS|bAA B→b|bS|aBB

文法G[S]： S→0A|1B|0 A→0A|1B|0S B→1B|1|0例：定义标识符的3型（正规）文法

文法G[I]： I→lT I→l T→lT

T→dT

T→l

T→d文法和语言0型文法产生的语言称为0型语言1型文法或上下文有关文法（CSG）产生的语言称为1型语言或上下文有关语言（CSL）2型文法或上下文无关文法（CFG）产生的语言称为2型语言或上下文无关语言（CFL）3型文法或正则（正规）文法（RG）产生的语言称为3型语言或正则（正规）语言（RL）八、上下文无关文法及其语法树上下文无关文法有足够的能力描述现今程序设计语言的语法结构。算术表达式语句赋值语句条件语句循环语句……1、语法树与推导用于描述上下文无关文法的句型推导的直观方法

例:

G[S]: S→aAS A→SbA A→SS S→a A→ba

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

从左到右读出推导树的叶子标记，所得的句型为推导树的结果。也把该推导树称为该句型的语法树。推导过程中施用产生式的顺序例:G[S]: S→aAS A→SbA A→SS S→a A→ba

SaASSbAaaba句型aabbaa的语法树（推导树）SaASaAaaSbAaaSbbaaaabbaa2、最左（最右）推导：

在推导的任何一步αβ，其中α、β是句型，都是对α中的最左（右）非终结符进行替换。最右推导被称为规范推导。由规范推导所得的句型称为规范句型。SaASaAaaSbAaaSbbaaaabbaa（最右推导）SaASaSbASaabASaabbaSaabbaa（最左推导）SaASaSbASaSbAaaabAaaabbaa

例:G[S]: S→aAS A→SbA A→SS S→a A→ba问题：一个句型是否对应唯一的一棵语法树？例：G[E]:

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

EE+EE*Eiii

EE*EiE+Eii句型

i*i+i的两个不同的最左推导：推导2：EE*Ei*Ei*E+Ei*i+Ei*i+i推导1：EE+EE*E+Ei*E+Ei*i+Ei*i+i3、二义文法若一个文法存在某个句子对应两棵不同的语法树，则称这个文法是二义的。

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

E→E*EE→(E)G[E]:E→T|E+T T→F|T*F F→（E）|i练习：有文法G[N]：N→SE|ES→SD|DE→0|2|4|6|8|10D→0|1|2|3|4|5|6|7|8|9（1）证明此文法有二义性（2）此文法描述的语言是什么？（3）试写出另一文法，其产生的语言和G[N]产生的语言等价且是无二义性的。八、句型的分析句型分析就是识别一个符号串是否为某文法的句型，是某个推导的构造过程。在语言的编译实现中，把完成句型分析的程序称为分析程序或识别程序。分析算法又称识别算法。从左到右的分析算法，即总是从左到右地识别输入符号串，首先识别符号串中的最左符号，进而依次识别右边的一个符号。1、自上而下的语法分析：从文法的开始符号出发，反复使用各种产生式，寻找与输入符号串匹配的推导。例：文法G：S→cAd

A→ab

A→a

识别输入串

w=cabd是否该文法的句子

S S S c A d c A d ab推导过程：cabdcAd

S2、自下而上的语法分析：从输入符号串开始，逐步进行归约，直至归约到文法的开始符号。例：文法G：S→cAd

A→ab

A→a

识别输入串

w=cabd是否该文法的句子

S A A cabd cabd cabd规约过程：cabdcAd

S3、句型分析的有关问题1）如何选择使用哪个产生式进行推导？ 假定要被代换的最左非终结符号是V，且有n条规则：V→A1|A2|…|An，那么如何确定用哪个右部去替代V？2）如何识别可归约的串？ 在自下而上的分析方法中，在分析程序工作的每一步，都是从当前串中选择一个子串，将它归约到某个非终结符号，该子串