文法及其生成的语言 语言是从文法的开始符号出发，能推导得到的所 有句子的集合 文法G:S→aS I al b,L(G)={a(alb),i>=0} 文法G:S→aSb|ab,L(G)={ab",n>=1} 文法G:S→(S)SIε，L(G)={所有具有对称括号对的 串} 如何验证文法G所确定的语言L 证明G生成的每个串都在L中 证明L中的每个串都能被G生成 23
文法及其生成的语言 • 语言是从文法的开始符号出发，能推导得到的所 有句子的集合 – 文法G：S → aS | a | b，L(G) = { a i (a|b), i >= 0 } – 文法G：S → aSb | ab，L(G) = { a nb n , n >= 1 } – 文法G：S → (S)S | ε，L(G) = { 所有具有对称括号对的 串 } • 如何验证文法G所确定的语言L – 证明G生成的每个串都在L中 – 证明L中的每个串都能被G生成 23 南大编译许畅
设计文法(1) 文法能够描述程序设计语言的大部分语法 但不是全部，比如，标识符的先声明后使用则无法用 上下文无关文法描述 因此语法分析器接受的语言是程序设计语言的超集； 必须通过语义分析来剔除一些符合文法、但不合法的 程序 24
设计文法 (1) • 文法能够描述程序设计语言的大部分语法 – 但不是全部，比如，标识符的先声明后使用则无法用 上下文无关文法描述 – 因此语法分析器接受的语言是程序设计语言的超集； 必须通过语义分析来剔除一些符合文法、但不合法的 程序 24 南大编译许畅
设计文法(2) 在进行高效的语法分析之前，需要对文法做以下 处理 消除二义性 。二义性：文法可以为一个句子生成多颗不同的分析树 消除左递归 。 左递归：文法中一个非终结符号A使得对某个串：，存在一个 推导A±>A心，则称这个文法是左递归的 提取左公因子 25
设计文法 (2) • 在进行高效的语法分析之前，需要对文法做以下 处理 – 消除二义性 • 二义性：文法可以为一个句子生成多颗不同的分析树 – 消除左递归 • 左递归：文法中一个非终结符号A使得对某个串α，存在一个 推导 A Aα，则称这个文法是左递归的 – 提取左公因子 25 南大编译许畅
二义性的消除(1) 一些二义性文法可被改成等价的无二义性的文法 例子 stmt→if expr then stmt I if expr then stmt else stmt other ifE1 then if E2 then S1 else S2的两棵语法树 stmi stm then stmt then stmt stmt E E f then stmt else if then E2 S2 E 26
二义性的消除 (1) • 一些二义性文法可被改成等价的无二义性的文法 • 例子 stmt →if expr then stmt | if expr then stmt else stmt | other – if E1 then if E2 then S1 else S2的两棵语法树 26 南大编译许畅
二义性的消除(2) ·保证else和最近未匹配的then匹配 要求在then和else之间出现的语句必须是匹配好的 。 引入natched stmt表示匹配好的语句 stmt matched stmt open_stmt natched stmt→ if expr then matched _stmt else matched_stmt I other open_stmt if expr then stmt I if expr then matched stmt else open_stmt ·二义性的消除方法没有规律可循 27
二义性的消除 (2) • 保证else和最近未匹配的then匹配 – 要求在then和else之间出现的语句必须是匹配好的 • 引入matched_stmt表示匹配好的语句 stmt → matched_stmt | open_stmt matched_stmt → if expr then matched_stmt else matched_stmt | other open_stmt → if expr then stmt | if expr then matched_stmt else open_stmt • 二义性的消除方法没有规律可循 27 南大编译许畅