词法分析
1、 待分析的简单语言的词法
（1） 关键字：（所有关键字都是小写。）
begin if then while do end
（2） 运算符和界符：
:= + – * / < <= <> > >= = ; ( ) #
（3） 其他单词是标识符（ID）和整型常数（NUM），通过以下正规式定义：
ID=letter（letter| digit）*
NUM=digit digit *
（4） 空格由空白、制表符和换行符组成。空格一般用来分隔ID、NUM,运算符、界符和关键字，词法分析阶段通常被忽略。
2、 各种单词符号对应的种别码
单词符号 |
种别码 |
单词符号 |
种别码 |
begin |
1 |
: |
17 |
if |
2 |
:= |
18 |
then |
3 |
> |
20 |
while |
4 |
<> |
21 |
do |
5 |
<= |
22 |
end |
6 |
< |
23 |
letter(letter| digit)* |
10 |
>= |
24 |
digit digit * |
11 |
= |
25 |
* |
13 |
; |
26 |
/ |
14 |
( |
27 |
+ |
15 |
) |
28 |
- |
16 |
# |
0 |
依照状态转换图，进行匹配：
对单一字符，直接比较；
对关键字，进行循环匹配（0-1-2）；
对数字，进行循环匹配（0-3-4）。
4、词法分析程序的功能
输入：所给文法的源程序字符串。
输出：二元组（syn，token/sum）构成的序列。
其中：syn为单词种别码；
token为存放的单词自身字符串；
sum为整型常数。
错误：返回row行数
5、设计思路
设计scaner，查询当前所指字符，并与表格内字符进行比较匹配：
匹配成功，返回相应代码号；
匹配失败，则弹出错误信息（用row记录当前处理的行数）。
6、源程序代码：
#include<stdio.h>
#include<string.h>
#include<iostream.h>
char prog[80],token[8];
char ch;
int syn,p,m=0,n,row,sum=0;
char *rwtab[6]={"begin","if","then","while","do","end"};
//匹配字符
void scaner()
{
for(n=0;n<8;n++) token[n]=NULL;
ch=prog[p++];
while(ch==' ')
{
ch=prog[p];
p++;
}
if((ch>='a'&&ch<='z')||(ch>='A'&&ch<='Z'))
{
m=0;
while((ch>='0'&&ch<='9')||(ch>='a'&&ch<='z')||(ch>='A'&&ch<='Z'))
{
token[m++]=ch;
ch=prog[p++];
}
token[m++]='\0';
p--;
syn=10;
for(n=0;n<6;n++)
if(strcmp(token,rwtab[n])==0)
{
syn=n+1;
break;
}
}
else if((ch>='0'&&ch<='9'))
{
{
sum=0;
while((ch>='0'&&ch<='9'))
{
sum=sum*10+ch-'0';
ch=prog[p++];
}
}
p--;
syn=11;
if(sum>32767)
syn=-1;
}
else switch(ch)
{
case'<':m=0;token[m++]=ch;
ch=prog[p++];
if(ch=='>')
{
syn=21;
token[m++]=ch;
}
else if(ch=='=')
{
syn=22;
token[m++]=ch;
}
else
{
syn=23;
p--;
}
break;
case'>':m=0;token[m++]=ch;
ch=prog[p++];
if(ch=='=')
{
syn=24;
token[m++]=ch;
}
else
{
syn=20;
p--;
}
break;
case':':m=0;token[m++]=ch;
ch=prog[p++];
if(ch=='=')
{
syn=18;
token[m++]=ch;
}
else
{
syn=17;
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=25;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;
case'\n':syn=-2;break;
default: syn=-1;break;
}
}
//主程序读入 循环
void main()
{
p=0;
row=1;
cout<<"Please input string:"<<endl;
do
{
cin.get(ch);
prog[p++]=ch;
}
while(ch!='#');
p=0;
do
{
scaner();
switch(syn)
{
case 11: cout<<"("<<syn<<","<<sum<<")"<<endl; break;
case -1: cout<<"Error in row "<<row<<"!"<<endl; break;
case -2: row=row++;break;
default: cout<<"("<<syn<<","<<token<<")"<<endl;break;
}
}
while (syn!=0);
}
7、 结果验证
begin y:=11 if y<13 then y:1+2*3+y/2; end#
源程序（包括上式未有的while、do以及判断错误语句）：
begin
x<&
while
h<0
do
b>9
k>9-x
end
#
$ 字符不在表内，所以匹配错误，返回错误行数。
语法分析
1、分析文法
- 语法表达式
G(E)：E à E +T | T
T à T* F | F
F à i | (E)
- 展开表达式
(1)E à E +T
(2)E à T
(3)T à T* F
(4)T à F
(5)F à i
(6)F à (E)
- 消除左递归：
G’(E)：E->TE'
E'->+TE'|ε
T->FT'
T'->*FT'|ε
F->(E)|i
2、构造LL(1)分析表
非终结符 |
输入符号 |
|||||
i |
+ |
* |
（ |
） |
# |
|
E |
E->TE' |
|
|
E->TE' |
synch |
synch |
E’ |
|
E'->+TE' |
|
|
E'->ε |
E'->ε |
T |
T->FT' |
synch |
|
T->FT' |
synch |
synch |
T’ |
|
T'->ε |
T'->*FT' |
|
T'->ε |
T'->ε |
F |
F->i |
synch |
synch |
F->(E) |
synch |
synch |
- 构造LR分析表
状态 |
action |
goto |
|||||||
id |
+ |
* |
( |
) |
# |
E |
T |
F |
|
0 |
S5 |
|
|
S4 |
|
|
1 |
2 |
3 |
1 |
|
S6 |
|
|
|
acc |
|
|
|
2 |
|
R2 |
S7 |
|
R2 |
R2 |
|
|
|
3 |
|
R4 |
R4 |
|
R4 |
R4 |
|
|
|
4 |
S5 |
|
|
S4 |
|
|
8 |
2 |
3 |
5 |
|
R6 |
R6 |
|
R6 |
R6 |
|
|
|
6 |
S5 |
|
|
S4 |
|
|
|
9 |
3 |
7 |
S5 |
|
|
S4 |
|
|
|
|
10 |
8 |
|
S6 |
|
S11 |
|
|
|
|
|
9 |
|
R1 |
S7 |
|
R1 |
R1 |
|
|
|
10 |
|
R3 |
R3 |
|
R3 |
R3 |
|
|
|
11 |
|
R5 |
R5 |
|
R5 |
R5 |
|
|
|
- LL(1)状态切换
3、设计程序
LL(1)——————————————————————————————————
#include <iostream.h>LR——————————————————————
char inputstream[50];
int temp=0;
int right;
//状态转换函数
void e();
void e1();
void t();
void t1();
void f();
//主程序
void main()
{
right=1;
cout<<"请输入您要分析的字符串以#结束(^为空字符)："<<endl;
cin>>inputstream;
e();
if((inputstream[temp]=='#')&&right)
cout<<"分析成功"<<endl;
else
cout<<"分析失败"<<endl;
}
void e()
{
cout<<"E->TE'"<<endl;
t();
e1();
}
void e1()
{
if(inputstream[temp]=='+')
{
cout<<"E'->+TE'"<<endl;
temp++;
t();
e1();
}
else
if (inputstream[temp]!='#'||inputstream[temp]!=')')
{
cout<<"T'->^"<<endl;
return ;
}
else
right=0;
}
void t()
{
cout<<"T->FT'"<<endl;
f();
t1();
}
void t1()
{
if(inputstream[temp]=='*')
{
cout<<"T'->*FT'"<<endl;
temp++;
f();
t1();
}
else
if (inputstream[temp]!='#'&&inputstream[temp]!=')'&&inputstream[temp]!='+')
{
cout<<"T'->^"<<endl;
right=0;
}
}
void f()
{
if(inputstream[temp]=='i')
{
cout<<"F->i"<<endl;
temp++;
}
else
if(inputstream[temp]=='(')
{
cout<<"F->(E)"<<endl;
temp++;
e();
if(inputstream[temp]==')')
{
cout<<"F->(E)"<<endl;
temp++;
}
else
right=0;
}
else right =0;
}
#include<iostream>
#include<stack>
using namespace std;
char inputstream[50];
//栈区
//符号和状态
stack<char> symbol;
stack<int> state;
//分析表内容
//符号表
char sym[12][6]={
{'s','e','e','s','e','e'},
{'e','s','e','e','e','a'},
{'r','r','s','r','r','r'},
{'r','r','r','r','r','r'},
{'s','e','e','s','e','e'},
{'r','r','r','r','r','r'},
{'s','e','e','s','e','e'},
{'s','e','e','s','e','e'},
{'e','s','e','e','s','e'},
{'r','r','s','r','r','r'},
{'r','r','r','r','r','r'},
{'r','r','r','r','r','r'}
};
//数字表
char snum[12][6]={
{5,1,1,4,2,1},
{3,6,5,3,2,0},
{2,2,7,2,2,2},
{4,4,4,4,4,4},
{5,1,1,4,2,1},
{6,6,6,6,6,6},
{5,1,1,4,2,1},
{5,1,1,4,2,1},
{3,6,5,3,11,4},
{1,1,7,1,1,1},
{3,3,3,3,3,3},
{5,5,5,5,5,5}
};
//goto表
int go2[12][3]={
{1,2,3},
{0,0,0},
{0,0,0},
{0,0,0},
{8,2,3},
{0,0,0},
{0,9,3},
{0,0,10},
{0,0,0},
{0,0,0},
{0,0,0},
{0,0,0}
};
//action函数[i,a]
void action(int i,char *&a,char &how,int &num,char &A,int &b)
{
int j;//指向action表列号
switch(*a)
{
case 'i':
j=0;break;
case '+':
j=1;break;
case '*':
j=2;break;
case '(':
j=3;break;
case ')':
j=4;break;
case '#':
j=5;break;
default:
j=-1;break;
}
if(j!=-1)
{
how=sym[i][j];
num=snum[i][j];
if(how=='r')
{
switch(num)
{
case 1:
A='E',b=3;
cout<<"按E->E+T规约"<<endl;
break;
case 2:
A='E',b=1;
cout<<"按E->T规约"<<endl;
break;
case 3:
A='T',b=3;
cout<<"按T->T*F规约"<<endl;
break;
case 4:
A='T',b=1;
cout<<"按T->F规约"<<endl;
break;
case 5:
A='F',b=3;
cout<<"按F->(E)规约"<<endl;
break;
case 6:
A='F',b=1;
cout<<"按F->id规约"<<endl;
break;
default:
break;
}
}
}
}
//goto[t,A]
int go(int t,char A)
{
switch(A)
{
case 'E':
return go2[t][0];break;
case 'T':
return go2[t][1];break;
case 'F':
return go2[t][2];break;
}
}
//error处理函数
void error(int i,int j,char *&a)
{
cout<<"error"<<endl;
switch(j)
{
case 1://期望输入id或左括号,但是碰到+,*,或$,就假设已经输入id了,转到状态5
state.push(5);
symbol.push('i');//必须有这个,如果假设输入id的话,符号栈里必须有....
cout<<"缺少运算对象id"<<endl;
break;
case 2://从输入中删除右括号
a++;
cout<<"不配对的右括号"<<endl;
break;
case 3://期望碰到+,但是输入id或左括号,假设已经输入算符+,转到状态6
state.push(6);
symbol.push('+');
cout<<"缺少运算符"<<endl;
break;
case 4://缺少右括号,假设已经输入右括号,转到状态11
state.push(11);
symbol.push(')');
cout<<"缺少右括号"<<endl;
break;
case 5:
a++;
cout<<"*号无效,应该输入+号!"<<endl;
case 6:
a++;
}
}
int main()
{
int s;
char *a;//当前操作符
char how;
int num;
int b;
char A;
while(1)
{
cin>>inputstream;
a=inputstream;
state.push(0);//0状态入栈
while(*a!='\0')
{
b=0;num=0;how='\0';A='\0';
s=state.top();
action(s,a,how,num,A,b);
if(how=='s')//移进
{
cout<<"移进"<<endl;
symbol.push(*a);
state.push(num);
a++;
}
else if(how=='r')//规约
{
for(int i=0;i<b;i++)
{
if(!state.empty())
state.pop();
if(!symbol.empty())
symbol.pop();
}
int t=state.top();
symbol.push(A);
state.push(go(t,A));
}
else if(how=='a')//接受
break;
else
{
error(s,num,a);//错误处理
}
}
cout<<"成功接受"<<endl;
}
return 0;
}
4、总结
学完语法分析这章后，对LL、LR、SLR、LR(1)、LALR还有着不少疑问。
LL是常用的自上而下的语法分析，方法比较简单容易理解，从非终结符到终结符，树节点到叶节点；LR文法则是自下而上，将终结符一步步规约缩减，从叶节点直到规约成树根，LR(0)-SLR、LR(1)是对是否规约冲突选择的不同方法，LALR了解较少，为了处理LR(1)的同心集合的冲突设置的文法。
参考了部分教材和代码后，简单编写（理解并改动部分）了词法分析和语法分析器（也是老师作业- -）。
词法分析器作用无非是剔除无关字符、将特殊字符分类放到表中作为后续（如语法分析的操作符+/-/*等）、报错（主要是键入错误）。
语法分析器顾名思义，就是判断句子说法是否正确，例如:+号左右是否都是数字或未知数，遇到不合理的‘=+*’就要相应报错；进一步的语法分析，除了语句还有声明、函数名、变量声明....