编译原理_02文法和语法概要.ppt

例7 文法G[S]： （1）S→aSBE （2）S→aBE （3）EB→BE （4）aB→ab （5）bB→bb （6）bE→be （7）eE→ee L（G）={ anbnen | n≥1 } 如：证明aabbee是G的句子: S ?a S BE (S→aSBE) ?a aBEBE (S→aBE) ?aabEBE (aB→ab ) ?aabBEE ( EB→BE ) ?aabbEE (bB→bb) ?aabbeE (bE→be) ?aabbee (eE→ee) 6. 文法的等价性 若L（G1）=L（G2），则称文法G1和G2是 等价的。 例：文法G1[A]：A→0R A→01 R→A1 文法G2[S]：S→0S1 S→01 显然有 L（G1）=L（G2） 通过对产生式施加不同的限制，Chomsky将文法分为四种类型，即0型、1型、2型、3型。 设有文法G=（VN ，VT ，P，S） 0型文法： 文法G中的任一产生式α→β，都满足： α、β∈(VN∪VT)* ，且α中至少含有一个非终结符。0型文法也叫短语文法。 例1：下列为1型（上下文有关）文法 文法G[S]： S→aSBE S→aBE EB→BE aB→ab bB→bb bE→be eE→ee 上下文无关文法有足够的能力描述现今程序设计语言的语法结构 例1：算术表达式上下文无关文法表示 文法G=({E}, {+,*,i,(,)}, P, E} P: E → i E → E+E E → E*E E → (E) 语法树是用于描述上下文无关文法的句型推导的直观方法 最左（最右）推导：若在推导中的任何一步α?β，其中α、β是句型，都是对α中的最左（右）非终结符进行替换，则称为最左（最右）推导。 最右推导也称为规范推导。 由规范推导所得的句型称为规范句型 问题：一个句型是否对应唯一的一棵语法树？ 句型分析就是识别一个符号串是否为某文法的句型，是某个推导的构造过程。 在语言的编译实现中，把完成句型分析的程序称为分析程序或识别程序。分析算法又称识别算法。 从左到右的分析算法: 即总是从左到右地识别输入符号串，首先识别符号串中的最左符号，进而依次识别右边的一个符号。 分析算法可分为： 自上而下分析法：从文法的开始符号出发，反复使用各种产生式，寻找与输入符号匹配的推导。 自下而上分析法：从输入符号串开始，逐步进行归约，直至归约到文法的开始符号。 两种方法反映了两种不同的语法树的构造过程 自上而下的语法分析 例：文法G：S → cAd A → ab A → a识别输入串 w = cabd 是否该文法的句子 自下而上的语法分析 例：文法G：S → cAd A → ab A → a识别输入串 w = cabd 是否该文法的句子 句型分析的有关问题 1）在自上而下分析中，假定要被代换的最左非终结符号是V，且有n条规则具有相同左部：V→A1|A2|…|An，那么如何选择产生式？ 方法之一：回溯法（代价太高） 方法之一：其他方法（如预测分析法等） 2）在自下而上的分析方法中，分析程序工作的每一步，都是从当前串中选择一个子串，将它归约到某个非终结符号，该子串称为“可归约串”，如何确定可规约串呢？ 方法：寻找句柄 短语、直接短语、句柄 文法G[S]， αβδ是G的一个句型，如果有：S αAδ且A β，则称β是句型αβδ相对于非终结符A的短语。 若有A ?β则称β是句型αβδ相对于规则A→β的直接短语（或简单短语）。一个句型的最左直接短语称为该句型的句柄。 E E T T T F F