形式语言与自动机理论基础(形式语言).ppt

第二章 形式语言与自动机理论基础 2.1 预备知识 2.2 文法的讨论 2.3 文法和语言的定义 2.4 分析树和二义性 2.5 形式语言概观2.1 预备知识 字母表 符号串 一、符号串的定义 二、术语 三、符号串的运算 四、符号串集合的运算 字母表是符号的非空有穷集合；例：=a，b，c任何程序语言都有自己的字母表。2.1.1 字母表 1.计算机语言：由符号“0”和“1”组成的字 母表:=0，1 2.Pascal语言字母表：=AZ,az,09,+,-,*,/,:,”,;，.，,(,),3.C语言字母表：=AZ,az,09,+,-,*,/,_,&,:,”,;，.，?,(,),空格,!,#,%一.符号串的定义 由字母表中的符号所组成的的任何有穷序列被称之为该字母表上的符号串。空符号串：无任何符号的符号串，记作 2.1.2 符号串 符号串的形式定义：(1)字母表上字符是上的符号串。(2)若x是上的符号串，而a是的元素,则xa 是上的符号串。(3)y是上的符号串,当且仅当它由(1)和(2)导出。二 术语（设s是符号串banana）前 缀：移走s的尾部的零个或多于零个符号所得符号串,b,ba,ban,bana,banan,banana后 缀：删去s的头部的零个或多于零个符号所得符号串 banana,anana,nana,ana,na,a,子 串:从s中删去一个前缀和一个后缀所得符号串 banana,anana,banan真前缀、真后缀和真子串：不是s和的前缀、后缀和子串子序列:从s中删去零个或多于零个符号(不要求是连续）而得到的符号串。如baaa长 度：是符号串中符号的个数。例如|aab|=3,|=0语 言：确定字母表上字符串的任何集合例如：不含任何元素的空集合，即 只含有空符号串的集合 符合Pascal语法的程序组成的集合（Pascal语言）符合英文语法的句子组成的集合