语言的定义(句型,句子) 对于文法G[Z],x称为G的一个句型如果: Z=>*x 识别符号是最简单的句型 G[Z的一个句型x被称为句子,如果: ⅹ∈YT 也就是说句子是全部由终结符号组成的 句型
语言的定义（句型,句子） • 对于文法G[Z]，x称为G的一个句型如果： Z =>* x 识别符号是最简单的句型。 • G[Z]的一个句型x被称为句子，如果： xVT * 也就是说句子是全部由终结符号组成的 句型
语言的定义(短语,简单短语) 短语:对于文法G[Z,如果Z→>*xUy, U>+u。显然,wxuy是一个句型。我 们称u是句型中相对孔U的短语。 简单短语:在上面的定义中,如果U∷= u是G的一个规则,那么,u是句型中相 矿孔U的简单短语。 例子:P2页例213
语言的定义（短语，简单短语） • 短语：对于文法G[Z]，如果Z =>* xUy， U=>+ u。显然，w=xuy是一个句型。我 们称u是句型w中相对于U的短语。 • 简单短语：在上面的定义中，如果U ::= u是G的一个规则，那么，u是句型w中相 对于U的简单短语。 • 例子：P22页例2.13
语言的定义(短语,句柄) 注意:在寻找一个句型的短语(或简单 短语)时,必须要求将这个短语规约为 相应的非终结符号后所得到的符号串仍 然是句型 句柄:一个句型的最左简单短语称为该 句型的句柄 定义句柄的原因:在自底向上识别 符号串时,总是规约这个句柄
语言的定义（短语，句柄） • 注意：在寻找一个句型的短语（或简单 短语）时，必须要求将这个短语规约为 相应的非终结符号后所得到的符号串仍 然是句型。 • 句柄：一个句型的最左简单短语称为该 句型的句柄。 • 定义句柄的原因：在自底向上识别一个 符号串时，总是规约这个句柄
语言的定义(文法的语言) 文法的语言:一个文法GZ的语言,用 L(G[Z])表示,定义如下 L(G[Z])={X|Z→>*x并且x∈Vr+} 一个文法的语言就是该文法的所有的句 子的集合。 文法的语言是所有终结符号串所组成的 集合的子集,一般是真子集
语言的定义（文法的语言） • 文法的语言：一个文法G[Z]的语言，用 L(G[Z])表示，定义如下： L(G[Z]) = {x | Z=>* x 并且 x VT +} • 一个文法的语言就是该文法的所有的句 子的集合。 • 文法的语言是所有终结符号串所组成的 集合的子集，一般是真子集
语言的定义(递归与语言) 递归的规则:U∷=.U 左右递归规则:U∷=U.;U 文法的递归:U=+..U.,称文法递归 于U。 文法的左右递归: 如果文法是非递归的,那么其语言是有 穷的
语言的定义（递归与语言） • 递归的规则：U ::= …U… • 左右递归规则：U ::= U…；U ::= …U • 文法的递归：U =>+ …U…，称文法递归 于U。 • 文法的左右递归： • 如果文法是非递归的，那么其语言是有 穷的