首页 > 代码库 > 词法分析

词法分析

1.词法分析的功能

 

词法分析(英语:lexical analysis)是计算机科学中将字符序列转换为单词(Token)序列的过程。进行词法分析的程序或者函数叫作词法分析器(Lexical analyzer,简称Lexer),也叫扫描器(Scanner)。词法分析器一般以函数的形式存在,供语法分析器调用。 完成词法分析任务的程序称为词法分析程序或词法分析器或扫描器。[1] 完成词法分析任务的程序称为词法分析程序或词法分析器或扫描器。从左至右地对源程序进行扫描,按照语言的词法规则识别各类单词,并产生相应单词的属性字。

 

 

 

词法分析器的功能输入源程序,按照构词规则分解成一系列单词符号。单词是语言中具有独立意义的最小单位,包括关键字、标识符、运算符、界符和常量等

 

 

 

(1) 关键字 是由程序语言定义的具有固定意义的标识符。例如,Pascal 中的begin,end,if,while都是保留字。这些字通常不用作一般标识符。
(2) 标识符 用来表示各种名字,如变量名,数组名,过程名等等。
(3) 常数  常数的类型一般有整型、实型、布尔型、文字型等。
(4) 运算符 如+、-、*、/等等。
(5) 界符  如逗号、分号、括号、等等。

 

 

 

 

 

   a | b {a, b}
                (a | b) (a | b ) {aa, ab, ba, bb}
                aa | ab | ba | bb {aa, ab, ba, bb}
                a* 由字母a构成的所有串集
                (a | b)* 由a和b构成的所有串集

 

 

 

比如如下的代码段:

 

 

 

while(i>=j) i--

 

 

 

经词法分析器处理后,它将被转为如下的单词符号序列:

 

 

 

   <while, _>

 

 

 

   <(, _>

 

 

 

   <id, 指向i的符号表项的指针>

 

 

 

   <>=, _>

 

 

 

   <id, 指向j的符号表项的指针>

 

 

 

   <), _>

 

 

 

   <id, 指向i的符号表项的指针>

 

2.符号与种别码对照表

技术分享

3.用文法描述词法规则

<字母> A->a|b|c|d|...|z
<数字> B->1|2...|9
<整数常数>  S->C|SB C->1|2|3|...|9
<标识符> F->A|SB|SA|S
<关键字> S->begin|if|then|while|do|end
<运算符> S->+|-|*|%|=|#|<|<=|>|>=|:=
<界符> S->(|)|,|;|.
#include<iostream.h>#define MAX 100typedef struct{    int n;    int data[MAX];}lqlist;void merge(int a[],int s1,int e1,int s2,int e2,int b[]){    int k=s1;    int i=s1;    while((s1<=e1)&&(s2<=e2))    {        if(a[s1]<=a[s2])        {                /*将数组a[s1]和数组a[s2]中小的数据暂存到数组b[]中*/            b[k]=a[s1];            k++;            s1++;        }        else        {                /*将数组a[s1]和数组a[s2]中小的数据暂存到数组b[]中*/            b[k]=a[s2];            k++;            s2++;        }    }    while(s1<=e1)    {            /*将第一个数组中剩余的数据暂存到数组b[]中*/        b[k]=a[s1];        k++;        s1++;    }    while(s2<=e2)    {            /*将第二个数组中剩余的数据暂存到数组b[]中*/        b[k]=a[s2];        k++;        s2++;    }    k--;    while(k>=i)    {            /*将暂存数组b[]中的数据存回到a[]中*/        a[k]=b[k];        k--;    }}main(){    cout<<"****************************************************"<<endl;    cout<<"             归并排序的递归和非递归实现             "<<endl;    cout<<"****************************************************"<<endl;    lqlist p;    int i=0,z,m,k;    cout<<"     请输入所要比较的数字组,以10000结束:     "<<endl;    cin>>z;    while(z!=100000&&i<MAX)    {        /*对数组进行循环输入,并以10000结束输入*/        p.data[i]=z;        i++;        cin>>z;    }    p.n=i;    cout<<"排序前的数组是:  "<<endl;    for(i=0;i<p.n;i++)        cout<<p.data[i]<<"  ";    cout<<"请选择需要归并排序的方法"<<endl;        <<"1.选择递归方法。"<<endl;    cout<<"2.选择非递归方法。"<<endl;    cin>>m;    if(m==1)        M(&p);    else    {        if(m==2)            mergesort2(&P);        else            cout<<"输入有误。"<<endl;)    }    cout<<endl<<"排序后的数组: "<<endl;    for(i=0;i<p.n;I++)    {        /*输出归并前的数组*/        cout<<p.data[i]<<"  ";    }    cout<<endl;    cout<<"请选择服务:"<<endl;    if(m==1)        cout<<"1.选择非递归方法。"<<endl;    else        cout<<"1.选择递归方法。"<<endl;    cout<<2.退出。"<<endl;cin>>k;    /*再次进行选择服务(另一种排序方法还是退出)*/    if(m==1&&k==1)        M(&p);    /* 将用递归方法进行归并排序*/    else    {        if(m==2&&k==1)        mergesort2(&p);        /*将用非递归的方法进行归并*/        else if(k==2)            return 0;    }    cout<<endl<<"排序后的数组: "<<endl;    for(i=0;i<p.n;i++)    {        cout<<p.data[i]<<"  ";    }    cout<<endl;    return 0;}

 

词法分析