211上下文无关文法 文法:描述语言的语法结构的形式规 则 aHe gave me a book. <句子〉→<主语〉谓语入<间接宾语×<直接宾语〉 <主语 <代词 <谓语〉→<动词 间接宾语〉 代词 直接宾语>→<冠词><名词 <代词>→He|me <名词 book <冠词 动词〉→gave
2.1.1 上下文无关文法 ◼文法： 描述语言的语法结构的形式规 则 ◼He gave me a book. <句子> → <主语><谓语><间接宾语><直接宾语> <主语> → <代词> <谓语> → <动词> <间接宾语> → <代词> <直接宾语> → <冠词> <名词> <代词> → He|me <名词> → book <冠词> → a <动词> → gave
<句子><主语><谓语><间接宾语><直接宾语> <代词><谓语><间接宾语><直接宾语> He<谓语><间接宾语><直接宾语> He<动词><间接宾语><直接宾语> He gave<间接宾语>直接宾语> He gave<代词><直接宾语> He gave me<直接宾语> He gave me<冠词><名词> He gave me a<名词> He gave me a book
<句子> <主语><谓语><间接宾语><直接宾语> <代词><谓语><间接宾语><直接宾语> He <谓语><间接宾语><直接宾语> He <动词><间接宾语><直接宾语> He gave <间接宾语><直接宾语> He gave <代词><直接宾语> He gave me <直接宾语> He gave me <冠词><名词> He gave me a <名词> He gave me a book
上下文无关文法 定义: 个上下文无关文法G是一个四元式(Vr,V,S,P),其中 V是一个非空有限集,它的每个元素称为终结符号; V是一个非空有限集,它的每个元素称为非终结符号, Vr∩vx=中 S是一个非终结符号,称为开始符号; P是一个有限的产生式集合,每个产生式的形式是A→a, 其中,A∈V,a∈(VrUV)*; 开始符号S至少必须在某个产生式的左部出现一次
定义： 一个上下文无关文法G是一个四元式（VT，VN，S，P），其中 VT是一个非空有限集，它的每个元素称为终结符号； VN是一个非空有限集，它的每个元素称为非终结符号， VT∩VN＝； S是一个非终结符号，称为开始符号； P是一个有限的产生式集合，每个产生式的形式是A→， 其中，A∈VN， ∈（VT∪VN）* ； 开始符号S至少必须在某个产生式的左部出现一次。 上下文无关文法
上下文无关文法的产生式 例c语言的if-else语句的格式为 if(expression) statement else statement 用exp表示 expression,stmt表示 statement 则这个语句的构成规则可以表示为 Stmt->if(expr)stmt else stmt ”读作“定义为”;这样的规则称为产生式
上下文无关文法的产生式 例:c语言的if-else语句的格式为: if(expression) statement else statement 用expr表示expression,stmt表示statement 则这个语句的构成规则可以表示为: Stmt->if (expr) stmt else stmt “->”读作“定义为”;这样的规则称为产生式
program→ stmf-sequence stmt-sequence- stmt-sequence i statement I statement statement+if-stmt repeat-stmt assign-stmt read-stmtwrite-stmt m→1 ep then m-sequence en if exp then stmur-sequence else stmt-sequence end repeat-stn→z0p· at stmt-sequence unt1卹p assign-stmt- identifier t=exp read-stmt-readidantifiar write.stm→ write er exp+ simple-exp comparison- op simuple-exp simple-exp compartson-op→<| simple-exp- simple-exp addo term term dlop→+ m→ term mulop factor factor factor+(erp) aumber identifier