编译程序的组织 (7).ppt

《编译程序的组织 (7).ppt》由会员分享，可在线阅读，更多相关《编译程序的组织 (7).ppt（8页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、1例例:描述语句的产生式：描述语句的产生式：语句语句条件语句条件语句|赋值语句赋值语句|循环语句循环语句 描述一种简单赋值语句的产生式为：描述一种简单赋值语句的产生式为：赋值语句赋值语句i=E 描述条件语句的产生式：描述条件语句的产生式：if then(语句语句)|if then else 2.4 上下文无关文法及语法树上下文无关文法及语法树2文法文法G=（E，+，*，i，（，），（，），P，EP：E i E E+E E E*E E（E）这里的非终结符这里的非终结符E E表示一类算术表达式。表示一类算术表达式。i i表示程序设计表示程序设计语言中的语言中的“变量变量”，该文法定义了，该文法定义

2、了(描述了描述了)由变量，由变量，+，*,(和和)组成的算术表达式的语法结构。组成的算术表达式的语法结构。3语法树：上下文无关文法句型推导的图解过程语法树：上下文无关文法句型推导的图解过程 例：例：GS:SaASASbAASSSaAba句型句型aabbaaaabbaa的语法树（推导树）的语法树（推导树）Sa A SS b Aab aa41、每个结点都有一个、每个结点都有一个V中的符号作标记。中的符号作标记。2、根的标记是开始符号、根的标记是开始符号S。3、若一结点、若一结点n至少有一个它自己除外的子孙，并且至少有一个它自己除外的子孙，并且n有标有标记记A，则，则AVN。4、如果结点、如果结点A

3、的的k直接子孙，从左到右的次序是结点直接子孙，从左到右的次序是结点n1，n2，nk，其标记分别为，其标记分别为A1，A2，Ak，那么，那么AA1A2，Ak一定是一定是P中的一个产生式。中的一个产生式。给定文法给定文法G G，对于，对于G G的任何句型都能构造与之关联的语法的任何句型都能构造与之关联的语法树（推导树）。这棵树满足下列树（推导树）。这棵树满足下列4 4个条件：个条件：5推导过程中施用产生式的顺序推导过程中施用产生式的顺序例：例：GS:GS:SaASSaASASbAASbAASSASSSaSaAbaAba1）SaASaAaaSbAaaSbbaaaabbaa2）SaASaSbASaab

4、ASaabbaSaabbaa）SaASaSbASaSbAaaabAaaabbaaSa A SS b Aab aa最左推导最左推导最右推导最右推导最左（最右）推导：在推导的任何一步最左（最右）推导：在推导的任何一步，其中，其中、是句型，都是对是句型，都是对中的最左（右）非终结符进行替换。中的最左（右）非终结符进行替换。最右推导被称为规范推导。由规范推导所得的句型称为规范句型。最右推导被称为规范推导。由规范推导所得的句型称为规范句型。6句型句型 i*i+i i*i+i 的两个不同的最左推导：的两个不同的最左推导：例：例：GE:GE:E iE iE E+EE E+EE E*EE E*EE (E)E

5、(E)问题：一个句型是否对应唯一的一棵语法树？问题：一个句型是否对应唯一的一棵语法树？E EE +EE *EiiiE EE *EE +Eiii7文法的二义性文法的二义性若一个文法存在某个句子对应两棵不同的语法树，则若一个文法存在某个句子对应两棵不同的语法树，则称这个文法是二义的。称这个文法是二义的。或者，若一个文法存在某个句子有两个不同的最左或者，若一个文法存在某个句子有两个不同的最左（右）推导，则称这个文法是二义的。（右）推导，则称这个文法是二义的。8二义文法改造为无二义文法二义文法改造为无二义文法GE:E i GE:E T|E+T E E+ET F|T*F E E*EF(E)|i E(E)规定优先顺序和结合律规定优先顺序和结合律 假若规定了运算符假若规定了运算符+与与*的优先顺的优先顺序和结合规则，即按惯例，让序和结合规则，即按惯例，让*的优的优先性高于先性高于+，且它们都服从左结合，且它们都服从左结合，那么就可以构造出一个无二义文法那么就可以构造出一个无二义文法例：例：GE:E iE E+EE E*EE (E)