程序设计语言的语法描述公开课一等奖市优质课赛课获奖课件

第3章程序设计语言的语法描述3.1文法的引入3.2上下文无关文法3.3文法举例（略）使用文法对程序设计语言的结构进行定义和描述。6/26/20233.1文法的引入先讨论自然语言的文法。例：thebigelephentateabanana㈠语法树根据英语的语法，上述句子的语法结构可用图（语法树）表示如下：非叶结点称为语法单位，在形式语言中称为非终结符。处于根结点位置的结点又称为开始符号。叶结点称为单词符号，在形式语言中称为终结符。6/26/2023㈡规则可以通过建立一组规则，来描述上述句子的语法结构，规则在形式语言中称为产生式。<句子>→<主语><谓语> <主语>→<冠词><形容词><名词><冠词>→the|a<形容词>→big<名词>→elephant|banana<谓语>→<动词><直接宾语><直接宾语>→<冠词><名词><动词>→ate㈢由规则推导句子可用规则来推导出句子。从开始符号出发，若能从规则推导出某符号串，则该符号串就是该文法的合法的句子，反之语法错误。上述英文句子可用下述规则来描述：6/26/2023 <句子><主语><谓语> <冠词><形容词><名词><谓语> the<形容词><名词><谓语> thebig<名词><谓语> thebigelephant<谓语> thebigelephant<动词><直接宾语> thebigelephantate<直接宾语> thebigelephantate<冠词><名词> thebigelephantatea<名词> thebigelephantateabanana上述推导可简单表示为： <句子>thebigelephantateabanana。值得注意的是用上述规则可推导出多个句子，因存在推导 <句子>abigbananaatetheelephant所以，abigbananaatetheelephant也是文法的一个合法的句子。但意义是荒谬的，也就是说句子的语义是错误的。一个语法正确的句子不能保证其语义是正确的，故一个句子是否正确，需要进行语法和语义两方面检查。综上所述，语言结构通常是用文法来定义和描述，文法是由终结符、非终结符、开始符号（特殊非终结符）及产生式四个要素构成。从开始符号出发，根据产生式能推导出的句子全体称为文法所规定的语言6/26/2023㈣递归规则和递归文法递归是编译技术中的一个重要概念。①递归定义：定义某事物，又用到该事物本身。②递归规则（直接递归）：在规则的左部和右部有相同的非终结符。例：U→xUy，通常用大写字母表示非终结符，用小写字母表示终结符。 ⑴左递归规则：x=ε，U→Uy（ε表示空串） ⑵右递归规则：y=ε，U→xU③间接递归：由规则推导产生。例：V→Uy|Z，U→xV 因存在推导VUyxVy，故存在间接递归。 ⑴间接左递归：若x=ε，则VVy。 ⑵间接右递归：若y=ε，则VxU。④递归文法：含有递归规则和间接递归的文法，称为递归文法。利用递归文法，可以用有穷的规则来描述无穷的语言，这不但解决了语言的定义问题，而且使得对语言的语法检查成为可能。6/26/20233.2 上下文无关文法形式语言的奠基人乔姆斯基（Chomsky）将文法分为4种类型，它们是：短语文法（0型文法）上下文有关文法（1型文法）上下文无关文法（2型文法）正规文法（3型文法）这四种文法在形式语言中都有严格的定义。但对于程序设计语言来说，上下文无关文法已经够用了，上下文无关文法有足够的能力描述大多数现今使用的程序设计语言的语法结构。以后，“文法”一词若无特别说明，则指“上下文无关文法”。6/26/2023㈠文法和语言一个文法G是一个四元式(VT,VN,S,P)，其中VT是一个终结符的非空有限集，终结符通常用小写字母表示。VN是一个非终结符的非空有限集，非终结符通常用大写字母表示。S是一个特殊的非终结符（S∈VN），称为开始符号。P是一个产生式（规则）的有限集合，每个产生式的形式是A→α，其中A∈VN，α∈(VT∪VN)*。①终结符是语言的基本符号，即程序设计语言的单词。语法分析时，终结符用单词的种别表示。根据前面约定： 标识符（简单变量）： i 无符号整常数： x 无符号实常数： y 单字符单词： 用单词本身表示（例单词“+”的 种别用+表示） 多字符单词： 需特别指定（例“++”用$表示）6/26/2023②非终结符表示抽象的语法单位.例“算术表达式”、“布尔表达式”、“赋值语句”、“说明语句”和“程序”等。非终结符通常用大写字母表示，也可以用带尖括号的汉字表示。③开始符号是一个特殊的非终结符，它代表我们最感兴趣的语法单位。例如讨论算术表达式，那么描述算术表达式文法的开始符号就是<算术表达式>。在程序设计语言中，我们最感兴趣的语法单位是“程序”。④产生式是定义语法单位的一种书写规则。上下文无关文法产生式的左部必定是一个非终结符，该非终结符称为左部符号。产生式的右部是终结符和非终结符经有限次连接构成的文法符号串，可以是空字ε。四种文法的区别主要是对产生式的左部和右部的限制不同。若干个左部符号相同的产生式，可合并为一个，例： A→α1|α2|……|αn，其中αi称为A的候选式(1≤i≤n)。6/26/2023例1：描述算术表达式文法G=(VT,VN,S,P)，其中 VT={+,-,*,/,i,x,y,(,)} VN={<算术表达式>,<项>,<因子>} S=<算术表达式> P={ <算术表达式>→<算术表达式>+<项> <算术表达式>→<算术表达式>-<项> <算术表达式>→<项> <项>→<项>*<因子> <项>→<项>/<因子> <项>→<因子> <因子>→(<算术表达式>) <因子>→i //标识符 <因子>→x //无符号整常数 <因子>→y //无符号实常数 }根据上述文法，可推导出任何仅包含加减乘除的算术表达式。6/26/2023

因已约定非终结符和终结符的书写方式，非终结符和终结符在产生式中一目了然，故终结符集VT和非终结符集VN无需再显式列出。若规定左部符号为开始符号的产生式写在所定义文法的第一行，上述文法G又可简单表示为如下形式： <算术表达式>→<算术表达式>+<项> <算术表达式>→<算术表达式>-<项> <算术表达式>→<项> <项>→<项>*<因子> <项>→<项>/<因子> <项>→<因子> <因子>→(<算术表达式>) <因子>→i <因子>→x <因子>→y若用E表示<算术表达式>、T表示<项>、F表示<因子>，借助符号'|'，算术表达式文法G可表示成如下最简形式：

E→E+T︱E–T︱T T→T*F︱T/F︱F F→(E)︱i︱x︱y6/26/2023例2：描述算术表达式文法G=(VT,VN,S,P)，其中 VT={+,-,*,/,i,x,y,(,)} VN={<算术表达式} S=<算术表达式> P={ <算术表达式>→<算术表达式>+<算术表达式> <算术表达式>→<算术表达式>-<算术表达式> <算术表达式>→<算术表达式>*<算术表达式> <算术表达式>→<算术表达式>/<算术表达式> <算术表达式>→(<算术表达式>) <算术表达式>→i //标识符 <算术表达式>→x //无符号整常数 <算术表达式>→y //无符号实常数 }根据上述文法，同样可推导出任何仅包含加减乘除的算术表达式。用E表示<算术表达式>，上述文法可简记为： E→E+E|E-E|E*E|E/E|(E)|i|x|y6/26/2023㈡基本术语以文法G： E→E+E|E*E|(E)|i为例，进行下述讨论。①直接推出和直接归约②推导和归约若α1α2…αn，则称该直接推出序列是从α1到αn的一个推导，记作α1αn或ααn。 α1αn：从α1始，经一步或一步以上可推导出αn。 α1αn：从α1始，经０步或０步以上可推导出αn，即 α1αn或α1=αn。也可称直接归约序列αn,αn-1,…,α1为αn到α1的一个归约。③句型若存在推导Sα（S为文法的开始符号），则称α是文法的一个句型。④句子仅包含终结符的句型称为句子。6/26/2023⑤语言文法Ｇ所能推导出的句子全体称为该文法的语言，记为： L(G)={α|(Sα)∧(α∈VT*)}⑥等价文法Ｇ1和Ｇ2是二个不同的文法，若L(G1)=L(G2)，则称G1和G2是等价文法。等价文法的存在，使我们能够在不改变文法所规定的语言的前提下，为了某种目的改造文法。⑦最左推导和最右推导在各种推导中，考虑今后语法分析的需要，我们仅对两种推导感兴趣。1）最左推导在推导过程中始终对最左面的非终结符进行替换，记为。2）最右推导在推导过程中始终对最右面的非终结符进行替换，记为。6/26/2023㈢文法的二义性①语法树我们可以用一个有向图表示一个句型的推导，这种表示称为语法树。语法树有助于理解一个句子语法结构的层次。在一般情况下，某一句型不论其推导过程如何，其最终形成的语法树是相同的，故语法树是不同推导过程的共性抽象。若仅进行最左（右）推导，则语法树和最左（右）推导等价。②二义文法若一个文法所产生的语言中，只要存在一个句子，它有二个最左推导，或有二个最右推导，或句子的推导对应两棵语法树，则称该文法为二义文法。③二义文法的利用和处理1)根据条件修改文法，语言不变。 算符优先性：规定*优先于+，i+i*i等价于i+(i*i)。 算符结合性：规定同级运算服从左结合，i+i+i等价于 (i+i)+i。

2)根据条件修改编译程序的语法分析表，文法保持不变（详见第四、五章）。6/26/20231）根据条件修改文法，语言不变。算符优先性：规定*优先于+，i+i*i等价于i+(i*i)。算符结合性：规定同级运算服从左结合，i+i+i等价于(i+i)+i。例文法GG：E→E+E|E*E|(E)|i是一个二义文法。根据上述条件将文法G修改成G’，如下所示G'：E→E+T|TT→T*F|FF→(E)|i显然G‘不是二义文法，但L(G)=L(G’)，故G和G‘等价。例句子i+i*i的最右推导：EE+TE+T*FE+T*iE+F*iE+i*iT+i*iF+i*ii+i*iETT*F?+?*?…先形成+，才有可能形成*。若先形成*，只有带括号才可能形成+。6/26/20232）根据条件修改编译程序的语法分析表，文法保持不变。例文法G：<语句>→if

标识符

then<语句>else<语句> S→fitSeS<语句>→if

标识符

then<语句> S→fitS<语句>→标识符=<算术表达式> S→i=E<算术表达式>→无符号整常数 E→x程序段 a=2 ifxthenifythena=4elsea=6相应的语法结构表示为 i=x fitfiti=xei=x句子fitfiti=xei=x的最左推导序列有二个，如下所示：SfitSeSfitfitSeSfitfiti=EeSfitfiti=xeSfitfiti=xei=Efitfiti=xei=xSfitSfitfitSeSfitfiti=EeSfitfiti=xeSfitfiti=xei=Efifii=xei=x因句子fitfiti=xei=x存在二个最左推导，故文法G为二义文法。6/26/2023这样对于该程序段有二个解释：假设else和最近的if结合，即a=2ifxthenbegin ifythena=4elsea=6end