[计算机软件及应用]3词法分析.pptVIP

* * 第三章 词法分析 词法分析的任务是：从左至右逐个字符地对源程序进行 扫描，识别出一个个地单词，将识别出的单词表示成二 元组（类号，内码）。 一、词法分析器的功能和输出形式 1、功能：输入源程序，输出单词符号，并翻译成 （类号，内码）。 2、单词符号：一个程序设计语言的基本词法符号。 3、单词符号的分类： （1）关键字 （2）标识符 （3）常数 （4）运算符 （5）界符 §3.1 对于词法分析器的要求 1、预处理：将要进行词法分析的源程序去掉多余的空格，注释，且在每个句子末尾加#后供词法分析用。 §3.2 词法分析器的设计 2、单词符号的识别——超前有哪些信誉好的足球投注网站 ——根据语言的文法，即词法规则来识别。 Pascal语言的词法规则如下： （1）标识符→字母|标识符(字母|数字) （2）整数 →数字|整数数字 （3）有符号整数 → (+| - |ε)整数 （4）无符号整数 → 整数| 整数. 整数 | 整数E有符号整数 | 整数. 整数E有符号整数 （5）界符 →+ | - |* | / ||…… （6）双界符 → | := |= | = |/*|…… 0 1 3 4 2 5 6 : = = ； ； 0 1 2 4 5 6 3 1 1 0 0 0 3 1 = 1 2 字母 字母 Pascal 标识符 0 * 其它 Pascal 运算符和界符 数字 3 4 数字 数字 Pascal整数 0 1 3 4 6 5 2 7 0 d d d d d d d ? E E + – 7 * * Pascal实数 其它 其它 其它 其它 实验一：将某门语言的关键字按字典顺序编上类号存入一张表格中，能从键盘随意输入一个标识符，输出该标识符的类号。 实验二：编写一个词法分析程序，对某源程序 文件进行词法分析，将其中的所有单词经词法 分析后变为由类号构成的目标文件。 program(); const ass=10; begin read (A,B); C:=A+B; if (AB) C=45; else D=60; end 注：可以自己书写一段pascal源程序（用记事本），但必须包含 所有类型的单词（关键字，界符，算术运算符，关系运算符， 常数，标识符） 1、正规文法 根据Chomsky对形式语言的定义，正规文法的产生式形式为： A→αB, A→α,或者 A→Bβ , A→β其中α,β∈VT*,A,B∈VN. 2、正规集 由正规文法所产生的语言称作正规集。 3、正规式Re （Regular expression） a）定义：设A是非空的有限字母表,A={αi|i=1,2,……n },则 1)ε,φ,αi都是正规式; 2)若α,β是正规式,则α|β,α·β,α*,β*也是正规式; 3)正规式只能通过有限次使用1),2)规则而获得. § 3. 3 正规式和有限自动机 一、 正规文法、正规集和正规式 例1 字母表?=?a,b? 正规式α 正规集L(α) a ?b ?a,b? (a ?b )(a ?b ) ?aa,ab,ba,bb} ba* ?上所有以b为首后跟任意多 个a的字（句子）。 a (a ?b)* ?上所有以a为首的字(句子). b）正规式的等价：若两个正规式所表示的正规集相同，则等价。 例2 证明b(ab)*=(ba)*b 注:1）Re涉及三种运算符“|”或者，“·”连接，“*”闭包，优先级*·|。 2）仅由字母表A={αi| i=1，2…k}上的正规式α所组成的语言称作正规集。 3）正规式，正规集表示的都是由正规文法产生的语言，只是形式不同。 4、正规式的代数性质 5、正规式和正规文法的联系。 正规文法G可直接求得对应语言的正规式，反之亦可。 例3、求语言L(a)={aibjck|i,j,k=1}的产生文法，再由相应文法转换成正规式。 文法产生式: (0) S? aS?aB (1) B?bB?bC (2) C?cC?c 正规式： a+b+c+ 二、 有限自动机 FA