第二章文法和语言的基本知识§2.1概述赋值语句s=2*3.1416*r*(r+h)的非形式化的描述如下：程序设计语言的定义是语言编译程序实现的基础，是语言使用者的用户手册；编译程序研制者则对哪些构造可以出现更感兴趣。程序语言是符号语言，即一个记号系统，它主要有语法、语义和语用等三方面定义。我们在此重点讨论语法和语义。语法语义语义的形式化比语法的形式化难得多，形式语义学有操作语义学、代数语义学、公理语义学、指称语义学等许多分支，它们分别用不同的形式系统来描述语义问题，但是目前还没有一种公认的形式系统，因此也还没有实用的语义自动分析方法。目前编译程序中常用的语义分析方法是一种基于属性文法的语法制导翻译，即在语法分析的同时对其中识别出的语法单位进行语义的分析与翻译工作，属性文法则是在描述文法的同时为定义的语法范畴加上它们的属性计算规则，属性可以是语法范畴的类型、地址、取值、执行动作等信息。*回顾：高级语言的一般特性高级语言的分类（根据语言范型）程序结构一个Fortran程序由一个主程序和若干个辅程序段组成。PROGRAMMAIN……ENDSUBROUTINESUB1……ENDSUBROUTINESUB1……END辅程序段可以是子程序、函数段或数据块。每个程序段由一系列说明语句和执行语句组成，各段可以独立编译。数据说明允许COMMON块。programmain……{主程序的其他说明部分}procedureP1;……{子程序P1的其他说明部分}procedureP11;……{子程序P11的其他说明部分}begein……{子程序P11的执行语句部分}end;begin……{子程序P1的执行语句部分}end;procedureP2;……{子程序P2其他说明部分}begin……{子程序P2的执行语句部分}end;begin……{主程序的执行语句部分}end.程序结构三、Ada程序结构四、Java数据类型与操作一、初等数据类型数值数据、逻辑数据、字符数据、指针类型（注：名字与标识符）二、数据结构1.数组：由同一类型数据所组成的某种n维矩形结构。可分为确定数组和可变数组，数组的内情向量包括：首地址、维数、各维的上下限及元素类型。2.记录：由已知类型（可以不同）的数据组合起来的结构。记录中每个域的相对数OFFSET是它相对于记录首地址的地址位移量。3.字符串、表格、栈和队列：数组或记录组合的访问受限的复合结构。**语句与控制结构本节介绍语言的形式定义基础：§2.2字母表和符号串的基本概念2.符号（字符）symbol（基本符号）3.符号串（字）string（单词、词组、句子）1.符号串的连结catenation2.集合的乘积product空集Φemptyset3.符号串的幂运算power4.集合的幂运算5.集合A的正闭包A+与闭包A*【例如】设A={a},则A+＝{a,aa,aaa,……}={an|n>=1}A*＝{a,aa,aaa,……}={an|n>=0}§2.3文法和语言的形式定义§2.3.1形式语言形式语言的描述当语言为无穷集合时，需要设计文法来描述无穷集合的语言。§2.3.2文法的形式定义【例】一组规则产生式中的符号2.文法左部相同的产生式，如A→α1，A→α2，…，A→αn，可合并为一个，缩写为A→α1|α2|…|αn，其中的每个αi称为A的一个侯选式，箭“→”读为“定义为”，直竖“|”读为“或”。【例2.1】设字母表∑＝{a,b},试设计文法，描述语言L={a2n,b2n|n1}定义语言L的文法G’=（VN，VT，P，S）其中：VN={A,B,D}VT={a,b}P={A→B|DB→aa|aBaD→bb|bDb}S=AG和G’是两个的文法，如果它们描述的语言相同，那么称G和G’为等价文法。描述该语言的文法不是唯一的。描述该语言的文法为什么不是G”【例2.2】设计一个表示所有标识符的文法【例2.3】用文法定义一个含+、*的算术表达式。【例2.4】设字母表∑＝{a,b}，设计一个文法，描述语言L={abna|n0}描述语言L={abna|n0}的等价文法§2.3.3语言的形式定义【例】2、推导【例】3、广义推导4、句型和句子【例2.6】设有文法G[E]:E→E+E|E*E|(E)|i试证明符号串(i*i+i)是文法G[E]的一个句子5、语言【例2.7】设有文法G[S]:S→01|0S1求该文法所描述的语言【例2.8】设有文法G[S]:S→0S|1S|求该文法所定义的语言【例2.9】设有文法G[A]:A→yB,B→xB|x求该文法所定义的语言【例】考虑文法G1:S→ABA→aA|aB→bB|b我们可以分