精华内容
下载资源
问答
  • 编译原理直接短语
    万次阅读 多人点赞
    2017-12-09 20:24:59

    首先来看一棵树:

    该文法产生句子abbaa

    为了方便,将重复的a和b从左往右编号分别为a1,b1,b2,a2,a3

    1. 判断短语
    1)从深度为1开始,找出父节点,该图为S,它的短语为所有其子节点(无法继续产生叶子节点的节点)的集合,此处即为a1b1b2a2a3
    2)从最上层刚才找过的S往下找下一个父节点,即深度为2的,有A,B,S,依照1)中的做法,它们的短语分别为:a1,b1b2,a2a3
    3)往下到深度为3,包含叶子节点的有S,B,B,A,它们的短语分别为(空代表没有):b1,b2,a2
    4)继续往下(深度为4)由于已经都是叶子节点,没有子节点,到此为止。

    综上,短语有a1b1b2a2a3,a1,b1b2,a2a3,b1,b2,a2

    2.判断直接短语(简单短语)
    简单短语为一次性能推导出来的,即一次性推出叶子节点,如图,A->a1,B->b1,B->b2,A->a2均为直接推出叶子节点,故直接短语有a1,b1,b2,a2

    需要注意的是,最右边的a3也是叶子节点,也能直接由其父节点直接推导,但由于兄弟节点还有子节点,因而不算。

    3.判断句柄
    句柄即最左直接短语,由图可看出为a1

    更多相关内容
  • 编译原理 —— 短语、直接短语、素短语和句柄

    万次阅读 多人点赞 2019-03-17 13:11:54
    如果 βββ 中至少含有一个终结符,而且除它自身之外不再含任何更小的素短语,那么称 βββ 为 素短语 题目 令文法 G1G_1G1​ 为: ①S−>(L)∣aS∣a①S->(L)|aS|a①S−>(L)∣aS∣a...

    定义

    如果 β β β 中至少含有一个终结符,而且除它自身之外不再含任何更小的素短语,那么称 β β β素短语


    题目

    令文法 G 1 G_1 G1 为:

    ① S − > ( L ) ∣ a S ∣ a ①S->(L)|aS|a S>(L)aSa
    ② L − > L , S ∣ S ②L->L,S|S L>L,SS

    证明 ( S , ( a ) ) (S,(a)) (S,(a))是它的一个句型,指出这个句型的所有短语,直接短语,句柄和素短语。


    步骤一:画出语法树


    步骤二:判断短语

    • 一个句型的语法树中任一子树的叶节点所组成的符号串都是该句型的短语。
    1. 对于第一层的非终结符 S ,其叶节点所组成的短语是(S,(a))
    2. 对于第二层的非终结符 L ,其叶节点所组成的短语是S,(a)
    3. 对于第三层的非终结符 L ,其叶节点所组成的短语是S
    4. 对于第三层的非终结符 S ,其叶节点所组成的短语是(a)
    5. 对于第四层的非终结符 L ,其叶节点所组成的短语是a
    6. 对于第五层的非终结符 S ,其叶节点所组成的短语是a

    故短语有:

    ① (S,(a))
    ② S,(a)
    ③ S
    ④ (a)
    ⑤ a


    步骤三:判断直接短语

    • 一个句型的语法树中任一最小子树的叶节点所组成的符号串都是该句型的短语。

    故直接短语有:

    ① S
    ② a


    步骤四:判断句柄

    • 句柄是最左边的直接短语

    故句柄为:

    ① S


    步骤五:判断素短语

    • 有后往前对短语进行判断,如果短语中至少含有一个终结符,而且除它自身之外不再含任何更小的素短语,那么称该短语为素短语

    ① 对于短语 a ,a不含其他任何更小的素短语。故短语 a 为素短语
    ② 对于短语 (a) ,(a) 含素短语 a。故短语 (a) 不是素短语
    ③ 对于短语 S ,S 不含终结符。故短语 S 不是素短语
    ④ 对于短语 S,(a) ,S,(a) 含素短语a。故短语 S,(a) 不是素短语
    ⑤ 对于短语 (S,(a)) ,(S,(a)) 含素短语a。故短语 (S,(a)) 不是素短语

    故素短语为:

    ① a


    练习 1 如下

    题目:
    在这里插入图片描述

    语法树:
    在这里插入图片描述

    短语: T ∗ F T*F TF, E + T ∗ F E+T*F E+TF

    直接短语: T ∗ F T*F TF

    句柄: T ∗ F T*F TF

    素短语: T ∗ F T*F TF


    练习 2 如下

    题目:

    令文法 G 1 G_1 G1 为:

    ① S − > a ∣ b ∣ ( T ) ① S -> a|b|(T) S>ab(T)
    ② T − > T d S ∣ S ② T -> TdS|S T>TdSS

    证明 ( S d ( T ) d b ) (Sd(T)db) (Sd(T)db) 是 S 的一个句型,并求出短语,直接短语,句柄和素短语。

    语法树:

    在这里插入图片描述

    短语:S,(T),b,Sd(T),Sd(T)db,(Sd(T)db)

    直接短语:S,(T),b

    句柄:S

    素短语:(T),b


    参考链接:

    https://blog.csdn.net/it_dream_er/article/details/53612006

    展开全文
  • 编译原理:短语、直接短语和句柄

    千次阅读 多人点赞 2020-03-19 11:28:19
    γ,则称γ是句型αγβ的相对于变量A的直接(简单)短语,最左直接短语叫做句柄 一般画出语法树来判断 判断方法:一个句型的语法树中任一子树叶结点所组成的符号串都是该句型的短语; 当子树中不包含其他更小...

    概念:

    如果S->* αAβ and A->+γ,则称γ是句型αγβ的相对于变量A的短语
    如果S->* αAβ and A->γ,则称γ是句型αγβ的相对于变量A的直接(简单)短语,最左直接短语叫做句柄

    一般画出语法树来判断

    判断方法:一个句型的语法树中任一子树叶结点所组成的符号串都是该句型的短语;

                      当子树中不包含其他更小的子树时,该子树叶结点所组成的字符串就是该句型的直接(简单)短语;

                      一个句型的最左直接短语汇称为该句型的句柄。


    每棵语法树的叶子结点从左到右排列构成一个句型 
    每棵语法树的子树的叶子结点从左到右排列构成一个短语 
    每棵语法树的简单子树(只有父子两层结点)的叶子结点从左到右排列构成一个简单(直接)短语 

    例题:

    已知文法

    E→T| E+T | E-T

    T→F| T*F |T/F

     F→(E) | i

    请写出该文法句型T+T*F+i的短语,直接短语和句柄。

    先画出语法树:

    判断短语: 

    1. 对于第一层的非终结符 E ,其叶节点所组成的短语是 T + T*F + i 
    2. 对于第二层的非终结符 E,其叶节点所组成的短语是 T
    3. 对于第二层的非终结符 T,其叶节点所组成的短语是 T*F + i
    4. 对于第三层的非终结符 E ,其叶节点所组成的短语是 T*F
    5. 对于第三层的非终结符 F ,其叶节点所组成的短语是 i
    6. 对于第四层的非终结符 T,其叶节点所组成的短语是 T*F
    7. 对于第五层的非终结符 F ,其叶节点所组成的短语是 i

     所以短语有:T+T*F+i , T*F+i , T , T*F , i 

    图中画圈的“+”号,虽然是叶子结点,但是他的父节点所在子树不是简单子树

    直接短语: T , T*F , i

    句柄:T

     

    展开全文
  • 编译原理之 短语&直接短语&句柄 定义与区分

    万次阅读 多人点赞 2020-03-12 14:57:50
    编译原理之 短语&直接短语&句柄 定义与区分一、关于短语二、关于直接短语三、关于句柄四、小练习1、练习一2、练习二五、知识加强拓展1、利用语法树寻找句型的短语、直接...其中编译原理中的短语,直接短语,...


    叮嘟!这里是小啊呜的学习课程资料整理。好记性不如烂笔头,今天也是努力进步的一天。一起加油进阶吧!
    在这里插入图片描述

    其中编译原理中的短语,直接短语,句柄的定义参见博文:
    https://blog.csdn.net/it_dream_er/article/details/53612006
    

    一、关于短语

    书上的定义如下:
    在这里插入图片描述

    书上写的比较抽象,我这里简单解释一下,有两个文法,分别是:

    S=*=>aAp (由于部分字符难以输入,在此用a,b,p代替)
    A=+=>b
    

    我们由此可以画出他的抽象语法树,如下:
    在这里插入图片描述
    那么,abp为此句型的短语 。

    总结来说:一个句型的语法树中任一子树叶结点所组成的符号串都是该句型的短语,由这概念,那么我们自然可以想到,b也应该是该句型的一个短语。

    二、关于直接短语

    书中的定义:

    在这里插入图片描述
    书中的意思总结来说,指的是如果子树中不再包含其他的子树,即A只能推导出b,而b不能再推出其他的式子,则b为此句型的直接短语。

    三、关于句柄

    先来看一下书中的定义:
    在这里插入图片描述
    书中的意思就是:直接短语中的最左直接短语为该句型的句柄

    四、小练习

    1、练习一

    在这里插入图片描述

    如何证明E+T*F是句型呢?
    最简单的方法就是画抽象语法树,如果能画出对应的抽象语法树,则就表明此表达式是文法的一个句型。

    抽象语法树如下:
    在这里插入图片描述

    按如上的语法树可知,E=T*F为此文法的一个句型:

    • 短语: TF, E+TF

    • 直接短语:T*F

    • 句柄:T*F

    简析:对于子树T来说,其所有叶子节点为:TF,对于E来说,其所有叶子节点为:E+TF故短语为 TF 和 E+TF

    这个比较简单,我们下面来个比较复杂的题目。

    2、练习二

    S -> a|b|(T) 
    T -> TdS|S
    证明(Sd(T)db)是S的一个句型,并求出短语,直接短语,句柄。
    

    此文法的抽象语法树为:
    在这里插入图片描述

    由此可得S=(Sd(T)db)为此文法的一个句型:

    • 短语:S,(T),b,Sd(T),Sd(T)db,(Sd(T)db)
    • 直接短语:S,(T),b
    • 句柄:S

    五、知识加强拓展

    1、利用语法树寻找句型的短语、直接短语、句柄方法

    在这里插入图片描述

    2、利用语法树寻找短语、句柄等方法总结

    在这里插入图片描述

    3、利用语法树寻找短语、句柄举例

    (1)示例一:

    在这里插入图片描述
    (2)示例二:

    在这里插入图片描述
    在这里插入图片描述

    Ending!
    更多课程知识学习记录随后再来吧!

    就酱,嘎啦!
    

    在这里插入图片描述

    注:
    1、我们愈是学习,愈觉得自己的贫乏。 —— 雪莱
    2、编译原理中的短语,直接短语,句柄的定义参见文章:https://blog.csdn.net/it_dream_er/article/details/53612006

    展开全文
  • 一般先根据句型写出语法树,然后再根据语法树进行求解。 举个例子: 先画出语法树(最左推导): 短语:在语法树中,先找出所有的非...在这个例子,我们可以用叶子节点T一步替换掉E,那么T就是一个直接短语,然后我们
  • γ,则称γ是句型αγβ的相对于变量A的直接(简单)短语 最左直接短语叫做句柄 其实最简单的判断方法直接画出语法树了。 文法 S->(L)|aS|a L->L,S|S 分析(S,(a)) 1.先画出语法树 2.判断短语 一个句型的...
  • 由于我的编译原理课程不讲人话,在阅读《数据结构》和CSDN相关博文之后,总结编译原理语法分析中的三个词的定义: 1.短语,所有子树的末端节点行成的字符串。 2.直接短语,所有简单子树的末端节点形成的字符串。 3....
  • 编译原理中:短语,直接短语,句柄

    万次阅读 多人点赞 2016-12-13 19:37:55
    这几天邻近期末,感觉上了快一学期的编译原理的许多方面还是难以理解,今天早上就突然遇到了一道题,求短语,直接短语和句柄的题,突然才发现自己连这些词的定义都不清楚,于是仔细查了以下,下面分享出来:短语书上...
  • γ,则称γ是句型αγβ的相对于变量A的直接(简单)短语 最左直接短语叫做句柄。 其实最简单的判断方法直接画出语法树了。 文法 S->(L)|aS|a L->L,S|S 分析(S,(a)) 1.先画出语法树 ...
  • 编译原理:短语、直接短语、句柄

    千次阅读 多人点赞 2019-07-01 20:06:46
    学习分享:超详细解析短语、直接短语、句柄 例文法: E → E + E E →( E ) E → E * E E → id 分析 id1 * id2 + id3 1.首先推导出 id1 * id2 + id3 E ⇒ E * E ⇒ E * E + E ⇒ E * E + id3 ⇒ E * id2 + id...
  • 编译原理:短语、直接短语、句柄、最左素短语 短语: 同一子树的所有叶子(终结符类型的)节点 直接短语: 同一父节点一步推出的所有叶子节点,即最末端的单一子树(不拼凑)的所有叶节点 句柄: 最左直接短语 素...
  • 短语 直接短语 句柄 素短语 区别短语直接短语句柄素短语 短语 一个节点的叶节点的组合即为短语 直接短语 一个节点的子节点没有子节点,则其子节点构成的短语即为直接短语(即子节点均为叶节点) 句柄 最左边的直接...
  • 直接短语:二级子树的叶子节点的序列(子树中不再包含其他的子树,即A只能推导出b,而b不能再推出其他的式子,则b为此句型的直接短语) 句柄:最左边的直接短语 用一个栗子来理解一下: 证明是句型,我们只需要...
  • 编译原理素短语和直接短语

    千次阅读 2020-03-20 00:45:31
    直接短语 找一个子树它的节点都没有子树 素短语 在短语里面找,有终止符的,终止符包括加减乘除,但是一个素短语不能包括其他素短语
  • 短语和直接短语的概念:一个句型的语法树中任一子树叶结点所组成的符号串都是该句型的短语,当子树中不包含其他更小的子树时,该子数叶结点所组成的字符串就是该句型的直接(简单)短语。 句柄的概念:一个句型的最...
  • 直接短语 < 短语 一、先找句柄! 分析一波先,这是课本上给予的偏理解性的定义, (1)首先要找到最左边的子树 (2)这个子树有多少代(层),(缩小范围->) 只看最下面的两代,下面两代作为要寻找的子树。...
  • 编译原理之 句型&句子&短语&直接短语&句柄&素短语&最左素短语 定义实例详解 一、定义详解 1、句型&句子 2、短语&直接短语 3、句柄 4、素短语&最左素短语 二、 实例巩固理解 1、实例一求解短语、直接短语、句柄和素...
  • 编译原理:语法树的子树,短语,直接短语,句柄 子树: 某一非终结符号(子树的根)以及下面的分支,整个语法树也可看成一个子树 短语: 给定一个句型,分析树中的每一个子树的边缘(叶子)称为句型的一个短语 直接...
  • <编译原理>短语、直接短语及句柄

    万次阅读 2017-12-10 16:18:43
    用语法树求短语、简单短语和句柄的方法是: 1)每个句型都有一棵语法树; 2)每棵语法树的叶(从左到右)组成一句型; 3)每个子树 的叶(从左到右)组成一短语; 4)每个简单子树 的叶(从左到右)组成一简单短语;...
  • 素短语的概念:它是一个递归的定义,至少含有一个终结符,并且除它自身之外不再含任何更小的素短语,所谓最左素短语就是处于句型最左边的素短语的短语。而一个算符优先文法G的任何句型的最左素...短语和直接短语的概念
  • --句型与句子 如果 S⇒*α,α∈(VT∪VN)*,则称α是G的一个句型(sentential form) 一个句型中既可以包含终结符,又可以...如果S αAβ且Aγ,则称γ是句型αγβ的相对于非终结符A的短语 。 如果SαAβ 且...
  • 1.定义 句型、句子、语言 设文法G=(VT,VN,S和P)。如果S =&...短语、直接短语、句柄 令G是一个文法,S是文法的开始符号,假定αβδ是文法G的一个句型,如果有S =&gt;* αAδ 且 A =&gt;+ ...
  • 短语 每棵子树的叶子节点的拼接(整棵树也算) 直接短语 是短语的子集,区别是这里的子树只能有一个叶子节点 句柄 最左边的直接短语 例子
  • 编译原理》求短语,直接短语,句柄,素短语,最左素短语 - 例题解析 笔记 (一)明确概念: 名称 概念 短语 定义: 若 S 为文法 G 的开始符号,αβδ 是该文法的一个句型,即 S ⇒* αβδ,且有 A ⇒+ ...
  • 2019-2020人大作业,编译原理

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 3,597
精华内容 1,438
关键字:

编译原理直接短语