云南大学《p-Cha2.ppt

2017/7/31
1
目前形式语言与自动机理论已成为计算机科学中的一个重要分枝。
Hopcroft 曾说:“在不了解语言及自动机理论的技术和结果的情况下,就不能对计算机科学进行严肃的研究。”
2017/7/31
2
一个程序设计语言是一个记号系统,包括语法和语义两个方面。一个语言的语法是指一组规则,用它可以形成和产生一个合适的程序。
阐明语法的一个工具是文法,这是形式语言理论的基本概念之一。
阐明语义比阐明语法困难得多,目前仍无一种公认的形式语义系统来自动构造编译系统。本章将介绍文法和语言的概念,重点讨论上下文无关文法及其句型分析中的有关问题。
2017/7/31
3
本章内容
符号和符号串
文法和语言的形式定义
文法的类型
上下文无关文法及其语法树
句型的分析
有关文法实用中的一些说明
扩展的BNF
2017/7/31
4
符号和符号串
结合语言的形式定义,首先讨论符号和符号串的有关概念。
1、字母表
元素的有穷非空集合。
如PASCAL语言的字符是由字母、数字、若干专用符号及BEGIN、IF之类的保留字组成。
2、符号串
由字母表中的符号组成的任何有穷序列。
如:PASCAL语言程序是PASCAL语言字母表上的一个符号串,不含任何符号的符号串为空符号串,记为。
2017/7/31
5
3、符号串的头尾,固有头和固有尾:
如果z=xy是一符号串,那么x是z的头,y是z的尾,如果x是非空的,那么y是固有尾;同样如果y非空,那么x是固有头。
如:设z=abc,那么z的头是,a, ab, abc, 除abc外,其它都是固有头;z的尾是,c, bc, abc, z的固有尾是,c, bc。
4、符号串的运算
(1)符号串的连接
设x和y是符号串
x和y的连接xy是把y的符号写在x的符号后得的符号串。
如:x=ST, y=abu,
则xy=STabu 显然有x=x=x。
2017/7/31
6
(2)符号串的方幂
设x是符号串,把x自身连接n次得x的几次方幂xn。
如:设x=ab
则x0= x1=ab x2=abab x3=ababab
(3)符号串集合的乘积
设A和B为符号串集合,则A和B的乘积定义为
AB={xy|xA且yB}
如:a={a, b}, B={00, 11}
则AB={a00, a11, b00, b11}
显然:{}A=A{}=A
2017/7/31
7
(4)符号串集合的方幂
设A为符号串集,则A的n次方幂An定义为:
An=AA……A=AAn-1=An-1A
n个A
(5)符号串集合的正闭包A+
A+=A1 U A2 U … U An U …
(6)符号串集合的闭包A*
A*=A0 U A+ = {} U A+
如:设有正字母表={0,1}
则*=0 U 1 U 2 U … U n U …
={, 1, 1, 00, 01, 10, 11, 000, 001,……}
2017/7/31
8
文法和语言的形式定义
文法是描述语言的语法结构的形式规则。
1、文法的形式定义
2、推导的概念
3、句型、句子的定义
4、语言的定义
5、文法等价定义
2017/7/31
9
1、文法的形式定义
文法G定义为四元组(VN ,VT,P,S) 其中:
(1)VN 为非终结符号集
非终结符号表示一个语言短语(或语法成分、语法单位)。如程序、语句、表达式等。一般用大写字母或用〈〉括起表示非终结符号。
(2)VT 为终结符号集
终结符号:组成语言的基本符号。是文法中不属于非终结符号集合的符号。一般用小写字母或不带〈〉的符号表示。如程序设计语言的单词符号。
设V=VN U VT,称V为文法G的字母表。
2017/7/31
10
(3)P 为产生式(也称规则)的集合。
产生式的形式:→或∷=,其中∈V+,∈V*
(4)S 称作识别符号或开始符号,是一个非终结符号。
一般表示此文法定义的最大语法短语,至少要在一条产生式中作为左部出现。(例2_2_1)(例2_2_2)