形式语言与语法分析

形式语言与语法分析第一页，共六十五页，2022年，8月28日第三章语法分析介绍第二页，共六十五页，2022年，8月28日第3章outline语法分析概述1.功能需求(输入，输出，主要功能)2.分析算法+数据结构3.构造语法分析器的通用过程上下文无关文法语法分析树和抽象语法树二义性文法文法变换算法语法错误处理第三页，共六十五页，2022年，8月28日知识关系图开发语法分析程序语法定义基于上下文无关文法使用实现自顶向下自底向上第四页，共六十五页，2022年，8月28日3.1语法分析概述部分语法分析程序的功能输入：词法分析程序输出的Token/TokenList输出：语法结构的内部表示(抽象语法树，AST)

或语法错误信息分析过程：从左到右扫描Token序列，根据上下文无关文法，建立语法结构的内部表示，检查语法错误。语法分析Token序列抽象语法树语法错误第五页，共六十五页，2022年，8月28日语法分析过程C程序：Parser输入：Parser输出：if

(x=y)

{z=1;}else{z=0;}

IFLparenidEQidRparenLGidEQnumsemiRGelseLGidEQnumsemiRGIF_Stmt=idid=idnum=idnum第六页，共六十五页，2022年，8月28日程序设计语言的语法结构(1)程序(2)声明

-常量声明

-类型声明

-变量声明

-过程/函数声明(3)程序体(4)语句（赋值语句，条件语句，循环语句，函数调用语句）(5)表达式(算术表达式，逻辑表达式，关系表达式)第七页，共六十五页，2022年，8月28日语法错误语法错误的类型语法结构的开始单词错误表达式E的开始单词是id,(,n---其他Token则出错语法结构的后继单词错误语句；语句----语句，语句标识符或者常量错id

:=E----begin:=E或123:=E关键字错ifEthen语句else

语句----其他关键字则出错括号配对错（（）（））----）（（）第八页，共六十五页，2022年，8月28日语法错误的例子intGetMax(intx;inty){if(x>y){returnx}elsereturny;}}vodmain(){real10,y;10+;GetMax(x,y);}后继单词错括号配对错关键字错,开始单词错标识符错开始单词错第九页，共六十五页，2022年，8月28日语法分析方法自顶向下的分析从上往下生成树的过程自底向上的分析从下往上生成树的过程IF_Stmt=idid=idnum=id0递归下降分析LL(1)分析LR(0),SLR(1),LR(1),LALR(1)第十页，共六十五页，2022年，8月28日语法分析与词法分析的比较阶段（Phase）输入（Input）输出（Output）词法分析（scanner）字符序列Token序列语法分析（parser）Token序列抽象语法树第十一页，共六十五页，2022年，8月28日第3章outline语法分析概述1.功能需求(输入，输出，主要功能)2.分析算法+数据结构3.构造语法分析器的通用过程上下文无关文法语法分析树和抽象语法树二义性文法文法变换算法语法错误处理√第十二页，共六十五页，2022年，8月28日3.2上下文无关文法

不是所有的Token串都是合法的程序，因此需要一个工具来描述合法的Token串。一般地，程序设计语言的结构都是递归结构(recursivestructure)例如：表达式，上下文无关文法非常适合描述这种结构变量是表达式（表达式）是表达式表达式+表达式是表达式第十三页，共六十五页，2022年，8月28日3.2上下文无关文法上下文无关文法是一个四元组(VT,VN,S,P)VT是有限的终极符集合VN是有限的非终极符集合S是开始符，SVNP是产生式的集合，且具有下面的形式：

AX1X2…Xn

其中AVN，Xi(VTVN)符号约定：非终极符用大写字母表示终极符用小写字母表示开始符是第一条产生式左部的符号不绝对！第十四页，共六十五页，2022年，8月28日上下文无关文法的例子例1：简单算术表达式的上下文无关文法，EidE(E)EE+EEE*EEid|(E)|E+E|E*EEid|(E)|E+E|E*EVT:{id,(,),+,*}VN:ES:E第十五页，共六十五页，2022年，8月28日上下文无关文法的例子例2：语句的上下文无关文法：

VT：{id，（，），+，*,=,if,else,while,;}VN：E,StmtS：StmtStmt

id=EStmtifEStmtelseStmtStmtwhileEStmtStmtStmt;Stmt

EidE(E)EE+EEE*E第十六页，共六十五页，2022年，8月28日上下文无关文法的例子例3：变量声明的上下文无关文法：

变量声明变量声明一个变量定义;变量声明一个变量定义;变量声明变量定义类型标识符序列标识符序列一个标识符标识符序列一个标识符,标识符序列VarDecVarDecVarDef;VarDecVarDef;VarDecVarDefTypeIdListIdListidIdListid,IdList第十七页，共六十五页，2022年，8月28日上下文无关文法是怎样定义语言的？第十八页，共六十五页，2022年，8月28日与上下文无关文法有关的一些概念直接推导()：如果A是一个产生式，则有A,其中表示一步推导(用A→)。这时称是由A直接推导的。“”的含义是，使用一条规则，代替左边的某个符号，产生右端的符号串推导(+)：若通过一步或多步推导可从串导出串,则称为的推导,并记为+星推导(*):称*当且仅当=或+第十九页，共六十五页，2022年，8月28日例子(E)(E+T)(应用产生式2)(E)(T)(应用产生式1)E直接推导出E+T或E直接推导出TETF（E）（E+T）（T+T）（F+T）（i+T）（i+F）（i+n),记作E+(i+n)E经过多步推导出i+nE*EE*i+(i）E经过若干步推导出i+(i）P:(1)ET(2)EE+T(3)TF(4)TT*F(5)F(E)(6)Fi(7)Fn第二十页，共六十五页，2022年，8月28日与上下文无关文法有关的一些概念句型：如果有S*,S是文法的开始符,∈(VTVN)*，则称是G的句型句子：如果有S+,S是文法的开始符,∈VT*，则称是G的句子语言：

L(G)={|S+,∈VT*}即文法G的所有句子的集合文法等价：

G1和G2两个文法,若L(G1)=L(G2),则称G1和G2等价第二十一页，共六十五页，2022年，8月28日例子句型:E,T,E+T,F,T*F,i,n,(E),

…….句子:i,n,(i),(n),i+i,i+n,……

语言:{i,n,(i),(n),i+i,i+n,……}P:(1)ET(2)EE+T(3)TF(4)TT*F(5)F(E)(6)Fi(7)Fn第二十二页，共六十五页，2022年，8月28日与上下文无关文法有关的一些概念最左(右)推导：在推导过程中，总是对当前符号串中最左(右)边的非终极符进行替换，称为最左(右)推导,记为l(r)m规范推导：最右推导左(右)句型：通过最左(右)推导得到的句型，称为左(右)句型规范句型：右句型第二十三页，共六十五页，2022年，8月28日例子最左推导:i+T*n+Flmi+F*n+F最右推导: i+T*n+F

rmi+T*n+i左句型:i+i*F右句型:E+(i)P:(1)ET(2)EE+T(3)TF(4)TT*F(5)F(E)(6)Fi(7)Fn第二十四页，共六十五页，2022年，8月28日特别注意例如文法G:ND|NDD0|1|2|…|9

NrmNDrm

N8rmND8rm

N98rm

D98rm198,句子198的最右推导

NrmNDNDD,句型NDD不存在最右推导每个句子一定有最右(规范)推导每个句型不一定有最右(规范)推导第二十五页，共六十五页，2022年，8月28日上下文无关文法小结ContextFreeGrammar,CFG(VT,VN,S,P)推导，句型，句子，语言的概念及含义语言与文法第二十六页，共六十五页，2022年，8月28日Chomsky文法分类第二十七页，共六十五页，2022年，8月28日Chomsky文法分类上下文无关文法只是文法的一种。文法有很多种。Chomsky将文法分为四类：0型文法：短语文法。产生式：，中至少有一个非终极符。0型语言。1型文法：上下文相关文法。产生式：A,,可为。1型语言(上下文有关语言)。2型文法：上下文无关文法。产生式：A，可为。2型语言(上下文无关语言)。3型文法：正则文法。产生式：AaB,Aa。3型语言(正则语言)。第二十八页，共六十五页，2022年，8月28日Chomsky文法分类描述能力：0型文法〉1型文法〉2型文法〉3型文法对应自动机：0型文法对应图灵机1型文法对应线性有届自动机2型文法对应下推自动机3型文法对应有限自动机第二十九页，共六十五页，2022年，8月28日第3章outline语法分析概述1.功能需求(输入，输出，主要功能)2.分析算法+数据结构3.构造语法分析器的通用过程上下文无关文法语法分析树和抽象语法树二义性文法文法变换算法语法错误处理√√第三十页，共六十五页，2022年，8月28日3.3语法分析树和抽象语法树问题:推导是从开始符产生句型的一种方法;对同一个句型存在多个推导：NNDNDDND8N98…或N9DN98…

或DDDDD8D98198

或D9DD98198或1DD19D198或1D8198

……

即线性推导不能唯一地表示句子的结构语法分析树:(SyntaxAnalysisTree)用于表示句型结构的一种较好方法;第三十一页，共六十五页，2022年，8月28日例子P:(1)ET(2)EE+T(3)TF(4)TT*F(5)F(E)(6)Fi(7)Fn句型（句子）:i+i*n该句型存在多个推导：语法分析树：第三十二页，共六十五页，2022年，8月28日语法分析树语法分析树是针对某个特定CFG的带标号的树树的每个节点都标记一个符号：树的根节点标记文法的开始符;树的每个叶子节点标记一个终极符;若有树的中间节点标记为A,它有n个儿子节点，从左到右标记为B1,……,Bn,则G中定存在产生式AB1…Bn;第三十三页，共六十五页，2022年，8月28日抽象语法树(AST)语法分析树存在的问题包含很多不必要(对语义分析和代码生成而言)的节点抽象语法树只包含必要的节点作为语法分析程序输出句型(句子):i+i*nP:(1)ET(2)EE+T(3)TF(4)TT*F(5)F(E)(6)Fi(7)Fn第三十四页，共六十五页，2022年，8月28日第3章outline语法分析概述1.功能需求(输入，输出，主要功能)2.分析算法+数据结构3.构造语法分析器的通用过程上下文无关文法语法分析树和抽象语法树二义性文法文法变换算法语法错误处理√√√第三十五页，共六十五页，2022年，8月28日3.4二义性文法二义性文法(ambiguousgrammar)

如果文法的一个句子有两棵或两棵以上不同的语法分析树，则称该句子是二义性的。

包含二义性句子的文法，称为二义性文法。第三十六页，共六十五页，2022年，8月28日二义性文法的例子P:ExpExp+ExpExpExp–ExpExpExp*ExpExpExp/ExpExp(Exp)ExpidExpnumid+id*id第三十七页，共六十五页，2022年，8月28日

<Stm>if<Exp>then<Stm>else<Stm> <Stm>if<Exp>then<Stm> <Stm>......假设有条件语句

ife1thenife2thens1elses2则可有下图所示的两棵不同的语法分析树：

if语句的二义性ififthen<Stm><Stm><Stm><Stm>elsethen<Exp><Exp>e1e2s1s2<Stm><Stm><Stm><Stm>elsethenifthenif<Exp><Exp>e1e2s1s1第三十八页，共六十五页，2022年，8月28日二义性文法(ambiguousgrammar)二义性会给语法分析带来不确定性，应尽量避免写出二义性的文法。但有时用二义性文法定义语法结构更简单直观。文法二义性问题是不可判定的，也就是不存在一种算法，能在有限步内确切的判定一个文法不是二义性文法。若要证明文法是二义性的，只要举出一个有两棵以上语法分析树的句子即可。若能控制文法的二义性，即加入人为的附加条件，则二义文法的存在并非坏事，有时二义性文法可以简化文法的表示。消除文法二义性的常用方法

1、规定符号的优先级

2、规定符号的结合性第三十九页，共六十五页，2022年，8月28日表达式的无二义性文法有二义性的表达式文法:ExpExp+ExpExpExp–ExpExpExp*ExpExpExp/ExpExp(Exp)ExpidExpnum无二义性的表达式的文法：ETEE+T|E-TTFTT*F|T/FF(E)FidFnum第四十页，共六十五页，2022年，8月28日If语句的无二义性文法定义

StmtMatched_stmt|Unmatched_stmtMatched_stmtifEthenMatched_stmtelseMatched_stmt|otherUnmatched_stmtifEthenStmt|ifEthenMatched_stmt

elseUnmatched_stmt第四十一页，共六十五页，2022年，8月28日第3章outline语法分析概述1.功能需求(输入，输出，主要功能)2.分析算法+数据结构3.构造语法分析器的通用过程上下文无关文法语法分析树和抽象语法树二义性文法文法变换算法语法错误处理√√√√第四十二页，共六十五页，2022年，8月28日文法变换有些语法分析方法要求被分析的文法满足一定的约束条件，当被分析的文法不满足这些条件时，常常要进行文法变换。文法变换必须保证变换前后的两个文法G1和G2是等价的，即L(G1)=L(G2)常用文法变换方法增补文法去除空产生式消除无用产生式消除特型产生式消除公共前缀消除左递归(直接，间接)第四十三页，共六十五页，2022年，8月28日文法变换算法（1）何时需要增补：在自底向上(bottomtoup)的语法分析方法中，要求文法开始符不能出现在产生式的右部.否则，需要对文法进行增补。变换方法：在原产生式基础上，增加一条产生式：ZS，S为原文法的开始符，Z为增补文法的开始符第四十四页，共六十五页，2022年，8月28日文法变换算法（2）文法中空产生式的存在常常给语法分析带来困难，因此最好将空产生式消除掉。变换依据：文法G中除了S以外的空产生式(A)可以消除;

变换方法：找出所有可以推导出的非终极符,记为S;对于所有产生式AX1X2……Xi-1XiXi+1……XnXiS增加AX1X2……Xi-1Xi+1……Xn直到没有新的产生式产生删除对应空产生式,除了S不可以删除第四十五页，共六十五页，2022年，8月28日消除空产生式的例子S|AaBBABB|aB|bS={S,B,A}ABABB

SaBBSAaBB

SAaBSAaSa

SaB

变换后得到的文法：S|AaBB|aBB|AaB|aB|Aa|aABB|B|aBb第四十六页，共六十五页，2022年，8月28日文法变换算法（3）无用产生式:A,A不出现在任何句型中;消除方法：关键是找到这样的非终极符，how?生成会出现在句型中的非终极符集合SSSS={S}SiSS,Si1,……,Sin把1,……,n中的所有非终极符加入SS中;重复直到没有新的非终极符加入;不属于SS的非终极符,它们的产生式是无用产生式,删除掉;第四十七页，共六十五页，2022年，8月28日消除无用产生式的例子S|AaBBABB|aB|bCcSS={S}SS={S,A,B}SS={S,A,B}Cc是无用产生式第四十八页，共六十五页，2022年，8月28日文法变换算法（4）特型产生式:AB消除算法对每个非终极符A,构造SA={B|A+B,BVN}如果CSA,而且C不是特型产生式,则增加A;删除特型产生式;删除无用产生式;第四十九页，共六十五页，2022年，8月28日消除特型产生式的例子S|AAB|aBbSS={A,B}SA={B}SaSbAbS|a|bAa|bBbSB={}第五十页，共六十五页，2022年，8月28日文法变换算法（5）消除公共前缀(leftfactoring)公共前缀A1|…|n|1|…|m提取公因子AA’|1|…|mA’

1|…|n第五十一页，共六十五页，2022年，8月28日文法变换算法（6-1）消除左递归(leftrecursion)

递归分为直接左递归和间接左递归直接左递归:A

A1|…|An|1|…|m消除方法:A1A’|…|mA’A’

1A’|…|nA’|第五十二页，共六十五页，2022年，8月28日消除左递归的例子P:(1)ET(2)EE+T(3)TF(4)TT*F(5)F(E)(6)Fi(7)Fn

ETE’E’+TE’|

EE+T|T

=+T1=T第五十三页，共六十五页，2022年，8月28日文法变换算法（6-2）消除左递归(leftrecursion)间接左递归:

消除方法:非终极符排序消元法

SAb

ASa|b

1:S2:AAAba|bAbA’A’baA’|第五十四页，共六十五页，2022年，8月28日文法变换算法（6-2）消除左递归(leftrecursion)间接左递归:

消除方法:非终极符排序消元法

SQc|

cQRb|b

RSa|a

1:R2:Q3:SRSa|aQRb|bSab|ab|bSQc|cSabc|abc|bc|cS(abc|bc|c)S’S’abcS’|第五十五页，共六十五页，2022年，8月28日文法变换算法（6-2）消除左递归(leftrecursion)间接左递归:

排序不同，变换后文法也不同

SQc|

cQRb|b

RSa|a

1:S2:Q3:RSQc|cQRb|bRSa|a(Qc|c)a|aQca|ca|a

(Rb|b)ca|ca|a

SQc|cQRb|bR(bca|ca|a)R’R’bcaR’|第五十六页，共六十五页，2022年，8月28日第3章outline语法分析概述1.功能需求(输入，输出，主要功能)2.分析算法+数据结构3.构造语法分析器的通用过程上