3.2语言和文法 ·例L={abnn≥1} S→aSb|ab L是不能用正规式描述的语言的一个范例 -若存在接受L的DFAD, 状态数为k个 设D读完&，a,aa,,dk分别到达状态S,S1,,S 至少有两个状态相同，例如是s,和s,? 则db属于L 标记为d-的路径 标记为α的路径 标记为b的路径
3 2. 语言和文法 • 例 L={anbn | n 1 } S aSb | ab aSb | ab L是不能用正规式描述的语言的一个范例 – 若存在接受L的DFA D，状态数为k个 – 设D读完 a aa a – 设D读完, a, aa, …, ak 分别到达状态s s s 0,1, …, sk – 至少有两个状态相同，例如是si和sj，则ajbi属于L 标记为aj i的路径 … f s 标记为ai的路径 标记为bi的路径 … si … f s0 …
3.2语言和文法 3.2.2分离词法分析器理由 ·为什么要用正规式定义词法 -词法规则非常简单，不必用上下文无关文法 -对于词法记号，采用正规式描述简洁且易于理解 -从正规式构造出的词法分析器效率高
3 2. 语言和文法 3.2.2 分离词法分析器理由 • 为什么要用正规式定义词法 –词法规则非常简单，不必用上下文无关文法 –对于词法记号，采用正规式描述简洁且易于理解 –从正规式构造出的词法分析器效率高
3.2语言和文法 从软件工程角度看，词法分析和语法分析的 分离有如下好处 -简化设计 -编译器的效率会改进 -编译器的可移植性加强 ~便于编译器前端的模块划分
3 2. 语言和文法 • 从软件工程角度看，词法分析和语法分析的 分离有如下好处 –简化设计 –编译器的效率会改进 –编译器的可移植性加强 –便于编译器前端的模块划分
3.2语言和文法 能否把词法分析并入到语法分析中，直接从 字符流进行语法分析？ 若把词法分析和语法分析合在一起，则必须将语 言的注释和空白的规则反映在文法中，文法将大 大复杂 注释和空白由自己来处理的分析器，比注释和空 白已由词法分析器删除的分析器要复杂得多
3 2. 语言和文法 • 能否把词法分析并入到语法分析中，直接从 字符流进行语法分析？ – 若把词法分析和语法分析合在一起，则必须将语 言的注释和空白的规则反映在文法中，文法将大 大复杂 – 注释和空白由自己来处理的分析器，比注释和空 白已由词法分析器删除的分析器要复杂得多
3.2语言和文法 3.2.3验证文法产生的语言 G:S→(S)SεL(G)=配对的括号串的集合
3 2. 语言和文法 3.2.3 验证文法产生的语言 G : S (S ) S | L(G) = 配对的括号串的集合 配对的括号串的集合