编译原理总复习chap3.ppt

第三章 文法和语言 本章知识点(内容) 字母表：元素的非空有穷集合。 符号：字母表中的元素。 符号串：字母表中的符号组成的任何有穷序列。 　　　　　空串:ε 符号串s的头（前缀） 移走s尾部的零个或多于零个符号。 符号串s的尾（后缀） 删去s头部的零个或多于零个符号。 符号串的长度 3.3 文法和语言的形式定义 文法 规则(产生式) 非终结符号 终结符号 直接推导 推导序列 句型 句子 语言L(G) 等价文法 四元组（VN,VT,P,S） VN：非终结符号集（语法实体）； VT ：终结符号集； P：产生式（生成式、规则）的集合； VN ∩ VT = φ VN ∪ VT =V ：字母表 /字汇表 S：识别符号(开始符号)，非终结符，至少要在一条规则中作为左部出现。 定义3.2 直接推导 ? v=w0=w1=w2=…=wn=w ,(n0) 则称v推导出（产生）w，记作v?w。(推导长度为 n) 文法G[S] S?x,则称x是句型 若L（G1）= L（G2），则G1和G2是等价的。 3.4 文法的类型 P38 例文法G[S]： S→CD Ab→bA C→aCA Ba→aB C→bCB Bb→bB AD→aD C→ε BD→bD D→ε Aa→bD 例 文法G[S]：S→AB A→BS|0 B→SA|1 3型文法 G[S]： S→0A|1B|0 A→0A|1B|0S B→1B|1|0 3.5 上下文无关文法及其语法树 设G=( VN, VT , P , S)为cfg： 结点：标记是V的一个符号。 根：开始符。 中间结点：非终结符 叶结点：终结符或非终结符 边：表示结点间的派生关系 标记A的结点,其儿子结点的标记为A1，A2，…， Ak， 则：A→A1A2，…，Ak∈ P 例：G[E]:E → i E → E+E E → E*E E → (E) 句型 i*i+i 消除二义性 [例3.8]简单算术表达式的文法 3.6 句型的分析 “自上而下”中如何选择使用哪个产生式？ 假定要被代换的最左非终结符号是B，B→A1|A2|…|An，如何确定用哪个右部去替代B？ “回溯问题”的解决。 “自下而上”中如何识别“可归约串”？ 每一步，选择一个子串“可归约串” ，归约到某个非终结符号。 确定“可归约串”是关键。 “可归约串”的不同定义，形成了不同的分析方法。 “规范归约”（最左规约）的“可归约串”—句柄。 一个句型的最左直接短语 E + T T * i3 F i1 本章小结 概念较多，重点理解文法、推导、句型、句子、语言、语法树、二义性、直接短语、句柄的定义。语法分析有关内容在后面章节会详细讨论。 计算：句型的推导、语法树、短语 G[E]：E→E+T|T T→T*F|F F→(E)|i 句型：i*i+i 刻画“可归约串” i3 直接短语： i1 ， i2 ， i3 句柄： i1 子树的叶结点 是相对于子树的根的短语 i1* i2+ i3 i1* i2 E T F F i1 i2 i2 短语 * * 本章目的 语言的语法结构的精确、无二义的形式描述 从形式描述中，研究语法分析器的构造 3.2 符号和符号串 3.3 文法和语言的形式定义 3.4 文法的类型 3.5 上下文无关文法及其语法树 3.6 句型的分析 1. ε是符号串 2.若x是符号串,a是元素,则 xa 是符号串 3. y是符号串,当且仅当它可以由1和2导出。 字母表与符号串 例：?={0，1} ?上的符号串的递归定义 例如： Σ={a,b} ε,a,b,aa,ab,aabba…都是?上的符号串 符号串的运算 符号串的头：ε,b,ba,ban,bana,banan,banana 符号串的尾：ε,a,na,ana,nana,anana,banana 例如：符号串banana 符号串s的子串 从s中删去一个前缀和一个后缀得到的符号串。 符号串s： s和ε是前缀、后缀和子串 如:a