高级语言及其文法

高级语言及其文法内容摘要：

的一个出现。 β∈( Ｖ T∪ Ｖ N)*。 α 称为产生式 α → β的 左部 (Left Part)， β 称为产生式 α → β 的 右部(Right Part)。 产生式定义各个语法成分的结构 （ 组成规则 ） 例 21 算术表达式的文法  递归定义 —— 中缀表示  标识符 (id)（ 常数、变量）是表达式 (E)；  表达式加一个表达式是表达式；  表达式减一个表达式是表达式；  表达式乘一个表达式是表达式；  表达式除一个表达式是表达式；  表达式加上括号后是表达式； 例 21 算术表达式的文法  考虑简单算术表达式组成的语言  G =({id， +， *， (， )}， {E}， P， E)  P: E→E + E  E→E * E  E→( E )  E→id  约定：只写产生式  简写  E → E + E | E * E | ( E ) | id （ ） 产生式的简写 对一组有相同左部的产生式 α→β 1， α→β 2… ， α→β n 可以简单地记为： α→β 1|β 2|… |β n 读作： α 定义为或者 β 1， 或者 β 2， … ，或者 β n。 并且称它们为 α 产生式。 β 1，β 2， … ， β n称为 候选式 (Candidate)。 基于产生式的变换 推导或归约  E → E + E | E * E | ( E ) | id  E由第一个候选式可以变成 E+E  E+E中的第一个 E由第二个候选式可以变成 E*E， 从而 E+E变成 E*E+E  根据第 4个候选式， E*E+E中的 E都可以变成 id:  E*E+E 变成 id*E+E  id*E+E变成 id*E+id  id*E+id变成 id*id+id  也就是说，根据第 4个候选式， E*E+E经 3步变换变成 id*id+id 直接推导与归约  根据产生式对符号串进行变换的过程  Ａ → γ 是文法Ｇ的一个产生式，  且 α 、 β∈ （ Ｖ T∪ Ｖ N） *，  称 α Ａ β 直接推导 /派生 (Derive)出 αγβ ，也称 αγβ 直接归约 (Reduce)为 α Ａ β。  记为 α Ａ β αγβ  例：  id + Eid + E * E （多步）推导  α 0α 1α 2 … α n  记为 α 0n α n (恰用 n步 )  α 0+ α n （ 至少一步）  α 0* α n （ 若干步 :零步或多步） 推导 /归约举例 E  E + E （ 1） 串中含有变量   id + E （ 4） 串中含有变量   id + E * E （ 2） 串中含有变量   id + id * E （ 4） 串中含有变量   id + id * id （ 4） 串中没有变量  到此串中已经没有（语法）变量了，不能再推导了  E→E + E  E→E * E  E→( E )  E→id 句型与句子  E 5 id + id * id  句子 :如果 S * x， 且 x∈ Ｖ T* ， 则称 x是G产生的一个 句子 (Sentence)  E  E + E E + E * E  E 4 id + id * E  句型 :如果 S*α ， α∈( Ｖ T∪ Ｖ N)*则称 α是 G产生的一个 句型 (Sentential Form) 文法 G产生的语言 Ｌ (Ｇ )＝ {x｜ Ｓ * x and x∈ Ｖ T*} 文法 E→E+E|E*E|(E)|id 可以派生出多少个句子。 文法 G的作用 —— 语言的有穷描述 以有限的规则描述无限的语言现象 有限： 产生式集合、终结符集合、非终结符集合 无限： 可以导出无穷多个句子（ L也可是有穷） id+id*id的不同推导 E→E+E|E*E|(E)|id E  E+E  id+E  id+E*E  id+id*E  id+id*id E  E+E  E+E*E  E+E*id  E+id*id  id+id*id E  E*E  E+E*E  E+id*E  id+id*E  id+id*id 不做限制 句型 (sentential Form) （ 归约） E * id+id*id 施于最 右 变量 右句型 /规范句型 (canonical ~) (最左 /规范归约 ) E + id+id*id 施于最 左 变量 左句型 (left~) （ 最右归约） E5 id+id*id 最左推导与最右推导 最左推导 (Leftmost Derivation) 每次推导都施加在句型的最左边的语法变量上。 —— 与最右归约对应 最右推导 (Rightmost Derivation) 每次推导都施加在句型的最右边的语法变量上。 —— 与最左归约（规范规约）对应的规范 (Canonical)句型 短语 (Phrase) 什么叫短语。  如果 Ｓ * α Ａ β and A +γ ， 则称 γ是句型 αγβ 的相对于变量 A的短语  如果 Ｓ * α Ａ β and A γ ， 则称 γ是句型 αγβ 的相对于变量 A的直接短语 最左直接短语叫做句柄 (Handle) 例： (直接 )短语 EE+T T+T F+T (E)+T (E+T)+T (E+T)+T (T+T)+T (F+T)+T (id+T)+T (a+T*F)+T (a+F*F)+T (a+b*F)+T (a+b*c)+T (a+b*c)+F (a+b*c)+d E→E+T|T T→T* F|F F→( E )| id 句柄 (Handle)： 最左直接短语 E→E+T|T T→T* F|F F→( E )| id EE+T T+T F+T (E)+T。