第2章形式语言概论.ppt

短语、直接短语和句柄 注意：短语和直接短语的区别在于第二个条件, 直接短语中的第二个条件表示有文法规则 A?β ，因此，每个直接短语都是某规则右部。 短语、直接短语和句柄 句柄 一个句型的最左直接短语称为该句型的句柄。 句柄特征： (1) 它是直接短语，即某规则右部。 (2) 它具有最左性。 短语、直接短语和句柄 注意: 短语、直接短语和句柄都是针对某一句型的，都是指句型中的哪些符号串能构成短语和直接短语，离开具体的句型来谈短语、直接短语和句柄是无意义的。 短语、直接短语和句柄 例如 设有文法G[S]=({S,A,B},{a,b},P,S) 其中P为： 求句型 baSb的全部短语、直接短语和句柄。 S?AB A?Aa | bB B?a | Sb 短语、直接短语和句柄 对文法，首先建立该句型的推导过程： 最左推导: 最右推导: S?AB A?Aa | bB B?a | Sb S?AB ?ASb ?bBSb ?baSb S?AB ?baB ?baSb ?bBB 分析 根据短语定义，可以从句型的推导过程 中找出其全部短语、直接短语和句柄。 句型 baSb 短语、直接短语和句柄 句型baSb中的子串Sb，是(相对于非终结符B)句型baSb的短语，且为直接短语。 S?AB ?bBB ?baB ?baSb (2) S?baB * B ?Sb (1) S ?S * S ?baSb + 句型本身是(相对于非终结符S)句型baSb的短语。 根据最左推导: S?? αAδ * + A ? β 短语、直接短语和句柄 句型baSb中的子串a，是(相对于非终结符B)句型baSb的短语，且为直接短语、句柄。 句型baSb中的子串ba，是(相对于非终结符A)句型baSb的短语。 B ?a (3) S?bBSb * 根据最右推导: S?AB ?ASb ?bBSb ?baSb (4) S?ASb * A ?ba + S? αAδ * + A ? β 语法树与文法的二义性 推导和语法树 1. 语法树 对句型的推导过程给出一种图形表示, 这种表示称为语法树，也称推导树。 推导和语法树 例如 设有文法G[E]: 构造句型i*i+i的语法树。 首先给出句型的推导过程 (最左推导) ： E?E+T | E–T | T T?T*F | T/F | F F?(E) | i E?E+T?T+T?T*F+T?F*F+T?i*F+T ?i*i+T?i*i+F?i*i+i 推导和语法树 根据推导过程构造句型i*i+i的语法树如下： E?E+T E E + T ?T+T T ?T*F+T T * F ?F*F+T F ?i*F+T i ?i*i+T i ?i*i+F F ?i*i+i i 推导和语法树 由例可知，语法树的构造过程是从文法的开始符号出发，构造一个推导的过程。 因为文法的每一个句型 (句子) 都存在一 个推导，所以文法的每个句型(句子) 都存在一棵对应的语法树。 E?E+T ?E+F ?E+i ?T+i ?T*F+i ?T*i+i ?F*i+i ?i*i+i 推导和语法树 对句型i*i+i，还可给出最右推导： E E + T T T * F F i i F i 推导和语法树 这也就是说，一棵语法树表示了 一个句型的种种可能的(但未必是所 有的)不同推导过程, 包括最左(最右) 推导。 推导和语法树 2. 子树 语法树的子树是由某一结点连同所有分枝组成的部分。 E E + T T T * F F i i F i 推导和语法树 3. 简单子树 语法树的简单子树是指只有单层分枝的子树。 E E + T T T * F F i i F i 推导和语法树 句型的短语、直接短语和句柄的 直观解释是： 短语：子树的末端结点形成的符号串是 相对于子树根的短语。 直接短语：简单子树的末端结点形成的 符号串是相对于简单子树根的直接短语。 句柄：最左简单子树的末端结点形成的 符号串是句柄。 推导和语法树 E E + T T T * F F i i F i 短语: i*i+i i*i 第一个i 第二个i 第三个i 三个i都是直接短语 第一个i是句柄 注意:i+i不是句型的短语 句子 i*i+i 推导和语法树 前例 对文法G[S]=({S,A,B},{a,b},P,S) 其中P为： 可用语法树非常直观地求出句型baSb的全