编译原理chapter2new.ppt

子树：由语法树的某个结点(子树的根)连同它下面射出 的部分组成语法树的子树。只含有单层分支的子树为简 单子树或直接子树。 E E T + T * F F i 子树与短语：在句型所对应的 语法树中，若某些符号按从左 到右的顺序组成某棵子树的末 端结点，那么由这些末端结点 所组成的符号串是相对于子树 根结点的短语。 原则上语法树有多少棵子树，就有多少个短语。 练习：文法G[S]: S →aAcBe A →b | Ab B →d 求句型abbcde的短语，直接短语和句柄。 S a A c B e A b b d b是句型abbcde相对于A的短语 bb是句型abbcde相对于A的短语 d是句型abbcde相对于B的短语 abbcde是句型abbcde相对于S的短语 b是句型abbcde相对于A的直接短语 d是句型abbcde相对于B的直接短语 b是句柄 文法的二义性：若一个文法存在某个句子对应两棵不同 的语法树，则称此文法是二义性文法。 例： 文法G[E] : E→E+E | E*E | (E) | i 试为符号串E*E+i构造语法树. E E E + E E * i E E E * E E + i 先乘后加 先加后乘 文法是二义性的。在进行语法分析时通过人工干预(规定算符的优先级)，确定归约(分析)顺序。 2.5 文法的分类 按照文法中产生式的不同情况，Chomsky把文法分成 四种类型，四种类型的文法对应着四种类型的语言。 0型文法：产生式形式为: u →v 且 u?V+ , v ? V*,u中 应至少含有一个非终结符号，这种文法又叫短语文法， 它所确定的语言称为0型语言。 1型文法: 产生式形式为 xUy →xuy,且 U?VN,u?V+, x,y ? V* ,则称该文法为1型文法，也称为上下文敏感 文法或上下文有关文法。 即只有在U的左部为符号串x而右部为符号串y时， 才允许把非终结符U用符号串u来代替，即U必须 在上下文x…y中才行。这种文法所对应的语言为 1型语言。 2型文法: 产生式形式为U →u,且 U?VN,u?V*,则称该文 法为2型文法，也称为上下文无关文法。2型文法所确定 的语言为2型语言，大部分程序设计语言都是2型语言。 3型文法: 产生式形式为 U→xV | y 或U→Vx | y,且 U,V∈VN，x,y∈VT+ ,则称该文法为3型文法，也称线性 文法、正则文法或正规文法。这种文法所对应的语言称 为3型语言(正则语言、正规语言)，大多数程序设计语言 的单词 (标识符、无符号整数) 的文法都是3型文法。 从0型文法到3型文法是逐渐增加限制的，而它们 所确定的语言是逐步缩小的。 2.6 有关文法的使用限制 1.不能有形如： U →U的产生式； 2.不能有多余产生式，多余产生式可以从文法中删掉， 所谓多余产生式有这样的特点： (1)在推导文法的所有句子时，始终都用不到的产生式； (2)在推导过程中，一旦使用此产生式，将无法推出任 何句子的的产生式； 例：有文法G[z]: Z →Be A →Ae | e B → Ce | Af C → Cf D → f Z →BeA →Ae | eB →Af 2.7 扩充的巴科斯范式(EBNF)表示 1. 产生式的花括号表示法 m n t } { 表示符号串t可重复出现n次到m次(nm)，一般约定n=0; 例：若有产生式 S→xS│x,其中：S∈VN,x∈VT , 则可用花括号表示为： S→x{x} 2. 产生式的方括号表示法 [t] 表示符号串t为可选项，即可出现0次或1次： 例：设有产生式T→T*F│F, 可用方括号表示成： T→ [ T*]F 例：条件语句 → if 条件 then 语句 [else 语句] 3. 使用圆括号( )——提取候选式的公用因子 例：若有产生式 A→xW1y│xW2y│┄│xWny 则可表示成： A→x(W1│W2│ ┄│Wn )y 例：S→if B then s│if B then S else S 提取左公因子，可写成： S→if B then S (ε│else S) 作业：P35 . 1-C、Java ，6，7 ，8，9，11 编 译 原 理