上下文无关文法 ·一个上下文无关文法 (CFG)包含四个部分 终结符号：组成串的基本符号（词法单元名字） 非终结符号：表示串的集合的语法变量 。 在程序设计语言中通常对应于某个程序构造，比如stmt(语句) 开始符号：某个被指定的非终结符号 它对应的串的集合就是文法的语言 产生式：描述将终结符号和非终结符号组成串的方法 形式：头（左）部今体（右）部 头部是一个非终结符号，右部是一个符号串 例子：expression→expression+term 6
上下文无关文法 • 一个上下文无关文法 (CFG) 包含四个部分 – 终结符号：组成串的基本符号 (词法单元名字) – 非终结符号：表示串的集合的语法变量 • 在程序设计语言中通常对应于某个程序构造，比如stmt (语句) – 开始符号：某个被指定的非终结符号 • 它对应的串的集合就是文法的语言 – 产生式：描述将终结符号和非终结符号组成串的方法 • 形式：头 (左) 部 → 体 (右) 部 • 头部是一个非终结符号，右部是一个符号串 • 例子：expression → expression + term 6 南大编译许畅
上下文无关文法的例子 ·简单算术表达式的文法 终结符号：id,+,-,*,/,() 非终结符号：expressic0n,term,factor 开始符号：expression 产生式集合 expression>expression +term expression expression-term expression→term term→term*factor term→term/factor term→factor factor→(expression) factor→id 7
上下文无关文法的例子 • 简单算术表达式的文法 – 终结符号：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 7 南大编译许畅
文法简单形式的例子 E→E+TIE-TIT T→T*FIT/FIF F→(E)Iid 译许 ·注意 是元符号（即文法描述中的符号，而不是文法符号） 这里的（和）不是元符号 9
文法简单形式的例子 E → E + T | E – T | T T → T * F | T / F | F F → ( E ) | id • 注意 – |是元符号 (即文法描述中的符号，而不是文法符号) – 这里的 ( 和 ) 不是元符号 9 南大编译许畅
推导(1) ·推导 将待处理的串中的某个非终结符号替换为这个非终结 符号的某个产生式的体 从开始符号出发，不断进行上面的替换，就可以得到 文法的不同句型 例子 文法：E→-EIE+EIE*EI(E)Iid 推导序列：E=>-E=>-（E)=>-（id) 10
推导 (1) • 推导 – 将待处理的串中的某个非终结符号替换为这个非终结 符号的某个产生式的体 – 从开始符号出发，不断进行上面的替换，就可以得到 文法的不同句型 • 例子 – 文法：E → – E | E + E | E * E | ( E ) | id – 推导序列：E => – E => – ( E ) => – ( id ) 10 南大编译许畅
推导(2) ·推导的正式定义 如果A→Y是一个产生式，那么xAB=>yB 最左（右）推导：（β）中不包含非终结符号 。 符号：言>盖> rm 经过零步或者多步推导出：> 对于任何串x±x 如果x±>阝且阝=>Y,那么x>y 。经过一步或者多步推导出：〧 -xB即x>B且不等于B(不严格) 11
推导 (2) • 推导的正式定义 – 如果A → γ是一个产生式，那么αAβ => αγβ – 最左 (右) 推导：α(β) 中不包含非终结符号 • 符号： • 经过零步或者多步推导出： – 对于任何串α α – 如果α β且β => γ，那么α γ • 经过一步或者多步推导出： – α β即α β且α不等于β (不严格) 11 南大编译许畅