编译原理课程设计--语法分析器.doc

福建农林大学计算机与信息学院
计算机类
课程设计报告
课程名称:
编译原理
课程设计题目:
语法分析器
姓名:
系:
计算机
专业:
计算机科学与技术
年级:
2009计科
学号:
指导教师:
职称:
副教授
2011~2012学年第一学期
福建农林大学计算机与信息学院计算机类
课程设计结果评定
评语:
成绩:
指导教师签字:
任务下达日期:
评定日期:
目录
1 正则表达式 1
正则表达式 1
确定化(化简)后的状态转换图 1
分析程序代码 1
程序运行截图 1
小结 1
2 LL(1)分析 2
LL(1)文法 2
LL(1)预测分析表 2
分析程序代码 2
程序运行截图 2
小结 2
3 算符优先分析 3
算符优先文法 3
算符优先关系表 3
分析程序代码 3
程序运行截图 3
小结 3
4 LR分析 4
LR文法 4
LR分析表 4
分析程序代码 4
程序运行截图 4
小结 4
参考文献: 4
1 正则表达式
正则表达式
(a|b)*(aa|bb)(a|b)* (注:该正规式为示例,可更改)
确定化(化简)后的状态转换图

分析程序代码
#include <iostream>
#include <string>
#include <map>
using namespace std;
//定义一个存储状态转换的类
class Statu
{
public:
map<char, Statu *> MAP;
};
int main()
{
//定义4个状态并初始化各个状态间的关系,以及定义一个存储当前状态的变量status
Statu A, B, C, D, *status;
['a'] = &B;
['b'] = &C;
['a'] = &D;
['b'] = &C;
['a'] = &B;
['b'] = &D;
['a'] = &D;
['b'] = &D;
while(1)
{
string::size_type size=0;
string str;
bool flag = true;
cout<<"请输入符合(a|b)*(aa|bb)(a|b)* 的正则表达式"<<endl;
cin >> str;
status = &A;//刚开始指向初始状态
const char *ch = ();
while(ch[size])
{
if(ch[size] != 'a' && ch[size] != 'b')
{
flag = false;
break;
}
status = status->MAP[ch[size++]];//根据输入字符串调整状态
}
if(status == &D && flag)//若为终结状态则符合此正则表达式
cout<<"√正确"<<endl;
else
cout<<"×错误"<<endl;
}
return 0;
}
程序运行截图

小结
通过定义各个状态,并生成各个状态间的关系可以方便地表示状态转换图,使用关联容器则可以方便的管理状态。
2 LL(1)分析
LL(1)文法
E→TE' (注:该文法为示例,可更改)
E'→+TE'|ε
T→FT'
T'→*FT'|ε
F→(E)|i
LL(1)预测分析表
i
+
*
(
)
#
E
E→TE'
E→TE'
E'
E'→+TE'
E'→ε
E'→ε
T
T→FT'
T→FT'
T'
T'→ε
T'→*FT'
T'→ε
T'→ε
F
F→i
F→(E)
分析程序代码
#include <iostream>
#include <string>
#include <map>
#include <stack>
using namespace std;
enum Symbols
{
// 终结符号 Terminal symbols:TS
TS_I, // i
TS_PLUS, // +
TS_MULTIPLY, // *
TS_L_PARENS