语法树的画法(根据文法求字符串)

语法树的画法(根据文法求字符串)语法树的画法 根据文法求字符串 语法树怎么画

大家好,欢迎来到IT知识分享网。

目录

1.语法树的画法

2.语法树的短语

3.直接短语(直接到根部)

4.素短语

5.句柄

6.算符优先分析句型


1.语法树的画法

文法G[E]:E->E+E | E*E | (E) | i ,字符串 i+i*i

推导方式有两种最左推导和最右推导(推导的技巧就是逐步靠近字符串的形式)

最左推导(从左往右替换):

E->E+E->i+E->i+E*E->i+i*E->i+i*i

最右推导(从右往左替换):

E->E+E->E+E*E->E+E*i->E+i*i->i+i*i

最右推导得出的语法树:

语法树的画法(根据文法求字符串)

也可以通过唯一的语法树,写出相应的最左推导和最右推导:

语法树的画法(根据文法求字符串)

最左推导(从左至右,从上到下):

S->ABS->aBS->aSBBS-> abbS ->abbAa->abbaa

S->ABS->ABAa->ABaa->ASBBaa->Abbaa->abbaa

文法的二义性:

一个文法的某个句子存在两棵不同的分析树,就可以称这个文法时二义的。或者,若一个文法的某个句子存在两个不同的最左(右)推导,则称这个文法是二义的。

注:文法二义不代表语言一定是二义的,只有当产生一个语言的所有文法都是二义时,这个语言才是二义的。

判断一个文法是二义性的

第一步:找一个句子

第二步:证明该句子是二义的

①可以写推导式,如果可以写出两种不同的推导式,就是具有二义性的。

②可以画分析树,这里的分析树,需要都是最左分析树/最右分析树,如果能画出两种不同的分析树,那么就是具有二义性的。

例1:

语法树的画法(根据文法求字符串)

①写推导式

•S->aSb->aSbb->abbb

•S->Sb->aSbb->abbb

②画分析树

语法树的画法(根据文法求字符串)

由于句子”abbb”的最左推导,存在两棵不一样的语法分析树,根据定义,该文法为二义性文法。

例2:

语法树的画法(根据文法求字符串)

语法树的画法(根据文法求字符串)

对于句子”aadbd”,最左推导有两棵不同的语法分析树,由定义得:该文法具有二义性。

2.语法树的短语

一个节点的最根部就是这个节点的短语,那么短语有几个呢,就看语法树中有分支的字符有几个,就有几个短语

语法树的画法(根据文法求字符串)

由上图分析,第一个节点(①)的短语是i+i*i        第二个节点的短语i*i            ③④⑤的短语为i

3.直接短语(直接到根部)

所以上面这棵语法树的直接短语就是i,例如这里的直接短语就是 S,a(注意”(“”)”不是直接短语)

语法树的画法(根据文法求字符串)

4.素短语

寻找素短语的前提是在短语中找,这些短语要满足以下条件

(1)至少包含一个终结符

(2)该短语不再包含满足第一个条件的更小的短语

由上面的语法树可以得到的语法为①i+i*i        ②i*i        ③i

①i+i*i,其中包含了满足第一个条件的②

②i*i,包含了满足第一个条件的③

所以素短语只有③

注:有些地方会提到最左素短语,最左素短语就是素短语中位于语法树最左的字符

5.句柄

最左最小的树对应的符号串,或者是直接短语中最左的符号串,在上面的语法树中,句柄就是i

例题1:

这里注意T+T也是素短语,因为他不包含满足第一个条件的短语

语法树的画法(根据文法求字符串)

例题2:

语法树的画法(根据文法求字符串)

例题3:

语法树的画法(根据文法求字符串)

语法树的画法(根据文法求字符串)

例题4:

语法树的画法(根据文法求字符串)

(1)10,0011,1100

语法树的画法(根据文法求字符串)

(2)S–>1A–>11AA–>11A0S

(3)语法树如下:

语法树的画法(根据文法求字符串)

消除左递归和消除回溯(这一部分比较难,还是要多做题感受下)

消除左递归:

语法树的画法(根据文法求字符串)

例题1:

E–>E+T|T:

① 将T提前,其他改写为文法E’:E->TE’

②剩下的写下来,”|”右边的T由于已经被提出来所以变为\varepsilon(空串):E’—>+TE’|\varepsilon

T–>T*F|F:

①T—>FT’

②*FT’|\varepsilon

F–>(E)|i:不符合左递归的形式,所以照搬即可

例题2:

语法树的画法(根据文法求字符串)

消除回溯:

语法树的画法(根据文法求字符串)

例题1:G[A] = A->aAB|a|b

①:将公共左因子”a”提走,另一部分改写为A’,没有公共左因子的照抄:A–>aA’|b

②:将改造后的文法A’补齐:A’–>AB|\varepsilon

例题2:

语法树的画法(根据文法求字符串)

语法树的画法(根据文法求字符串)

6.算符优先分析句型

若有句型…N_{i}a_{i}N_{j}a_{j}N_{j+1}….,当a_{i}...N_{j}a_{j}属于句柄时,则 N_{i} 和N_{j+1}也在句柄中,这是由于算符文法的任何句型中均无两个相邻的非终结符,且终结符和非终结符相邻时,含终结符的句柄必含相邻的非终结符,句柄终结符之间的关系如下:

语法树的画法(根据文法求字符串)

例题:
 语法树的画法(根据文法求字符串)

第一步:需要将算符优先分析表得出来

语法树的画法(根据文法求字符串)

这可以看:算符优先分析的方法

第二步:进行算符优先分析

①默认的#是小于当前输入符号(a)的,所以动作为移入

②接下来继续看栈顶的终结符(a),#<a且a>;所以a就形成了句柄

③对句柄进行归约

语法树的画法(根据文法求字符串)

由式子可以看到:H->a|(S),可以看到句柄a可以归约为H,但是由于这里是算符优先级分析, 只考虑终结符,所以写任何非终结符是没有关系的,所以这里也可以写T

由于栈中最顶层的终结符为#,又因为#<;所以继续移进

语法树的画法(根据文法求字符串)

接下来继续下一步的操作:

这里最顶层的终结符a满足,a>+,且”(”< “a”,所以a是这个整个语句的句柄,继续归约为T

语法树的画法(根据文法求字符串)

继续下一步操作:

语法树的画法(根据文法求字符串)

此时最顶层的终结符为+,因为“(”<“+”,且“+” > “)”,所以+为句柄,又因为,两端有两个非终结符,也在句柄中,所以由T–>T+S|S ,形似T+S,将“T+T”归约为T

语法树的画法(根据文法求字符串)

由于“(“=”)“,且“;” < “(” ,所以这里的”(“是句柄,由于公式中含有H->G|(S),所以我们可以将其归约为H,但是这里非终结符是什么没有关系,所以统一归结为T

语法树的画法(根据文法求字符串)

由于式子中包含S–>S;G|G,这里还是可以归约为S,但是同理我们归约为非终结符T也没有影响

语法树的画法(根据文法求字符串)

所以可得结论:a;(a+a)G[S]文法中推出来的

但是这里我们注意:a;(a+a)的最右推导,无法推导出a;(a+a),所以a;(a+a)不是G[S]文法的句子

语法树的画法(根据文法求字符串)

这与算符优先分析中的结论矛盾了,但是最右推导属于规范推导,正确答案是: (不是)

所以算符优先分析可能会错误地接受非法的句子,其推导的过程不规范。

免责声明:本站所有文章内容,图片,视频等均是来源于用户投稿和互联网及文摘转载整编而成,不代表本站观点,不承担相关法律责任。其著作权各归其原作者或其出版社所有。如发现本站有涉嫌抄袭侵权/违法违规的内容,侵犯到您的权益,请在线联系站长,一经查实,本站将立刻删除。 本文来自网络,若有侵权,请联系删除,如若转载,请注明出处:https://haidsoft.com/125631.html

(0)
上一篇 2025-09-25 16:33
下一篇 2025-09-25 16:45

相关推荐

发表回复

您的邮箱地址不会被公开。 必填项已用 * 标注

关注微信