上下文无关文法的例子 简单算术表达式的文法: 终结诗号:id+-*/() 非终结符号: expression,term, factor 开始符号: expression 生式集合 expression expression term expression expression -term expression term tem→term* factor term→term/ factor tem→ factor factor >(expression) factor→id
上下文无关文法的例子 • 简单算术表达式的文法： – 终结符号：id + - * / ( ) – 非终结符号：expression, term, factor – 开始符号：expression – 产生式集合： expression → expression + term expression → expression – term expression → term term → term * factor term → term / factor term → factor factor → (expression) factor → id
文法书写的约定 终结符号 靠前的小写字母(a2b,);运算符号(+*);标点符号;数 位;黑体字符串(id,if, while ·非终结符号 靠前的大小字母(AB,C);字母S(通常是开始符号); 小写斜体字母;表示程序枃造的大写字母 X,Y,Z文法符号(终结苻号或非终结符号) 小写希腊字母表示文法符号串(,B,y) ·靠后的小写字母表示终结符号串 具有相同头的产生式可以合并成A→a1|02….an的 形式 通常第一个产生式的左部就是开始苻号
文法书写的约定 • 终结符号 – 靠前的小写字母(a,b,c)；运算符号(+ *)；标点符号；数 位；黑体字符串(id, if, while) • 非终结符号 – 靠前的大小字母(A,B,C)；字母S（通常是开始符号）； 小写斜体字母；表示程序构造的大写字母 • X,Y,Z文法符号（终结符号或非终结符号） • 小写希腊字母表示文法符号串(α, β, γ) • 靠后的小写字母表示终结符号串 • 具有相同头的产生式可以合并成A→ α1 | α2 | … | αn的 形式 • 通常第一个产生式的左部就是开始符号
文法简单形式的例子 E→E+T|E-T|T T>T*FIT/FF F→(E)id 注意 是元符号(即文法描述方式中的符号,而不是 文法符号) 这里()不是元符号;在有些地方会把(看作元 子号
文法简单形式的例子 E → E + T | E – T | T T → T * F | T / F | F F → ( E ) | id • 注意: – | 是元符号（即文法描述方式中的符号，而不是 文法符号） – 这里(,)不是元符号；在有些地方会把( )看作元 符号
推导(1) 推导 一将待处理的串中的某个非终结脊号替换为这个 非终结符号的某个产生式的体 从开始号出发,不断进行上面的替换.就可 以得到文法的不同句型 ·例子 文法:E→|E+E|E*E|(E)|id 推导序列:E→>→>(E)=>-(id)
推导（1） • 推导： – 将待处理的串中的某个非终结符号替换为这个 非终结符号的某个产生式的体。 – 从开始符号出发，不断进行上面的替换，就可 以得到文法的不同句型 • 例子 – 文法: E → -E | E+E | E*E | (E) | id – 推导序列：E => -E => -(E) => -(id)
推导(2) 推导的正式定义 如果A+y是一个产生式,那么AB=>YB 最左(右)推导:0(β)中不包含非终结符号 符号:需 经过零步或者多步推导出: 对于任何串Q=Q 如果β且β 那么0=y 经过一步或者多步推导出: 0→>β等价于>阝且不等于β
推导（2） • 推导的正式定义 – 如果A→γ是一个产生式，那么αAβ => αγβ – 最左(右)推导：α(β)中不包含非终结符号 • 符号： • 经过零步或者多步推导出： – 对于任何串α α – 如果α β且β=>γ，那么α γ • 经过一步或者多步推导出： – α β等价于α β且α不等于β