分享
 
 
 

[编译原理] LR分析表的生成

王朝other·作者佚名  2006-01-31
窄屏简体版  字體: |||超大  

暂时完成了 SLR ……

LR语法分析自动生成程序实验文档

1. 在程序中表示文法

1.1

文法的输入和读取

为了程序读取的方便,非/终结符相互间以空格分开。

例如

应该输入:

E

-> E + T

T

-> T * F | T

F

-> ( E ) | id

E

-> T

而不是输入:

E->E+T|T

……

文法先保存到文件中然后程序读取文件。

1.2

文法的拓展

为了在LR分析时能够指示分析器正确停止并接受输入,一般在所有输入文法前加上一个新的产生式,以上面文法为例,我们要保存的文法应该是如此:

E’ -> E + T

E

-> T * F | T

……

1.3

文法的保存格式

设计一个类Grammar来对文法进行各种处理。

首先把文件中的文法保存到一个序偶表中,以上面的文法为例子,我们保存的格式类似于下面的表

非终结符

产生试右部

E

E + T

T

T

T * F

T

F

( E )

id

也就是说,每一个项是一个2元组,记录了终结符,和产生式右部。其中非终结符可以用字符串(string)类型表示,产生式右部可用字符串数组( vector<string

> )表示。而在保存的同时又可记录下文法的所有非终结符(因为文法的产生式左部会出现所有的非终结符),然后再对已经记录的文法的产生式右部再扫描一遍,记录下所有的终结符。

在本程序中,我虽然记录了原始的符号串,但是在具体过程处理时使用的是符号串对应的下标来进行的,因此再对原始形式的文法再扫描一遍,生成对应的以下标形式保存的文法。同时我对终结符号和非终结符号的保存位于不同的数组中,于是下标就会产生冲突,我采用方式是建立一个下标数据结构 Index 来保存下标

struct

Index

{

int index; //

[非终结符或者终结符的下标]

bool teminal; // [为真表示该下标保存的是终结符]

bool is_teminal();

//[下标为终结符则返回true]

}

现在往类Grammar 中加入数据成员为:

vector< pair< string/*非终结符号*/,vector<string

>/*产生式右部*/ > > m_s_grammar

; // [记录以字符串形式保存的文法]

vector<

vector<vector<Index > > > m_idx_grammar;

// [记录以下标保存的文法]

MyCollection m_s_nonteminals; //

[记录原始的非终结符号串]

MyCollection m_s_terminals; //

[记录原始的终结符号串]

现在已经可以对文法进行保存了,接下来要对文法进行相关处理了。

2. LR(0)项目规范集的生成

2.1

LR(0)项目

如果有产生式

E

-> A | B

则其对应的所有项目为

E

-> 。A

E –> A 。

E

-> 。BZ

E

-> B 。

其实就是多了一个插在符号之间的点。

项目的数据结构为

struct

Item

{

int index_of_nont; // [该项目所在的非终结符位置]

int index_of_pro; // [该项目对应该非终结符的产生式位置]

int index_of_dot; // [记录点的位置]

}

为了方便(不考虑内存空间的因素),我把所有的项目保存到一个数组中。

Item_0 {0, 0, 0 }数据项

Item_1 {0, 0, 1 }

Item_2 {0, 0, 2 }

……

Item_i {0, m , n }

……

其中数据类型为

vector<Item

> m_items; // [记录所有的项目]

2.2

项目集合及其相关运算

一个项目集合包含了多个项目,也等价于后面要建立的自动机的一个状态。

本程序中对项目集合中存储的项目,我采取的也是下标形式存储。因此项目集合的数据结构为:

struct

Item_c

{

vector<int > 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<int>&

get_itemc_of_nont_dot_at_begin(const Index& index,vector<int>&

out_itemc)

{

/*

* [首先获得该非终结符的项目开始位置]

* */

Item

tmp_item(index.index,0,0);

vector<Item>::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<m_idx_grammar[index.index].size(); i++)

{

out_itemc.push_back(idx_pos +

m_idx_grammar[index.index][i-1].size()+1);

idx_pos +=

(int)m_idx_grammar[index.index][i].size()+1;

}

}

return out_itemc;

}

// [获得项目的闭包]

Item_c&

closure(Item_c& itemc)

{

for( int j = 0; j< itemc.size(); j++ )

{

Item

item = m_items[itemc[j]];

Index

nxt_index;

if(

IT_S == get_info_of_next_index(item,nxt_index) )

{

// [如果是非终结符]

if(

!nxt_index.is_teminal())

{

vector<int> 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

> m_item_c_list;

Item_c&

goto(const Item_c& in_item,

const string& label,

const Item_c& out_item)

{

for(unsigned

int i=0; i<in_itemc.size(); 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; i<this->m_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;

j<nxt_infos.size(); j++)

{

const Index& index =

nxt_infos.GetElement(j);

int next_pos_of_itmc = this->go_to(i,

index);

/*

* [记录状态转换关系]

* */

this->m_dfa.set_next( i, index,

next_pos_of_itmc);

}

}

debug_out("项目集规范族");

debug_out(m_item_c_list);

}

3.

First,Follow 集的生成

由于之前我已经完成了 LL1语法器的生成。这里仅是借鉴了之前的代码。下面是类的声明和部分实现

/************************************************************************/

/* Author : 陈正

/* Time : 2005/06/23

/* Desc : 计算文法的

First 集

/************************************************************************/

#include "TypeDefine.h"

#include "Grammar.h"

#include <hash_map>

#include <deque>

using namespace std;

class First

{

public:

typedef

Grammar::TypeProductionItem TypeProductionItem;

typedef

Grammar::TypeProduction TypeProduction ;

typedef

Grammar::TypeProductionList TypeProductionList;

typedef

CustomCollection<Index > TypeFirstCollection;

typedef

deque<TypeFirstCollection > TypeFirstListCollection;

public:

First(const

Grammar& grammar);

~First(void);

/*

* [计算规则的First集]

* */

void Calculate_First();

/*

* [返回First集]

* */

const TypeFirstCollection& GetFirst(const Index& index)const;

TypeFirstCollection& GetFirst(const

TypeProductionItem&

grammar,TypeFirstCollection&

outC)const;

TypeFirstCollection& GetFirst(const

TypeProductionItem::const_iterator begin, const TypeProductionItem::const_iterator

end,

TypeFirstCollection& outC)const;

/* —— 2005/06/24 ——

* [返回字符串形式]

* */

string ToString();

protected:

/*

* [计算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& m_grammar;

map<Index,bool> m_has_calculated;

TypeFirstListCollection m_first_of_nonterminal;

TypeFirstListCollection m_first_of_terminal;

};

/************************************************************************/

/* Author : 陈正

/* Time : 2005/06/23

/* Desc : 计算 follow 集

/************************************************************************/

#include "Grammar.h"

#include "First.h"

#include "CustomCollection.h"

#include <deque>

using namespace std;

class Follow

{

public:

typedef

Grammar::TypeProductionItem TypeProductionItem;

typedef

Grammar::TypeProduction TypeProduction ;

typedef

Grammar::TypeProductionList TypeProductionList;

typedef

CustomCollection<Index > TypeFollowCollection;

typedef

deque<TypeFollowCollection > TypeFollowListCollection;

public:

Follow(const

First& _first,const Grammar &_grammar);

~Follow(void);

public:

/*

* [计算规则的Follow集]

* */

void Calculate_Follow();

/*

* [返回某个非终结符的 Follow 集]

* */

const

TypeFollowCollection& GetFollow(int

vn_index)const;

/* —— 2005/06/24 ——

* [字符串显示]

* */

string

ToString()const;

protected:

/*

* [根据课本第2个规则计算Follow集]

* */

TypeFollowCollection& Calculate_Follow_2nd_rules(const

Index& vn_index,TypeFollowCollection& outC);

/*

* [根据第3个规则计算,注意必须先根据第2个规则计算后才能调用此函数]

* */

TypeFollowCollection& Calculate_Follow_3rd_rules(const

Index& vn_index,TypeFollowCollection& outC);

protected:

const

First& m_first;

const

Grammar& m_grammar;

TypeFollowListCollection m_follow_of_nonterminal;

deque<CustomCollection<Index>

> m_helper; // [在根据第三个条件求Follow集时辅助]

bool m_has_calculated;

};

4.

SLR分析表的生成

#pragma once

/************************************************************************/

/* Author : 陈正

/* Time : 2005/06/24

/* Desc : SLR 分析表

/************************************************************************/

#include "Grammar.h"

#include "TypeDefine.h"

#include "First.h"

#include "Follow.h"

#include <deque>

#include <vector>

using namespace std;

class SLR_Table

{

public:

typedef

deque<map<string, Action > > TypeAction;

typedef

deque<map<string, int > > TypeGoto;

public:

SLR_Table(const

Grammar& m_grammar,const

First& first,const Follow& follow);

~SLR_Table(void);

/* —— 2005/06/24 ——

* [生成SLR 分析表]

* */

bool gen_table(string& error_str);

/* —— 2005/06/24 ——

* [返回GOTO值]

* */

bool get_goto(int ,const Index& index,

int& );

/* —— 2005/06/24 ——

* [返回动作表]

* */

bool get_action(int cur,const Index& index,

Action& out_action)const;

/* —— 2005/06/24 ——

* [设置动作表]

* */

bool add_to_action_s(int cur,const Index&

index,int nxt);

bool add_to_action_r(int index_of_itemc,int

index_of_item,const Index& index);

bool add_to_action_a(int cur);

/* —— 2005/06/24 ——

* [设置goto表]

* */

void add_to_goto(int index_of_itemc,const

Index& index, int nxt);

/* —— 2005/06/24 ——

* [字符串显示]

* */

string ToString();

private:

const

Grammar& m_grammar;

const

First& m_first;

const

Follow& m_follow;

TypeAction m_action_table;

TypeGoto m_goto_table;

};

……

 
 
 
免责声明:本文为网络用户发布,其观点仅代表作者个人观点,与本站无关,本站仅提供信息存储服务。文中陈述内容未经本站证实,其真实性、完整性、及时性本站不作任何保证或承诺,请读者仅作参考,并请自行核实相关内容。
2023年上半年GDP全球前十五强
 百态   2023-10-24
美众议院议长启动对拜登的弹劾调查
 百态   2023-09-13
上海、济南、武汉等多地出现不明坠落物
 探索   2023-09-06
印度或要将国名改为“巴拉特”
 百态   2023-09-06
男子为女友送行,买票不登机被捕
 百态   2023-08-20
手机地震预警功能怎么开?
 干货   2023-08-06
女子4年卖2套房花700多万做美容:不但没变美脸,面部还出现变形
 百态   2023-08-04
住户一楼被水淹 还冲来8头猪
 百态   2023-07-31
女子体内爬出大量瓜子状活虫
 百态   2023-07-25
地球连续35年收到神秘规律性信号,网友:不要回答!
 探索   2023-07-21
全球镓价格本周大涨27%
 探索   2023-07-09
钱都流向了那些不缺钱的人,苦都留给了能吃苦的人
 探索   2023-07-02
倩女手游刀客魅者强控制(强混乱强眩晕强睡眠)和对应控制抗性的关系
 百态   2020-08-20
美国5月9日最新疫情:美国确诊人数突破131万
 百态   2020-05-09
荷兰政府宣布将集体辞职
 干货   2020-04-30
倩女幽魂手游师徒任务情义春秋猜成语答案逍遥观:鹏程万里
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案神机营:射石饮羽
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案昆仑山:拔刀相助
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案天工阁:鬼斧神工
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案丝路古道:单枪匹马
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案镇郊荒野:与虎谋皮
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案镇郊荒野:李代桃僵
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案镇郊荒野:指鹿为马
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案金陵:小鸟依人
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案金陵:千金买邻
 干货   2019-11-12
 
推荐阅读
 
 
 
>>返回首頁<<
 
靜靜地坐在廢墟上,四周的荒凉一望無際,忽然覺得,淒涼也很美
© 2005- 王朝網路 版權所有