资源描述：
《《上形式语言简介》PPT课件》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第3章上形式语言简介3.1文法和语言3.2推导与语法树3.1文法和语言文法是程序语言的生成系统，而自动机则是程序语言的识别系统；用文法可以精确地定义一个语言，并依据该文法构造出识别这个语言的自动机。因此，文法对程序语言和编译程序的构造具有重要意义，如程序语言的词法可用正规文法描述，语法可用上下文无关文法描述，而语义则要借助于上下文有关文法描述。3.1.1文法和语言的概念1．语言通常我们用Σ表示字母表，字母表中的每个元素称为字符或符号。不同语言的字母表可能是不同的，程序语言的字母表通常是ASCII字符集。由字母表Σ中的字符所组成的有穷系列称为Σ上的
2、字符串或字，字母表Σ上的所有字符串(包括空串)组成的集合用Σ*表示。那么，对字母表Σ来说，Σ*上的任意一个子集都称为Σ上的一个语言，记为L(LΣ*)，该语言的每一个字符串称为语言L的一个语句或句子。每一个形式语言都是某字母表上符号串的一个集合，反之字母表上符号串的一个集合可定义为一个形式语言。例如，C语言是其基本符号字母表上符号串的集合，而每个C语言程序是基本符号的符号串。再如，假定∑={a,b,c}，则L1={a,b,c}L2={a,aa,ab}L3={c,cc}均可表示字母表∑={a,b,c}上的一个形式语言。当一语言是有穷集合时，可用上述枚
3、举方法来表示语言。但如果语言是无穷集合，那就无法用这种枚举方法。我们要设计出表示无穷集合的强有力的工具。文法就是这样一种工具。设∑={a,b}，则根据定义∑+表示a和b的所有可能的符号串的集合。下面用A表示∑+则A可表示成：A→aA→b⑴A→AaA→Ab其中，符号“→”读作“生成”。显然，由A生成的符号串都属于∑+，另一方面，可用归纳法证明∑+A，因此有A=∑+。考虑∑={a}上的符号串集合：A={a2n
4、n≥1}显然aa∈A；如果yaa∈A，因此，A可按下法构造：A→aaA→Aaa⑵考虑∑={a,b}上的符号串集合：A={abna
5、n≥1}显然
6、A可表示为A=aBaB={bn
7、n≥1}其中B是我们会构造的，于是可以写出：①A→aBa②B→b⑶③B→Bb在这里A是所要构造的，B是辅助集合。这样A→aBa可理解为A可生成aBa。若用“”表示“推出”，则我们有AaBaaBaaBbaaBbaaBbbaaBbbaabbba于是得出：A推出符号串abbba，即abbba∈A。2．文法文法通常表示成四元组G=(VT，VN，S，ξ)，其中：(1)VT为终结符号集，这是一个非空有限集，它的每个元素称为终结符号；(2)VN为非终结符集，它也是一个非空有限集，其每个元素称为非终结符号，且有VT∩VN=Φ；(3
8、)S为一文法开始符，是一个特殊的非终结符号，即S∈VN；(4)ξ是产生式的非空有限集，其中每个产生式(或称规则)是一序偶(α，β)，通常写作α→β或α::=β读作“α是β”或“α定义为β”。在此，α为产生式的左部，而β为产生式的右部，α、β是由终结符和非终结符组成的符号串，α∈(VT∪VN)+且至少有一个非终结符，而β∈(VT∪VN)*。终结符号是指语言不可再分的基本符号，通常是一个语言的字母表；终结符代表了语法的最小元素，是一种个体记号。非终结符号也称语法变量，它代表语法实体或语法范畴；非终结符代表一个一定的语法概念，因此，一个非终结符是一个类
9、、一个集合。例如，在程序语言中，可以把变量、常数、“+”、“*”等看作是终结符，而像“算术表达式”这个非终结符则代表着一定算术式组成的类，如i*(i+i)、i+i+i等；也即每个非终结符代表着由一些终结符和非终结符且满足一定规则的符号串组成的集合。文法开始符号是一个特殊的非终结符，它代表文法所定义的语言中我们最终感兴趣的语法实体，即语言的目标，而其它语法实体只是构造语言目标的中间变量；如表达式文法的语言目标是表达式，而程序语言的目标通常为程序。产生式(也称产生规则或规则)是定义语法实体的一种书写规则。一个语法实体的相关规则可能不止一个。例如，有：
10、P→α1P→α2P→αn为书写方便，可将这些有相同左部的产生式合并为一个，即缩写成P→α1∣α2∣…∣αn其中，每个αi(i=1,2,…,n)称为P的一个候选式，直竖“∣”读为“或”，它与“→”一样是用来描述文法的元语言符号(即不属于Σ的字符)例3.1试构造产生标识符的文法。[解答]首先，标识符是以字母开头的字母数字串，我们用L表示“字母”类非终结符，用D表示“数字”类非终结符，而用T表示“字母或数字”类非终结符，则有：L→a∣b∣…∣zD→0∣1∣…∣9T→L∣D其次，如果用S表示“字母数字串”类，则T是一字母或数字，ST也是字母数字串，即有S
11、→T∣ST其中，产生式S→T∣ST是一种左递归形式，由它可以产生一串T。最后，作为“标识符”的非终结符I，它或者是一单个字母，或者为一字
