网站建设中故障排除方法,浙江省建设安监站网站,东营网站,个人网站设计论文道客巴巴3.1词法分析器的作用
词法分析是编译的第一阶段。词法分析器的主要任务是读入源程序的输入字符、将它们组成词素#xff0c;生成并输出一个词法单元序列#xff0c;每个词法单元对应于一个词素。
但在这个过程中#xff0c;词法分析器还要和语法分析器进行交互。交互…3.1词法分析器的作用
词法分析是编译的第一阶段。词法分析器的主要任务是读入源程序的输入字符、将它们组成词素生成并输出一个词法单元序列每个词法单元对应于一个词素。
但在这个过程中词法分析器还要和语法分析器进行交互。交互语法分析器通过一个指令调用词法分析器让词法分析器从它的输入中不断读取字符直到识别出下一个词素为止词法分析器根据这个词素生成下一个词法单元并返回给语法分析器。
词法分析器还会完成一些额外的任务
过滤掉源程序中的注释和空白空格、换行符、制表符以及在输入中用于分隔词法单元的其他字符将编译器生成的错误信息与源程序的位置联系起来。
总结词法分析器可以分为两个联级阶段
扫描阶段主要负责完成一些不需要生成词法单元的简单处理比如删除注释和将多个连续的空白字符压缩成一个字符。词法分析阶段是较为复杂的部分它处理扫描阶段的输出并生成词法单元。
3.1.1词法分析及语法分析
把编译过程的分析部分划分成词法分析和语法分析两个阶段的原因
简化编译器的设计。比如如果在语法分析中还要处理关于一些注释或者空白字符的问题那么将会更加复杂。提高编译器的效率。二者独立实现一些功能提高对某个环节处理的专业性。增强编译器的可移植性。输入设备相关的特殊性可以被限制在词法分析过程中。
3.1.2词法单元、模式和词素
词法单元词法单元名可选择的属性。模式是一种解释描述了一个词法单元的词素可能具有的形式。词素就是可以被词法分析器识别为该词法单元的一个实例。
大部分的词法单元
每个关键字有一个词法单元。一个关键字的模式就是该关键字本身。表示运算符的词法单元。它可以表示单个运算符也可以表示一类运算符。一个表示所有标识符的词法单元。一个或多个表示常量的词法单元。每个标点符号有一个词法单元比如左括号、逗号和分号。
3.1.3词法单元的属性
词法分析器不仅仅向语法分析器返回一个词法单元名字还会返回一个描述该词法单元的词素的属性值。这个属性则会影响语法分析之后对这个词法单元的翻译。
3.2词法单元的规约
正则表达式是一种用来描述词素模式的重要表示方法。
3.2.1串和语言
串s的长度通常记作|s|是指s中符号出现的次数。
语言是某个给定字母表上一个任意的可数的串集合。
串的各部分术语
串s的前缀prefix从s的尾部删除0个或多个符号后得到的串。串s的后缀suffix从s的开始处删除0个或多个符号后得到的串。串s的子串substring删除s的某个前缀和某个后缀之后得到的串。串s的真前缀、真后缀、真子串既不等于空也不等于s本身的前缀、后缀、子串。串s的子序列subsequence从s中删除0个或多个符号后得到的串这些被删除的符号可能不相邻。
如果x和y是串那么x和y的连接concatenation是把y附加到x后面而形成的串。例如x handsome 且 y you 。那么xy handsomeyou 。
3.2.2语言上的运算
L和M的并就是简单的合并成一个集合L和M的连接以各种可能的方式从第一个语言中任取一个串再从第二个语言中任取一个串然后将它们连接后得到的串集。L的Kleene闭包L*就是将L连接0次或多次后得到的串集。L的正闭包只不过是去掉空串。
3.2.3正则表达式
正则表达式可以由较小的正则表达式按照如下规则递归地构建。
归纳基础e是一个正则表达式L(e){e}即该语言只包含空串。
归纳步骤由小的正则表达式构造较大的正则表达式的步骤有四个部分。假定r和s都是正则表达式分别表示语言L(r)和L(s)。
(r)|(s)是一个正则表达式表示语言L(r) U L(s)。(r)(s)是一个正则表达式表示语言L(r)L(s)。(r)*是一个正则表达式表示语言(L(r))*。(r)是一个正则表达式表示语言L(r)。最后这个规则是说在表达式的两边加上括号并不影响表达式所表示的语言。
当然有时候是可以去掉括号的*具有最高优先级且是左结合的连接具有次高优先级且是左结合的|的优先级最低且是左结合的。
正则表达式的代数定律只记录特殊的一条r** r* 。 具有幂等性。
取自某学习视频
限定符
a*a出现次或多次aa出现1次或多次aa出现0次或1次a{6}a出现6次a{26}a出现2-6次a{2}a出现两次以上
运算符
a|b匹配a或者bab|cd匹配ab或者cd
字符类
[abc]匹配a或者b或者c[a-c]同上[a-fA-F0-9]匹配小写大写英文字符以及数字[^0-9]匹配非数字字符
元字符
\d匹配数字字符\D匹配非数字字符\w匹配单词字符字母数字下划线\W匹配非单词字符\s匹配空白符\S匹配非空白字符. 匹配任意字符换行符除外\b标注字符的边界^匹配行首$匹配行尾
3.3词法单元的识别
3.3.1状态转换图
接下来将通过一张图来解释 有一组被称为“状态”的结点或圆圈。状态图中的边从图的一个状态指向另一个状态定向搜索可能性也就只有1。图中的双层的圈就是“接受状态”或“最终状态”。由一条没有出发结点的箭头指向的是“开始状态”或“初始状态”。如果需要将指针回退到上一个位置则需要在接受状态的附近加上一个*若是多个位置就加多个*。
3.3.2保留字和标识符的识别
主要目的就是防止一些关键字被识别成标识符。
解决方法通常有两种
将所有可能用到的关键字一一列举在符号表中为每个关键字设定一个状态转换图但是在最后的接受状态要添加一个“非字母或数字”的测试来确保这个状态转换图确实不会成为一个标识符。
3.3.3基于状态转换图的词法分析器的体系结构
用一个函数来模拟状态转换图的实现。不同的词法单元分析有不同的状态转换图但是为了实现对某个未知的词法单元进行词法分析你首先要做的就是选定某个状态转换图。
依次调用所有的状态转换图直到分析出。同时调用所有的状态转换图选择最长匹配。将所有状态转换图归成一个状态转换图。
3.4词法分析器生成工具Lex
Lex最近也叫Flex这个F就是Fast的意思。它的核心功能就是将输入的模式转换成一个状态转换图并生成相应的实现代码。
3.4.1 Lex的使用
使用者本身首先要使用Lex语言写一个.l文件然后运用配置好的Lex编译器在终端输入相关指令将.l文件转换成lex.yy.c文件。
3.4.2 Lex程序的结构
%{
.... //声明部分%}//给一些正则表达式typedef一下%%
//转换规则
//正则表达式 {实现的操作}[a-zA-Z] { words; chars strlen(yytext); }
%%//辅助函数部分main()
{yylex();return 0;
}
声明部分、辅助函数部分都被直接拷贝到.c文件中yytext 是一个指向词素开头的指针yyleng 存放刚找到的词素的长度
3.4.3 Lex中的冲突解决
当输入的多个前缀与一个或多个模式匹配时Lex用如下规则选择正确的词素
总是选择最长的浅醉。如果最长的可能前缀与多个模式匹配总是选择在Lex程序中先被列出的模式。将关键字的定义靠前列出
3.4.4 向前看运算符
在一些语言中存在 IF 是一个数组的名字而不是关键字这样的使用就给词法分析带来了很大的困扰。
所以要采用一种新的方法用斜号来指明该模式中和词素实际匹配的部分的结尾斜号 / 之后的内容表示一个附加的模式只有附加模式也匹配成功了最后才能进行返回自己要找的词法单元并进行输出不包含附加内容。
举例这里的IF就变成了IF / \( . * \) {letter}
3.5 有穷自动机
自动机在本质上是与状态转换图类似的图但存在几点不同
有穷自动机是识别器它们只能对每个可能得输入串简单地回答“是”或“否”。不确定的有穷自动机NFA堆其边上的标号没有任何限制一个标号可以标记离开同一状态的多条边并且空串ε也可以作为标记。确定的有穷自动机DFA就只有一条离开该状态的边且这个边上的标记只能用一次。
