编译原理70.pptVIP

编译原理;文法和语言;;文法和语言;一、文法的概念 二、符号和符号串 三、文法和语言的定义 四、文法的类型 五、上下文无关文法及其语法树 六、句型的分析 七、有关文法的一些限制;语言 ;〈句子〉∷=〈主语〉〈谓语〉 〈主语〉 ∷ =〈代词〉|〈名词〉 〈代词〉 ∷ = 我|你|他 〈名词〉 ∷ = 王明|大学生|教师|英语 〈谓语〉 ∷ =〈动词〉〈直接宾语〉 〈动词〉 ∷ = 是|学习 〈直接宾语〉 ∷ =〈代词〉| 名词 ;推导： 我是教师 ;符号和符号串;先讨论一些有关概念： 1、字母表—符号集：是字母的有穷非空集合。 汉语字母表包括： 汉字、数字、标点符号等 Pascal语言字母表包括： 字母、数字、若干专用符号以及Begin、if等保留字。;符号和符号串;3、符号串的长度：符号串x有m个符号，则长度就为m，表示|x|=m 如： ababa 则长度是5 4、空符号串：用ε表示，长度为0（不含任何符号） 若符号串x ,则有εx = xε= x 5、符号串的运算： (1) 符号串的头和尾 若z=xy,则x是z的头，y是z的尾。;例：设z=abc ,则z的头是 ε，a，ab，abc 则z的尾是 ε，c，bc，abc （2）符号串的固有头和固有尾 若z=xy符号串，x非空，则y是固有尾； 若y非空，则x是固有头。 例：设z=abc，则z的固有头是 ε， a， ab 则z的固有尾是 ε，c ，bc;（3）符号串的连接： 设x，y是符号串，连接xy是y符号写在x符号之后。 例：x=ab, y=MN 则xy=abMN 显然：εx=xε=x （4）符号串的方幂： 设x是符号串，则z=xx……xx，称z为x的方幂, 记z=xn。 因此 x0=ε, x1=x, x2=xx, x3=xxx 显然n0时, 有xn =x·x n-1＝ x n-1·x;（5）符号串的集合： 若集合A中的一切元素都是某字母表上的符号串，则称A为该字母表上的符号串集合。 两个符号串集合A、B乘积定义： AB={xy| x∈A且y∈b} 例：A={a,b}，B={c,d} 则AB=;（6）闭包（∑*） 字母表∑，用∑* 表示∑上所有有穷长的串集合，∑*称为∑的闭包。 例：字母表∑={0,1} 则∑*=;〈7〉正闭包(∑+) ∑+ =∑1 ∪ ∑2∪. …∪∑n ∑+称∑的正闭包。 显然：∑*＝ ∑0∪∑+ ∑+ ＝ ∑∑*＝∑*∑;?三、文法和语言的形式定义 （用以上术语对文法的概念进行形式化）;其中： VN —— 非终结符号集 VT —— 终结符号集 P —— 产生式（规则） S —— 开始符号或称作识别符号，它是一个非终结符，至少要在一条规则中作为左部出现。 规定：（1）VN ，VT，P是有穷非空集合； （2）VN∩VT＝? （不含公共元素）;例1 文法G =（VN ，VT ，P，S）， 其中 VN={S}，VT ={0，1}， P={S → 0S1，S → 01}。 非终结符集中只含一个元素S； 终结符集由两个元素0和1组成； 有两条产生式；开始符号是S。 想：从终结符可推出哪些符号串？;例2 文法G =（VN ，VT，P，S） 其中 VN ={标识符，字母，数字} VT= {a,b ,c,…,x,y,z,0,1,…,9} ?P = { 标识符 →〈字母〉 标识符 → 标识符字母〉 标识符 → 标识符数字〉 字母 →a 字母 →b … ;字母 →z 数字 →1 … 数字 →9 ｝ S＝ 标识符;2 文法G的第二种表示法： 上例1改为： G: S → 0S1 S → 01 3 文法G的第三种表示法： 上例1改为： G[S]: S → 0S1 S → 01;3、直接推导的定义 1 ? → ? 是文法G=（VN ，VT ，P，S）的规则， ?和?是V*中的任意符号，若有符号串V，W满足： V= ? ? ?，W