概述:
词在语言中的地位:1儿童学习语言,模仿无意义的音节->感知词->形成句子,2词是从无意义的声音到有意义的语音的关键过渡,3计算机理解和处理语言，也是从词开始
语言学上，词是能够独立运用的，有意义的最小语法单位
词法分析的重要性:
1词法分析是语言分析的基础
2很多自然语言处理系统是建立在词的基础上(如：文本检索、文本校对、自动文摘、机器翻译等...)
什么是词法分析：
1.自然语言的字符串转换成词串
将句子中的词分离出来(tokenization)
分析出词的语素成分(lematization, morphological analysis)
2.给词加上句法范畴标记(Part of Speech Tagging)，甚至语义范畴标记(Word Sense Tagging)
“字串”->“词串”->“词性/词义标记串”
计算机对自然语言的句子增加确定性的过程，也是对自然语言理解过程的一部分
排除歧义
一个句子对应多种分词结果
美国会通过这项法案
美国/ 会/ 通过/ 这/ 项/ 法案/。
美/ 国会/ 通过/ 这/ 项/ 法案/。
一个词串对应多个词性标记串
这个句子三个翻译都没有翻译正确。
不同的自然语言其特点各不相同，因此面临的问题也会有所不同
构词、词的结构、使用、书写等规则不同
例如：朝鲜语中对上辈、同辈和下辈的语言表达不同
词的识别
英语分词：英文在书写时在词与词之间基本都有空格作为分隔符，因而词的界限比较分明。英语真实文本的情况相对复杂：
单词与标点符号之间没有空格
有些词之间不是以空格分开
缩略语中的“.”号句末“.”号可能造成混淆
其他
英文还需要“分词”(Tokenization)：在英文词法分析阶段，还需要对字符串进行分析，找出其中的单词。
屈折型语言的词形变化，给词的识别造成困难
词形还原(lemmatization)是把一个任何形式的语言词汇还原为一般形式（能表达完整语义）。词形还原主要采用“转变”的方法，将词转变为其原形，如将“drove”处理为“drive”，将“driving”处理为“drive”。
词干提取(stemming)是抽取词的词干或词根形式（不一定能够表达完整语义）。
词干提取主要是采用“缩减”的方法，将词转换为词干，如将“cats”处理为“cat”，将“effective”处理为“effect”。
英文词识别中的一些问题：
1)数字：123,456.78, 87%, 3/8, 11/20/2003
2)缩略：1)X.X.形式：U.S., i.e. 2)字母开头，"."号结束：Mr., prof., etc.
3)包含非字母字符：AT&T
4)带杠的词串：three-years-old, one-third, so-called
5)带撇号的词串：I'm, can't, dog's, let's
6)带空格的词串：and so on, ad hoc(点对点)
解决方法：
1，2类字符串很难全部收入词典，因此用形式化方法（正则表达式）来描述其结构模式
a)分数、日期：[0-9]+(/[0-9]+)+
b)百分数：([+|-])?[0-9]+.?[0-9]*%
c)十进制数：([0-9]+,?)+((.[0-9]+)|([0-9]+))*
d)X.X.：[A-Za-z].([A-Za-z0-9].)+
e)字母开头，点号结束：[A-Za-z]+.
3，4类词中的“&，-”等字符与一般字符(A-Z,a-z)等同处理，这样这些词要么收录到词典中，要么作为未登录词处理
5类词可通过规则识别
I’m -> I + am, Let's -> Let + us, dog's -> dog + 's
6类词可收录到词典中，分词时通过最大匹配法识别为一个词汇单位
英语词语的识别（特殊词需要相应处理）：
1)对一个带分析的字符串S,从左到右进行扫描，读入当前字符char到候选词数组W[i],并将指针pointer前移；
2)检查char是否为分隔符（事先可预定义空格等分隔符）
3)如果是分隔符，并且W[i]不是空串，将当前W[i]作为一个词汇输出，同时将S中的W[i]部分删去，清空W[i]，转入1)
4)如果不是分隔符，检查指针是否指到字符串尾部；
5)如果指针指向尾部，则将当前W[i]作为一个词汇输出，结束；
6)如果不是字符串尾部，转入1)
词形分析的任务就是对识别的词进行分析，使得每个词都能够正确地与词典中的词条对应起来。同时，也尽可能为下一步的句法分析提供一些初步的词法属性
屈折型语言的词构成形式：
{前缀}+{词根}+{后缀}+[词尾]
完成词形分析，除了上述有限状态转移图以外，还需要构建词典（含词干）、前缀表、后缀表、词尾变化规则等。
英文词尾分析一般步骤：
1)初始化：待分析的词形W,d=W的字符数，i=1，输出串R=""；
2)到词典查找W，如果找到，则R=W,转入8)
3)如果i<=(d/2), 执行4)到7), 否则转入8)
4)从W中取i个尾字字符，使W=W1+W2（取出的尾字符串）；
5)在后缀表中查找W2，如果找到，则调用规则对W1进行处理，得到W1';
6)到词典查找W1'，如果找到，则R=W1'+" "+W2,转入8)
7)如果没有找到，则i=i+1,转入3)
8)输出R，结束。
前缀和复合词分析也可以采用类似步骤完成
词法分析中的一些特例：
一些词的基本形式中含后缀
后缀：-est:biggest, -ly:strongly,beautifully
非后缀：best，only
词尾变化特殊的词
wholly->whol->whole(正确)
fully->ful->fule(full)(错误)
英语词形分析小结
在词形分析中，对于有共性的构词模式，一般可以用规则来描述，对于特殊的构词模式，一般通过在词典中列举的方式解决。
汉语分词：以整句为处理对象，目标是将一个句子中的所有的词给切出来。
汉语分词的特点：
1现代汉语的书面形式是以句子为单位连写，词与词之间无显性的分割标记。
2汉语分词和英文的Tokenization有很大区别
*最大匹配法：选取候选词是从待切分字串左边开始扫描，这种方法叫顺向（正向）最大匹配法。
1首先准备一个汉语分词词表，顺序扫描待分词的句子，将句子中的候选词按词长从大到小的顺序依次与词表中的词进行匹配，匹配成功即作为一个词输出。每次输出的词是长度最长的。
2词表中可以不收录单字词。因为多字候选词和词表中的所有词都匹配不上，就把单字当作分词结果进行输出。
流程图
最大匹配法举例：
带切分字串=“计算语言学课程是三个课时”MaxLen=5
分词词表={“计算语言学”，“课程”，“课时”}
分词过程：
1)S2="",S1="计算语言学课程是三个课时", W="计算语言学"
2)查词表，W在词表中，故S2="计算语言学/",
S1="课程是三个课时"
3)S1不为空，W="课程是三个"
4)查词表，W不在词表中，将W的最右边一个字去掉，得到W="课程是三"
5)查词表，W不在词表中，将W的最右边一个字去掉，得到W="课程是"
6)查词表，W不在词表中，将W的最右边一个字去掉，得到W="课程"
7)查词表，W在词表中，S2="计算语言学/ 课程/", S1="是三个课时"
8)S1不为空，W="是三个课时"......
22)S1为空，输出S2作为分词结果，结束。
逆向最大匹配法：
如果从右面开始扫描来选取候选词，这种方法叫做逆向最大匹配法。
最大匹配法的问题：
1)最大词长的选取
2)歧义切分
如果词典中的一个词长度超过MaxLen，则该词不会被匹配上
MaxLen取词典中最长词
会带来无谓匹配次数过多，效率低。
一般把带切分字串存在多种分词可能性，叫做分词歧义
分词歧义的种类：
1)交集型歧义
2)组合型歧义
最大匹配法小结
正向最大匹配法和逆向最大匹配法结合使用，可以发现一部分交集型歧义，但仍有一部分交集型歧义无法发现
对于组合型歧义，最大匹配法肯定无法发现。
组合型歧义
最大匹配法+歧义词表+规则
歧义词表：{“个人”，“家人”，“马上”，....}
如果最大匹配法切分的词属于歧义词表，则调用相关规则处理
IF W="个人"，Wleft=数词THEN W="个/ 人/" ENDIF
交集型歧义
对于部分交集型歧义，可以通过“回溯”机制改进最大匹配法的分词结果
最大概率法
当待切分汉字串含有多种分词结果时，计算每种分词结果的概率，并将其中概率最大的作为该字串的分词结果。
概率的计算方法
公式1)P(W)=P(w1)×P(w2)×...×P(wi)，其中W=w1w2...wi
公式2)P(wi)=wi在语料库中出现次数n/语料库的总词数N
累计概率
P'(wi)=P'(wi-1)*P(wi)
其中P'(wi)是从起点到词wi的累计概率
例如：“有意见分歧”
P'(意见)=P'(有)*P(意见)
P'(有)=P(有) ，即起点词的累计概率等于该词的概率
左邻词
设对字串从左到右进行扫描得到候选词串w1,w2,...,wi,...,wn,如果wi的首字和wi-1的尾字邻接，则称wi-1是wi的左邻词。
例如“有意见分歧”中“意见”的左邻词是“有”，“意见”和“见”都是分歧的左邻词
最佳左邻词
如果一个候选词有若干个左邻词，其中累计概率最大的候选词称为最佳左邻词
例如“有意见分歧”中“意见”的累计概率大于“见”的累计概率，因此“意见”是“分歧”的最佳左邻词
如果一个候选词只有一个左邻词，那么该左邻词同时也是最佳左邻词。
最大概率法的计算
1) 对待分词的字串S，按照从左到右的顺序列出全部候选词w1,w2,...,wi,...,wn;
2) 到词典查找每个候选词wi的概率P(wi),并记录每个候选词的所有左邻词；
3) 按照公式计算每个候选词的累计概率，并比较得到每个候选词的最佳左邻词；
4) 如果当前词wn是字串S的尾词，且累计概率P'(wn)最大，则wn就是S的终点词；
5) 从终点词开始从右到左依次输出每个词的最佳左邻词即为S的分词结果。
最大概率法小结
1) 尽管最大概率法对有些交集型歧义可得到正确结果，但对有些则无法完成正确分词
例如对字串“这事的确定不下来”运用最大概率法得到如下分词结果：
这/ 事/ 的/ 确定/ 不/ 下来/
因为上述句子中“的”的概率很高，因此“的/ 确定”作为分词结果的概率比“的确/ 定/”的概率高，导致分词结果出现错误。
2) 对于组合型歧义，最大概率法也无能为力。因为对于组合型词AB，P(AB)通常会比P(A)P(B)大，因此分词结果总是AB/,而不会是A/ B/。
例如对字串“做完作业才能看电视”运用最大概率法分词，其结果会是：
做完/ 作业/ 才能/ 看/ 电视/，正确结果应是：
做完/ 作业/ 才/ 能/ 看/ 电视/
实验一词法分析器的设计 (2) 1.1 词法分析器的结构和主要任务 (2) 1.1.1 输入输出接口 (2) 1.1.2 条件限制 (2) 1.2 词法分析程序的总体设计 (3) 1.3 词法分析程序的详细设计 (4) 1.4实验步骤 (5) 1.5输入数据 (15) 1.6结果输出 (15)
实验一词法分析器的设计 实验目的：掌握词法分析的概念，设计方法，熟悉高级语言中词法的定义，词法分析程序的编写。 实验要求：在8学时内实现SAMPLE语言的词法分析器，要求用VC窗口界面实现。 实验内容：分为4次实验完成。 1.1 词法分析器的结构和主要任务 1.1.1 输入输出接口 图1-1词法分析器的输入输出界面 词法分析程序的主要任务是从左到右扫描每行源程序，拼成单词，换成统一的内部表示(token)输出，送给语法分析器。具体包括： 1.组织源程序的输入； 2.按规则拼单词，并转换成二元形式； 3.滤掉空白符，跳过注释、换行符及一些无用的符号(如字符常数的引号) 4.进行行列计数，用于指出出错的行列号，并复制出错部分； 5.列表打印源程序； 6.发现并定位词法错误； 7.生成符号表。 token文件和符号表用作语法分析的输入部分。 1.1.2 条件限制 本实验可以作如下假定： (1) 假定SAMPLE语言采用自由格式书写； (2) 可以使用注解，用/*……*/或者{……}标识，但注解不能插在单词内部，注解要在一行内结束，若一行结束，没有遇到注释后面的结束标记，自动认为注释也结束； (3) 一行可以有多个语句，一个语句也可以分布在多行中，单词之间和语句之间可以插入任意空格，单词中间不能有空白符号，单词中间也不能有回车换行符，即单词不能跨行书写； (4) 关键字都是保留字。
实验一词法分析 一、实验目的 通过设计编制调试一个具体的词法分析程序，加深对词法分析原理的理解。并掌握在对程序设计语言源程序进行扫描过程中将其分解为各类单词的词法分析方法。 编制一个读单词过程，从输入的源程序中，识别出各个具有独立意义的单词，即基本保留字、标识符、常数、运算符、分隔符五大类。并依次输出各个单词的内部编码及单词符号自身值。（遇到错误时可显示“Error”，然后跳过错误部分继续显示） 二、实验要求 使用一符一种的分法 关键字、运算符和分界符可以每一个均为一种 标识符和常数仍然一类一种 三、实验内容 功能描述： 1、待分析的简单语言的词法 （1）关键字： begin if then while do end （2）运算符和界符： := + –* / < <= <> > >= = ; ( ) # （3）其他单词是标识符（ID）和整型常数（NUM），通过以下正规式定义： ID=letter（letter| digit）* NUM=digit digit * （4）空格由空白、制表符和换行符组成。空格一般用来分隔ID、NUM,运算符、界符和关键字，词法分析阶段通常被忽略。 2、各种单词符号对应的种别码 图 1
程序结构描述： 图 2 四、实验结果 输入begin x:=9: if x>9 then x:=2*x+1/3; end # 后经词法分析输出如下序列：(begin 1)(x 10)(：17)(= 18)(9 11)(；26)(if 2)……如图3所示：
图3 输入private x:=9;if x>0 then x:=2*x+1/3; end#后经词法分析输出如下序列：(private 10)(x 10)(：17)(= 18)(9 11)(；26)(if 2)……如图4所示： 图4 显然，private是关键字，却被识别成了标示符，这是因为图1中没有定义private关键字的种别码，所以把private当成了标示符。 输入private x:=9;if x>0 then x:=2*x+1/3; @ end#后经词法分析输出如下序列：(private 10)(x 10)(：17)(= 18)(9 11)(；26)(if 2)……如图5所示
实验一词法分析程序设计与实现 一、实验目的及内容 调试并完成一个词法分析程序，加深对词法分析原理的理解。 二、实验原理（状态转换图） 1、C语言子集 （1）关键字： begin if then while do end 所有关键字都是小写。 （2）运算符和界符： := + – * / < <= <> > >= = ; ( ) # （3）其他单词是标识符（ID）和整型常数（NUM），通过以下正规式定义：ID=letter（letter| digit）* NUM=digit digit * （4）空格由空白、制表符和换行符组成。空格一般用来分隔ID、NUM,运算符、界符和关键字，词法分析阶段通常被忽略。 2、各种单词符号对应的种别码
3、词法分析程序的功能 输入：所给文法的源程序字符串。 输出：二元组（syn，token或sum）构成的序列。 其中：syn为单词种别码； token为存放的单词自身字符串； sum为整型常数。 二、软件平台及工具 PC机以及VISUAL C++6.0软件。 三、实验方法、步骤（或：程序代码或操作过程）（1）程序代码： #include
词法分析小结 词法分析是编译器工作的第一阶段，它的工作就是从输入（源代码）中取得token，以作为parser（语法分析）的输入，一般在词法分析阶段都会把一些无用的空白字符（whitespace，即空格、tab和换行）以及注释剔除，以降低下一步分析的复杂度，词法分析器一般会提供一个gettoken()这样的方法，parser可以在做语法分析时调用词法分析器的这个方法来得到下一个token，所以词法分析器并不是一次性遍历所有源代码，而是采取这种on-demand的方式：只在parser需要时才工作，并且每次只取一个token。 token和lexeme 首先，token不等于lexeme。token和lexeme的关系就类似于面向对象语言中“类”和“实例”（或“对象”）之间的关系，这个用中文不知该如何解释才好，比如语言中的变量a和b，它们都属于同一种token：identifier，而a的lexeme是”a”，b则是”b”，而每个关键字都是一种token。token可以附带有一个值属性，例如变量a，当调用词法分析器的gettoken()时，会返回一个identifier类型的token，这个token带有一个属性“a”，属性可以是多样的，例如表示数字的token
可以带有一个表示数字值的属性，它是整型的。 如下代码： intage=23; intcount=50; 可以依次提取出8个token：int(值为”int”)，id(值为”age”)，assign(值为”=”)，number(值为整型数值23)，int(值为”int”)，id(值为”count”)，assign(值为”=”)，number(值为50) 正则表达式 正则表达式可以用来描述字符串模式，例如我们可以用digit+来表示number的token，其中digit表示单个数字（这里说正则表达式并不完全和实现的正则引擎所识别的正则表达式等价，这里只是为了描述问题而已）。 然而像c语言的的多行注释，用正则表达式来描述就比较麻烦，此时更倾向于直接用有穷自动机（finiteautomaton）来描述，因为用它来描述非常直观且很容易。
实验一词法分析实验报告
实验一词法分析 一、实验目的 通过设计编制调试一个具体的词法分析程序，加深对词法分析原理的理解。并掌握在对程序设计语言源程序进行扫描过程中将其分解为各类单词的词法分析方法。 编制一个读单词过程，从输入的源程序中，识别出各个具有独立意义的单词，即基本保留字、标识符、常数、运算符、分隔符五大类。并依次输出各个单词的内部编码及单词符号自身值。（遇到错误时可显示“Error”，然后跳过错误部分继续显示） 二、实验要求 使用一符一种的分法 关键字、运算符和分界符可以每一个均为一种标识符和常数仍然一类一种 三、实验内容 功能描述： 1、待分析的简单语言的词法 （1）关键字：
begin if then while do end （2）运算符和界符： := + –* / < <= <> > > = = ; ( ) # （3）其他单词是标识符（ID）和整型常数（NUM），通过以下正规式定义： ID=letter（letter| digit）* NUM=digit digit * （4）空格由空白、制表符和换行符组成。空格一般用来分隔ID、NUM,运算符、界符和关键字，词法分析阶段通常被忽略。 2、各种单词符号对应的种别码 图 1
程序结构描述： 是 否 是 调用scanner() 字母 数 其他 运算符、 符号 界符等符号 否 是 图 2 四、实验结果 输入begin x:=9: if x>9 then x:=2*x+1/3; end # 后经词法分析输出如 变量忽略 是否输入返 拼数 syn=11返 对不同报拼字是否关syn 为对syn=10
1、实验目的 1、为初等函数运算语言构造词法分析器。 2、掌握生成词法分析器的方法，加深对词法分析原理的理解。 3、掌握设计、编制并调试词法分析程序的思想和方法 2、实验内容 一、根据下面的要求设计初等函数运算语言的词法模式，并用正则式表达出来 1、初等函数运算语言的常量为实数类型，其定义方式为实数的最一般书写方式，如： 123.321。具体要求：不支持整数部分大于。时首数字为0；不支持小数点后结尾为 0；不支持科学记数法；不支持仅为整数时有小数点；支持负数符号，不支持正数 符号。 2、初等函数运算语言的变量采用与C语言的标识符定义一样的方式：首字符为字母或 下划线；其他的为字母、数字及下划线的混合串；区分大小写；变量长度不超过32 个字符。 3、初等函数运算语言需要处理的函数仅为表一中所列举的内容。函数的格式及参数内 容也如表一所示。 4、初等函数运算语言支持四则运算，其计算的符号与C语言相同，为：+-*/。 5、初等函数运算语言的合法的分隔符包括：空格、制表符、、分行符圆括号（左、右）、 分号。其中空格、制表符、分行符可以出现在任何两个不同的单词中间；圆括号（左、右）用于表达式中，用于改变运算的优先级，以及标识函数的参数；分号用于标识一个语句的结束。 6、初等函数运算语言支持的常量还包括:PI,Eo其中,PI为圆周率,E为自然常数。 二、将正则式转化为最小DFA,给出该DFA的形式化表示和图形表示。 三、根据DFA给出状态转换表。 四、给出初等函数运算语言的记号表，即词法分析中，语言中的记号将分为多少类，每一类型的编码、类型、属性等内容是什么。 五、编写词法分析器，将输入的字符串转化成为记号流，便于后续的语法分析工作。要求词法分析器中能够识别词法错误。
编译原理实验2 词法分析器 一、实验目的 1. 通过设计编制调试一个具体的词法分析程序，加深对词法分析原理的理解。 2. 掌握在对程序设计语言源程序进行扫描过程中将其分解为各类单词的词法分析方法。 3. 编制一个读单词的程序，从输入的源程序中，识别出各个具有独立意义的单词，即基本保留字、标识符、常数、运算符和分隔符五大类。并依次输出各个单词的内部编码及单词符号自身值。（遇到错误时可显示“Error”，然后跳过错误部分继续显示） 二、词法分析的基础知识 1. 词法分析器的功能和输出格式 词法分析器的功能是输入源程序，输出单词符号。词法分析器的单词符号常常表示成以下的二元式(单词种别码，单词符号的属性值)。在本实验中，采用的是一类符号一种别码的方式。 标识符的BNF表示： <标识符>-> <字母><字母数字串> ） <字母数字串>-><字母><字母数字串>|<数字><字母数字串>|ε 无符号整数的BNF表示： <无符号整数>-> <数字><数字串> <数字串>-> <数字><数字串> |ε 运算符的BNF表示： <加法运算符>-> + <减法运算符>-> - <大于关系运算符>-> > <大于等于关系运算符>-> >= 2. 超前搜索 ; 词法分析时，常常会用到超前搜索方法。如当前待分析字符串为“a > i”，当前字符为“>”，此时，分析器到底是将其分析为大于关系运算符还是大于等于关系运算符呢显然，只有知道下一个字符是什么才能下结论。于是分析器读入下一个字符“+”，这时可知应将“>”解释为大于运算符。但此时，超前读了一个字符“i”，所以要回退一个字符，词法分析器才能正常运行。在分析标识符，无符号整数等时也有类似情况。 三、程序要求 1. 程序输入示例： 如源程序为C语言，输入如下一段： main() { int a, b; a = 10; b = a+20; } ； 2. 程序输出示例：
编译原理实验报告 实验名称：分析调试语义分析程序 TEST抽象机模拟器完整程序 保证能用！！！！！ 一、实验目的 通过分析调试TEST语言的语义分析和中间代码生成程序，加深对语法制导翻译思想的理解，掌握将语法分析所识别的语法范畴变换为中间代码的语义翻译方法。 二、实验设计 程序流程图
extern int TESTScan(FILE *fin,FILE *fout); FILE *fin,*fout; //用于指定输入输出文件的指针 int main() { char szFinName[300]; char szFoutName[300]; printf("请输入源程序文件名（包括路径）:"); scanf("%s",szFinName); printf("请输入词法分析输出文件名（包括路径）："); scanf("%s",szFoutName); if( (fin = fopen(szFinName,"r")) == NULL) { printf("\n打开词法分析输入文件出错！\n"); return 0; } if( (fout = fopen(szFoutName,"w")) == NULL) { printf("\n创建词法分析输出文件出错！\n"); return 0; } int es = TESTScan(fin,fout); fclose(fin); fclose(fout); if(es > 0) printf("词法分析有错，编译停止！共有%d个错误！\n",es); else if(es == 0) { printf("词法分析成功！\n"); int es = 0;
词法分析器 一、实验目的： 通过设计编制调试一个具体的词法分析程序，加深对词法分析原理的理解。并掌握在对程序设计语言源程序进行扫描过程中将其分解为各类单词的词法分析方法。 编制一个读单词过程，从输入的源程序中，识别出各个具有独立意义的单词，即基本保留字、标识符、常数、运算符、分隔符五大类。并依次输出各个单词的内部编码及单词符号自身值。 二、实验要求 如源程序为C语言。输入如下一段：Array main() { int a,b; a = 10; b = a + 20; }# 要求输出如右图。 要求： 1、将单词分为五种 识别关键字：main、if、int、for、while、do、return、break、continue； 单词种别码为1。 标识符；单词种别码为2。 常数为无符号整形数；单词种别码为3。 运算符包括：+、-、*、/、=、>、<、>=、<=、!= ； 单词种别码为4。 分隔符包括：,、;、{、}、(、)；单词种别码为5。 2、使用一符一种的分法 关键字、运算符和分界符可以每一个均为一种 标识符和常数仍然一类一种 三、实验内容 1、功能描述 改程序是一个实现词法分析的功能，能识别5种单词，其他单词报错。 2、程序结构描述 int IsKey(char *Word)关键字匹配函数,查询是否为关键字，若是，返回值为1，否则为0。 int IsAlpha(char c) 查看是否为字母，若是，返回值为1，否则为0。 int IsNum(char c) 查看是否为数字，若是，返回值为1，否则为0。 void scanner(FILE *fp) 扫描函数，扫描程序中的字符串并调用上述三种函数检查是否是字母、 数字，是否是关键字，并输出。 fseek（fp，-1，1）回退一个字符。 fgetc（fp）从数据流中区下一个字符。 fopen 文件打开函数，返回指向文件第一个字符的指针 四、实验结果 测试内容为 main() {
实验二：词法分析 一、实验目的：编制一个读单词过程，从输入的源程序中，识别出各个具有独立意义的单词， 即基本保留字、标识符、常数、运算符、分隔符五大类。并依次输出各个单词的内部编码及 Error”，然后跳过错误部分继续显示） 二、估计实验时间：1.课余准备15小时；2.上机二次4小时；3.完成实验报告5小时。 三、实验过程和指导： （一）准备：1.阅读课本有关章节，花一周时间明确语言的语法，写出基本保留字、标识符、 常数、运算符、分隔符和程序例。2.初步编制好程序。3.准备好多组测试数据。 （二）上课上机：将源代码拷贝到机上调试，发现错误，再修改完善。第二次上机调试通过。 （三）程序要求：Array程序输入/输出示例： 如源程序为C语言。输入如下一段： main() { int a,b; a = 10; b = a + 20; } 要求输出如右图。 要求： 识别保留字：if、int、for、while、do、return、break、 其他的都识别为标识符；
常数为无符号整形数； 运算符包括：+、-、*、/、=、>、<、>=、<=、!= 分隔符包括：,、;、{、}、(、) 程序思路（仅供参考）： 0.定义部分：定义常量、变量、数据结构。 1.初始化：从文件将源程序全部输入到字符缓冲区中。 2.取单词前：去掉多余空白。 3.取单词后：去掉多余空白（可选，看着办）。 4.取单词：利用实验一的成果读出单词的每一个字符，组成单词，分析类型。（关键是如何判断取单词结束？取到的单词是什么类型的单词？） 5.显示结果。 （四）练习该实验的目的和思路： 程序开始变得复杂起来，可能是大家以前编过的程序中最复杂的，但相对于以后的程序来说还是简单的。因此要认真把握这个过渡期的练习。程序规模大概为200行。本实验和以后的实验相关。通过练习，掌握对字符进行灵活处理的方法。 （五）为了能设计好程序，主意以下事情： 1.模块设计：将程序分成合理的多个模块（函数），每个模块做具体的同一事情。 2.写出（画出）设计方案：模块关系简图、流程图、全局变量、函数接口等。 3.编程时注意编程风格：空行的使用、注释的使用、缩进的使用等。 四、上交： 1.程序源代码；
词法分析器实验报告 词法分析器设计 一、实验目的： 对C语言的一个子集设计并实现一个简单的词法分析器，掌握利用状 态转换图设计词法分析器的基本方法。利用该词法分析器完成对源程 序字符串的词法分析。输出形式是源程序的单词符号二元式的代码， 并保存到文件中。 二、实验内容： 1. 设计原理 词法分析的任务：从左至右逐个字符地对源程序进行扫描，产生一个个单词符号。 理论基础：有限自动机、正规文法、正规式 词法分析器(Lexical Analyzer) 又称扫描器(Scanner)：执行词法分析的程序 2. 词法分析器的功能和输出形式 功能:输入源程序、输出单词符号 程序语言的单词符号一般分为以下五种：关键字、标识符、常数、运算符,界符 3. 输出的单词符号的表示形式: 单词种别用整数编码，关键字一字一种，标识符统归为一种，常数一种，各种符号各一种。 4. 词法分析器的结构 单词符号 5. 状态转换图实现
三、程序设计 1．总体模块设计 /*用来存储目标文件名*/ string file_name; /*提取文本文件中的信息。*/ string GetText(); /*获得一个单词符号,从位置i开始查找。并且有一个引用参数j，用来返回这个单词最后一个字符在str的位置。*/ string GetWord(string str,int i,int& j); /*这个函数用来除去字符串中连续的空格和换行 int DeleteNull(string str,int i); /*判断i当前所指的字符是否为一个分界符，是的话返回真，反之假*/ bool IsBoundary(string str,int i); /*判断i当前所指的字符是否为一个运算符，是的话返回真，反之假*/ bool IsOperation(string str,int i);
词法分析设计 1. 实验目的 通过本实验的编程实践，了解词法分析的任务，掌握词法分析程序设计的原理和构造方法，对编译的基本概念、原理和方法有完整的和清楚的理解，并能正确地、熟练地运用。 2. 实验内容 用C++语言实现对C++语言子集的源程序进行词法分析。通过输入源程序从左到右对字符串进行扫描和分解，依次输出各个单词的内部编码及单词符号自身值；若遇到错误则显示“Error”，然后跳过错误部分继续显示；同时进行标识符登记符号表的管理。 3. 实验原理 本次实验采用NFA->DFA->DFA0的过程: 对待分析的简单的词法（关键词/id/num/运算符/空白符等）先分别建立自己的FA，然后将他们用产生式连接起来并设置一个唯一的开始符，终结符不合并。 待分析的简单的词法 （1）关键字： "asm","auto","bool","break","case","catch","char","class","
const","const_cast"等 （2）界符（查表） ";",",","(",")","[","]","{","}" （3）运算符 "*","/","%","+","-","<<","=",">>","&","^","|","++","--"," +=","-=","*=","/=","%=","&=","^=","|=" relop： （4）其他单词是标识符（ID）和整型常数（SUM），通过正规式定义。 id/keywords: digit: （5）空格有空白、制表符和换行符组成。空格一般用来分隔ID、SUM、运算符、界符和关键字，词法分析阶段通常被忽略。
《词法分析》实验报告
目录 目录错误!未定义书签。 1 实验目的错误!未定义书签。 2 实验内容错误!未定义书签。 TINY计算机语言描述错误!未定义书签。 实验要求错误!未定义书签。 3 此法分析器的程序实现错误!未定义书签。状态转换图错误!未定义书签。 程序源码错误!未定义书签。 实验运行效果截图错误!未定义书签。 4 实验体会错误!未定义书签。
实验目的 1、学会针对DFA转换图实现相应的高级语言源程序。 2、深刻领会状态转换图的含义，逐步理解有限自动机。 3、掌握手工生成词法分析器的方法，了解词法分析器的内部工作原理。 实验内容 TINY计算机语言描述 TINY计算机语言的编译程序的词法分析部分实现。 从左到右扫描每行该语言源程序的符号，拼成单词，换成统一的内部表示（token）送给语法分析程序。 为了简化程序的编写，有具体的要求如下： 1、数仅仅是整数。 2、空白符仅仅是空格、回车符、制表符。 3、代码是自由格式。 4、注释应放在花括号之内，并且不允许嵌套 ＴＩＮＹ语言的单词 要求实现编译器的以下功能 1、按规则拼单词,并转换成二元式形式 2、删除注释行 3、删除空白符(空格、回车符、制表符) 4、列表打印源程序，按照源程序的行打印，在每行的前面加上行号，并且打印出每行包含的记号的二元形式 5、发现并定位错误 词法分析进行具体的要求 1、记号的二元式形式中种类采用枚举方法定义；其中保留字和特殊字符是每个都一个种类，标示符自己是一类，数字是一类；单词的属性就是表示的字符串值。 2、词法分析的具体功能实现是一个函数GetToken()，每次调用都对剩余的字符串分析得到一个单词或记号识别其种类，收集该记号的符号串属性，当识别一个单词完毕，采用返回值的形式返回符号的种类，同时采用程序变量的形式提供当前识别出记号的属性值。这样配合语法分析程序的分析需要的记号及其属性，生成一个语法树。
实验2 词法分析程序的设计 一、实验目的 掌握计算机语言的词法分析程序的开发方法。 二、实验内容 编制一个能够分析三种整数、标识符、主要运算符和主要关键字的词法分析程序。 三、实验要求 1、根据以下的正规式，编制正规文法，画出状态图； 标识符<字母>(<字母>|<数字字符>)* 十进制整数0 | (（1|2|3|4|5|6|7|8|9）（0|1|2|3|4|5|6|7|8|9）*) 八进制整数0（1|2|3|4|5|6|7）（0|1|2|3|4|5|6|7）* 十六进制整数0x（0|1|2|3|4|5|6|7|8|9|a|b|c|d|e|f）（0|1|2|3|4|5|6|7|8|9|a|b|c|d|e|f）* 运算符和界符+ - * / > < = ( ) ； 关键字if then else while do 2、根据状态图，设计词法分析函数int scan( )，完成以下功能： 1）从文本文件中读入测试源代码，根据状态转换图，分析出一个单词， 2）以二元式形式输出单词<单词种类，单词属性> 其中单词种类用整数表示： 0：标识符 1：十进制整数 2：八进制整数 3：十六进制整数 运算符和界符，关键字采用一字一符，不编码 其中单词属性表示如下： 标识符，整数由于采用一类一符，属性用单词表示 运算符和界符，关键字采用一字一符，属性为空 3、编写测试程序，反复调用函数scan( )，输出单词种别和属性。 四、实验环境 PC微机 DOS操作系统或Windows 操作系统 Turbo C 程序集成环境或Visual C++ 程序集成环境 五、实验步骤 1、根据正规式，画出状态转换图；
编译原理实验一 姓名：朱彦荣 学号： 专业：软件工程2 实验题目：词法分析 完成语言：C/C++ 上级系统：VC++6.0 日期：2015/11/7 词法分析 设计题目：手工设计c语言的词法分析器 （可以是c语言的子集） 设计内容： 处理c语言源程序，过滤掉无用符号，判断源程序中单词的合法性，并分解出正确的单词，以二元组形式存放在文件中。 设计目的： 了解高级语言单词的分类，了解状态图以及如何表示并识别单词规则，掌握状态图到识别程序的编程。 结果要求：课程设计报告。 完成日期：第十五周提交报告 一．分析 要想手工设计词法分析器，实现C语言子集的识别，就要明白什么是词法
主要是对源程序进行编译预处理（去除注释、无用的回车换行找到包含的文件等）之后，对整个源程序进行分解，分解成一个个单词，这些单词有且只有五类，分别是标识符、保留字、常数、运算符、界符。以便为下面的语法分析和语义分析做准备。可以说词法分析面向的对象是单个的字符，目的是把它们组成有效的单词（字符串）；而语法的分析则是利用词法分析的结果作为输入来分析是否符合语法规则并且进行语法制导下的语义分析，最后产生四元组(中间代码)，进行优化（可有可无）之后最终生成目标代码。可见词法分析是所有后续工作的基础，如果这一步出错，比如明明是‘<=’却被拆分成‘<’和‘=’就会对下文造成不可挽回的影响。因此，在进行词法分析的时候一定要定义好这五种符号的集合。下面是我构造的一个C语言子集。 第一类：标识符letter(letter | digit)* 无穷集 第二类：常数(digit)+ 无穷集 第三类：保留字(32) auto break case char const continue default do double else enum extern float for goto if int long register return short signed sizeof static struct switch typedef union unsigned void volatile while 第四类：界符‘/*’、‘//’、() { } [ ] " " ' 等 第五类：运算符<、<=、>、>=、=、+、-、*、/、^、等 对所有可数符号进行编码： <$,0>
词法分析器的实现 开篇 编译，简单的说，就是把源程序转换为可执行程序。从hello world 说程序运行机制里面简单的说明了程序运行的过程，以及一个程序是如何一步步变成可执行文件的。在这个过程中，编译器做了很多重要的工作。对底层该兴趣的我，自然的，也就迫切想搞清楚编译的内部实现，也就是编译的原理。 这篇文章主要说的是编译器前端，词法分析器的原理，最后会给出一个词法分析器的简单实现。 介绍 编译简单的说，就是把源程序转化为另一种形式的程序,而其中关键的部分就是理解源程序所要表达的意思，才能转化为另一种源程序。 可以用一个比喻来说明问题：人A和人B想要交谈，但是他们都不知道彼此的语言，这就需要一个翻译C，同时懂得A和B的语言。有了C做中间层，A和B才能正常交流。C的作用就有点像编译器，它必须能理解源程序所要表达的意思，才能把信息传递给另一个。 编译器也一样，它的输入是语言的源文件（一般可以是文本文件）对于输入的文件，首先要分离出这个输入文件的每个元素（关键字、变量、符号、、） 然后根据语言的文法，分析这些元素的组合是否合法，以及这些组合所表达的意思。 程序设计语言和自然语言不一样，都是用符号来描述，每个特定的符号表示特定的意思，而且程序设计语言是上下文无关的。上下文无关就是某一个特定语句所要表达的意思和它所处的上下文没有关系，只有它自身决定。 这篇博文主要说的就是词法分析，也就是把输入的符号串整理成特定的词素。 词法分析 定义： 词法分析器的功能输入源程序，按照构词规则分解成一系列单词符号。单词是语言中具有独立意义的最小单位，包括关键字、标识符、运算符、界符和常量等 (1) 关键字是由程序语言定义的具有固定意义的标识符。例如，Pascal 中的begin，en d，if，while都是保留字。这些字通常不用作一般标识符。 (2) 标识符用来表示各种名字，如变量名，数组名，过程名等等。 (3) 常数常数的类型一般有整型、实型、布尔型、文字型等。 (4) 运算符如+、-、*、/等等。 (5) 界符如逗号、分号、括号、等等。 输出：
词法分析器实验报告 一、实验目的及要求 本次实验通过用C语言设计、编制、调试一个词法分析子程序，识别单词，实现一个C语言词法分析器，经过此过程可以加深对编译器解析单词流的过程的了解。 运行环境： 硬件：windows xp 软件：visual c++6.0 二、实验步骤 1.查询资料，了解词法分析器的工作过程与原理。 2.分析题目，整理出基本设计思路。 3.实践编码，将设计思想转换用c语言编码实现，编译运行。 4.测试功能，多次设置包含不同字符，关键字的待解析文件，仔细察看运行结果，检测该分析器的分析结果是否正确。通过最终的测试发现问题，逐渐完善代码中设置的分析对象与关键字表，拓宽分析范围提高分析能力。 三、实验内容 本实验中将c语言单词符号分成了四类：关键字key（特别的将main说明为主函数）、普通标示符、常数和界符。将关键字初始化在一个字符型指针数组*key[]中，将界符分别由程序中的case列出。在词法分析过程中，关键字表和case列出的界符的内容是固定不变的（由程序中的初始化确定），因此，从源文件字符串中识别出现的关键字，界符只能从其中选取。标识符、常数是在分析过程中不断形成的。 对于一个具体源程序而言，在扫描字符串时识别出一个单词，若这个单词的类型是关键字、普通标示符、常数或界符中之一，那么就将此单词以文字说明的形式输出．每次调用词法分析程序，它均能自动继续扫描下去，形成下一个单词，直到整个源程序全部扫描完毕，从而形成相应的单词串。 输出形式例如：void $关键字
流程图、程序流程图：
程序： #include
一、创建环境 1.将java拷贝到c:盘根目录下。 2.设置环境变量： 在“计算机”图标上单击右键--------属性------高级系统设置------环境变量-----系统变量 path中设置内容为： c:\java\jdk1.6.0_10\bin; classpath中设置内容为： c:\java\jdk1.6.0_10\lib\dt.jar; c:\java\jdk1.6.0_10\lib\tools.jar; c:\java\jre6\lib\rt.jar; .; c:\1000; 3.在c盘要建立1000 文件夹，将SimpleLexer文件夹复制到该文件 夹内（注意字母的大小写）。 二、词法分析 1. 运行cmd 命令 输入cmd回车
输入cd\ 回车，使输入符号到c:\> 状态 再输入cd 1000 回车。进入到c:\1000> 状态 2.编译程序 先编译Token.java文件，再编译Main.java文件，最后编译lexer.java 文件。如下图所示。 3.运行程序 test.in 是词法分析器的输入程序（即输入的源程序，此程序由学生给出）。运行后，自动在1000目录下生成result.out文件。（test.in 和result.out文件都可由记事本查看内容）
test.in 文件内容如下： result.out文件内容如下：
如果test.in中输入有误，则运行时提示：
4.编译原理课程设计内容如下：(注：每个同学从下列关键字中各选 五个，从运算符中各选四个，标识符和界符都要设计) 单词符号分为关键字，标识符，运算符，界符等： 关键字：begin end if then else while do void switch catch try case for continue break default return long short int float double char abstract Boolean
《词法分析》 实验报告 目录 目录 0 1 实验目的 (1) 2 实验内容 (1) 2、1 TINY计算机语言描述 (1) 2、2 实验要求 (1) 3 此法分析器的程序实现 (2) 3、1 状态转换图 (2) 3、2 程序源码 (3) 3、3 实验运行效果截图 (8) 4 实验体会 (8)
1实验目的 1、学会针对DFA转换图实现相应的高级语言源程序。 2、深刻领会状态转换图的含义,逐步理解有限自动机。 3、掌握手工生成词法分析器的方法,了解词法分析器的内部工作原理。 2实验内容 2.1TINY计算机语言描述 TINY计算机语言的编译程序的词法分析部分实现。 从左到右扫描每行该语言源程序的符号,拼成单词,换成统一的内部表示(token)送给语法分析程序。 为了简化程序的编写,有具体的要求如下: 1、数仅仅就是整数。 2、空白符仅仅就是空格、回车符、制表符。 3、代码就是自由格式。 4、注释应放在花括号之内,并且不允许嵌套 ＴＩＮＹ语言的单词 2.2实验要求 要求实现编译器的以下功能 1、按规则拼单词,并转换成二元式形式 2、删除注释行 3、删除空白符(空格、回车符、制表符)
4、列表打印源程序,按照源程序的行打印,在每行的前面加上行号,并且打印出每行包含的记号的二元形式 5、发现并定位错误 词法分析进行具体的要求 1、记号的二元式形式中种类采用枚举方法定义;其中保留字与特殊字符就是每个都一个种类,标示符自己就是一类,数字就是一类;单词的属性就就是表示的字符串值。 2、词法分析的具体功能实现就是一个函数GetToken(),每次调用都对剩余的字符串分析得到一个单词或记号识别其种类,收集该记号的符号串属性,当识别一个单词完毕,采用返回值的形式返回符号的种类,同时采用程序变量的形式提供当前识别出记号的属性值。这样配合语法分析程序的分析需要的记号及其属性,生成一个语法树。 3、标示符与保留字的词法构成相同,为了更好的实现,把语言的保留字建立一个表格存储,这样可以把保留字的识别放在标示符之后,用识别出的标示符对比该表格,如果存在该表格中则就是保留字,否则就是一般标示符。 3此法分析器的程序实现 3.1状态转换图 图1 TINY语言的确定有限自动机(DFA)
词法分析实验报告 中北大学软件学院 实验报告 专业课程名称学号姓名 辅导教师成绩 实验日期实验时间 1实验名称 :词法分析器的设计与实现 2、实验目的 (1)掌握C语言单词符号的划分、正规式、状态转换图及词法分析器的实现。 (2)掌握词法分析程序的作用。 3、实验要求 (1)对任给的一个C语言源程序，能够滤掉空格、回车换行符、tab键及注释。 (2)识别各类单词符号，如关键字、标识符、运算符、常数、界符，结果以二元式形式输出，并构造符号表。 (3)输出有词法错误的单词及所在行号。(在此阶段只能识别有限的词法错误) 4、实验原理 根据扫描到的单词符号的第一个字符的种类，分别转到相应的程序进行处理。这些程序的功能就是识别以相应字符开头的各类单词符号。 5、实验步骤 (1)根据C语言各类单词的正规式，构造能识别各类单词的状态转换图。 (2)根据状态转换图，构造识别各类单词的词法分析器。 6、状态转换图及词法分析程序 (1)标识符(ID)和整型常数(NUM)的正规式如下:
ID = _ | letter (letter | digit)* NUM = digit digit* 其中标识符的状态转换图为: 其词法分析程序为: if(((ch>='A')&&(ch<='Z'))||((ch>='a')&&(ch<='z'))||(ch=='_')) { /*以字母开头*/ while(((ch>='A')&&(ch<='Z'))||((ch>='a')&&(ch<='z'))||(ch =='_')||((ch>='0')&&(ch<='9'))) { array[i++]=ch; ch=fgetc(fpin); } word=(char *)malloc((i+1)*sizeof(char)); memcpy(word,array,i); word[i]='\0'; is_id_key(word); if(ch!=EOF) fseek(fpin,-1L,SEEK_CUR); } 常数的状态转换图为: 其词法分析程序为: else if(ch>='0'&&ch<='9') { /*以数字开头*/ while(ch>='0'&&ch<='9')
南昌大学实验报告一 学生姓名：学号：专业班级：网络工程091 实验类型：□验证█综合□设计□创新实验日期：2012-4-12 实验成绩： 实验1 词法分析程序的设计 一、实验目的 掌握计算机语言的词法分析程序的开发方法。 二、实验内容 编制一个能够分析三种整数、标识符、主要运算符和主要关键字的词法分析程序。 三、实验要求 1、根据以下的正规式，编制正规文法，画出状态图； 标识符<字母>(<字母>|<数字字符>)* 十进制整数（0 | （1|2|3|4|5|6|7|8|9））（0|1|2|3|4|5|6|7|8|9）* 如有余力，则进一步分析八进制和十六进制整数，其正规式如下： 八进制整数0（1|2|3|4|5|6|7）（0|1|2|3|4|5|6|7）* 十六进制整数0x（0|1|2|3|4|5|6|7|8|9|a|b|c|d|e|f）（0|1|2|3|4|5|6|7|8|9|a|b|c|d|e|f）* 运算符和界符+ - * / > < = <= >= ( ) ；{ } 关键字main if then else while do int (可根据需要添加) 2、根据状态图，设计词法分析函数int scan( )，完成以下功能： 1）从文本文件中读入测试源代码，根据状态转换图，分析出一个单词， 2）以二元式形式输出单词<单词种类，单词属性> 其中单词种类用整数表示： 0：标识符 1：十进制整数 2：八进制整数 3：十六进制整数 运算符和界符，关键字采用一字一符，不编码 其中单词属性表示如下： 标识符，整数由于采用一类一符，属性用单词表示 运算符和界符，关键字采用一字一符，属性为空 3、编写测试程序，反复调用函数scan( )，输出单词种别和属性。 四、实验环境 PC微机 DOS操作系统或Windows 操作系统 Turbo C 程序集成环境或Visual C++ 程序集成环境 五、实验步骤