语法分析器

语法分析器

• 1.课程设计内容与要求
• • 1.1实验目的
  • 1.2实验内容与要求
  • 1.3文法表示
• 2.分析与设计
• • 2.1模块一 求firstvt和lastvt集合
  • • 2.1.1 数据结构
    • 2.1.2 主要函数
    • 2.1.3 算法描述
    • • 2.1.3.1 First_VT
      • 2.1.3.2 Last_VT
      • 2.1.4 运行结果
  • 2.2 模块二 构建优先关系表
  • • 2.2.1 数据结构
    • • 2.2.2 主要函数
      • 2.2.3 算法描述
      • 2.2.4 运行结果
  • 2.3 模块三 词法分析
  • • 2.3.1 单词种别码设计
    • 2.3.2 状态转换图
    • 2.3.3 数据结构
    • 2.3.4 主要函数
    • 2.3.5 算法描述
    • 2.3.6 运行结果
  • 2.4 模块四 语法分析
  • • 2.4.1 数据结构
    • 2.4.2 主要函数
    • 2.4.3 算法描述
• 2.5 模块五 主函数
• 3.程序运行测试
• 4.源代码

1.课程设计内容与要求 1.1实验目的

1.了解掌握算符优先分析的基本方法、内容；
2.学会科学思考并解决问题，提高程序设计能力。

1.2实验内容与要求

用算符优先分析方法设计一个分析解释程序，对输入的赋值语句、输出语句、清除语句进行词法分析、语法分析、表达式求值并存储于指定变量中；若存在错误，提示错误相关信息。

1.3文法表示

S→v=E|E?|clear
E→E+T|E-T|T
T→T*F|T/F|F
F→ (E)|v|c

2.分析与设计

程序分为以下五个模块

1. 构建firstvt和lastvt集合
2. 根据firstvt 和lastvt 集合构建优先关系表
3. 词法分析得到单词串
4. 语法分析
5. 主函数

单词符号二元组：
typedef struct
{
int code;//种别码
string attr;//属性值
}WordType;
输入串：用字符串对象s来存放输入串
单词串：用队列对象 queue res存放单词串
变量表：使用map对象来充当变量表
归约栈：使用vector对象来表示
可归约串语义解释：
变量归约:Nv,在变量表中查找该变量，若不存在则报错：变量未定义，否则修改非终结符N 的属性值为变量v的值，并设N的种别码为13
常量归约:Nc,修改非终结符的属性值为常量c的值，并设N的种别码为13
运算归约:设运算的操作数为N1,N2;将N1，N2进行相应的运算并将运算结果设N的属性值，将N的种别码设为13
括号归约: 将(N)归约为N
赋值语句：在变量表中查找被赋值的v,若不存在，则先在变量表中创建该变量，然后再将N的属性值赋值给v,最后将v=N归约为N
输出语句:先输出表达式N的属性值，然后将N?归约为N
清除语句：将变量表中的所有变量以及屏幕上的内容清空，然后clear归约为N

2.1模块一 求firstvt和lastvt集合 2.1.1 数据结构

map firstvt;//char为字符，vector则为集合
map lastvt;

2.1.2 主要函数

bool istermi(char c);//判断是否是终结符
bool isnontermi(char c);//判断是否是非终结符
void First_VT(vector s,char c) ;//求非终结符c的firstvt集合
void Last_VT(vector s,char c);//求终结符c的lastvt集合
void print_fv_lv();//打印FIRSTVT和LASTVT集合

2.1.3 算法描述 2.1.3.1 First_VT

定位非终结符P所在的产生式,遍历P的候选式
对每个候选式，执行以下程序
若P的候选式出现：
若该候选式形如P a…，将终结符a加入firstvt§中
否则：
若该候选式形如P Ba…，将终结符a加入firstvt§中
若firstvt(B)存在，则将firstvt(B)的所有元素加入firstvt§，反之，若firstvt(B)不
存在，先求firstvt(B)之后，再将firstvt(B)的所有元素加入firstvt§

2.1.3.2 Last_VT

定位非终结符P所在的产生式,遍历P的候选式
对每个候选式，执行以下程序
若A的候选式出现：
若该候选式形如P …a，将终结符a加入lastvt§中
否则：
若该候选式形如P …aB，将终结符a加入lastvt§中
若lastvt(B)存在，则将lastvt(B)的所有元素加入lastvt§，反之，若lastvt(B)不
存在，先求lastvt(B)之后，再将lastvt(B)的所有元素加入lastvt§

2.1.4 运行结果

2.2 模块二 构建优先关系表 2.2.1 数据结构

map term_pos;//终结符以及其在数组中的位置
vector table;//算符优先关系表

2.2.2 主要函数

void table_init(vector s);//初始化算符优先关系表
void Get_Table(vector s);//构建算符优先关系表

2.2.3 算法描述

FOR 每条产生式PX1X2…Xn
FOR i=1 TO n-1 DO
BEGIN
IF Xi和Xi+1均为终结符 THEN 置 Xi=Xi+1
IF i<=n-2且Xi和Xi+2均为终结符，但Xi+1为非终结符 THEN 置 Xi=Xi+2
IF Xi为终结符而Xi+1为非终结符 THEN
FOR firstvt(Xi+1)中的每个a DO
置 Xi IF Xi为非终结符而Xi+1为终结符 THEN
FOR lastvt(Xi)中的每个a DO
置 a> Xi+1

2.2.4 运行结果

注：l代表clear

2.3 模块三 词法分析 2.3.1 单词种别码设计

2.3.2 状态转换图

2.3.3 数据结构

typedef struct
{
int code;//种别码
string attr;//属性值
}WordType;//单词二元组
queue res; //存储词法分析的结果
map v_table;//符号表，-1表示未赋值

2.3.4 主要函数

bool isdigit(char c);//判断是不是数字
bool ischar(char s);//判断是不是字符
bool isremain(string s);//判断是不是保留字，即clear
queue LEX(string s);//词法分析程序
void print_word(queue res);//打印词法分析结果

2.3.5 算法描述

对输入的字符串s,前后加上#号，长度为n
For i=0 to n-1:
IF s[i]==‘ ’，THEN CONTINUE。
ELSE：
IF s[i]为字母，THEN 进行标识符和保留字的识别；
ELSE IF s[i]为数字，THEN 进行数字的判断。
ELSE 依次对这个字符可能的情况进行判断。
每次成功识别了一个单词后，创建新的WordType t,将单词种别码和单词属性值存入其中，然后将t加入队列res中。
END

2.3.6 运行结果

2.4 模块四 语法分析 2.4.1 数据结构

vector Stack;//归约栈

2.4.2 主要函数

void print_stack();//打印归约栈中的元素
bool handle(int j,int k);//归约子程序，对s[j]到s[k]进行归约
void MainHandle();//归约主程序

2.4.3 算法描述

t=res.pop();//从单词串中取出一个单词
top=1;//栈顶指针
Stack.push_back(t);//压栈
DO
把下一个输入符号读入a中;
IF Stack[k]∈VT THEN j=top ELSE j=top-1;
IF Stack[j]>a DO
BEGIN
REPEAT
Q=Stack[j];
IF Stack[j-1] ∈VT THEN j=j-1 ELSE j=j-2
UNTIL Stack[j] 把Stack[j+1]…Stack[top]归约为N;
top=j+1;
END
ELSE IF Stack[j] BEGIN res.pop();将a入栈; END
ELSE ERROR
WHILE a!=’#’

2.5 模块五 主函数

程序流程：

3.程序运行测试

【输入示例】
a=5
b=a+10
b?
b+a*a?
a=a+b

【运行结果】

4.源代码

#include 
#include
#include 
#include