编译原理 语法树 句柄 简单短语 短语 |
您所在的位置:网站首页 › 最左直接短语知乎 › 编译原理 语法树 句柄 简单短语 短语 |
解析:
题目中的句型可用下面的语法树表示: S / | \ ( T ) / | \ T d S /|\ | T d S b | /|\ S ( T )
一个句型的语法树中任一子树叶结点所组成的符号串都是该句型的短语,当子树中不包含其他更小的子树时,该子数叶结点所组成的字符串就是该句型的直接(简单)短语。 因此本题的直接短语的为 S 、(T)、b,短语有S、(T)、b、Sd(T)、Sd(T)db 、(Sd(T)db)。 d不是直接短语,因为d所在的树还有子树所以它不是 ! 一个句型的最左直接短语汇称为该句型的句柄素语是一个短语,它至少含有一个终结符,而且除它自身以外不再含有更少的素短语,对于句型(Sd(T)db)的素短语是(T)、b.
每个句型对应一棵语法树 每棵语法树的叶子结点从左到右排列构成一个句型 每棵语法树的子树的叶子结点从左到右排列构成一个短语 每棵语法树的简单子树(只有父子两层结点)的叶子结点从左到右排列构成一个简单(直接)短语 每棵语法树的最左简单子树(只有父子两层结点)的叶子结点从左到右排列构成句柄 素短语是至少包含一个终结符的短语,但它不能包含其它素短语 最左推导:在每个推导过程中,总是首先考虑对当前最左边的非终结符号进行推导 最右推导:在每个推导过程中,总是首先考虑对当前最右边的非终结符号进行推导
例子2——直接推导 已知文法G[S] S::=aB|bA A::=a|aS|bAA B::=aBB|bS|b 句型aabbAb的句柄是 A.a B.ab C.b D.bA 解析: 句型aabbAb的句柄是D: bA; S->aB->aaBB->aabSB->aabbAB->aabbAb 按照最左推导,其中的S->bA这步是最后的直接推导(即它推出的bA不再被继续往下推导),虽然B->b也是这样的,但不是最左的。 总结: 画语法树: 一个节点的所有子叶子节点从左到右相连即是该句型的短语 当子树中不包含其他更小的子树时,该子数叶结点所组成的字符串就是该句型的直接(简单)短语——重点看该子叶子节点的兄弟节点。最左简单短语为句柄 直接推导: 按最左推导,最后的直接推导出的结果是简单短语,最左简单短语为句柄 句柄 简单短语 短语 素短语 都是取自句型的一部分 |
CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3 |