10-第三章有限自动机与词法分析器.ppt

《10-第三章有限自动机与词法分析器.ppt》由会员分享，可在线阅读，更多相关《10-第三章有限自动机与词法分析器.ppt（23页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第三章第三章 有限自动有限自动机与词法分析器机与词法分析器任课教师任课教师王养廷王养廷主要内容主要内容1.正则表达式到有穷自动机的转换正则表达式到有穷自动机的转换2.有穷自动机到正则表达式的转换有穷自动机到正则表达式的转换3.实例实例1 正则表达式到有穷自动机正则表达式到有穷自动机n正则定理正则定理对任意正则表达式对任意正则表达式RE，均可构造出一个有，均可构造出一个有穷自动机穷自动机FA，使得，使得FA所接受的字符串等所接受的字符串等价于价于RE所定义的正则集。所定义的正则集。正则表达式正则表达式RE与有穷自动机与有穷自动机FA等价等价1 正则表达式到有穷自动机正则表达式到有穷自动机n正则表

2、达式到有穷自动机的转换正则表达式到有穷自动机的转换正则表达式到正则表达式到NFANFA到到DFA转换转换DFA极小化极小化DFA等价性等价性1 正则表达式到有穷自动机正则表达式到有穷自动机n结构化自动机结构化自动机RE=RERE=a=a1 正则表达式到有穷自动机正则表达式到有穷自动机n结构化自动机结构化自动机RE=A|BRE=AB1 正则表达式到有穷自动机正则表达式到有穷自动机n结构化自动机结构化自动机RE=A*1 正则表达式到有穷自动机正则表达式到有穷自动机n结构化自动机举例结构化自动机举例aa|baba*a(b|c)(a|b)(a|c)(a|b)c*2 有穷自动机到正则表达式有穷自动机到正

3、则表达式n举例举例a aa a*2 有穷自动机到正则表达式有穷自动机到正则表达式n举例举例2 有穷自动机到正则表达式有穷自动机到正则表达式n举例举例3 实例实例n正则表达式到有穷自动机正则表达式到有穷自动机示例示例(a|bc)*d)+(0|1)*(2|3)+)|0011练习练习P60 2(1,2),3(1,2),4(1)PL/0PL/0编译程序编译程序 PL/0编译编译程序程序 PL/0 语言程序语言程序 类类 pcode 代吗代吗源语言源语言(PL/0)目标语言目标语言(类类 pcode)实现语言（实现语言（pascal)PL/0 类类 pcode pascal PL/0PL/0编译程序编译

4、程序类类 pcodepcode解释解释程序程序类类 pcode代码代码PL/0源程序源程序输入输入输出输出PL/0PL/0编译系统的结构框架编译系统的结构框架PL/0PL/0程序示例程序示例 CONST A=10;CONST A=10;（*常量说明部分常量说明部分*）VAR B,C;VAR B,C;（*变量变量说明部分说明部分*）PROCEDURE PROCEDURE P;P;（*过程过程说明部分说明部分*）VAR D;VAR D;PROCEDURE PROCEDURE Q;Q;VAR X;VAR X;BEGINBEGIN READ(X);READ(X);D:=X;D:=X;WHILE X#0

5、 WHILE X#0 DO CALL P;DO CALL P;END;END;BEGINBEGIN WRITE(D);WRITE(D);CALL Q;CALL Q;END;END;BEGINBEGIN CALL P;CALL P;END.END.Q的过程体的过程体p的过程体的过程体主主程序程序体体 程序程序分程序分程序.内的文字表示内的文字表示非终结符非终结符或内的文字或符号表示内的文字或符号表示终结符终结符constidentnumber=,;varident,;procedureident;分程序分程序语句语句分程序分程序PL/0PL/0编译程序的结构编译程序的结构词法分析程词法分析程序序

6、语法语义分析程序语法语义分析程序代码生成程序代码生成程序表格管理程序表格管理程序出错处理程序出错处理程序PL/0PL/0源程序源程序目标程序目标程序PL/0PL/0编译程序的总体设计编译程序的总体设计n其编译过程采用其编译过程采用一趟扫描方式一趟扫描方式n以语法以语法、语义分析语义分析程序程序为核心为核心 词法分析词法分析程序和程序和代码生成代码生成程序都作为一个程序都作为一个过程过程，当语法分，当语法分析需要读单词时就调用词法分析程序，而当语法析需要读单词时就调用词法分析程序，而当语法、语义语义分析正确，需要生成相应的目标代码时，则调用代码生分析正确，需要生成相应的目标代码时，则调用代码生成

7、程序。成程序。n表格管理表格管理程序实现程序实现变量变量，常量常量和和过程过程标识符的标识符的信息的登信息的登录与查找录与查找。n出错处理出错处理程序，对词法和语法程序，对词法和语法、语义分析遇到的错误给语义分析遇到的错误给出在源程序中出在源程序中出错的位置出错的位置和与和与错误错误 性质有关性质有关的编号，并的编号，并进行错误恢复。进行错误恢复。PL/0PL/0编译程序词法分析的设计与实现编译程序词法分析的设计与实现识别的单词：识别的单词：保留字或关键字：如：保留字或关键字：如：BEGINBEGIN、ENDEND、IFIF、THENTHEN等等运算符运算符：如：如：+、-、*、/、：、：=、

8、#、=、=等等标识符标识符：用户定义的变量名、常数名、过程名用户定义的变量名、常数名、过程名常数常数：如：如：1010、2525、100100等整数等整数界符界符：如：如：,、.、;、(、)等等词法分析过程词法分析过程GETSYMGETSYM所要完成的任务：所要完成的任务：读源程序（读源程序（getchgetch)滤空格滤空格识别识别保留字保留字识别标识符识别标识符拼数拼数识别单字符单词识别单字符单词拼双字符单词拼双字符单词实验报告格式实验报告格式n格式格式实验目的实验目的主要软件主要软件分析过程（算法、重点语句、对应书中的原理）分析过程（算法、重点语句、对应书中的原理）实验的结论、建议与设想实验的结论、建议与设想n要求要求使用使用FTP上传：上传：ftp:/10.1.10.136:26 wang/wang总结总结n总结总结NFANFA到到DFA转换转换n重点重点NFA到到DFA转换转换