精华内容
下载资源
问答
  • 素短语,最左素短语-编译原理
    万次阅读 多人点赞
    2017-01-01 15:58:27

    这个连接是句型,短语,简单短语,句柄的定义http://blog.csdn.net/qq78442761/article/details/53868673


    下面是素短语和最左素短语的定义:

    素短语,是指至少含有一个终结符的短语,并且除自身外,不包含更小的素短语。
    最左素短语是句型中最左边的素短语。

    下面给出一个例子:


    句型:cabB

    短语:c,ca,bB

    简单短语:c,bB

    句柄:c

    (上面的这部分判断在上面那个链接有)

    素短语:c,bB

    最左素短语:c

    更多相关内容
  • 编译原理》求短语,直接短语,句柄,素短语,最左素短语 - 例题解析 笔记 (一)明确概念: 名称 概念 短语 定义: 若 S 为文法 G 的开始符号,αβδ 是该文法的一个句型,即 S ⇒* αβδ,且有 A ⇒+ ...

    《编译原理》求短语,直接短语,句柄,素短语,最左素短语 - 例题解析

    笔记

    (一)明确概念:

    名称概念
    短语定义: 若 S 为文法 G 的开始符号,αβδ 是该文法的一个句型,即 S ⇒* αβδ,且有 A ⇒+ β,则称 β 是句型 αβδ 相对于非终结符 A 的短语。语法树: 在语法树中表示所有分支结点对应子树,短语即子树叶子对应的符号。注: 子树包括语法树本身,及句型本身也可以称为短语。
    直接短语定义: 若 S ⇒* αβδ,且文法中包含产生式 A → β,则称 β 是句型 αβδ 相对于非终结符 A 的直接短语。语法树: 在语法树中表示为该短语只有上下相邻父子两代
    句柄“可规约串”,句柄对应某个产生式的右部,是某个,但不是任意一个。作为一种规约对象,句柄表示最左直接短语语法树: 在语法树上,则表示为最左边的只包含相邻父子节点的短语(最左直接短语)
    素短语定义: 是指一个短语至少包含一个终结符,并且除它自身之外不再包含其他素短语
    最左素短语定义: 最左素短语就是句型最左边的素短语,是算符优先分析法的规约对象。语法树: 通过语法树分析时,要注意先判断是否为素短语,再找相对最左端的素短语。

    例题1:求短语,直接短语,句柄

    给定句型:

    T*P↑(T*F)

    给定文法:

    G[T]:
    T → T*F|F
    F → F↑P|P
    P → (T)|i

    解析:

    推导步骤为:

    T ⇒ T*F
    ⇒ T*F↑P
    ⇒ T*P↑P
    ⇒ T*P↑(T)
    ⇒ T*P↑(T*F)

    画出语法树为:

    在这里插入图片描述

    该语法树的 5 个子树及 5 个短语为:

    在这里插入图片描述

    求直接短语方法: 该句型的语法树有两颗直接子树(最左边的两颗子树),由这两颗直接子树的叶子结点组成的符号串(或者说只包含两层的子树叶子结点对应的),就是句型的两个直接短语,直接短语 P 和 T*F。

    求句柄: 因为 P 相对 T*F,在语法树上的左侧,所以句柄是 P

    最终结果:

    类型内容
    短语 5 个P,T*F,(T*F),P↑(T*F),T*P↑(T*F)
    直接短语 2 个P,T*F
    句柄P

    例题二:求素短语,最左素短语

    给定句型:

    FF↑*a*

    给定文法:

    G[T]:
    T → T*F|F
    F → F↑P|P
    P → (T)|i

    解析:

    推导步骤为:

    T ⇒ TF*
    ⇒ TF*F*
    ⇒ TF↑*\F*
    ⇒ TF↑*a*

    画出语法树:

    在这里插入图片描述

    最终结果:

    根据定义可以找出素短语有:

    类型内容
    素短语 2 个F↑,a
    最左素短语F↑
    展开全文
  • 先画出语法树(最左推导): 短语:在语法树中,先找出所有的非终结符,然后用叶子节点去替换他们,最后得到的集合就是短语的集合。 这里的非终结符从上到下为:E、E、T、E、T、F、T、T、F。我们用叶子节点全部替换...

    一般先根据句型写出语法树,然后再根据语法树进行求解。
    举个例子:
    在这里插入图片描述
    先画出语法树(最左推导):
    在这里插入图片描述

    短语:在语法树中,先找出所有的非终结符,然后用叶子节点去替换他们,最后得到的集合就是短语的集合。
    这里的非终结符从上到下为:E、E、T、E、T、F、T、T、F。我们用叶子节点全部替换这些非终结符。所以短语有:T、T * F、i、T+T * F、T+T * F+i。(重复的去掉了)

    直接短语:在语法树中,一步就能够用叶子节点替换掉非终结符的短语。
    在这个例子,我们可以用叶子节点T一步替换掉E,那么T就是一个直接短语,然后我们发现T * F这个短语也能一步替换掉T这个节点,因此T*F也是直接短语。同理可以知道i也是直接短语。
    所以直接短语有:T、T * F、i。

    句柄:语法树中最左边的直接短语。
    这里很明显是T。

    素短语:短语中的包含终结符的短语,同时不被其他素短语包含的短语。
    这里很拗口,因此仔细说一下。
    在这个例子中,我们看包含终结符的短语有:T*F、i、T+T * F、T+T * F+i。然后我们发现T+T * F+i包含了i和T+T * F和T * F,所以这个肯定不是。然后我们发现T+T * F包含了T * F,所以这个也不是。
    因此素短语有:i、T * F。

    最左素短语:顾名思义。
    这里是:T * F

    展开全文
  • 编译原理之 句型&句子&短语&直接短语&句柄&素短语&最左素短语 定义实例详解 一、定义详解 1、句型&句子 2、短语&直接短语 3、句柄 4、素短语&最左素短语 二、 实例巩固理解 1、实例一求解短语、直接短语、句柄和素...


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

    一、定义详解

    1、句型&句子

    概念:

    如果 S⇒* α,α∈(VT∪VN)*,则称α是G的一个句型 (sentential form)。
    一个句型中既可以包含终结符,又可以包含非终结符,也可能是空串。
    
    如果 S⇒* w,w ∈VT*,则称w是G的一个句子(sentence)。
        句子是不包含非终结符的句型。
    

    2、短语&直接短语

    概念:

    如果 S⇒* αAβ 且 A ⇒+ γ,则称γ是句型αγβ的相对于非终结符A的`短语` 。
    如果 S⇒* αAβ 且 A ⇒ γ,则称γ是句型αγβ的相对于规则A→γ的`直接(简单)短语`

    理解:

    短语:
    一个句型的分析树中的每一棵子树的边缘(所有叶节点)所组成的符号串称为该句型的一个短语(phrase)。 
    
    直接短语:
    如果子树只有父子两代结点,那么这棵子树的边缘称为该句型的一个直接短语(immediate phrase);
    所有子树中,深度为2的子树的叶子节点串就是直接短语(因为直接短语必须是由子树根节点用一步推出来的,所以深度为2);
    即如果子树中不再包含其他的子树,即A只能推导出b,而b不能再推出其他的式子,则b为此句型的直接短语。
    
    语法树: 在语法树中表示为直接短语只有上下相邻父子两代。
    

    3、句柄

    概念:

    直接短语中的最左直接短语为该句型的句柄。
    

    理解:

    “可规约串”,句柄对应某个产生式的右部,是某个,但不是任意一个。
    作为一种规约对象,句柄表示最左直接短语。
    语法树: 在语法树上,则表示为最左边的只包含相邻父子节点的短语(最左直接短语)
    

    4、素短语&最左素短语

    概念:

    素短语:
    是指一个短语至少包含一个终结符,并且除它自身之外不再包含其他素短语。
    
    最左素短语:
    最左素短语就是句型最左边的素短语,是算符优先分析法的规约对象。
    语法树:通过语法树分析时,要注意先判断是否为素短语,再找相对最左端的素短语。
    

    理解:

    素短语 :
    指一个短语至少包含一个终结符,并且除它自身之外不再包含其他素短语。
    从短语集合中找出所有含有终结符的短语,然后选出除它自身之外不再含更小的素短语。
    (这个小的概念是集合中没有被包含的元素,如有两个短语aAA和aAAA,aAA含于aAAA,所以aAA比aAAA小)
    
    最左素短语:
    从素短语集合中找出最左边的素短语。
    

    二、 实例巩固理解

    1、实例一求解短语、直接短语、句柄和素短语详解

    令文法 G1 为:
    ①S−>(L)∣aS∣a 
    ②L−>L,S∣S 
    

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

    题解:

    步骤一:画出语法树如下图
    在这里插入图片描述
    步骤二:判断短语
    一个句型的语法树中任一子树的叶节点所组成的符号串都是该句型的短语。
    对于第一层的非终结符 S ,其叶节点所组成的短语是(S,(a))
    对于第二层的非终结符 L ,其叶节点所组成的短语是S,(a)
    对于第三层的非终结符 L ,其叶节点所组成的短语是S
    对于第三层的非终结符 S ,其叶节点所组成的短语是(a)
    对于第四层的非终结符 L ,其叶节点所组成的短语是a
    对于第五层的非终结符 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
    

    2、实例二求解短语、直接短语、句柄、素短语和最左素短语详解

    在这里插入图片描述

    3、实例三求解短语、直接短语、句柄、素短语和最左素短语详解

    在这里插入图片描述

    4、实例四求解短语,直接短语,句柄详解

    给定句型:
    T*P↑(T*F)
    
    给定文法:
    G[T]:
    T → T*F|F
    F → F↑P|P
    P → (T)|i
    
    求解句型的短语,直接短语,句柄。
    

    题目解析:

    推导步骤为:
    T ⇒ T*F
      ⇒ T*F↑P
      ⇒ T*P↑P
      ⇒ T*P↑(T)
      ⇒ T*P↑(T*F)
    

    在这里插入图片描述
    该语法树的 5 个子树及 5 个短语为:
    在这里插入图片描述
    求直接短语方法: 该句型的语法树有两棵直接子树(最左边的两颗子树),由这两棵直接子树的叶子结点组成的符号串(或者说只包含两层的子树叶子结点对应的),就是句型的两个直接短语直接短语为 P 和 T*F

    求句柄: 因为 P 相对 T*F,在语法树上的左侧,所以句柄是 P

    综上:
    
    短语         P,T*F,(T*F),P↑(T*F),T*P↑(T*F)
    直接短语 	P,T*F
    句柄	        P
    

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

    就酱,嘎啦!
    

    在这里插入图片描述

    注:
    人生在勤,不索何获。

    展开全文
  • 编译原理:短语、直接短语、句柄、最左素短语 短语: 同一子树的所有叶子(终结符类型的)节点 直接短语: 同一父节点一步推出的所有叶子节点,即末端的单一子树(不拼凑)的所有叶节点 句柄: 左直接短语 素...
  • 短语 每棵子树的叶子节点的拼接(整棵树也算) 直接短语短语的子集,区别是这里的子树只能有一个叶子节点 句柄 左边的直接短语 例子
  • 编译原理 —— 短语、直接短语、素短语和句柄

    万次阅读 多人点赞 2019-03-17 13:11:54
    如果 βββ 中至少含有一个终结符,而且除它自身之外不再含任何更小的素短语,那么称 βββ 为 素短语 题目 令文法 G1G_1G1​ 为: ①S−>(L)∣aS∣a①S->(L)|aS|a①S−>(L)∣aS∣a...
  • 短语 定义: 若 S 为文法 G 的开始符号,αβδ 是该文法的一个句型,即 S ⇒* αβδ,且有 A ⇒+ β,则称 β 是句型 αβδ 相对于非终结符 A 的短语。语法树: 在语法树中表示所有分支结点对应子树,短语即子树...
  • 复习编译原理,理了一下几个基本概念的判断思路: 1. 根据句型画语法推导树。 2. 判断短语短语是语法推导树中每一个非叶子节点作为根的子树,从到右的叶子节点。注意:短语可以是非终结符。 3. 判断直接短语...
  • 自底向上分析方法,也称移进-归约分析法。 实现思想: 对输入符号串自左向右进行扫描,并将输入符逐个移入一个栈中,边移入边分析,一旦栈顶符号串形成某个句型的句柄时,就用该产生式的左部非终结符代替相应右部的...
  • --句型与句子 如果 S⇒*α,α∈(VT∪VN)*,则称α是G的一个句型(sentential form) 一个句型中既可以包含终结符,又可以...如果S αAβ且Aγ,则称γ是句型αγβ的相对于非终结符A的短语 。 如果SαAβ 且...
  • 短语 直接短语 句柄 素短语 区别短语直接短语句柄素短语 短语 一个节点的叶节点的组合即为短语 直接短语 一个节点的子节点没有子节点,则其子节点构成的短语即为直接短语(即子节点均为叶节点) 句柄 左边的直接...
  • γ,则称γ是句型αγβ的相对于变量A的直接(简单)短语 最左直接短语叫做句柄 其实简单的判断方法直接画出语法树了。 文法 S->(L)|aS|a L->L,S|S 分析(S,(a)) 1.先画出语法树 2.判断短语 一个句型的...
  • 素短语:至少含有一个终结符,并且除它自身之外不再含任何更小的素短语 短语和直接短语的概念:一个句型的语法树中任一子树叶结点所组成的符号串都是该句型的短语,当子树中不包含其他更小的子树时,该子数叶结点所...
  • 短语、句柄、素短语、最左素短语

    万次阅读 多人点赞 2015-04-07 21:31:39
    很久没写博客了=== 今天写一发=== 关于编译原理 语法树 句柄 简单短语 短语 的区分,通过两个例子来理解概念以及方法: 例子1——语法树 S -> a|b|(T)  ...____是最左素短语;____是该句型的
  • 编译原理素短语和直接短语

    千次阅读 2020-03-20 00:45:31
    直接短语 找一个子树它的节点都没有子树 素短语 在短语里面找,有终止符的,终止符包括加减乘除,但是一个素短语不能包括其他素短语
  • 素短语的概念:它是一个递归的定义,至少含有一个终结符,并且除它自身之外不再含任何更小的素短语,所谓最左素短语就是处于句型左边的素短语的短语。而一个算符优先文法G的任何句型的最左素短语是满足以下条件的...
  • 1.定义 句型、句子、语言 设文法G=(VT,VN,S和P)。如果S =&...短语、直接短语、句柄 令G是一个文法,S是文法的开始符号,假定αβδ是文法G的一个句型,如果有S =>* αAδ 且 A =>+ ...
  • γ,则称γ是句型αγβ的相对于变量A的直接(简单)短语 最左直接短语叫做句柄。 其实简单的判断方法直接画出语法树了。 文法 S->(L)|aS|a L->L,S|S 分析(S,(a)) 1.先画出语法树 ...

空空如也

空空如也

1 2 3 4 5 ... 19
收藏数 367
精华内容 146
关键字:

编译原理最左素短语