《编译技术编译原理 (14).pdf》由会员分享,可在线阅读,更多相关《编译技术编译原理 (14).pdf(15页珍藏版)》请在得力文库 - 分享文档赚钱的网站上搜索。
1、编译技术语 法 分 析本讲纲要上下文无关文法定义推导分析树二义性上下文无关文法定义文法推导二义性给出上下文无关文法的概念定义本讲纲要正规式来定义一些简单的语言,能表示给定结构的固定次数的重复或者没有指定次数的重复。例:a(ba)5,a(ba)*正规式不能用于描述配对或嵌套的结构例:配对括号串的集合,wcw|w 是a 和b 的串上下文无关文法的定义上下文无关文法是四元组(VT,VN,S,P)VT:终结符集合(非空有限集合,记号名是其同义词)VN:非终结符集合(非空有限集合,)S:开始符号P:产生式集合,产生式形式:A 上下文无关文法的定义*,()NTNAVVVTNVV=(id,+,*,(,),e
2、xpr,op,expr,P)exprexpr op exprexpr(expr)expr exprexpr idop+op*上下文无关文法示例(id,+,*,(,),expr,op,expr,P)exprexpr op exprexpr(expr)expr exprexpr idop+op*上下文无关文法示例(id,+,*,(,),expr,op,expr,P)exprexpr op exprexpr(expr)expr exprexpr idop+op*上下文无关文法示例同一个符号可以在多个产生式中出现每个产生式之间没有强制的顺序关系,这与正规式不同(id,+,*,(,),expr,op,e
3、xpr,P)exprexpr op exprexpr(expr)expr exprexpr idop+op*上下文无关文法示例终结符终结符的简化表示1)字母表中前面的小写字母,如a,b,c2)黑体串,如id或while3)数字 0,1,94)标点符号,如括号,逗号等5)运算符号,如+,-等上下文无关文法简化表示非终结符的简化表示1)字母表中前面的大写字母,如A,B,C2)字母S,通常它表示开始符号3)小写字母的名字,如expr和stmt上下文无关文法简化表示其它的简化表示1)字母表中后面的大写字母,如X,Y等,表示非终结符或终结符2)字母表中后面的小写字母,如u,v,.z,代表终结符串3)小写希腊字母,代表文法的符号串4)如果 A a1,A a2,记为 A a1|a2上下文无关文法简化表示(id,+,*,(,),expr,op,expr,P)exprexpr op exprexpr(expr)expr exprexpr idop+op*简化表示EE A E|(E)|E|idA+|*上下文无关文法上下文无关文法与正规式比较上下文无关文法EE A E|(E)|E|idA+|*正规式定义letter A-Za-zdigit 0-9id letter(letter|digit)*谢 谢!