编译原理:如何判断一颗语法树的短语、直接短语、句柄、素短语 |
您所在的位置:网站首页 › bundle短语 › 编译原理:如何判断一颗语法树的短语、直接短语、句柄、素短语 |
概念
如果S->* αAβ and A->+γ,则称γ是句型αγβ的相对于变量A的短语 。 如果S->* αAβ and A->γ,则称γ是句型αγβ的相对于变量A的直接(简单)短语 最左直接短语叫做句柄。 其实最简单的判断方法直接画出语法树了。 文法S->(L)|aS|a L->L,S|S 分析(S,(a)) 1.先画出语法树 2.判断短语一个句型的语法树中任一子树叶节点所组成的符号串都是该句型的短语。 很明显的,最下面的a是S的叶子节点、最左边的S是L的叶子节点。 其他的叶子节点从左往右分别是(,,,(,),) 在树的第四层的(,L,)都是子树S的孩子,因为短语都是叶子节点,所以这边的短语有(a) 在树的第三层的L,,,S都是子树L的孩子,因为短语都是叶子节点,所以这边的短语有S,(a) 在树的第二层的(,L,)都是根节点S的孩子,因为短语都是叶子节点,所以这边的短语有(S,(a)) 所以短语有a (a) S,(a) (S,(a)) 3.判断直接(简单)短语当子树不包含其他更小的子树时,该子树叶节点所组成的字符串就是该句型的直接短语。 短语包含直接短语,我们可以直接在短语中判断。 这里只有第五层的S和第三层的L不包含其他更下的子树,所以有a和S是直接短语。 其中(a)的父节点S包含L,S,(a)的父节点L包含L和S, (S,(a))的父节点S包含L 4.判断句柄句柄是最左边的直接短语。 因为S处于最左边,所以S是直接短语。 5.判断素短语素短语是一个短语,它至少含有一个终结符,而且除他之外不含有其他素短语。 短语包含素短语,我们可以直接在短语中判断。 因为S可以推导出其他字符,(a);S,(a);(S,(a))都包含其他素短语,所以符合条件的只有a。
此文为转载文章: --------------------- 作者:大胆10 来源:CSDN 原文:https://blog.csdn.net/u014297473/article/details/45825663 版权声明:本文为博主原创文章,转载请附上博文链接! |
今日新闻 |
推荐新闻 |
CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3 |