2-词法分析

自然语言处理的词法分析与句法分析自然语言处理是人工智能领域的一个重要分支，旨在使计算机能够理解和处理人类语言。

其中，词法分析和句法分析是自然语言处理的两个主要任务。

词法分析负责将一段文本分解成单词或词素，而句法分析则对文本的语法结构进行分析和解析。

本文将详细介绍词法分析和句法分析的基本概念、方法和应用。

一、词法分析1. 概念和任务词法分析是自然语言处理中的一个基础任务，主要目标是将一段文本拆分成一个个单词或词素。

词法分析可以看作是自然语言处理中最初的处理环节，在很大程度上决定了后续处理任务的难度和准确性。

具体而言，词法分析的任务包括以下几个方面：（1）分词：将连续的文本流分成一个个独立的单词。

分词在汉语处理中尤为重要，因为汉语中没有像英语中的空格来明确标识词之间的边界。

（2）词性标注：对每个单词进行词性标注，即确定它的词性类别（如名词、动词、形容词等）。

词性标注常常需要结合上下文语境进行判断。

（3）词干提取：将一个单词的派生形式还原为它的词干或原型形式。

例如，“running”和“ran”都可以还原为“run”。

2. 方法和技术（1）规则法：基于规则的词法分析方法依靠人工定义的词法规则和规则库进行分析。

这种方法简单直观，易于理解和实现，但对规则的编写需要大量的人工劳动，并且规则难以适应复杂多变的语言现象。

（2）统计法：统计法通过学习大量的语料库数据，利用统计模型来进行词法分析。

常见的统计模型包括隐马尔可夫模型（Hidden Markov Model，HMM）、最大熵模型（Maximum Entropy Model，MEM）、条件随机场（Conditional Random Field，CRF）等。

统计法的优点是能够自动学习语言规律，适应性较好，但需要大量的训练数据和计算资源。

（3）深度学习法：深度学习方法基于神经网络，通过多层的神经网络结构来进行词法分析。

典型的深度学习模型包括循环神经网络（Recurrent Neural Network，RNN）、长短期记忆网络（Long Short-Term Memory，LSTM）等。

常见的两类程序设计语言处理程序一、编译型语言处理程序1. 编译型语言的定义编译型语言是指在程序运行之前需要经过编译器将源代码转化为机器语言的一种程序设计语言。

编译型语言的处理程序主要包括以下几个步骤：2. 词法分析词法分析是编译型语言处理程序的第一步，主要将源代码划分为一个个单词，也称为词法单元。

词法分析器会根据编程语言的语法规则，将代码中的关键字、标识符、操作符等进行识别和分类。

3. 语法分析语法分析是编译型语言处理程序的第二步，主要是对词法单元进行语法分析，判断代码的语法是否符合语言规范。

语法分析器会根据语法规则构建语法树，以便后续的语义分析和代码生成。

4. 语义分析语义分析是编译型语言处理程序的第三步，主要是对代码的语义进行分析和检查。

语义分析器会检查代码中的语义错误，如类型不匹配、未声明的变量等，并生成相应的错误提示。

5. 代码生成代码生成是编译型语言处理程序的最后一步，主要是将经过词法分析、语法分析和语义分析的代码转化为目标机器的机器语言。

代码生成器会根据目标机器的特性和指令集，生成相应的机器码。

6. 优缺点分析编译型语言处理程序的优点包括编译后的代码执行速度快、占用系统资源少等。

然而，编译型语言的缺点是开发周期相对较长，对于程序的修改和调试比较麻烦。

二、解释型语言处理程序1. 解释型语言的定义解释型语言是指在程序运行时逐行解释执行的一种程序设计语言。

解释型语言的处理程序主要包括以下几个步骤：2. 词法分析解释型语言的词法分析与编译型语言的词法分析类似，都是将源代码划分为一个个词法单元。

3. 语法分析解释型语言的语法分析与编译型语言的语法分析类似，都是对词法单元进行语法分析，判断代码的语法是否符合语言规范。

4. 解释执行解释型语言的解释执行是指在程序运行时逐行解释执行代码。

解释器会将代码转化为一个个可执行的指令，并逐行执行。

5. 优缺点分析解释型语言处理程序的优点包括开发周期短、对程序的修改和调试比较方便等。

实验2 词法分析（4学时）实验要求：1. TEST语言的单词符号有：标识符：字母打头，后接字母数字,识别出的标识符用ID标记。

保留字（它是标识符的子集）：if,else,for,while,do,int,write,read，识别出的保留字直接用该保留字标记。

无符号整数：由数字组成，用NUM标记。

分界符：+、-、*、/、（、）、；、，>、<、{、}、!等单分界符，直接用单分界符标记。

>=、<=、!=、==等双字符分界符，直接用双分界符标记。

注释符：用/*….*/括起为了从源程序字符流中正确识别出各类单词符号，相邻的标识符、整数或保留字之间至少要用一个空格分开。

TEST语言的各类单词符号的正则文法规则如下：<ID>∷=<letter>|ID<letter>|ID<digit><NUM>∷=<digit>|NUM <digit><letter>∷= a|b|…|z|A|B|…|Z<digit>∷=1|2|…|9|0<singleword>∷=+|-|*|/|=|（|）|{|}|：|，|；|＜|＞|!<doubleword>∷=＞=|＜=|！=|==<commend_first>∷=/*<commend_last>∷=*/2、修改TESTscan（）程序，添加其余符号的处理。

1、AAA.test内容：= + - * / < > ( ) [ ] { } ; : ' " , == >= <= !=if else for while do int read write 358 aaa输出BBB.test的内容为：if else for while do int read write 358 aaaif else for while do int read write NUM ID这部分实验要求同学理解单词符号。

GDOU-B-11-112广东海洋大学学生实验报告书（学生用表）
实验名称实验2:词法分析程序课程名称编译原理课程号16242211 学院(系) 数计学院专业计算机科学与技术班级计科
学生姓名学号实验地点科425 实验日期
一、实验目的
（1）通过完成词法分析程序，了解词法分析的过程。

（2）掌握分析程序的设计和实现过程。

二、实验内容及步骤
对实验1的输出文件进行词法分析。

词法分析程序从左到右读入源程序的字符流，把字符串形式的源程序分割成一个个单词符号，即基本保留字、标识符、常数、运算符、界符五大类。

在识别出一个单词同时验证其词法正确性之后，词法分析程序将此单词以及其相关属性进行保存。

三、程序分析
四、源代码
五、测试结果
六、实验小结
成绩指导教师日期
注:请用A4纸书写，不够另附纸。

第页，共页
1。

编译原理词法分析实验报告软工082班兰洁200831104044一、实验内容二、实验目的三、实验预期四、程序规定五、实验原理●程序流程图●判别浮点功能扩展流程图●状态转换图六、程序代码与浮点判别功能扩展七、测试用例●扩展功能测试用例；●普通功能测试用例八、输出结果九、实验心得一、实验内容：词法分析：1、识别简单语言的单词符号；2、识别关键字、标识符、数字、运算符等。

并扩展浮点识别功能。

二、实验目的调试词法分析程序，加深对词法分析原理的理解，掌握编写简单词法分析程序的一般步骤。

三、实验预期结果：经过调试源代码程序，程序能够成功运行编译，对输入的简单字符串，能够别关键字、标识符、数字、运算符等，并且给出单词符号的对应编码。

四、程序规定：1、关键字："function","if","then","while","do","endfunc"；2、算术运算符：”+”,”-”,”*”,”/”,”=”；3、关系运算符："<" ">" "<=" ">=" "==" "!="；4、界符："(" ")" ";" "#"；5、标识符规定以字母开头,字母均为小写；6、空格和换行符跳过；7、单词对应编码：十、实验原理：输入串--------------------〉词法分析程序————————〉单词符号串输入：字符串以#结束。

输出：单词的二元组(syn，token/sum)程序流程图分析浮点数功能扩展部分流程图：shuzi()函数状态转换图六、程序代码：备注：红色字体部分为程序功能的功能扩展，使程序能够分析浮点数！我把浮点数的syn设置为80！/*词法分析源代码*/#include<stdio.h>#include<string.h>scaner();char prog[80],token[8];char ch;int syn,p,m,n,sum;char * rwtab[6]={"function","if","then","while","do","endfunc"}; int i=0,k,c,sumint,f;char fenshu[80],sum1[80];double sumf=0,fudian;int shuzi(){if(ch>='0' && ch<='9')syn=80;elsesyn=-2;return syn;}main(){p=0;printf("\n please input string :\n");do{scanf("%c",&ch);prog[++p]=ch;}while(ch!='#');p=0;do{scaner();switch(syn){ case 11:printf("\n(%d,%d)",syn,sum);break;case -1:printf("\n error");break;case 80:printf("\n(%d,%f)",syn,fudian);break; default:printf("\n(%d,%s)",syn,token);}}while(syn!=0);}scaner(){for(n=0;n<8;n++)token[n]=NULL;//if(1+2!=3)ch=prog[++p];while(ch==' ' || ch=='\n')ch=prog[++p];//跳过空格if(ch>='a' && ch<='z'){m=0;while(ch>='a' && ch<='z' || ch>='0' && ch<='9') {token[m++]=ch;//token[0]=f,m=1ch=prog[++p];}token[m]='\0';ch=prog[--p];syn=10;for(n=0;n<6;n++){if(strcmp(token,rwtab[n])==0){syn=n+1;break;}}}elseif(ch>='0' && ch<='9'){c=p;k=0;do{ sum1[k]=ch;ch=prog[++c]; //ch取后一个数字k++;shuzi();//这个函数用来分析浮点数的整数部分是否已经输入到数组里f=syn;} while(f==80)if(ch=='.'){for(n=0;n<k;n++){sumint=sumint*10+sum1[n]-'0';} //计算整数部分i=0;do{ch=prog[++c];fenshu[i]=ch;i++;shuzi();//这个函数用来分析浮点数的小数部分是否已经输入到数组里} while(syn==80);sumf=0;for(k=i-2;k>=0;k--){sumf=sumf*0.1+(fenshu[k]-'0')*0.1;} //计算浮点数的小数部分fudian=sumint+sumf; //浮点数计算syn=80;p=--c;}else{ch=prog[p];//若是整数，ch等于原来的值 sum=0;while(ch>='0' && ch<='9'){sum=sum*10+ch-'0';ch=prog[++p];}ch=prog[--p];syn=11;}}elseswitch(ch){case'<':m=0;token[m++]=ch;ch=prog[++p];if(ch=='='){syn=22;token[m++]=ch;}elseif(ch=='>'){syn=21;token[m++]=ch;}else{syn=20;ch=prog[--p];}break;case'>':m=0;token[m++]=ch;ch=prog[++p];if(ch=='='){syn=24;token[m++]=ch;}else{syn=23;ch=prog[--p];}break;case'=':m=0;token[m++]=ch;ch=prog[++p];if(ch=='='){syn=25;token[m++]=ch;}else{syn=18;ch=prog[--p];}break;case'!':m=0;token[m++]=ch;ch=prog[++p];if(ch=='='){syn=22;token[m++]=ch;}else{syn=-1;p--;}break;case'+':syn=13;token[0]=ch;break;case'-':syn=14;token[0]=ch;break;case'*':syn=15;token[0]=ch;break;case'/':syn=16;token[0]=ch;break;case';':syn=26;token[0]=ch;break;case'(':syn=27;token[0]=ch;break;case')':syn=28;token[0]=ch;break; case'#':syn=0;token[0]=ch;break;default:syn=-1;}}七、测试用例：补充：功能扩展测试用例：八、程序输出结果：功能扩展测试用例输出结果用例一：用例二：用例三：普通功能测试用例显示结果九、实验心得通过编译原理实验一词法分析实验，使得自己对词法分析的流程有了更深刻的了解，虽然源代码并非由自己设计，但是在调试程序的过程中，尤其是进行测序功能扩展的过程中，想了很多种办法，终于找到了最合适的方法，而且还进行了代码的优化，这个过程虽然有时有些枯燥，但是更多时候是欣喜的，不仅复习了c语言的许多内容，并且有了更深的理解。

第二章 词法分析2.1 完成下列选择题：(1) 词法分析器的输出结果是。

a. 单词的种别编码b. 单词在符号表中的位置c. 单词的种别编码和自身值d. 单词自身值(2) 正规式M1和M2等价是指。

a. M1和M2的状态数相等b. M1和M2的有向边条数相等c. M1和M2所识别的语言集相等d. M1和M2状态数和有向边条数相等(3) DFA M(见图2-1)接受的字集为。

a. 以0开头的二进制数组成的集合b. 以0结尾的二进制数组成的集合c. 含奇数个0的二进制数组成的集合d. 含偶数个0的二进制数组成的集合【解答】(1) c (2) c (3) d图2-1 习题2.1的DFA M2.2 什么是扫描器？扫描器的功能是什么？【解答】 扫描器就是词法分析器，它接受输入的源程序，对源程序进行词法分析并识别出一个个单词符号，其输出结果是单词符号，供语法分析器使用。

通常是把词法分析器作为一个子程序，每当词法分析器需要一个单词符号时就调用这个子程序。

每次调用时，词法分析器就从输入串中识别出一个单词符号交给语法分析器。

2.3 设M=({x,y}, {a,b}, f, x, {y})为一非确定的有限自动机，其中f 定义如下：f(x,a)={x,y} f {x,b}={y}f(y,a)=Φ f{y,b}={x,y}试构造相应的确定有限自动机M ′。

【解答】 对照自动机的定义M=(S,Σ,f,So,Z)，由f 的定义可知f(x,a)、f(y,b)均为多值函数，因此M 是一非确定有限自动机。

先画出NFA M 相应的状态图，如图2-2所示。

图2-2 习题2.3的NFA M 用子集法构造状态转换矩阵，如表表2-1 状态转换矩阵1b将转换矩阵中的所有子集重新命名，形成表2-2所示的状态转换矩阵，即得到 M ′=({0,1,2},{a,b},f,0,{1,2})，其状态转换图如图2-3所示。

表2-2 状态转换矩阵将图2-3所示的DFA M ′最小化。