上下文无关文法和正则表达式(1) 上下文无关文法比正则表达式的能力更强。即 所有的正则语言都可以使用文法描述 但是一些用文法描述的语言不能用正则文法描述。 ·证明 首先S→ asb ab描述了语言{ annaN>0},但是这个 语言无法用DFA识别。 假设有DFA识别此语言,且这个文法有K个状态。那么在 识别a1..的输入串时,必然两次到达同一个状态。设自 动机在第1个和第个a时进入同一个状态,那么:因为 DFA识别L,叫b必然到达接受状态,因此ab必然也到达 接受状态。 直观地讲:有穷自动机不能数(大)数
上下文无关文法和正则表达式（1） • 上下文无关文法比正则表达式的能力更强。即： – 所有的正则语言都可以使用文法描述 – 但是一些用文法描述的语言不能用正则文法描述。 • 证明： – 首先S→aSb | ab 描述了语言{a nb n |n>0}，但是这个 语言无法用DFA识别。 • 假设有DFA识别此语言，且这个文法有K个状态。那么在 识别a k+1…的输入串时，必然两次到达同一个状态。设自 动机在第i个和第j个a时进入同一个状态，那么：因为 DFA识别L，a jb j必然到达接受状态，因此a ib j必然也到达 接受状态。 • 直观地讲：有穷自动机不能数（大）数
上下文无关文法和正则表达式(2) 证明(续) 其次证明:任何正则语言都可以表示为上下文 无关文法的语言, 任何正则语言都必然有一个NFA。对于任意的 NFA构造如下的上下文无关文法 对NFA的每个状态i,创建非终结苻号A。 如果有i在输入a上到达j的转换,增加产生式AaA 如果在输入上到达j,那么增加产生式AA 如果是一个接受状态,增加产生式A→E 如果是开始状态,令A为所得文法的开始符号
上下文无关文法和正则表达式（2） • 证明（续） – 其次证明：任何正则语言都可以表示为上下文 无关文法的语言。 – 任何正则语言都必然有一个NFA。对于任意的 NFA构造如下的上下文无关文法 • 对NFA的每个状态i，创建非终结符号Ai。 • 如果有i在输入a上到达j的转换，增加产生式Ai→aAj。 • 如果i在输入ε上到达j，那么增加产生式Ai→Aj . • 如果i是一个接受状态，增加产生式Ai→ε • 如果i是开始状态，令Ai为所得文法的开始符号
NFA构造文法的例子 start b A0→aAo|bAo|aA1 A,>bA2 A2 >bA3 A2→8 考虑babb的推导和接受过程可知:NFA接受一个旬 子的运行过程实际是文法推导出该句子的过程
NFA构造文法的例子 • A0→aA0 | bA0 | aA1 • A1→bA2 • A2→bA3 • A3→ ε • 考虑baabb的推导和接受过程可知：NFA接受一个句 子的运行过程实际是文法推导出该句子的过程
设计文法 文法能够描述程序设计语言的大部分语法 但不是全部。比如:标识符的先声明后使用无 法用上下文无关文法描述。 因此:语法分析器接受的语言是程序设计语言 的超集。必须通过语义分析来剔除一些符合文 法、但不合法的程序
设计文法 • 文法能够描述程序设计语言的大部分语法 – 但不是全部，比如：标识符的先声明后使用无 法用上下文无关文法描述。 – 因此：语法分析器接受的语言是程序设计语言 的超集。必须通过语义分析来剔除一些符合文 法、但不合法的程序
二义性的消除(1) 些二义性文法可以被改成等价的元二义性的文法 ·例子 smt→ if expr then stmt if expr then stmt else stmt other ·ifE; then ife, then s1 else s的两棵语法树 stmt then tmt if erpr then stmt stint E if then stmt else stint erpr then st S E2
二义性的消除(1) • 一些二义性文法可以被改成等价的无二义性的文法 • 例子： stmt → if expr then stmt | if expr then stmt else stmt |other • if E1 then if E2 then S1 else S2的两棵语法树