
- 领 域
- 编译原理
- 本 质
- 按照语言的词法规则识别各类单词
- 中文名
- 词法分析
-
词法分析
2020-10-18 21:20:36词法分析总体概念 1、词法分析的任务 词法分析是编译的第一个阶段,其任务是:从左至右逐个字符地对源程序(用高级语言编写的)进行扫描,产生一个个单词符号,把字符串形式的源程序改造成为单词符号串形式的中间...词法分析总体概念
1、词法分析的任务
词法分析是编译的第一个阶段,其任务是:从左至右逐个字符地对源程序(用高级语言编写的)进行扫描,产生一个个单词符号,把字符串形式的源程序改造成为单词符号串形式的中间程序。
2、词法分析器(也叫扫描器)
执行词法分析的程序称为词法分析程序,也称为词法分析器或扫描器。
词法分析器的功能是输入源程序,输出单词符号。
3、词法分析的两种处理结构
(1)把词法分析程序作为主程序。即,把词法分析与语法分析明显分开,由词法分析程序将字符串形式的源程序改造成单词符号串形式的中间程序,以这个中间程序作为语法分析程序的输入。在这种处理结构中,词法分析和语法分析实际上是分别实现的。
(2)把词法分析程序作为语法分析程序调用的子程序。在进行语法分析时,每当语法分析程序需要一个单词时,便调用词法分析程序,词法分析程序每一次调用便从字符串源程序中识别出一个单词交给语法分析程序。在这种处理结构中,词法分析和语法分析实际上是交替进行的。
词法分析器的设计方法
2.1 单词符号
由语法分析程序的任务可以知道:单词符号是程序语言的基本语法单位具有确定的语法意义。
1、程序语言的单词符号通常可以分为以下5种:保留字 标识符 常数 运算符 界符 也称为基本字,例如C语言中的if、else、while、do等,保留了语言所规定的含义,是编译程序识别各类语言语法成分的依据。几乎所有程序语言都限制用户使用保留字来作为标识符 用来标记常量、数组、类型、变量、过程或函数名等,通常由用户自己定义 包括各种类型的常数,如整型常数、实型常数、布尔型常数等 如“ + ”、“ - ”、“ * ”、“ / ”、“ > ” 等。 在语言中是作为语法上的分界符号使用的,如“ , ”、“ ; ”、“ ; ”、“ ( ”、“ ) ”等。 2、词法分析程序输出的单词符号,通常表示为:
(单词种别,单词自身的值)
一词一码的单词符号,二元式中不必写出值(用null代替即可);一类一码的单词符号,二元式中要写出值。
(1)单词种别
单词种别表示单词的种类,它是语法分析所需要的信息。通常让每种单词对应一个整数码,这样可以最大限度地把各个单词区分开来。
(2)单词自身的值
单词自身的值,是编译中其它阶段所需要的信息。若一个种别只含有一个单词符号 若一个种别含有多个单词符号 对于这个单词符号,其种别编码就完全代表了它自身的值 对于他的每个单词符号,除了给出种别编码之外,还应给出单词符号自身的值,以便把同一种类的不同单词区别开来
保留字 标识符 常数 运算符 界符 可将其全体视为一种,也可以一词一种 一般统一归为一种 可以统一归为一种,也可按整型、实型、布尔型等分为几种 可采用一符一种的分法,也可以统一归为一种 可采用一符一种的分法,也可以统一归为一种 采用一词一种比较方便 如果一词一类,那么种别编码就代表自身的值 标识符自身的值就是标识符自身的字符串 常数自身的值是常数本身的二进制数值 注:此外,我们也可以用指向某类表格中一个特定项目的指针来区分同类中的不同单词。
eg: 对于标识符,可以用它在符号表的入口指针作为它自身的值;
常数可以用它在常数表的入口指针作为它自身的值
2.2 状态转换图
举例:无符号数的状态转换图:
当到达一类单词符号的终止状态时即可给出相应的单词编码。由于某些终止状态是在读入一个其它不属于该单词的符号后,才得到相应的单词编码,这表明在识别单词的过程中多读入了一个符号,所以识别处单词后应将最后多读入的这个符号予以回退。
a. 对于不含回路的分支状态来说,可以让它对应一个 switch()语句或者一组if-else语句:
b. 对于含回路的状态来说,可以让它对应一个 while语句。:
终态一般对应一个return()语句。return 意味着从词法分析器返回到调用段,一般指返回到语法分析器。一个简单的词法分析器
一个重要的事实是:大多数程序语言的单词符号都可以用状态转换图予以识别。
举例:
1、C语言子集的单词符号及内码表示:
(由于直接使用整数编码不利于记忆,故用一些特殊符号来表示种别编码)
备注:表格中的保留字,采用一词一码的方式处理→种别编码就完全代表了自身的值;
标识符、常数,采用的是一类一码→分别用指向符号表、常数表的一个特定项目的指针来区分同类中的单词;
运算符、界符,采用一词一码的方式处理。
2、在设计的状态转换图中,首先对输入的串做预处理,剔除多余的空白符 → 将保留字作为一类特殊的标识符来处理,即对保留字不单独设置状态转换图,当转换图识别出一个标识符时,先去查对应的表的前5项,确定它是否为一个保留字。(也可以专设一个保留字表来进行处理)
对应的状态转换图为:
注意:
在图中的状态2时,先确定是否为保留字,否则就是标识符。如果是标识符,应该先查符号表,如果表中无此标识符,则将它加入到符号表中,返回它在符号表中的入口指针(地址)作为该标识符的内码值;如果表中已经有此标识符,则给出重名错误信息。
在状态4时,应将识别的常数转换成二进制常数,并将其加入到常数表中,然后返回其在常数表中的入口指针作为该常数的内码值。
3、状态转换图的实现(C语言代码)
最简单的实现状态转换图的方法:让每个状态对应一小段程序。
对于这个例子的状态转换图,引进一组变量和函数:(1) character: 字符变量,存放新读入的源程序字符
(2)token: 字符数组,存放构成单词符号的字符串
(3) getbe(): 若character中的字符为空白,则调用getchar(), 直至character为非空白字符为止
(4) concatenation(): 将token中的字符串与character中的字符连接并作为token 中新的字符串
(5) letter()和 digit(): 判断character中的字符是否为字母和数字的布尔函数,是则返回true(即1),否则返回false(即0)。
(6) reserve(): 按token数组中的字符串查表中的前五项(即判别其是否为保留字),若是保留字则返回它的编码,否则返回0值
(7)retract(): 扫描指针回退一个字符,同时将character置为空白。
(8) buildlist(): 将标识符登灵到符号表中或将赏数登录到常数表中
(9) error(): 出现非法字符,显示出错信息。 -
词法分析1&词法分析概述&词法分析器的设计
2020-04-23 09:50:04 -
C#词法分析器之词法分析的使用详解
2020-09-05 11:07:25本篇文章介绍了,C#词法分析器之词法分析的使用详解。需要的朋友参考下 -
java 词法分析器_词法分析 | 词法分析的任务
2020-12-14 00:27:11在其中,词法分析器的任务就是读入源程序,对其进行一定的切分,得到记号流。对于字符流和记号流之间的区别,下面给出一个例子来说明。if (x > 5) y = "hello"; else z = 1;对面上面这段程序,在词法分析器的...在编译原理介绍中,我们已经对前端的工作有了大致的了解。
在其中,词法分析器的任务就是读入源程序,对其进行一定的切分,得到记号流。
对于字符流和记号流之间的区别,下面给出一个例子来说明。
if (x > 5) y = "hello"; else z = 1;
对面上面这段程序,在词法分析器的眼中,是这样表示的:
i, f, " ", (, x, " ",>, " ", 5, ), n, " "," ", y, " ", =, .........
可见词法分析器看到的字符流和我们眼中的字符流是不一样的。 而词法分析器的任务就是对字符进行 切分。将 i 和 f 并在一起做为一个 if 关键字,去除掉没有意义的空格等等。
对于像 IF, LPAREN, IDENT 等的单词,我们都称为记号。
在记号中,有一些记号是没有属性的,类似于 IF 之类的关键字, IDENT(x) 之类的标识符需要表明其中的元素具体是什么。
记号的数据结构定义如下:
enum kind {IF, LPAREN, ID, INTLIT, ...}; struct token{ enum kind k; char *lexname; }
因此,对于语句 if (x > 5) 可以转变为
token { k = IF; lexname = 0; //0 表示没有赋任何的值 } token { k = LPAREN; laxname = 0; } token { k = ID; laxname = "x"; } ....
通过上面的学习,我们可以知道词法分析器的任务是将字符流转化为记号流。
- 字符流:和被编译的语言密切相关(ASCII(C), Unicode(Java, Swift), or ...)
- 记号流:编译器内部定义的数据结构,编码所识别出的词法单元。
原文链接:
- 编译原理 - 网易云课堂
-
编译原理实验:词法分析
2018-09-29 21:17:16编译原理实验:词法分析1. 实验题目:词法分析实验目的实验内容实验要求输入输出2. 设计思想3.算法流程4. 源程序5. 调试数据 1. 实验题目:词法分析 实验目的 根据PL/0语言的文法规范,编写PL/0语言的词法分析...1. 实验题目:词法分析
实验目的
- 根据PL/0语言的文法规范,编写PL/0语言的词法分析程序;或者调研词法分析程序的自动生成工具LEX或FLEX,设计并实现一个能够输出单词序列的词法分析器。
- 通过设计调试词法分析程序,实现从源程序中分出各种单词的方法;加深对课堂教学的理解;提高词法分析方法的实践能力。
- 掌握从源程序文件中读取有效字符的方法和产生源程序的内部表示文件的法。
- 掌握词法分析的实现方法。上机调试编出的词法分析程序。
实验内容
已给PL/0语言文法,输出单词符号(关键字、专用符号以及其它标记)。
实验要求
- 把词法分析器设计成一个独立一遍的过程。
- 词法分析器的输出形式采用二元式序列,即:(单词种类,单词的值)
输入输出
输入:
const a=10;
var b,c;
begin
read(b);
c:=a+b;
write( c);
end.
输出:
(constsym, const)
(ident , a)
(eql, =)
(number, 10)
(semicolon, ; )
(varsym, var)
(ident,b)
(comma, ,)
(ident, c)
(semicolon, ; )
(beginsym, begin)
(readsym, read )
(lparen,( )
(ident, b)
(rparen, ))
(semicolon, ; )
(ident, c)
(becomes, := )
(ident, a)
(plus, +)
(ident,b )
(semicolon, ; )
(writesym,write)
(lparen, ( )
(ident, c)
(rparen,) )
(endsym, end )
(period, .)2. 设计思想
基本字:
单词(编码) 正规式r begin(beginsym) begin call(callsym) call const(constsym) const do(dosys) do end(endsym) end if(ifsym) if odd(oddsym) odd procedure(proceduresym) procedure read(readsym) read var(varsym) var while(whilesym) while write(writesym) write then(thensym) then 标识符:
单词(编码) 正规式r <标识符>(ident) (字母)(字母 |数字)* 常数:
单词(编码) 正规式r <常数>(ident) (数字)(数字)* 运算符:
单词(编码) 正规式r +(plus) + -(minus) - *(times) * /(slash) / =(eql) = <>(neq) <> <(lss) < <=(leq) <= >(gtr) > >=(geq) >= :=(becomes) := 界符:
单词(编码) 正规式r ( (lparen) ( ) (rparen) ) , (comma) , ; (semicolon) ; . (period) . 3.算法流程
- 词法分析程序打开源文件,读取文件内容,直至遇上文件结束符,然后读取结束。
- 接下来就要对源文件从头到尾进行扫描了,从头开始扫描,这个时候扫描程序首先要询问当前的字符是不是空格,若是空格,则继续扫描下一个字符,直至不是空格。然后询问这个字符是不是字母,若是则进行标识符和保留字的识别;若这个字符为数字,则进行数字的判断。否则,依次对这个字符可能的情况进行判断(界符和运算符),若将所有可能都走了一遍还是没有知道它是谁,则认定为错误符号,输出该无法识别error,程序结束。每次成功识别了一个单词后,单词都会存在word1[]数组中,然后字符指针往后移,进行下一个单词的识别。
- 主控程序需要负责对每次识别的种别码进行判断,对于不同的单词种别做出不同的反应,直至文件结束。
- 本次实验我采用了map这个STL关联容器,主要是考虑到词法分析中的数据映射的关系,因此采用这种结构。map提供一对一的数据处理能力,其中第一个可以称为关键字,每个关键字只能在map中出现一次,第二个可能称为该关键字的值。这个容器是非常方便使用的,对于查找可以直接使用迭代器进行,利用find()函数,若一直到末尾都未找到,则是不能识别或为标识符。
4. 源程序
#include<bits/stdc++.h> using namespace std; map<string,string> word;//应用map数据结构形成一个string->string的对应 std::map<string,string>::iterator it;//用来遍历整个对应关系的迭代器 void map_init(){//对应关系进行初始化 word["begin"]="beginsym"; word["call"]="callsym"; word["const"]="constsym"; word["do"]="dosym"; word["end"]="endsym"; word["if"]="ifsym"; word["odd"]="oddsym"; word["procedure"]="proceduresym"; word["read"]="readsym"; word["then"]="thensym"; word["var"]="varsym"; word["while"]="whilesym"; word["write"]="writesym"; word["+"]="plus"; word["-"]="minus"; word["*"]="times"; word["/"]="slash"; word["="]="eql"; word["<>"]="neq"; word["<"]="lss"; word["<="]="leq"; word[">"]="gtr"; word[">="]="geq"; word[":="]="becomes"; word["("]="lparen"; word[")"]="rparen"; word[","]="comma"; word[";"]="semicolon"; word["."]="period"; } int main(){ map_init();//初始化 char ch; char a; string word1;//string变量识别单词 string str;//string变量进行字符识别 ifstream infile("F:\\编译原理\\第一次实验\\analysis.txt");//文件输入流 ofstream outfile("F:\\编译原理\\第一次实验\\result.txt");//文件输出流 ostringstream buf; while(buf&&infile.get(ch)) buf.put(ch);//将文件中的字符读出来 str= buf.str();//将得到的字符储存到string类型变量中 int csize=str.length(); for(int i=0;i<csize;i++){//对整个字符串进行遍历 while(str[i]==' '||str[i]=='\n') i++;//若最开始为空格或换行符,则将指针的位置往后移 if(isalpha(str[i])){//对标识符和基本字进行识别,调用库函数isalpha() word1=str[i++]; while(isalpha(str[i])||isdigit(str[i])){ word1+=str[i++]; } it=word.find(word1); if(it!=word.end()){//判断是不是基本字,若为基本字则进行输出 cout<<"("<<word[word1]<<","<<word1<<")"<<endl; } else{//否则直接输出 cout<<"(ident"<<","<<word1<<")"<<endl; } i--; } else if(isdigit(str[i])){//判断是不是常数,调用库函数isdigit() word1=str[i++]; while(isdigit(str[i])){ word1+=str[i++]; } if(isalpha(str[i])){ cout<<"error!"<<endl; break; } else{ cout<<"(number"<<","<<word1<<")"<<endl; } i--; }else if(str[i]=='<'){//对<,<=分别进行判断 word1=str[i++]; if(str[i]=='>'){ word1+=str[i]; cout<<"("<<word[word1]<<","<<word1<<")"<<endl; }else if(str[i]=='='){ word1+=str[i]; cout<<"("<<word[word1]<<","<<word1<<")"<<endl; }else if(str[i]!=' '||!isdigit(str[i])||!isalpha(str[i])){ cout<<"("<<word[word1]<<","<<word1<<")"<<endl; }else{ cout<<"error!"<<endl; break; } i--; }else if(str[i]=='>'){//对>,>=分别进行判断 word1=str[i++]; if(str[i]=='='){ word1+=str[i]; cout<<"("<<word[word1]<<","<<word1<<")"<<endl; }else if(str[i]!=' '||!isdigit(str[i])||!isalpha(str[i])){ cout<<"("<<word[word1]<<","<<word1<<")"<<endl; }else{ cout<<"error!"<<endl; break; } i--; }else if(str[i]==':'){//对:=进行判断 word1=str[i++]; if(str[i]=='='){ word1+=str[i]; cout<<"("<<word[word1]<<","<<word1<<")"<<endl; }else{ cout<<"error!"<<endl; break; } i--; }else{//对其他的基本字依次进行判断 word1=str[i]; it=word.find(word1); if(it!=word.end()){ cout<<"("<<word[word1]<<","<<word1<<")"<<endl; }else{ cout<<"error!"<<endl; break; } } } infile.close(); return 0; }
5. 调试数据
待输入的文件流:
输出数据:
说明:如上实验仅符合当时实验要求的相关条件,其他的需求略微进行更改就行,思想是一样的,还是很简单的。输入输出自己按自己需求更改即可。 -
atitit 词法分析原理 词法分析器 Lexer
2018-11-13 03:55:05atitit 词法分析原理 词法分析器 Lexer -
词法分析程序.pdf 词法分析程序.pdf 词法分析程序.pdf
2009-03-21 15:50:36词法分析程序.pdf 词法分析程序.pdf 词法分析程序.pdf -
词法分析——词法分析的任务
2018-10-30 13:02:25词法分析器的任务是读入源程序,对其进行一定的切分,得到记号流 对于字符流和记号流之间的区别,下面给出一个例子来说明 if (x > 5) y = "hello"; else z = 1; 对面上面这段程序,在词法分析器... -
python表达式词法分析_Python的词法分析与语法分析
2020-12-15 06:37:33Python的词法分析与语法分析更新时间:2013年05月18日 11:59:54 作者:这篇文章主要介绍了Python的词法分析(Lexical Analysis)与 语法分析(Syntactic Analysis),需要的朋友可以参考下词法分析(Lexical Analysis):... -
词法分析器
2018-05-09 16:06:37设计并实现一个词法分析器,实现对指定位置的类C语言源程序文本文件的读取,并能够对该源程序中的所有单词进行分类,指出其所属类型,实现简单的词法分析操作。 -
flex词法分析
2016-11-10 10:06:05Flex编程实现词法分析目的: 了解C--语法 掌握Flex创建词法分析的基本步骤 掌握编写Flex源文件 学会正则表达式的书写 了解Flex生成的词法分析函数yylex(),并且思考yylex()与语法分析之间的联系 txt中为实验代码,请... -
3 词法分析
2020-02-20 16:50:59文章目录3.1词法分析程序的设计3.1.1词法分析程序和语法分析程序的接口方式3.1.2词法分析程序的输出 词法分析是编译的第一阶段, 从左至右逐个字符地对源程序扫描,产生一个单词序列, 用于语法分析。 执行词法分析...
-
基于X210的裸机时钟温度显示器-第3/3季
-
(新)备战2021软考网络工程师终极解密培训套餐
-
01. pyhton 统计句子的长度
-
(新)备战2021软考信息安全工程师顺利通关套餐
-
前端性能优化
-
STM32(HAL)驱动0.96寸TFT屏幕(可显示任意尺寸图片).zip
-
BCB6 集成LUA5.4 静态库及应用示例源码
-
【数据分析-随到随学】量化交易策略模型
-
多媒体技术实验报告-图片处理-图片解压缩-GIF制作-视频播放-MP3播放器
-
STM32-HMC5883L.rar
-
(新)备战2021软考网络规划设计师终极解密套餐
-
hadoop自动化运维工具Ambari应用实践
-
单元测试UnitTest+Pytest【Selenium3】
-
【数据分析-随到随学】数据分析建模和预测
-
DzFilter,使用DFA算法实现的内容安全,反垃圾,智能鉴黄,敏感词过滤,不良信息检测,文本校验,敏感词检测,包括关键词提取,过滤html标签等。
-
OPPO A83(MT6763)原厂原理图维修图(PDF格式)
-
(新)备战2021软考网络工程师历年真题培训套餐
-
基于java的来访咨询系统的设计与实现
-
复制带随机指针的链表
-
基于php的图书借阅系统(比较简单)