加载中…
个人资料
  • 博客等级:
  • 博客积分:
  • 博客访问:
  • 关注人气:
  • 获赠金笔:0支
  • 赠出金笔:0支
  • 荣誉徽章:
正文 字体大小:

句型、短语、直接短语和句柄

(2012-10-07 17:20:04)
标签:

杂谈

分类: 算法和C /C

 

本文讲解如何找到一个文法的句型、短语和句柄的问题。因为这些概念在编译理论中会经常用,所以正确和熟练掌握它们是十分重要的。要求出一个文的这些成分,主要就是要根据定义来进行推算。

1.句型的求法

文本框: 分析 从定义中看出: 1.计算句型必须从文法的开始符号进行推导,这是关键! 2.定义中说“如果S Þ* a,…”,注意其中的“Þ*”。它表明由S可进行0步推导,也就是说SÞ*S也包含在内,所以S也是句型。 3.同样,根据“如果S Þ* a,且a Î V*,…”可看出,由开始符号推导出的所有符号串都是句型,包含句子(a Î VN*)在内。 定义2.13(句型/句子)设有文法G =VNVTSP),如果S Þ* a,且a Î V*(这里V= VN ÈVT),则称a是文法G的一个句型。如果 a Î VT*,则a称是文法G的一个句子

这样,我们就容易正确地计算出任何一个文法地句型了。例如,对于下述文法:

S®aSd|aAd

      A®aAc|bc

SÞ*SÞaSdÞaaSddÞaaaAdddÞaaabcddd, …

SÞaAdÞaaAcdÞaabccd, …

除去“S”以外,凡是由S推导出来的符号串都是句型。其中特别地,aaabcdddaabccd等由终结符构成的符号串都是句子

2.短语求法

文本框: 分析 请注意,定义中说: 1.adb是必须是句型,即有S Þ* adb。 2.另外,还要有A Þ+ d,即有S Þ* aAb Þ+adb。(aAb也是个句型) 3.有了以上的条件,于是 d 就是句型 adb 的(记住,而不是aAb的!)短语。 4.如果还有A定义2.16(短语)adb是文法G的一个句型,如果有A Þ+ d,则称d是句型adb的关于非终结符A的一个短语,或简称dadb的一个短语。特别地,当(A"d) Î P时,d称为句型adb的一个直接短语简单短语

[例子] 例如,在SÞ*SÞaSdÞaaSddÞaaaAdddÞaaabcddd中:

1aSd是其自己的短语:因有SÞ*SÞaSd,且是直接短语(S®aSd);

2aSdaaSdd的短语,因有SÞ*aSdÞaaSdd,且是直接短语(S®aSd);

3aaAdd是句型aaaAddd(关于aSd)的短语,因有SÞ*SÞaSdÞ+aaaAddd;但aAd却是句型aaaAddd(关于aaSdd)的直接短语。因有SÞ*aaSddÞaaaAdddS®aAd

4aaabcddd的短语则有3个:即aabcdd(关于aSd的),abcd(关于aaSdd的),bc(关于aaaAddd的)且是直接短语(因有A®bc)。

当然,在SÞ*SÞaSdÞaaSddÞaaaAdddÞaaabcddd中还能找到其它的短语。

3素短语求法

定义2.18(素短语)含有终结符的短语,如果其中可能包含的短语中不再有素短语作为其真子串,则该含有终结符的短语就称为素短语

在上述例子中,素短语aSdaAdbc等,因它们符合定义2.18。其余的短语,如aaAddaabcddabcd等都不是素短语,因它们都包含了其它素短语—红字串—作为其真子串。

4.句柄求法

定义2.17(句柄)一个句型的最左直接短语称为该句型的句柄

在上面的例子中,几个直接短语都是相应句型的句柄,因为它们都是它们的最作直接短语。

注意:一个句型的直接短语可能不止一个,但其最左直接短语则是唯一的。如对于书本上的文法G=({i, +, *, (, )}, {E, T, F}, E, P)p={E®E+T|T, T®T*F|F, F®(E)|i},有最左推导:

EÞE+EÞE+E*EÞE+E*iÞE+i*iÞi+i*i

0

阅读 收藏 喜欢 打印举报/Report
前一篇:文法的分类
后一篇:2012年10月07日
  

新浪BLOG意见反馈留言板 欢迎批评指正

新浪简介 | About Sina | 广告服务 | 联系我们 | 招聘信息 | 网站律师 | SINA English | 产品答疑

新浪公司 版权所有