工科课程设计 编译原理
课程设计报告
题 目: LR(0)分析器动构造程序实现
学 号:
姓 名:
班 级:
指导教师:
日 期: 2016年 X月X日
目 录
第章 概 述 4
第二章 设计基原理 5
21 识文法LR(0)项目集规范族构造 5
22 LR(0)分析表构造 5
23 LR(0)分析器总控程序构造 6
第三章 程序设计 7
31 程序总体构架 7
32 程序存储结构 8
321 符号表存储结构 8
322 产生式表存储结构 8
323 项目集规范族表存储结构 9
324 LR(0)分析表存储结构 9
33 程序算法 10
331 项目集规范族构造 10
332 LR(0)分析表构造 11
第四章 程序测试 12
41 符号表测试 12
42 产生式表测试 13
43 项目集规范族表测试 13
44 LR(0)分析表测试 14
45 LR(0)分析器测试 14
第五章 总结展 15
附录 16
参考文献 17
概 述
课程设计完成容:
1 实现意定文法识文法活前缀状态转化矩阵项目集规范族构造
2 判断该文法否文法实现分析表构造输出指定文件中
3 实现分析器总控程序输入表达式进行文法分析
4VC++60程序运行
二 设计基原理
课程设计核心算法[1]三点:1 识文法活前缀状态转化矩阵项目集规范族构造2 分析表构造3 分析器总控程序构造
21 识文法LR(0)项目集规范族构造
采(闭包)构造文法项目规范簇
假定文法项目集定义构造闭包算法:
(1)项目属
(2)属关产生式项目属
(3)重复执行述两步骤直增
中初始 文法进行拓广构造引进出现中非终结符
定义状态转换函数第变元项目集第二变元文法符号函数值定义
中 {形项目| 属}
22 LR(0)分析表构造
假定令项目集标作分析器状态特令包含项目集合标分析器初态分析表子表子表方法构造:
(1)项目属终结符置移栈简记
(2)项目属终结符(结束符#)置产生式进行规约简记(假定产生式文法第j产生式)
(3)项目属置接受简记acc
(4)置
(5)分析表中规1~4填入信息空白处均置报错标志果分析表中项重复填入说明分析表入口唯项目集中存突项目该文法文法
23 LR(0)分析器总控程序构造
分析表包括量部分动作表状态转换表规定状态面输入符号时应采取什动作规定状态面文法符号时状态什
项规定动作外述四种
(1)移进 状态输入符号推进栈输入符号变成现行输入符号
(2)约 指某产生式进行规约假长度规约动作栈顶项状态变成栈顶状态然状态推进栈规约动作改变现行输入符号规约动作改变现行输入符号
(3)接受 宣布分析成功停止分析器工作
(4)报错 发现源程序含错误调出错处理程序
三 程序设计
31 程序总体构架
课程设计开发程序4张表组成分:符号表产生式表表项目集规范簇表时项目集规范簇表包含分析栈作分析器总控程序产生式表包含符号表作子表项目集规范簇表包含产生式表表作子表
程序工作流程:
1 读取含文法规文件该文法中文法符号(终结符非终结符分配编号)记录文法符号属性(终结符非终结符)存储张符号表中
2 次读取文件产生式存储产生式表中
3 根产生式构建项目集规范族存储表中
4 根构建项目集规范族构建分析表填写分析表时检查该文法否文法
5 输入表达式分析器根构建分析表进行文法分析出分析结果
32 程序存储结构
321 符号表存储结构
动态数组标时作符号编号
标识符
否非终结符
322 产生式表存储结构
产生式标号
非终结符标号 (中致)
指示前非终结符产生式
前非终结符产生式长度帮助区分产生式项目项目数等
指示非终结符
产生式中标识符名(中致)
产生式中标识符
323 项目集规范族表存储结构
1)定义二元组 :
:产生式标号 中致
:产生式第项目 中帮助确定
:产生式 :
2)结构:
前状态编号
指示状态
指示闭包中项目
闭包中项目名
前项目产生新状态编号状态转移目状态编号
闭包中项目
构造项目闭包
构造项目闭包
构造状态
构造状态项目
324 LR(0)分析表存储结构
指示表头孩子结点
指示表头继结点
指示该表项操作
指示该表项操作数
指示该表项否填写判断文法否文法
33 程序算法
331 项目集规范族构造
1 (初始化)初始条件作该状态头结点第孩子结点构造该孩子结点闭包连接指第状态头结点指第状态头结点第孩子结点
2 查空停止空转3
3 查空转4空构造检查该状态前构造状态重复重复停止构造填写重复已存状态编号重复作新状态连接构造闭包连接指转2
4 指状态状态空结束否指状态头结点第孩子结点转3
具体细节:
设指项目构造闭包该项目定终态区分项目圆点符号位第标识符左侧现构造闭包分两步骤实现:
1 构造 :
查中编号产生式取该产生式长度属性
1) 停止构造前闭包(已终态)时 项填
2) 否作该闭包第项目时 项填该新状态状态编号
2 构造该孩子结点闭包 :
查中编号产生式第标识符取该标识符查中该标识符类属性
3) 1(非终结符)查非终结符产生 式记产生式编号加入闭包
4) 否结束
3 检查该状态前构造状态重复
断言:意两状态状态
332 LR(0)分析表构造
编号状态现项目填写分析表:
1 果该项目形查该项目属性
1)终结符表状态应行应列填写表示 移进栈
2)非终结符表状态应行应列填写表示状态转移状态
2 果该项目形
1)起始符号置表状态应行应列填写表示接受
2)否终结符结束符表状态应行应列填写表示产生式进行规约
四 程序测试
文法G例:
程序模块输入:含述文法文件面展示模块输出结果
41 符号表测试
图6 符号表测试
输出结果 <符号编号符号否终结符>
预期结果相
图7 产生式表测试
42 产生式表测试
输出结果读入文件中产生式相产生式中符号编号正确
43 项目集规范族表测试
图8 DFA表测试
输出结果 <状态编号> :<产生式编号产生式项目编号项目转移目标状态>
预期结果相
44 LR(0)分析表测试
图9 分析表测试
输出结果分析表预期结果相
45 LR(0)分析器测试
输入字符串accd#acad#例图10 分析器测试
表达式分析结果正确
五 总结展
完成编译原理课程设计感十分疲惫份富成感欣喜胜十分疲惫次选题匆忙选道较难度题目做课程设计程中翻阅相关资料课中点止知识进行更加深入学更加深入理解做课程设计程痛苦星期次熬夜战斗时甚顾吃饭揪出程序中错误精益求精完成课程设计写份总结时候发现点累反兴奋成感
通次课程设计发现实践检验学深度学成果唯途径课知识点浓缩精华理阐述做面面俱学知识然直接运实际情况实践程中需学知识进行定程度扩充次课程设计涉算法LR分析器动构造程序机制原理C++语言C++语言实现次课程设计程中更加熟悉C++语言语法机制语言规范实现LR分析器动构造程序程中更加熟悉构造程序原理相关算法
时间匆忙完成课程设计足处工作继续完善提交作业会放里会继续完善更加性化具操作性做视化界面出丰富功相信工作更加彩丰富更加成感
附录
说明:附录中包含次课程设计代码
Closure_Listh
#ifndef CLOSURE_LIST_H
#define CLOSURE_LIST_H
#include Formula_Listh
#include LR0_Tableh
struct Item_Name_Type
{
int Formula_Num
int Formula_Item
}
struct Closure_Child_Node
{
Item_Name_Type Item_Name
int Destination
Closure_Child_Node *Next_Item
}
struct Closure_Parent_Node
{
int Current_State
Closure_Parent_Node *Next_State
Closure_Child_Node *Item
}
class Closure_List
{
private
Closure_Parent_Node *Closure_List_head
Closure_Parent_Node *GoToSet_Parent
Closure_Parent_Node *Current_Parent
Closure_Child_Node *GoToSet_Child
Closure_Child_Node *Current_Child
int AmountOf_State
Formula_List sub_Formula_List
LR0_Table sub_LR0_Table
public
Closure_List()sub_Formula_List()sub_LR0_Table()
{
Closure_List_head NULL
GoToSet_Parent NULL
Current_Parent NULL
GoToSet_Child NULL
Current_Child NULL
AmountOf_State 0
Create_Closure_List()
}
~Closure_List()
void print_Closure_List()
void make_LR0_Table()
void print_LR0_Table()
void Output_LR0_Table_ToFile()
bool Sentence_Analyse(const char Sentence[50])
private
void Add_Clousure()
bool Add_GoToSet()
void Set_Initial_State()
bool Is_Same_State_Exist(const int Formula_Numconst int Formula_Itemint& Same_State_Num)
void Create_Closure_List()
void Destroy_Closure_List()
}
#endif
Formula_Listh
#ifndef FORMULA_LIST_H
#define FORMULA_LIST_H
#include Sign_Listh
struct Formula_List_ChildItem
{
int Sign_Name
Formula_List_ChildItem* Next_Sign
}
struct Formula_List_ParentItem
{
int Formula_Num
int Vn_Name
int Formula_Length
Formula_List_ParentItem* Next_Vn
Formula_List_ChildItem* Formula
}
class Formula_List
{
private
Formula_List_ParentItem *Formula_List_head
Formula_List_ChildItem *current_Formula_Item
Formula_List_ParentItem *current_VnNode
Sign_List Sub_Sign_List
public
Formula_List()Sub_Sign_List()
{
Formula_List_head NULL
current_Formula_Item NULL
current_VnNode NULL
Create_Formula_List()
}
~Formula_List()
void print_Formula_List()
int int_check_Sign_Name(const char word)
char char_check_Sign_Name(const int Sign_Name)
int Get_Formula_Length(const int Formula_Num)
int Get_Sign_Name(const int Formula_Num const int Item_Num)
int Get_Formula_LeftVn(const int Formula_Num)
bool Is_Sign_Name_Vn(const int Sign_Name)
int Get_AmountOf_Identity()
private
void Destroy_Formula_List()
void Create_Formula_List()
}
#endif
LR0_Tableh
#ifndef LR0_TABLE_H
#define LR0_TABLE_H
#include
#include
using namespace std
#include ConstValueh
struct LR0_Table_Child
{
char Operation
int Oprand
bool Has_Been_Filled
LR0_Table_Child *Next_Table_Child
}
struct LR0_Table_Parent
{
LR0_Table_Child *Table_Child
LR0_Table_Parent *Next_Table_Parent
}
class LR0_Table
{
private
LR0_Table_Parent *LR0_Table_head
LR0_Table_Parent *Current_Parent
LR0_Table_Child *Current_Child
public
LR0_Table()
~LR0_Table()
void initial(const int AmountOf_State const int AmountOf_Identity)
bool Fill_In_Table(const int State_Num const int Identity_Num
const char char_Opration const int int_Oprand)
void _OutputToFile()
void _print_LR0_Table()
void Visit_LR0_Table(const int State_Num const int Identity_Num
char& char_Opration int& int_Oprand)
private
void Destroy_LR0_Table()
}
#endif
Sign_Listh
#ifndef SIGN_LIST_H
#define SIGN_LIST_H
#include
#include
using namespace std
#include ConstValueh
struct Sign_List_item
{
char Identity
bool Is_Vn
Sign_List_item *next_Identity
}
struct Identity_List_item
{
char Identity
bool Is_Vn
}
class Sign_List
{
private
Identity_List_item *Identity_List
int AmountOf_Identity
public
Sign_List()
~Sign_List()
void print_Identity_List()
int _int_check_Sign_Name(const char word)
char _char_check_Sign_Name(const int Sign_Name)
bool _Is_Sign_Name_Vn(const int Sign_Name)
int _Get_AmountOf_Identity()
private
void Destroy_temp_Sign_List()
void Create_Identity_List()
private
Sign_List_item *current_Identity
Sign_List_item *head
bool Is_sameIdentity_Exist(const char word)
}
#endif
Stackh
#ifndef STACK_H
#define STACK_H
struct elem
{
int data
elem *next
}
class Stack
{
private
elem *top
int count
public
Stack()
~Stack()
bool pushElem(const int Data)
bool getElem(int &Data)
bool popElem()
int countElem()const
}
#endif
Closure_Listcpp
#include Closure_Listh
#include Stackh
bool Closure_ListAdd_GoToSet()
{
int temp_Formula_Length
sub_Formula_ListGet_Formula_Length(GoToSet_Child>Item_NameFormula_Num)
if (GoToSet_Child>Item_NameFormula_Item < temp_Formula_Length)
{
int SameDestination 0
if (Is_Same_State_Exist(GoToSet_Child>Item_NameFormula_Num
GoToSet_Child>Item_NameFormula_Item +1SameDestination)true)
{
GoToSet_Child>Destination SameDestination
return false
}
Closure_Child_Node *tempChild new Closure_Child_Node
tempChild>Item_NameFormula_Num GoToSet_Child>Item_NameFormula_Num
tempChild>Item_NameFormula_Item GoToSet_Child>Item_NameFormula_Item +1
tempChild>Next_Item NULL
Current_Child tempChild
Closure_Parent_Node *tempParent new Closure_Parent_Node
tempParent>Item tempChild
tempParent>Next_State NULL
tempParent>Current_State Current_Parent>Current_State +1
Current_Parent>Next_State tempParent
Current_Parent tempParent
GoToSet_Child>Destination Current_Parent>Current_State
++AmountOf_State
return true
}else
{
GoToSet_Child>Destination 1
return false
}
}
void Closure_ListAdd_Clousure()
{
int temp_Sign_Name
sub_Formula_ListGet_Sign_Name(GoToSet_Child>Item_NameFormula_Num
GoToSet_Child>Item_NameFormula_Item +1)
if (temp_Sign_Name1)
{
return
}
if (sub_Formula_ListIs_Sign_Name_Vn(temp_Sign_Name)true)
{
int temp_Formula_Num 1
int temp_Vn_Name 0
while ((temp_Vn_Name sub_Formula_ListGet_Formula_LeftVn(temp_Formula_Num))1)
{
if (temp_Sign_Nametemp_Vn_Name)
{
Closure_Child_Node *tempChild new Closure_Child_Node
tempChild >Item_NameFormula_Num temp_Formula_Num
tempChild >Item_NameFormula_Item 1
tempChild>Next_Item NULL
Current_Child>Next_Item tempChild
Current_Child tempChild
}
++temp_Formula_Num
}
}
}
void Closure_ListSet_Initial_State()
{
Closure_List_head new Closure_Parent_Node
Closure_List_head>Current_State 0
Closure_List_head>Item NULL
Closure_List_head>Next_State NULL
GoToSet_Parent Closure_List_head
Current_Parent Closure_List_head
Closure_Child_Node *tempChild new Closure_Child_Node
tempChild >Item_NameFormula_Num 1
tempChild >Item_NameFormula_Item 1
tempChild>Next_Item NULL
Closure_List_head >Item tempChild
GoToSet_Child tempChild
Current_Child tempChild
++AmountOf_State
int temp_Sign_Name sub_Formula_ListGet_Sign_Name(11)
int temp_Formula_Num 1
int temp_Vn_Name 0
while ((temp_Vn_Name sub_Formula_ListGet_Formula_LeftVn(temp_Formula_Num))1)
{
if (temp_Sign_Nametemp_Vn_Name)
{
Closure_Child_Node *tempChild new Closure_Child_Node
tempChild >Item_NameFormula_Num temp_Formula_Num
tempChild >Item_NameFormula_Item 1
tempChild>Next_Item NULL
Current_Child>Next_Item tempChild
Current_Child tempChild
}
++temp_Formula_Num
}
}
void Closure_ListCreate_Closure_List()
{
Set_Initial_State()
while (GoToSet_ParentNULL)
{
if (GoToSet_ChildNULL)
{
if (Add_GoToSet()true)
{
Add_Clousure()
}
GoToSet_Child GoToSet_Child>Next_Item
}
else
{
GoToSet_Parent GoToSet_Parent>Next_State
if (GoToSet_ParentNULL)
{
break
}
GoToSet_Child GoToSet_Parent>Item
}
}
}
void Closure_ListDestroy_Closure_List()
{
Current_Parent Closure_List_head
if (Closure_List_head NULL)
{
return
}
else
{
while (Current_Parent NULL)
{
Closure_Parent_Node *temp_ToDelete Current_Parent
Current_Child Current_Parent>Item
while (Current_Child NULL)
{
Closure_Child_Node *ToDelete Current_Child
Current_Child Current_Child>Next_Item
delete ToDelete
}
Current_Parent Current_Parent>Next_State
delete temp_ToDelete
}
}
Closure_List_head NULL
GoToSet_Parent NULL
Current_Parent NULL
GoToSet_Child NULL
Current_Child NULL
}
void Closure_Listprint_Closure_List()
{
Closure_Parent_Node *print_Vn_Node Closure_List_head
if (Closure_List_head NULL)
{
return
}
else
{
while (print_Vn_Node NULL)
{
cout<
Closure_Child_Node *pirnt_Item_Node print_Vn_Node>Item
while (pirnt_Item_Node NULL)
{
cout<<'<'<
<
<
pirnt_Item_Node pirnt_Item_Node>Next_Item
}
cout<
}
}
}
bool Closure_ListIs_Same_State_Exist(const int Formula_Numconst int Formula_Item
int& Same_State_Num)
{
Closure_Parent_Node *Check_Parent_Node Closure_List_head
while (Check_Parent_Node NULL)
{
if (Check_Parent_Node>Item>Item_NameFormula_Item Formula_Item &&
Check_Parent_Node>Item>Item_NameFormula_Num Formula_Num)
{
Same_State_Num Check_Parent_Node>Current_State
return true
}
Check_Parent_Node Check_Parent_Node>Next_State
}
Same_State_Num 1
return false
}
void Closure_Listmake_LR0_Table()
{
sub_LR0_Tableinitial(AmountOf_Statesub_Formula_ListGet_AmountOf_Identity())
Closure_Parent_Node *Traverse_Parent Closure_List_head
Closure_Child_Node *Traverse_Child Closure_List_head>Item
bool No_ErrorOccurIn_FillingTable true
while (Traverse_ParentNULL)
{
Item_Name_Type Traverse_Item
Traverse_ItemFormula_Num Traverse_Child>Item_NameFormula_Num
Traverse_ItemFormula_Item Traverse_Child>Item_NameFormula_Item
int CurrentFormulalength
sub_Formula_ListGet_Formula_Length(Traverse_ItemFormula_Num)
if (Traverse_ItemFormula_Item
int Traverse_Sign_Name sub_Formula_ListGet_Sign_Name(Traverse_ItemFormula_Num
Traverse_ItemFormula_Item)
int Goal_State_Num Traverse_Child>Destination
if (sub_Formula_ListIs_Sign_Name_Vn(Traverse_Sign_Name)false)
{
No_ErrorOccurIn_FillingTable
sub_LR0_TableFill_In_Table(Traverse_Parent>Current_State
Traverse_Sign_Name's'Goal_State_Num)
}
else
{
No_ErrorOccurIn_FillingTable
sub_LR0_TableFill_In_Table(Traverse_Parent>Current_State
Traverse_Sign_Name'g'Goal_State_Num)
}
}
else
{
int Traverse_Sign_Name sub_Formula_ListGet_Sign_Name(Traverse_ItemFormula_Num
Traverse_ItemFormula_Item1)
if (Traverse_Sign_Name1)
{
No_ErrorOccurIn_FillingTable
sub_LR0_TableFill_In_Table(Traverse_Parent>Current_State
sub_Formula_ListGet_AmountOf_Identity()'a'1)
}
else
{
for (int i0 i
if (sub_Formula_ListIs_Sign_Name_Vn(i)false)
{
No_ErrorOccurIn_FillingTable
sub_LR0_TableFill_In_Table(Traverse_Parent>Current_State
i'r'Traverse_ItemFormula_Num)
}
}
No_ErrorOccurIn_FillingTable
sub_LR0_TableFill_In_Table(Traverse_Parent>Current_State
sub_Formula_ListGet_AmountOf_Identity()'r'Traverse_ItemFormula_Num)
}
}
if (No_ErrorOccurIn_FillingTablefalse)
{
cout<
}
if (Traverse_Child>Next_ItemNULL)
{
Traverse_Child Traverse_Child>Next_Item
}
else
{
if (Traverse_Parent>Next_StateNULL)
{
Traverse_Parent Traverse_Parent>Next_State
Traverse_Child Traverse_Parent>Item
}
else
{
break
}
}
}
}
void Closure_Listprint_LR0_Table()
{
for (int i1 i
cout<<' '<
cout<< #\t state<
}
void Closure_ListOutput_LR0_Table_ToFile()
{
ofstream fout(OUTPUT_FILE_NAMEiosout)
for (int i1 i
fout<<' '<
fout<< #\t state<
sub_LR0_Table_OutputToFile()
}
bool Closure_ListSentence_Analyse(const char Sentence[50])
{
Stack State_Stack
State_StackpushElem(0)
char Read_Charactor '\0'
int Read_Sign_Name 0
int Table_Check_Oprand 0
char Table_Check_Opration '\0'
int Read_Index 0
int Current_Stack_State 0
bool Do_Continue true
while (Do_Continuetrue)
{
Read_Charactor Sentence[Read_Index]
if (Read_Charactor'#')
{
Read_Sign_Name sub_Formula_ListGet_AmountOf_Identity()
}
else
{
Read_Sign_Name sub_Formula_Listint_check_Sign_Name(Read_Charactor)
if (Read_Sign_Name1)
{
cout<
}
}
State_StackgetElem(Current_Stack_State)
sub_LR0_TableVisit_LR0_Table(Current_Stack_State Read_Sign_Name
Table_Check_Opration Table_Check_Oprand)
switch (Table_Check_Opration)
{
case 'r'
{
int j sub_Formula_ListGet_Formula_Length(Table_Check_Oprand)
for (int i0 i
State_StackpopElem()
}
State_StackgetElem(Current_Stack_State)
Read_Sign_Name sub_Formula_ListGet_Formula_LeftVn(Table_Check_Oprand)
sub_LR0_TableVisit_LR0_Table(Current_Stack_State Read_Sign_Name
Table_Check_Opration Table_Check_Oprand)
State_StackpushElem(Table_Check_Oprand)
}
break
case 's'
{
State_StackpushElem(Table_Check_Oprand)
++Read_Index
}
break
case 'g'
{
State_StackpushElem(Table_Check_Oprand)
}
break
case 'a'
{
cout<
}
break
case '\0'
{
cout<
}
break
}
}
return true
}
Closure_List~Closure_List()
{
Destroy_Closure_List()
}
Formula_Listcpp
#include Formula_Listh
Formula_List~Formula_List()
{
Destroy_Formula_List()
}
void Formula_Listprint_Formula_List()
{
Formula_List_ParentItem *print_Vn_Node Formula_List_head
if (Formula_List_head NULL)
{
return
}
else
{
while (print_Vn_Node NULL)
{
cout<
<<'('<
Formula_List_ChildItem *pirnt_Item_Node print_Vn_Node>Formula
while (pirnt_Item_Node NULL)
{
cout<
<<'('<
pirnt_Item_Node pirnt_Item_Node>Next_Sign
}
cout<
}
}
}
void Formula_ListDestroy_Formula_List()
{
current_VnNode Formula_List_head
if (Formula_List_head NULL)
{
return
}
else
{
while (current_VnNode NULL)
{
Formula_List_ParentItem *temp_ToDelete current_VnNode
current_Formula_Item current_VnNode>Formula
while (current_Formula_Item NULL)
{
Formula_List_ChildItem *ToDelete current_Formula_Item
current_Formula_Item current_Formula_Item>Next_Sign
delete ToDelete
}
current_VnNode current_VnNode>Next_Vn
delete temp_ToDelete
}
}
current_VnNode NULL
current_Formula_Item NULL
}
void Formula_ListCreate_Formula_List()
{
ifstream fcin(INPUT_FILE_NAMEiosin)
if ( fcin)
{
cerr<
}
char word '\0'
bool Is_FirstNode true
bool Is_Vn_Node false
while ((word fcinget())EOF)
{
if (word' ' || word'' || word'>' || word'\n')
{
if ( word'\n' )
{
Is_Vn_Node true
}
continue
}
else
{
int Sign_Name Sub_Sign_List_int_check_Sign_Name(word)
if (Is_FirstNodetrue)
{
Formula_List_head new Formula_List_ParentItem
Formula_List_head>Vn_Name Sign_Name
Formula_List_head>Formula_Num 1
Formula_List_head>Formula_Length 0
Formula_List_head>Next_Vn NULL
Formula_List_head>Formula NULL
current_VnNode Formula_List_head
Is_FirstNode false
}
else
{
if (Is_Vn_Nodefalse)
{
Formula_List_ChildItem *tempNode new Formula_List_ChildItem
tempNode>Sign_Name Sign_Name
tempNode>Next_Sign NULL
if (current_VnNode>Formula_Length 0)
{
current_VnNode>Formula tempNode
}
else
{
current_Formula_Item>Next_Sign tempNode
}
current_Formula_Item tempNode
++(current_VnNode>Formula_Length)
}
else
{
Formula_List_ParentItem *tempNode new Formula_List_ParentItem
tempNode>Formula_Length 0
tempNode>Formula_Num current_VnNode>Formula_Num +1
tempNode>Vn_Name Sign_Name
tempNode>Formula NULL
tempNode>Next_Vn NULL
current_VnNode>Next_Vn tempNode
current_VnNode tempNode
Is_Vn_Node false
}
}
}
}
fcinclose()
}
int Formula_ListGet_Formula_Length(const int Formula_Num)
{
Formula_List_ParentItem *current Formula_List_head
if (Formula_Num1 && currentNULL)
{
return 1
}
for (int i0 i
if (current>Next_Vn NULL)
{
return 1
}else
{
current current>Next_Vn
}
}
return (current>Formula_Length)
}
int Formula_ListGet_Sign_Name(const int Formula_Num const int Item_Num)
{
Formula_List_ParentItem *current_Parent Formula_List_head
if (Formula_Num1 && current_ParentNULL)
{
return 1
}
for (int i0 i
if (current_Parent>Next_Vn NULL)
{
return 1
}else
{
current_Parent current_Parent>Next_Vn
}
}
Formula_List_ChildItem *current_Child current_Parent>Formula
if (Item_Num1 && current_ChildNULL)
{
return 1
}
for (int j0 j
if (current_Child>Next_SignNULL)
{
return 1
}else
{
current_Child current_Child>Next_Sign
}
}
return current_Child>Sign_Name
}
int Formula_ListGet_Formula_LeftVn(const int Formula_Num)
{
Formula_List_ParentItem *current Formula_List_head
if (Formula_Num1 && currentNULL)
{
return 1
}
for (int i0 i
if (current>Next_Vn NULL)
{
return 1
}else
{
current current>Next_Vn
}
}
return (current>Vn_Name)
}
int Formula_Listint_check_Sign_Name(const char word)
{
return Sub_Sign_List_int_check_Sign_Name(word)
}
char Formula_Listchar_check_Sign_Name(const int Sign_Name)
{
return Sub_Sign_List_char_check_Sign_Name(Sign_Name)
}
bool Formula_ListIs_Sign_Name_Vn(const int Sign_Name)
{
return Sub_Sign_List_Is_Sign_Name_Vn(Sign_Name)
}
int Formula_ListGet_AmountOf_Identity()
{
return Sub_Sign_List_Get_AmountOf_Identity()
}
LR0_Tablecpp
#include LR0_Tableh
LR0_TableLR0_Table()
{
LR0_Table_head NULL
Current_Parent NULL
Current_Child NULL
}
void LR0_Tableinitial(const int AmountOf_State const int AmountOf_Identity)
{
bool Is_First_Node true
for (int i0 i
LR0_Table_Parent *tempParent new LR0_Table_Parent
tempParent>Next_Table_Parent NULL
if (Is_First_Nodetrue)
{
LR0_Table_head tempParent
Is_First_Node false
Current_Parent tempParent
}
else
{
Current_Parent>Next_Table_Parent tempParent
Current_Parent tempParent
}
bool Is_First_Child true
for (int j0 j
LR0_Table_Child *tempChild new LR0_Table_Child
tempChild>Next_Table_Child NULL
tempChild>Operation '\0'
tempChild>Oprand 0
tempChild>Has_Been_Filled 0
if (Is_First_Childtrue)
{
Current_Parent>Table_Child tempChild
Current_Child tempChild
Is_First_Child false
}
else
{
Current_Child>Next_Table_Child tempChild
Current_Child tempChild
}
}
}
}
LR0_Table~LR0_Table()
{
Destroy_LR0_Table()
}
void LR0_TableDestroy_LR0_Table()
{
if (LR0_Table_headNULL)
{
return
}
Current_Parent LR0_Table_head
while (Current_ParentNULL)
{
LR0_Table_Parent *ToBe_Deleted_Parent Current_Parent
Current_Child Current_Parent>Table_Child
Current_Parent Current_Parent>Next_Table_Parent
while (Current_ChildNULL)
{
LR0_Table_Child *ToBe_Deleted_Child Current_Child
Current_Child Current_Child>Next_Table_Child
delete ToBe_Deleted_Child
}
delete ToBe_Deleted_Parent
}
}
bool LR0_TableFill_In_Table(const int State_Num const int Identity_Num const char char_Opration
const int int_Oprand)
{
Current_Parent LR0_Table_head
for (int i0 i
Current_Parent Current_Parent>Next_Table_Parent
}
Current_Child Current_Parent>Table_Child
for (int j0 j
Current_Child Current_Child>Next_Table_Child
}
if (Current_Child>Has_Been_Filledfalse)
{
Current_Child>Operation char_Opration
Current_Child>Oprand int_Oprand
Current_Child>Has_Been_Filled true
return true
}
else
{
return false
}
}
void LR0_TableVisit_LR0_Table(const int State_Num const int Identity_Num
char& char_Opration int& int_Oprand)
{
Current_Parent LR0_Table_head
for (int i0 i
Current_Parent Current_Parent>Next_Table_Parent
}
Current_Child Current_Parent>Table_Child
for (int j0 j
Current_Child Current_Child>Next_Table_Child
}
char_Opration Current_Child>Operation
int_Oprand Current_Child>Oprand
}
void LR0_Table_print_LR0_Table()
{
if (LR0_Table_headNULL)
{
return
}
Current_Parent LR0_Table_head
int index 0
while (Current_ParentNULL)
{
Current_Child Current_Parent>Table_Child
Current_Parent Current_Parent>Next_Table_Parent
while (Current_ChildNULL)
{
cout<
Current_Child Current_Child>Next_Table_Child
}
cout<< <
}
}
void LR0_Table_OutputToFile()
{
if (LR0_Table_headNULL)
{
return
}
ofstream fout(OUTPUT_FILE_NAMEiosapp|iosout)
Current_Parent LR0_Table_head
int index 0
while (Current_ParentNULL)
{
Current_Child Current_Parent>Table_Child
Current_Parent Current_Parent>Next_Table_Parent
while (Current_ChildNULL)
{
fout<
Current_Child Current_Child>Next_Table_Child
}
fout<< <
}
foutclose()
}
Sign_Listh
#include Sign_Listh
Sign_ListSign_List()
{
head NULL
current_Identity NULL
ifstream fcin(INPUT_FILE_NAMEiosin)
if ( fcin)
{
cerr<
}
char word '\0'
bool Is_FirstNode 1
while ((word fcinget())EOF)
{
if (Is_FirstNode 1)
{
head new Sign_List_item
head>Identity word
if (word>65 && word<90)
{
head>Is_Vn 1
}
else
{
head>Is_Vn 0
}
AmountOf_Identity 1
head>next_Identity NULL
current_Identity head
Is_FirstNode 0
}else
{
if (word' ' || word'' || word'>' || word'\n')
{
continue
}
else if ( Is_sameIdentity_Exist(word))
{
Sign_List_item *tempNode new Sign_List_item
tempNode>Identity word
if (word>65 && word<90)
{
tempNode>Is_Vn 1
}
else
{
tempNode>Is_Vn 0
}
tempNode>next_Identity NULL
current_Identity>next_Identity tempNode
current_Identity tempNode
++AmountOf_Identity
}
}
}
fcinclose()
Create_Identity_List()
Destroy_temp_Sign_List()
}
int Sign_List_int_check_Sign_Name(const char word)
{
for (int i0 i
if (wordIdentity_List[i]Identity)
{
return i
}
}
return 1
}
char Sign_List_char_check_Sign_Name(const int Sign_Name)
{
if (Sign_Name>AmountOf_Identity)
{
return '\0'
}else
{
return Identity_List[Sign_Name]Identity
}
}
bool Sign_List_Is_Sign_Name_Vn(const int Sign_Name)
{
return Identity_List[Sign_Name]Is_Vn
}
int Sign_List_Get_AmountOf_Identity()
{
return AmountOf_Identity
}
void Sign_ListCreate_Identity_List()
{
Identity_List new Identity_List_item[AmountOf_Identity]
Sign_List_item *current head
for (int i0 i
Identity_List[i]Identity current>Identity
Identity_List[i]Is_Vn current>Is_Vn
current current>next_Identity
}
}
void Sign_ListDestroy_temp_Sign_List()
{
int copy_AmountOf_Identity AmountOf_Identity
if (copy_AmountOf_Identity 0)
{
return
}
else
{
while (copy_AmountOf_Identity0)
{
current_Identity head>next_Identity
delete head
copy_AmountOf_Identity
head current_Identity
}
}
head current_Identity NULL
}
Sign_List~Sign_List()
{
delete []Identity_List
}
void Sign_Listprint_Identity_List()
{
for (int i0 i
cout<
}
bool Sign_ListIs_sameIdentity_Exist(const char word)
{
Sign_List_item *check_item head
while (check_itemNULL)
{
if (word check_item>Identity)
{
return true
}
else
{
check_item check_item>next_Identity
}
}
return false
}
Stackcpp
#include Stackh
#define NULL 0
StackStack()
{
count0
topNULL
}
bool StackpushElem(const int Data)
{
if(count0)
{
topnew elem
top>dataData
top>nextNULL
++count
return true
}
else
{
elem *tempnew elem
temp>dataData
temp>nexttop
toptemp
++count
return true
}
}
bool StackgetElem(int &Data)
{
if(count0) return false
Datatop>data
return true
}
bool StackpopElem()
{
if(count0) return false
if(count1)
{
delete top
topNULL
count
}
else
{
elem *temptop
toptop>next
delete temp
count
}
return true
}
int StackcountElem()const
{
return count
}
Stack~Stack()
{
cout<
if(count0) return
elem *tempNULL
for(int i1i
temptop
toptop>next
delete temp
}
delete top
topNULL
}
Maincpp
#include
using namespace std
#include Closure_Listh
#include Sign_Listh
#include Formula_Listh
int main()
{
Closure_List list
listmake_LR0_Table()
listprint_LR0_Table()
Closure_List List
Listprint_Closure_List()
Listmake_LR0_Table()
Listprint_LR0_Table()
ListOutput_LR0_Table_ToFile()
注意:输入空格
char sentence[50]
cin>>sentence
listSentence_Analyse(sentence)
cout<<\n\n
cin>>sentence
listSentence_Analyse(sentence)
return 0
}
参考文献
[1] 陈火旺刘春林谭庆赵克佳刘越 程序设计语言编译原理 国防工业出版社 2006
[2] 谭浩强 C++程序设计 清华学出版社 2007
衡yang师范学院
文档香网(httpswwwxiangdangnet)户传
《香当网》用户分享的内容,不代表《香当网》观点或立场,请自行判断内容的真实性和可靠性!
该内容是文档的文本内容,更好的格式请下载文档