有关句型、短语和句柄的问题.docx

《有关句型、短语和句柄的问题.docx》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、有关句型、短语和句柄的问题本文讲解如何找到一个文法的句型、短语和句柄的问题。因为这些概念在编译理论中会经常用，所以正确和熟练掌握它们是十分重要的。要求出一个文的这些成分，主要就是要根据定义来进行推算。1．句型的求法分析从定义中看出：1．计算句型必须从文法的开始符号进行推导，这是关键！2．定义中说“如果SÞ*a，…”，注意其中的“Þ*”。它表明由S可进行0步推导，也就是说SÞ*S也包含在内，所以S也是句型。3．同样，根据“如果SÞ*a，且aÎV*，…”可看出，由开始符号推导出的所有符号串都是句型，包

2、含句子（aÎVN*）在内。定义2.13（句型/句子）：设有文法G=（VN，VT，S，P），如果SÞ*a，且aÎV*（这里V=VNÈVT），则称a是文法G的一个句型。如果aÎVT*，则a称是文法G的一个句子。这样，我们就容易正确地计算出任何一个文法地句型了。例如，对于下述文法：S®aSd

3、aAdA®aAc

4、bcSÞ*SÞaSdÞaaSddÞaaaAdddÞaaabcddd,…SÞaAdÞaaAcdÞaabccd,…除去“S”以外，凡是由S推导出来的符号串都是句型。其中特别地，aaabcddd，aab

5、ccd，…等由终结符构成的符号串都是句子。2．短语求法分析请注意，定义中说：1．adb是必须是句型，即有SÞ*adb。2．另外，还要有AÞ+d，即有SÞ*aAbÞ+adb。（aAb也是个句型）3．有了以上的条件，于是d就是句型adb的（记住，而不是aAb的！）短语。4．如果还有A"d，即它是个产生式，则d就是句型adb的直接短语。定义2.16（短语）：设adb是文法G的一个句型，如果有AÞ+d，则称d是句型adb的关于非终结符A的一个短语，或简称d是adb的一个短语。特别地，当(A"d)ÎP时，d

6、称为句型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）aaa

7、bcddd的短语则有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等都不

8、是素短语，因它们都包含了其它素短语—红字串—作为其真子串。4．句柄求法定义2.17（句柄）：一个句型的最左直接短语称为该句型的句柄。在上面的例子中，几个直接短语都是相应句型的句柄，因为它们都是它们的最作直接短语。注意：一个句型的直接短语可能不止一个，但其最左直接短语则是唯一的。如对于书本上的文法G=({i,+,*,(,)},{E,T,F},E,P)，p={E®E+T

9、T,T®T*F

10、F,F®(E)

11、i}，有最左推导：EÞE+EÞE+E*EÞE+E*iÞE+i*iÞi+i*i其每步推导中的句柄有：i

12、，i，i，E*E，E+E等。