第1页 / 共9页
第2页 / 共9页
第3页 / 共9页
第4页 / 共9页
第5页 / 共9页
第6页 / 共9页
第7页 / 共9页
第8页 / 共9页
SLR（1）分析表的生成.doc
1．为了程序读取的方便，非/终结符相互间以空格分开。
例如
应该输入：
E -> E + T
T -> T * F | T
F -> ( E ) | id
E -> T
而不是输入：
E->E+T
……
文法先保存到文件中然后程序读取文件。
2．文法的拓展
为了在 LR 分析时能够指示分析器正确停止并接受输入，一般在所有输入文法前加上一个新的产生式，
以上面文法为例，我们要保存的文法应该是如此：
E’ -> E
E -> E + T
E -> T * F | T
……
3．文法的表示格式
设计一个类 Grammar 来对文法进行各种处理。
首先把文件中的文法保存到一个序偶表中，以上面的文法为例子，我们保存的格式类似于下面的表
非终结符
E
T
F
产生试右部
E + T
T
T * F
T
( E )
Id
也就是说，每一个项是一个 2 元组,记录了终结符，和产生式右部。其中非终结符可以用字符串类型表
示，产生式右部可用字符串数组表示。而在保存的同时又可记录下文法的所有非终结符（因为文法的产生
式左部会出现所有的非终结符），然后再对已经记录的文法的产生式右部再扫描一遍，记录下所有的终结
符。
在本程序中，我虽然记录了原始的符号串，但是在具体过程处理时使用的是符号串对应的下标来进行
的，因此再对原始形式的文法再扫描一遍，生成对应的以下标形式表示的文法。同时将终结符号和非终结
符号以下标的方式保存，采用方式是建立一个下标数据结构 Index 来保存下标
struct Index
{
int
bool
bool
}
index;
teminal;
is_teminal();
// [非终结符或者终结符的下标]
// [为真表示该下标保存的是终结符]
//[下标为终结符则返回 true]
现在往类 Grammar 中加入数据成员为:
vector< pair< string/*非终结符号*/,vector/*产生式右部
*/ > >
m_s_grammar ; // [记录以字符串形式保存的文法]
vector< vector > >
// [记录以下标保存的文法]
MyCollection
MyCollection
m_s_nonteminals;
m_s_terminals;
m_idx_grammar;
// [记录原始的非终结符号串]
// [记录原始的终结符号串]
现在已经可以对文法进行保存了，接下来要对文法进行相关处理了。
4．项目规范集的生成
如果有产生式
E -> A | B
则其对应的所有项目为
E -> .A
E –> A .
E -> .B
E -> B .
其实就是多了一个插在符号之间的点“.”
项目的数据结构为
struct Item
{
int index_of_nont;
int index_of_pro;
int index_of_dot;
// [该项目所在的非终结符位置]
// [该项目对应该非终结符的产生式位置]
// [记录点的位置]
}
{0, 0, 0 }
{0, 0, 1 }
{0, 0, 2 }
为了方便（不考虑内存空间的因素），我把所有的项目保存到一个数组中。
Item_0
Item_1
Item_2
……
Item_i
……
其中数据类型为
{0, m , n }
vector- m_items; // [记录所有的项目]
5.项目集合及其相关运算
一个项目集合包含了多个项目，也等价于后面要建立的自动机的一个状态。
本程序中对项目集合中存储的项目，我采取的也是下标形式存储。因此项目集合的数据结构为：
struct Item_c
{
vector
index_c;
int operator[](int index);
int size();
bool operator == ();
Item_c& operator = (const Item_c& item);
void push_back(int idx);
void clear();
}
之所以为项目集合新建一个类来封装一个数组，是为了能够支持相等的语义。因为在之后要建立自动
机时会对状态进行等价判断，而状态的类型估计我会直接这样表示:
typedef Item_c TypeState; // [一般进行别名定义时，我喜欢在类型前加上 Type]
下面我定义一下项目集合的闭包函数, 在这之前我要定义一个辅助函数：
// [返回项目的类型，如果不是规约项目，还返回点的下一位置的符号下标信息]
enum ItemType
{
IT_R = 0;
IT_S ,
IT_A ,
IT_IVALID
// [规约]
// [移进]
// [接受]
// [非法]
}
ItemType get_info_of_next_index(const Item& item, Index& out_index)
{
// [如果点的位置在最后，则表示规约项目]
if(item.index_of_dot>=m_idx_grammar[item.index_of_nont][item.index_of_pro].size())
{
// [判断是否为接受项目]
if(m_idx_grammar[item.index_of_nont][item.index_of_pro][ item.index_of_dot - 1]
== this->get_pre_idx_start()
/*获得开始符号下标,输入时的而不是扩展后的*/)
{
}
return IT_A;
return IT_R;
}
// [暂时不做下标越界判断]
out_index =
this->m_idx_grammar[item.index_of_nont][item.index_of_pro][item.index_of_dot];
return IT_S;
}
// [获得非终结符的项目下标集，条件是项目的点在最前面]
vector& get_itemc_of_nont_dot_at_begin(const Index& index,vector& out_itemc)
{
/* [首先获得该非终结符的项目开始位置] */
Item tmp_item(index.index,0,0);
vector- ::const_iterator it = find( m_items.begin(),m_items.end(),tmp_item );
if( it != m_items.end() )
{
unsigned int idx_pos = unsigned int(it - m_items.begin());
out_itemc.push_back(idx_pos);
for(unsigned int i=1 ; i
tmp_itemc;
get_itemc_of_nont_dot_at_begin(nxt_index,tmp_itemc)
for_each(tmp_itemc.begin(),tmp_itemc.end(),item_c.
}
{
}
;
add_item );
}
}
// [GOTO 运算]
// [首先我要定义个个项目集合表来保存所有的项目集合，然后再对索引进行计算]
vector
Item_c& goto(const Item_c& in_item,
m_item_c_list;
const string& label,
const Item_c& out_item)
{
for(unsigned int i=0; i
Index nxt_idx;
if(IT_S==
this->get_info_of_next_index(m_items[in_itemc[i]],nxt_idx) )
的位置加一]*/
{
}
if(nxt_idx == in_idx)
{
/*[根据保存的结构可知道，下一个项目的位置是当前项目
out_item.add_item(in_itemc[i] + 1);
}
}
/*[接着对该项目集合进行闭包运算]*/
return this->closure(out_item);;
}
接下来可以生成项目集规范族了，生成的方法是：
(1)获得项目集合 item_c 中点的位置的下一个符号的下标集合 index_collection。
(2)然后对下标集合的每一个下标求 goto(item_c, index_collection[i] )
(3)记录集合之间的状态转换信息( DFA )
/*—————————————————————————————————/
* Desc:
*
Parm
生成项目集规范族
/—————————————————————————————————*/
void
{
Grammar::gen_itemc()
Item_c itemc;
/* [首先生成第一个项目集，包含第一个项目] */
itemc.add_item(0);
this->closure(itemc);
/*[加入项目集表中] */
this->m_item_c_list.Add(itemc);
for(unsigned int i=0; im_item_c_list.size(); i++)
{
const Item_c& cur_itemc = this->m_item_c_list.GetElement(i);
IndexCollection nxt_infos;
this->get_infos_of_next_index(cur_itemc,nxt_infos);
for(unsigned int j=0; jgo_to(i, index);
/*[记录状态转换关系] */
this->m_dfa.set_next( i, index, next_pos_of_itmc);
}
}
debug_out("项目集规范族");
debug_out(m_item_c_list);
}
6.First,Follow 集的生成
由于之前我已经完成了 LL1 语法器的生成。这里仅是借鉴了之前的代码。下面是类的声明和部分实
现
#include "TypeDefine.h"
#include "Grammar.h"
#include
#include
using namespace std;
class First
{
public:
typedef Grammar::TypeProductionItem
typedef Grammar::TypeProduction
typedef Grammar::TypeProductionList
typedef
TypeProductionItem;
TypeProduction
;
TypeProductionList;
CustomCollection
TypeFirstCollection;
typedef deque
TypeFirstListCollection;
public:
First(const Grammar& grammar);
~First(void);
/* [计算规则的 First 集] */
void
/* [返回 First 集] */
Calculate_First();
const TypeFirstCollection&
GetFirst(const Index& index)const;
TypeFirstCollection&
TypeFirstCollection&
TypeProductionItem::const_iterator begin,
TypeProductionItem::const_iterator end,
GetFirst(const TypeProductionItem&
grammar,TypeFirstCollection& outC)const;
GetFirst(const
const
TypeFirstCollection& outC)const;
/* [返回字符串形式] */
string
protected:
ToString();
/* [计算 First] */
TypeFirstCollection& Calculate_First(const TypeProductionItem& pro_itm,
TypeFirstCollection& firstC);
TypeFirstCollection& Calculate_First(TypeProductionItem::const_iterator begin,
TypeProductionItem::const_iterator end,
TypeFirstCollection& firstC);
TypeFirstCollection& Calculate_First(const TypeProduction& production,
TypeFirstCollection& firstC);
TypeFirstCollection& Calculate_First(const Index& index, TypeFirstCollection&
firstC);
TypeFirstCollection& Calculate_First(
TypeProductionItem::const_iterator begin,
TypeProductionItem::const_iterator end,
TypeFirstCollection& firstC)const;
protected:
const Grammar&
map
alculated;
TypeFirstListCollection
_nonterminal;
TypeFirstListCollection
_terminal;
};
#include "Grammar.h"
#include "First.h"
#include "CustomCollection.h"
#include
using namespace std;
class Follow
{
public:
typedef Grammar::TypeProductionItem
typedef Grammar::TypeProduction
typedef Grammar::TypeProductionList
typedef
m_grammar;
m_has_c
m_first_of
m_first_of
TypeProductionItem;
TypeProduction
;
TypeProductionList;
CustomCollection
TypeFollowCollection;
typedef deque
TypeFollowListCollection;
public:
Follow(const First& _first,const Grammar
~Follow(void);
&_grammar);
public:
/* [计算规则的 Follow 集] */
void
/* [返回某个非终结符的 Follow 集] */
const TypeFollowCollection&
Calculate_Follow();
/* [字符串显示] */
string ToString()const;
protected:
GetFollow(int vn_index)const;
/* [根据课本第 2 个规则计算 Follow 集] */
TypeFollowCollection&
Calculate_Follow_2nd_rules(const Index&
vn_index,TypeFollowCollection& outC);
/* [根据第 3 个规则计算，注意必须先根据第 2 个规则计算后才能调用此函数] */
TypeFollowCollection&
Calculate_Follow_3rd_rules(const Index&
m_first;
m_grammar;
m_follow_of_nonterminal;
m_helper;
// [在根据第三个条件
m
vn_index,TypeFollowCollection& outC);
protected:
const First&
const Grammar&
TypeFollowListCollection
deque >
求 Follow 集时辅助]
bool
_has_calculated;
};
7.分析表的生成
#pragma once
#include "Grammar.h"
#include "TypeDefine.h"
#include "First.h"
#include "Follow.h"
#include
#include
using namespace std;
class SLR_Table
{
public:
typedef deque >
typedef deque
>
TypeAction;
TypeGoto;
public:
SLR_Table(const Grammar&
m_grammar,const First& first,const Follow&
follow);
~SLR_Table(void);
/* [生成 SLR 分析表]*/
bool
gen_table(string& error_str);
/* [返回 GOTO 值] */
bool
get_goto(int ,const Index& index, int& );
相关推荐
2023年江西萍乡中考道德与法治真题及答案.doc
2012年重庆南川中考生物真题及答案.doc
2013年江西师范大学地理学综合及文艺理论基础考研真题.doc
2020年四川甘孜小升初语文真题及答案I卷.doc
2020年注册岩土工程师专业基础考试真题及答案.doc
2023-2024学年福建省厦门市九年级上学期数学月考试题及答案.doc
2021-2022学年辽宁省沈阳市大东区九年级上学期语文期末试题及答案.doc
2022-2023学年北京东城区初三第一学期物理期末试卷及答案.doc
2018上半年江西教师资格初中地理学科知识与教学能力真题及答案.doc
2012年河北国家公务员申论考试真题及答案-省级.doc
2020-2021学年江苏省扬州市江都区邵樊片九年级上学期数学第一次质量检测试题及答案.doc
2022下半年黑龙江教师资格证中学综合素质真题及答案.doc
