编译原理知识点参考.docx

第三章3.1 对于词法分析器的要求1．词法词法分析的任务：从左至右逐个字符地对源程序进行扫描，产生一个个单词符号。词法分析器(Lexical Analyzer) 又称扫描器(Scanner)：执行词法分析的程序。2．程序语言的单词符号：关键字、标识符、常数、运算符、界符。3．输出的单词符号的表示形式:(单词种别，单词自身的值)Eg：while (i=j) i--;输出单词符号： while, - (, - id, 指向i的符号表项的指针 =, - id, 指向j的符号表项的指针 ), - id, 指向i的符号表项的指针 --, - ;, - 4．词法分析器作为一个独立子程序：结构简洁、清晰和条理化，有利于集中考虑词法分析一些枝节问题。5．词法分析器3.2 词法分析器的设计1．词法分析器2．输入、预处理：输入串放在输入缓冲区中。预处理子程序：剔除无用的空白、跳格、回车和换行等编辑性字符;区分标号区、捻接续行和给出句末符等扫描缓冲区（指向开始位置，向前有哪些信誉好的足球投注网站确定终点）3．单词符号的识别、超前有哪些信誉好的足球投注网站：(1)基本字识别Eg：DO99K=1，10 DO 99 K = 1，10 IF(5.EQ.M)GOTO55 IF (5.EQ.M) GOTO 55DO99K=1.10IF(5)=55需要超前有哪些信誉好的足球投注网站才能确定哪些是基本字(2)标识符(3)常数(4)算符和界符4．状态转换图(有限方向图)1结点代表状态2状态之间用箭弧连结，箭弧上的标记(字符)代表射出结状态下可能出现的输入字符或字符类。3一个状态转换图可用于识别(或接受)一定的字符串。5．语法分析的状态转换图6．状态转换图的实现思想：每个状态结对应一小段程序。7．状态转换图实现(了解)1)ch 字符变量、存放必威体育精装版读入的源程序字符2)strToken 字符数组，存放构成单词符号的字符串3)GetChar 子程序过程，把下一个字符读入到 ch 中4)GetBC 子程序过程，跳过空白符，直至 ch 中读入一非空白符5)Concat 子程序，把ch中的字符连接到 strToken6)IsLetter和 IsDisgital 布尔函数，判断ch中字符是否为字母和数字7) Reserve 整型函数，对于 strToken 中的字符串查找保留字表，若它是保留字则给出它的编码，否则回送08) Retract 子程序，把有哪些信誉好的足球投注网站指针回调一个字符位置9)InsertId 整型函数，将strToken中的标识符插入符号表，返回符号表指针10)InsertConst 整型函数过程，将strToken中的常数插入常数表，返回常数表指针。8．一个词法分析器的例子(多看看、了解吧)：int code, value;strToken := “ ”;/*置strToken为空串*/GetChar(); GetBC();if (IsLetter())beginwhile (IsLetter() or IsDigit())beginConcat(); GetChar(); endRetract();code := Reserve();if (code = 0)beginvalue := InsertId(strToken);return ($ID, value);endelsereturn (code, -);endelse if (IsDigit())beginwhile (IsDigit())beginConcat( ); GetChar( );endRetract();value := InsertConst(strToken);return($INT, value);endelse if (ch =‘=’) return ($ASSIGN, -);else if (ch =‘+’) return ($PLUS, -);else if (ch =‘*’)beginGetChar();if (ch =‘*’) return ($POWER, -);Retract(); return ($STAR, -);endelse if (ch =‘;’) return ($SEMICOLON, -);else if (ch =‘(’) return ($LPAR, -);else if (ch =‘)’) return ($RPAR, -);else ProcError( );/* 错误处理*/3.3正规表达式和有限自动机正规集与正规式正规式与正规集的递归定义（见课本P46，47）若两个正规式所表示得正规集相同，则二者等价。确定有限自动机（DFA）确定有限自动机的定义。（课本P47）DFA可以表示为状态转换图。假定DFA M含有m个状态和n个输入字符，那么，这个图含有m个状态结点，每个结点顶多含有n条箭弧