-
2020-11-01 15:46:54更多相关内容
-
编译原理基本定义(短语、直接短语、句柄、素短语、最左素短语)
2021-12-26 16:30:14短语:在语法树中,先找出所有的非终结符,然后用叶子节点去替换他们,最后得到的集合就是短语的集合。 这里的非终结符从上到下为:E、E、T、E、T、F、T、T、F。我们用叶子节点全部替换这些非终结符。所以短语有:T...一般先根据句型写出语法树,然后再根据语法树进行求解。
举个例子:
先画出语法树(最左推导):
短语:在语法树中,先找出所有的非终结符,然后用叶子节点去替换他们,最后得到的集合就是短语的集合。
这里的非终结符从上到下为: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 -
编译原理 —— 短语、直接短语、素短语和句柄
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)∣aS∣a
② L − > L , S ∣ S ②L->L,S|S ②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
练习 1 如下
题目:
语法树:
短语: T ∗ F T*F T∗F, E + T ∗ F E+T*F E+T∗F
直接短语: T ∗ F T*F T∗F
句柄: T ∗ F T*F T∗F
素短语: T ∗ F T*F T∗F
练习 2 如下
题目:
令文法 G 1 G_1 G1 为:
① S − > a ∣ b ∣ ( T ) ① S -> a|b|(T) ①S−>a∣b∣(T)
② T − > T d S ∣ S ② T -> TdS|S ②T−>TdS∣S证明 ( 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
-
《编译原理》求短语,直接短语,句柄,素短语,最左素短语 - 例题解析
2019-06-21 21:46:39《编译原理》求短语,直接短语,句柄,素短语,最左素短语 - 例题解析 笔记 (一)明确概念: 名称 概念 短语 定义: 若 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↑ -
编译原理:素短语、短语、直接短语、句柄的基本概念
2017-05-28 12:21:23素短语的概念:它是一个递归的定义,至少含有一个终结符,并且除它自身之外不再含任何更小的素短语,所谓最左素短语就是处于句型最左边的素短语的短语。而一个算符优先文法G的任何句型的最左素短语是满足以下条件的... -
编译原理知识点总结——素短语、短语、直接短语、句柄的概念
2020-12-17 09:37:20素短语:至少含有一个终结符,并且除它自身之外不再含任何更小的素短语 短语和直接短语的概念:一个句型的语法树中任一子树叶结点所组成的符号串都是该句型的短语,当子树中不包含其他更小的子树时,该子数叶结点所... -
短语,直接短语,句柄,素短语,最左素短语---编译原理
2020-04-24 19:09:55短语 每棵子树的叶子节点的拼接(整棵树也算) 直接短语 是短语的子集,区别是这里的子树只能有一个叶子节点 句柄 最左边的直接短语 例子 -
编译原理:短语、直接短语、句柄、素短语
2019-04-13 16:39:29γ,则称γ是句型αγβ的相对于变量A的直接(简单)短语 最左直接短语叫做句柄 其实最简单的判断方法直接画出语法树了。 文法 S->(L)|aS|a L->L,S|S 分析(S,(a)) 1.先画出语法树 2.判断短语 一个句型的... -
编译原理之找短语、句柄、素短语等
2018-04-20 20:13:591.定义 句型、句子、语言 设文法G=(VT,VN,S和P)。如果S =&...短语、直接短语、句柄 令G是一个文法,S是文法的开始符号,假定αβδ是文法G的一个句型,如果有S =>* αAδ 且 A =>+ ... -
编译原理——短语、简单短语、句柄
2019-10-12 19:04:50接下来给出短语、简单短语、句柄的不严谨定义: 短语:一颗树及其子树包含的所有叶节点组成的符号串,上图的短语为 id1 id1*id2 id2 三个。 简单短语:只包含叶节点的子树,其叶节点组成的符号串,上图的简单短语为 ... -
编译原理之 短语&直接短语&句柄 定义与区分
2020-03-12 14:57:50句柄 定义与区分一、关于短语二、关于直接短语三、关于句柄四、小练习1、练习一2、练习二五、知识加强拓展1、利用语法树寻找句型的短语、直接短语、句柄方法2、利用语法树寻找短语、句柄等方法总结3、利用语法树寻找... -
编译原理:如何判断一颗语法树的短语、直接短语、句柄、素短语
2019-05-25 19:31:34γ,则称γ是句型αγβ的相对于变量A的直接(简单)短语 最左直接短语叫做句柄。 其实最简单的判断方法直接画出语法树了。 文法 S->(L)|aS|a L->L,S|S 分析(S,(a)) 1.先画出语法树 ... -
编译原理之:短语,直接短语,句柄
2021-03-15 23:49:20由于我的编译原理课程不讲人话,在阅读《数据结构》和CSDN相关博文之后,总结编译原理语法分析中的三个词的定义: 1.短语,所有子树的末端节点行成的字符串。 2.直接短语,所有简单子树的末端节点形成的字符串。 3.... -
编译原理之 句型&句子&短语&直接短语&句柄&素短语&最左素短语 定义实例详解
2020-04-29 23:37:26编译原理之 句型&句子&短语&直接短语&句柄&素短语&最左素短语 定义实例详解 一、定义详解 1、句型&句子 2、短语&直接短语 3、句柄 4、素短语&最左素短语 二、 实例巩固理解 1、实例一求解短语、直接短语、句柄和素... -
编译原理中:短语,直接短语,句柄
2020-03-29 17:51:46编译原理中:短语,直接短语,句柄 -
编译原理——短语、直接短语、句柄
2017-12-09 20:24:591)从深度为1开始,找出父节点,该图为S,它的短语为所有其子节点(无法继续产生叶子节点的节点)的集合,此处即为a1b1b2a2a3; 2)从最上层刚才找过的S往下找下一个父节点,即深度为2的,有A,B,S,依照1)中的... -
编译原理中的短语、直接短语、句柄,怎么找呀!个人理解,看完细品
2021-05-15 17:23:28句柄范围最小, 句柄 < 直接短语 < 短语 一、先找句柄! 分析一波先,这是课本上给予的偏理解性的定义, (1)首先要找到最左边的子树 (2)这个子树有多少代(层),(缩小范围->) 只看最下面的两代,... -
编译原理句柄寻找
2022-06-13 22:36:18寻找句柄 -
编译原理:短语、直接短语和句柄
2020-03-19 11:28:19γ,则称γ是句型αγβ的相对于变量A的直接(简单)短语,最左直接短语叫做句柄 一般画出语法树来判断 判断方法:一个句型的语法树中任一子树叶结点所组成的符号串都是该句型的短语; 当子树中不包含其他更小... -
编译原理:短语、直接短语、句柄、最左素短语
2020-06-22 20:30:50编译原理:短语、直接短语、句柄、最左素短语 短语: 同一子树的所有叶子(终结符类型的)节点 直接短语: 同一父节点一步推出的所有叶子节点,即最末端的单一子树(不拼凑)的所有叶节点 句柄: 最左直接短语 素... -
编译原理:短语,简单短语,句柄,语法树
2016-09-23 18:22:37在文法和语言概念这里,比较难理解的是短语、简单短语,所以好好梳理一下。 先给出短语、简单短语的概念: ...句柄:任一句型的最左简单短语称为该句型的句柄,一个句型只有一个句柄。 所以,短语,简 -
编译原理:短语、直接短语、句柄
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... -
短语、直接短语、句柄、素短语、最左素短语
2019-06-21 15:33:45复习编译原理,理了一下几个基本概念的判断思路: 1. 根据句型画语法推导树。 2. 判断短语:短语是语法推导树中每一个非叶子节点作为根的子树,从左到右的叶子节点。注意:短语可以是非终结符。 3. 判断直接短语... -
编译原理素短语和直接短语
2020-03-20 00:45:31直接短语 找一个子树它的节点都没有子树 素短语 在短语里面找,有终止符的,终止符包括加减乘除,但是一个素短语不能包括其他素短语 -
编译原理:句型、句子、短语、直接短语、句柄、素短语、最左素短语
2020-04-24 18:25:30--句型与句子 如果 S⇒*α,α∈(VT∪VN)*,则称α是G的一个句型(sentential form) 一个句型中既可以包含终结符,又可以...如果S αAβ且Aγ,则称γ是句型αγβ的相对于非终结符A的短语 。 如果SαAβ 且...