第2章+文法和语言

1、文法和语言文法和语言 n一个程序设计语言是一个记号系统，它的完整一个程序设计语言是一个记号系统，它的完整 定义应包括两个方面定义应包括两个方面: q语法语法 指一组规则，用它可以形成和产生一个合适的程序。 q语义语义 n静态语义 是一系列限定规则，并确定哪些合乎语法的程序是合 适的； n动态语义 也称作运行语义或执行语义，表明程序要做些什么， 要计算什么。 n文法是阐明语法的一个工具文法是阐明语法的一个工具 2. 2 符号和符号串符号和符号串 n字母表字母表 q字母表是元素的非空有穷集合字母表是元素的非空有穷集合 n符号符号 q字母表中的元素称为符号字母表中的元素称为符号 n符号串符号串 q由

2、符号组成的任何有穷序列由符号组成的任何有穷序列 q符号串符号串x的长度：的长度：x所包含的符号个数，记作所包含的符号个数，记作|x| q空符号串空符号串 n符号串的头、尾、固有头、固有尾符号串的头、尾、固有头、固有尾 n符号串的连接符号串的连接 q设设x和和y是符号串，它们的连接是符号串，它们的连接xy是把是把y的符号写在的符号写在x 的符号之后得到的符号串。的符号之后得到的符号串。 n符号串的方幂符号串的方幂 q设设x是符号串，把是符号串，把x自身连接自身连接n次得到符号串次得到符号串z，即即 z=xx.xx，称为符号串称为符号串x的方幂。的方幂。 0=, n =n-1 =n-1（n0） n

3、符号串集合及其运算符号串集合及其运算 q若集合若集合A中的一切元素都是字母表上的符号串，则中的一切元素都是字母表上的符号串，则 称称A为该字母表上的符号串集合。为该字母表上的符号串集合。 q合并：字符串集合合并：字符串集合A和和B的合并的合并AB=|A或或 B。 q乘积：字符串集合乘积：字符串集合A和和B的乘积的乘积AB=|A且且 B。 显然显然A=A=A。 q幂：幂：An=An-1A=AAn-1（n0），），并规定并规定A0=。 q正闭包：正闭包：A+ =A1A2An。 q闭包：闭包：A*=A0A+。 显然显然*=012n 。 *表示表示上的所有有穷长的串的集合上的所有有穷长的串的集合 2.

4、3 文法和语言的形式定义文法和语言的形式定义 n引例引例1 =a, A=an|n1 n引例引例2 =a,b, A=anbm|n,m1 n引例引例3 =a,b, A=anbn|n1 n定义定义2.1-文法文法 文法文法G定义为四元组定义为四元组(VN，VT，P，S)。其中其中 VN: 非终结符的非空有穷集；非终结符的非空有穷集； VT: 终结符的非空有穷集；终结符的非空有穷集； P: 产生式（也称规则）的非空有穷集；产生式（也称规则）的非空有穷集； S: 开始符号，它是一个非终结符，至少要开始符号，它是一个非终结符，至少要 在一条规则中作为左部出现。在一条规则中作为左部出现。 通常用通常用V表示

5、表示VN VT，V称为文法称为文法G的的文法文法 符号集符号集。 n例例1 =a,b, A=ambn|mn0 n例例2 =a,b, A=wwR|wR是是w的反向串的反向串 n例例3 GS: SaSBE|aBE EB BE aB ab bB bb bE be eE ee n定义定义2.2-直接推导、直接归约直接推导、直接归约 设设 是文法是文法G=(VN ，VT，P，S)的规则，的规则， 和和 是是V*中的任意符号串。若有符号串中的任意符号串。若有符号串v，w满满 足：足：v=， w=，则说则说 v（应用规则应用规则 ）直接产生）直接产生w，或说或说w是是v的直接推导，或说的直接推导，或说 w直

6、接归约到直接归约到v，记作记作 vw。 n定义定义2.3 -推导推导 若存在若存在v w0 w1 . wn=w (n0)，则则 说说v推导出推导出w，或说或说w归约到归约到v，记为记为 v w。 n定义定义2.4-星推导星推导 若有若有v w，或或v=w，则记为则记为 v w。 * n最左（最右）推导最左（最右）推导 q如果在推导的任何一步如果在推导的任何一步 ，其中，其中 V* ，都是，都是 对对 中的最左（最右）非终结符进行替换，则称这中的最左（最右）非终结符进行替换，则称这 种推导为最左（最右）推导种推导为最左（最右）推导 n规范推导规范推导 q在形式语言中，最右推导常被称为规范推导。在

7、形式语言中，最右推导常被称为规范推导。 n定义定义2.5-句型、句子句型、句子 设设有文法有文法G。若若S x，则称则称x是文法是文法G的句型；的句型； 若若S x，且且xVT*，则称则称x是文法是文法G的句子。的句子。 n规范句型规范句型 q由规范推导所得的句型称为规范句型。由规范推导所得的句型称为规范句型。 * * n定义定义2.6- 语言语言 由文法由文法G生成的语言记为生成的语言记为L(G),它是文法它是文法G的一切的一切 句子的集合。句子的集合。 n定义定义2.7-文法等价文法等价 若若L(G1) = L(G2)，则称文法则称文法G1和和G2是等价的。是等价的。 2.4 文法的类型文

8、法的类型 nChomsky分类分类 q0型文法型文法 短语文法短语文法 对任一产生式对任一产生式，都有都有(VNVT)+且至少含有一个且至少含有一个 非终结符，非终结符， (VNVT)* q1型文法型文法-上下文有关文法（上下文有关文法（CSG） 对任一产生式对任一产生式，都有都有|， 仅仅仅仅 S除外除外 q2型文法型文法-上下文无关文法（上下文无关文法（CFG） 对任一产生式对任一产生式，都有都有VN ， (VNVT)* q3型文法型文法-正规文法（正规文法（RG） 任一产生式任一产生式的形式都为的形式都为AaB或或Aa，其中其中 AVN ，BVN ，aVT 2型文法型文法 1型文法型文法

9、 0型文法 3型文法 2型文法型文法 1型文法型文法 2型文法型文法 1型文法型文法 2型文法型文法 1型文法型文法 0型文法 3型文法 n0型文法产生的语言称为型文法产生的语言称为0型语言型语言 1型文法或上下文有关文法产生的语言称为型文法或上下文有关文法产生的语言称为1 型语言或上下文有关语言型语言或上下文有关语言 2型文法或上下文无关文法产生的语言称为型文法或上下文无关文法产生的语言称为2 型语言或上下文无关语言型语言或上下文无关语言 3型文法或正规文法产生的语言称为型文法或正规文法产生的语言称为3型语言型语言 正则规语言正则规语言 n例例 给出一个正规文法给出一个正规文法G，使使 L(

10、G)=anbm|n,m1 2.5 上下文无关文法及其语法树上下文无关文法及其语法树 n引例引例 GS: SaAS | a ASbA | SS | ba 写出写出aabbaa的最左推导和最右推的最左推导和最右推 导。导。 n给定文法给定文法G=( VN,VT,P,S)，对于对于G的任何句型的任何句型 都能够造与之关联的语法树。这棵树满足下列都能够造与之关联的语法树。这棵树满足下列 4个条件：个条件： q每个结点都有一个标记，此标记是每个结点都有一个标记，此标记是V的一个符号。的一个符号。 q根的标记是根的标记是S。 q若一结点若一结点n至少有一个它自己除外的子孙，并且有至少有一个它自己除外的子孙

11、，并且有 标记标记A，则肯定则肯定AVN。 q如果结点如果结点n有标记有标记A,其直接子孙结点从左到右的次其直接子孙结点从左到右的次 序是序是n1，n2，nk，其标记分别为其标记分别为A1，A2， Ak，那么那么AA1A2Ak一定是一定是P中的一个产生式。中的一个产生式。 n一棵语法树表示了一个句型的种种可能的一棵语法树表示了一个句型的种种可能的(但未但未 必是所有的必是所有的)不同推导过程，包括最左不同推导过程，包括最左(最右最右)推推 导。从左到右读出推导树的叶子标记连接成的导。从左到右读出推导树的叶子标记连接成的 文法符号串为文法符号串为G的的句型。句型。 n若一个文法存在某个句子对应两

12、棵不同的语法若一个文法存在某个句子对应两棵不同的语法 树，则称这个文法是二义的。或者说，若一个树，则称这个文法是二义的。或者说，若一个 文法存在某个句子有两个不同的最左（右）推文法存在某个句子有两个不同的最左（右）推 导，则称这个文法是二义的。导，则称这个文法是二义的。 n例例1 GE: EE+E|E*E|(E)|I n例例2 GE: E-EE|-E|a|b|c n文法的二义性和语言的二义性是两个不同的概文法的二义性和语言的二义性是两个不同的概 念。因为可能有两个不同的文法念。因为可能有两个不同的文法G和和G，其中其中 G是二义的，但是却有是二义的，但是却有L(G)=L(G)，也就是说也就是说

13、 ，这两个文法所产生的语言是相同的。，这两个文法所产生的语言是相同的。 2.6 句型的分析句型的分析 n句型分析句型分析 q句型分析就是识别一个符号串是否为某文法的句型，句型分析就是识别一个符号串是否为某文法的句型， 是某个推导的构造过程。是某个推导的构造过程。 n分析程序（识别程序）分析程序（识别程序） q在语言的编译实现中，把完成句型分析的程序称为分在语言的编译实现中，把完成句型分析的程序称为分 析程序或识别程序。析程序或识别程序。 n分析算法分析算法 q自上而下分析法自上而下分析法 q自下而上分析法自下而上分析法 考虑文法考虑文法GS： S cAd A ab A a 识别输入串识别输入串

14、w=cabd是否该文法的句子。是否该文法的句子。 q自上而下分析法的主要问题：自上而下分析法的主要问题： 假定要被替换的最左非终结符是假定要被替换的最左非终结符是V且有且有n条产生式：条产生式： V 1 | 2 | n，那么如何确定用哪个右部去替那么如何确定用哪个右部去替 换换V？ q自下而上分析法的关键问题：自下而上分析法的关键问题： 从当前串中选择一个可以归约到某个非终结符的子从当前串中选择一个可以归约到某个非终结符的子 串（称为串（称为“可归约串可归约串”）。）。 n定义定义3.8-短语，直接短语，句柄短语，直接短语，句柄 设文法设文法GS 如果有如果有S A且且A ，则称则称是句型是句

15、型相相 对于非终结符对于非终结符A的短语。的短语。 如果有如果有A ，则称则称是句型是句型相对于非终相对于非终 结符结符A的直接短语（简单短语）。的直接短语（简单短语）。 一个句型的最左直接短语称为该句型的句柄一个句型的最左直接短语称为该句型的句柄 。 * n例例 设文法设文法GE： EE+T|TEE+T|T TTTT* *F|FF|F F(E)|iF(E)|i 求句型求句型i i* *i+ii+i的短语、直接短语和句柄的短语、直接短语和句柄 2.7 有关文法实用中的一些说明有关文法实用中的一些说明 n在实用中，我们将限制文法中不得含有有害规则在实用中，我们将限制文法中不得含有有害规则 和多余规则。和多余规则。 q有害规则有害规则是形如是形如 U U的产生式。的产生式。 q多余规则多余规则是文法中连一个句