【计算机】形式语言02章文法语言语言

《【计算机】形式语言02章文法语言语言》由会员分享，可在线阅读，更多相关《【计算机】形式语言02章文法语言语言（187页珍藏版）》请在金锄头文库上搜索。

1、 第二章 文法与语言l一个语言的定义可以从两个方面进行：l 从语言产生的角度；（形式语言） l 从接收(识别)语言的角度。（自动机） l设是一个字母表，L *, L称为 字母表上的一个语言(language), x L, x叫做L的一个句子。2.1 例子语言l例1：括号匹配的语言(该语言是指 所有的左、右括号相匹配的串的集 合)。l问题：如何产生该语言？即如何生 成该集合中的所有的串？l自然语言的描述方式，采用如下的递归规则： ( )是合法的该语言的最基本的串； 若S是一个合法的串,则(S)是合法串 ； 若S是一个合法的串,则SS是合法串 ；l这些规则称为形成规则，根据这些规 则，可以l(1)

2、产生任意合法（即符合规则）的该 集合中的串；l(2)判断某个串是否是合法的该集合的 串（即合法的句子）。l例如： 可以产生串（）；而推断串（）不是合法的串。l规则(的个数)是有限的，但 可以产生无限个串和无限长 度的串；l因为规则是递归的。l巴科斯和诺尔采用的巴科斯-诺尔范式（BNF- Backus-Naur Form）描述规则：l:= ( )l:= l:=()l使用尖括号“”包括起来的部分，作为 一个整体来看待，表示某个语法成分，最终 ，需要使用字母表中的字母来定义。l符号“:=”是BNF本身的符号（元符号），代 表“定义为”或“就是”。l符号“( ”和“ )”是字母表的元素。lChomsk

3、y采用的符号化(形式化)的 描述方式，运用如下的规则（这些规 则被称为产生式）： S( ) S(S) SSS l”读作“定义为”或者“是” ， 它的左边和右边分别称为该产生式的 左边和右边； l根据这些规则，也可以生 成任意合法的串；可以判 断一个串是否为合法的串 。l产生串的过程为：从S开始，反 复利用产生式的右边代替产生 式的左边（称之为推导过程） ，最后，可以得到匹配的（） 组成的串。例:串( )( )( )的产生过程lS=SS=(S)S=( )S=( )(S)=( )(SS)=( )( )S)= ( )( )( )l其中：“=”表示单步推导过程。l虽然产生式的个数是有限的， 但是规则是

4、递归的，因而，所 有的小括号匹配的串（有无限 个）均可以由它们产生，它们 组成的集合就称为一个语言。lS称为非终结符，在推导过程中，可 以被代替的符号。l(和)称为终结符，在推导过程中，不 可以被代替的符号。l 是产生式系统的元符号，不属于 非终结符，也不属于非终结符。 l例2-2：由偶数个0组成的串的语言。l自然语言的描述方式： 00是合法的该语言的基本的串； 若S是合法的串,则SS是合法的串；l形式化的描述方式： S00 SSS 问题：l将产生式SSS换成S0S0或者S00S， 是否还产生相同的语言？ l同一个语言，可以使用不同的产 生式组合来产生。l考虑： 由奇数个1组成串的语言的产生。

5、l例2-3：包含有+、-、*、/ 、（）的算术表达式的语 言。自然语言的描述方式单个变量是合法的最基本的串； 若S是一个合法的串，则SAS是一 个合法的串（ 其中A代表运算符+ 、-、*、/） 若S是一个合法的串，则(S)是合法 的串；形式语言的描述方式 S i （i代表单个变量） SSAS S( S ) A+ A- A* A/l其中 ： lA+，A-，A*，A/ 四个产生 式的左边是相同的符号，可以合并 为A+|-|*|/+、-、*、/ 称为A的侯选式。注意：l这组产生式没有表示出运 算符的优先级。l表示出运算符的优先级的产生 式：EE+T|E-T|TTT*F|T/F|FF(E)|il其中：

6、E代表表达式，T代表项，F代 表因子，(E)代表的是带小括号的表 达式。该组产生式表示出先算因子， 再*、/，最后+、-。l如果使用%代表模运算(即取余数运算 )、使用代表指数运算，则有l EE+T|E-T|TlTT*F|T/F|T%F|Al AFA|F l F(E)|il注意：l还需要考虑运算的结合性：是右结 合的。l例2-4 标识符(以字母开头的字母、 数字的串)的产生(仅考虑小写字母) 。 l ILIILIIDLa |b|c|zD0|1|2|9将I的定义加入到表达式中： EE+T|E-T|TTT*F |T/F|FF (E)|IIL|IL|IDLa|b|c|d|e|f|g|h|i|j|k|

7、l|m|n|o|p|q|r|s|t|u|v|w|x|y|z D0|1|2|3|4|5|6|7|8|9 l考虑：其他类型的表达式 （如关系表达式等）的定 义例2-5lC语言中简单变量的说明语句的定义 。C语言中的说明语句形式为： lTYPE 变量名表；lTYPE 变量名表；llTYPE 变量名表；产生式为：SSS|PPT V；Tint|char|floatVV,V|IIL|IL|IDLa|b|c|d|e|f|g|h|i|j|k|l|m|n|o|p|q|r|s|t|u|v|w|x|y|zD0|1|2|3|4|5|6|7|8|9l其中：S代表简单变量的说明语句(可 以由一个或多个的单个说明语句构成

8、)，P代表单个的说明语句，T代表类 型，V代表变量名表(由，隔开的 多个变量)，I代表单个变量。l思考：l PASCAL语言的简单变量的说明语 句的形成。2.2 文法和语言的关系l介绍语言的定义。l介绍文法的定义。l介绍文法与语言的关系。l语言就是某个字母表上的字符串组成的一 个集合。语言中的字符串称为句子。l文法的作用就是产生一个语言。l有穷语言的表示较容易，即使语言中的句 子的组成没有什么规律，也可以使用枚举 的方式列出语言中的所有句子。l对于无穷语言，使用有穷描述的方式表达 。需要从语言包含的句子的一般构成规律 去考虑问题。这种从语言的有穷描述来表 达语言的方法对一般的语言都是有效的。

9、尤其在使用计算机判断一个字符串是否是 某个语言的句子时，从句子和语言的结构 特征上着手是非常重要的。l对于一类语言，可以在字母表上，按 照一定的构成规则，根据语言的结构 特点，定义一个文法。使用文法作为 相应语言的有穷描述，不仅可以描述 出语言的结构特征，而且可以产生这 个语言的所有句子。短语结构文法(文法)的定义文法G是一个四元式(由四个部分组成) ，即G=(，V，S，P)； l是一个有限字符的集合(字母表)， 它的元素称为字母或者终结符； lV是一个有限字符的集合，叫做非终 结符集合，它的元素称为变量或者非 终结符；lSV，称为文法的开始符号；lP是有序偶对(，)的集合，其中是集 合(UV

10、)上的字符串，但至少包含一个 非终结符；是集合(UV)*的元素。一 般，将有序偶对(，)记为，称为 产生式；l如果有，称之为空串产生 式或者产生式。l如果有AB，称之为单产生式。l一个产生式的左边可能不只一 个符号；第一个产生式的左边 只能有一个符号，就是开始符 号S。l文法的作用就是产 生一个语言。约定：如果没有特别说明第一个产生式左边的符号，就是开始符号，可以不为S； 大写的英文字母代表非终结符；推导（派生）的定义2-2l给定文法G，和是集合(UV)上的 串，若，分别可以写成pvr 和 pur(p和r可能同时为空串)，而vu是 文法G的一个产生式,则称串可以直 接推导出串 ，记为= ，或

11、pvr =pur。l推导的实质是用产生式的右边代 替产生式的左边。(非终结符代表 在推导的过程中可以被替代的符 号，而终结符代表在推导的过程 中不可以被替代的符号)。l推导的逆过程称为归约。l用符号y=*z表示y可以经 过任意步（包括0步）推导 出z，即 l y=z；或者l存在一个序列1，2 ，3 ，nl有 y=1，z=n，且i=i+1；对所有i1。l用符号y=+z表示y可以经 过多步(至少一步)，推导 出z，即l存在一个序列 1，2 ，3 ，n 有y=1 ，z=n，且i=i+1；对所有 i1。思考：l对于任意文法G：lS=*S 和lS=+S l一定都成立吗？l如果在推导的过程中，每一步都是将

12、 推导产生的串的最左边的非终结符代 替掉，称之为最左推导，如果每一步 都是将推导产生的串的最右边的非终 结符代替掉，称之为最右推导(也称 之为规范推导)，l当然，还有其它方式的推 导过程（例如混合），而 最左推导和最右推导是比 较常用的推导方式。l对于文法G，如果S=*，则 称是文法的一个句型，若 中包含的字符全是终结符，称 是句子。语言的定义l给定文法G，有开始符号S，则把S 可以推导出的所有的终结符串的集 合（即所有句子的集合），称为由 文法产生的语言，记为L(G)，即lL(G)=|S=*，且*。l例如：产生括号匹配的语言的文法是： G=(,),S,S, S( ), S(S), SSS )

13、l一般，对于文法G，可以只给出它的产生式的 集合即可。上述文法可以简写为：S( )S(S)SSSl对于文法和语言，可以从一个文 法得到该文法产生的语言；也可 以根据语言，写出产生该语言的 某个文法；还可以判断一个语言 是否由某一个文法产生。l考虑：文法 SaSa|bSb|c|产生的语言是什么？考虑：l产生语言L的文法，lL= wwT|wa,b,c+l其中：wT是w的逆（反序）。考虑：l产生下列语言的文法：L1=anbn|n=0；L2=anbn|n0；l文法S0B|1AA0|0S|1AAB1|1S|0BBl产生的语言是l0，1上包含相等个数0和1的串的 语言；即L(G)=|0,1+，且中有相同多

14、的0和1。l一个文法确实产生语言L(G)，必须 确定两个命题：l该文法推导出的串都在语言中；l所有语言中的串都可以由该文法 产生。l注意：一个语言可能由多个不同 的文法产生。l如果文法G1和文法G2产生同一 个语言，则称文法G1和G2是等价 的文法。记为L(G1)= L(G2)。l例2-9 构造文法G，使L(G)=0,1,00,11 。lG1： S0|1|00|11lG2： SA|B|AA|BB A0 B1lG3： S0|1|0A|1B A0 B1l有0,1,00,11=L(G1)=L(G2)=L(G3)l注意：l 两个文法G1和G2等价和两个文法 G1和G2相同的区别。 2.3Chomsky

15、对文法的分类l本节介绍Chomsky对文法和语言进行的分类。l语言是由文法产生的，对语言的分类，是根 据产生语言的文法的分类而进行的。短语结构文法l对于一般的短语结构文法PSG，G=(，V ，S，P)，产生式的形式是vw，其中： v(V)+，且至少包含一个非终结符； w(V)*。l如果一个语言L可以由短语结构文法产生 ，则该语言是短语结构语言PSL。定义2-4：右线性文法的定义l对于文法G=( ，V，S，P)，若它的 每个产生式都是下列形式之一：lAbC或者Aa；l其中：A，CV，aXU，b ；则文法G是右线性文法（RLG，也称 为正则文法RG）。l如果一个语言L可以由右线性文法 产生，则该语言是右线性语言（ RLL或RL）。l右线性文法自然地对应于句子的 推导过程。 左线性文法l对于文法G，若每个产生式都是: ：lACb或者Aa；其中A，CV， aXU，bX；则文法G是左 线性文法。如果一个语言L可以由 左线性文法产生，则该语言是左 线形语言。l左线性文法自