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

标签:
杂谈 |
分类: 算法和C /C |
本文讲解如何找到一个文法的句型、短语和句柄的问题。因为这些概念在编译理论中会经常用,所以正确和熟练掌握它们是十分重要的。要求出一个文的这些成分,主要就是要根据定义来进行推算。
1.句型的求法
定义2.13(句型/句子):设有文法G
=(VN,VT,S,P),如果S Þ*
a,且a Î V*(这里V=
VN ÈVT),则称a是文法G的一个句型。如果
a Î VT*,则a称是文法G的一个句子。
这样,我们就容易正确地计算出任何一个文法地句型了。例如,对于下述文法:
S®aSd|aAd
SÞ*SÞaSdÞaaSddÞaaaAdddÞaaabcddd, …
SÞaAdÞaaAcdÞaabccd, …
除去“S”以外,凡是由S推导出来的符号串都是句型。其中特别地,aaabcddd,aabccd,…等由终结符构成的符号串都是句子。
2.短语求法
定义2.16(短语):设adb是文法G的一个句型,如果有A Þ+ d,则称d是句型adb的关于非终结符A的一个短语,或简称d是adb的一个短语。特别地,当(A"d)
Î P时,d称为句型adb的一个直接短语或简单短语。
[例子] 例如,在SÞ*SÞaSdÞaaSddÞaaaAdddÞaaabcddd中:
1)aSd是其自己的短语:因有SÞ*SÞaSd,且是直接短语(S®aSd);
2)aSd是aaSdd的短语,因有SÞ*aSdÞaaSdd,且是直接短语(S®aSd);
3)aaAdd是句型aaaAddd(关于aSd)的短语,因有SÞ*SÞaSdÞ+aaaAddd;但aAd却是句型aaaAddd(关于aaSdd)的直接短语。因有SÞ*aaSddÞaaaAddd和S®aAd。
4)aaabcddd的短语则有3个:即aabcdd(关于aSd的),abcd(关于aaSdd的),bc(关于aaaAddd的)且是直接短语(因有A®bc)。
当然,在SÞ*SÞaSdÞaaSddÞaaaAdddÞaaabcddd中还能找到其它的短语。
3.素短语求法
定义2.18(素短语):含有终结符的短语,如果其中可能包含的短语中不再有素短语作为其真子串,则该含有终结符的短语就称为素短语。
在上述例子中,素短语有aSd,aAd和bc等,因它们符合定义2.18。其余的短语,如aaAdd、aabcdd、abcd等都不是素短语,因它们都包含了其它素短语—红字串—作为其真子串。
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