编译原理实验四 LR(0)分析法（LR0分析表的自动生成）

2023-02-22 1298

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

简介： 编译原理实验四 LR(0)分析法（LR0分析表的自动生成）

一、实验内容

1.实现LR(0)分析算法

3.输出：语句的分析过程（参见ppt例题）

4.要求：LR(0)分析表程序自动生成。如果使用已知的分析表，实验分数会降低。

二、实验目的

通过设计、编制、调试一个具体的文法分析程序，深入理解LR(0)预测分析法的基本分析原理，学会自动生成LR(0)分析表，并利用分析表对输入语句进行分析。

三、实验分析

待分析文法示例如下：

为了识别唯一的“接受”状态，并消除”|”符号，需要对文法进行增广，增广后的文法为：

对文法中每一个产生式的右部添加一个圆点·，称为文法的一个LR(0)项目（简称项目）。一个项目指明了在分析过程中某个时刻我们能看到产生式多大一部分。圆点“·”指出了分析过程中扫描输入串的当前位置。圆点“·”前的部分为已经扫描过的符号串，圆点“·”后的部分为待扫描的符号串，且圆点“·”前的符号串构成了一个活前缀。圆点在最右端的项目为“规约”项目，圆点“·”右侧第一个符号是终结符称为“移进”项目。圆点“·”右侧第一个符号是非终结符称为“待约”项目。

1.S → ⋅ E

2.S → E

3.E → ⋅ a A

4.E → a ⋅ A

5.E → a A ⋅

6.E → ⋅ b B

7.E → b ⋅ B

8.E → b B ⋅

9.A → ⋅ c A

10.A → c ⋅ A

11.A → c A ⋅

12.A → ⋅ d

13.A → d ⋅

14.B → ⋅ c B

15.B → c ⋅ B

16.B → c B ⋅

17.B → ⋅ d

18.B → d ⋅

构造该文法的DFA。对于一个项目集来说，除了规约项目之外，对于其余移进项目，“·”之后有多少个不同的字符，就要引出多少条有向边到不同的项目集。在项目集中根据某一项目“·”后的首字符，引出有向边到达另一项目集，要分两种情况考虑：一种是项目在目前已存在的所有项目集均未出现，则引出有向边到达一新产生的项目集，该项目集纳入新项目。另一种是项目在目前已存在的项目集中某一个已经出现，则不产生新的项目集。

本实验中，文法的DFA M如下图：

状态	a	b	c	d	#	S	E	A	B
0	s2	s7					1
1					acc
2			s4	s6				3
3	r1	r1	r1	r1	r1
4			s4	s6				5
5	r3	r3	r3	r3	r3
6	r4	r4	r4	r4	r4
7			s9	s11					8
8	r2	r2	r2	r2	r2
9			s9	s11					10
10	r5	r5	r5	r5	r5
11	r6	r6	r6	r6	r6

四、实验流程

4.1 整体流程

4.2 构造DFA

4.3 用分析表分析

首先，需要对输入串中加入“#”号。之后反复地执行如下的流程：

读取状态栈栈顶。读取输入串首字符。如果状态栈和输入串首字符的表项不存在，则出错。否则，根据表项中的内容进行下述步骤：若为“ACC”，则接受，返回。若表项中第一个字符为”s”，则为移进，根据表项中的内容将新的状态入栈，也将符号入栈，指向输入串下一字符。若表项中第一个字符为”r”，则为规约。根据表项中的内容，判断用哪条语句进行规约。计算这条语句产生式右部长度，符号栈和状态栈中都出栈元素，数量为产生式右部长度。根据产生式左部，将产生式的左部重新入符号栈，将状态栈加入该非终结符与栈顶状态的GOTO表项。

分析的流程图如下所示。

五、实验代码

5.1 数据结构

文法开始符为char S

终结符、非终结符记录在集合中。set VN,VT

用cell记录分析表中的表项。属性为类型、下一个状态id、规约的文法id。

struct cell {
  motionType mt = UNKNOWN;
  int nxtsid = -1;
  int gid = -1;
};

Table为分析表本体

cell table[100][100];

为了方便读取，需要将字符和编号互相转化。

map charToId;

char idToChar[100];

Gright为每个产生式的右部，键值为产生式左部。因为每个非终结符对应不止一个产生式，所以用vector存储。G为产生式本体。Grammer类也用于记录每条产生式。

map<char, vector<int>> Gright;
vector<pair<char, string>> G;
class grammer {
public:
  int gid;
  char left;
  string right;
};
vector<grammer> Gs;

item为文法中的项目

struct item {
  int gid;
  int i = 0;    // 圆点在第i个字符前
};    // 项目及项目的状态

State为由项目集规范族构成的状态

class state {
public:
  int sid;
  bool end = false;
  vector<item> Is;    // 该状态下的所有项目
  set<char> right_VNs;
}
vector<state> Ss;

5.2 部分核心算法设计

bool findMore() {
    if (end) return false;
    bool found = false;
    for (auto& p : Is) {
      if (VN.count(Gs[p.gid].right[p.i]) && !right_VNs.count(Gs[p.gid].right[p.i])) {    // 加入待归约项目
        right_VNs.insert(Gs[p.gid].right[p.i]);
        found = true;
        for (auto& gid : Gright[Gs[p.gid].right[p.i]]) {
          Is.push_back({ gid, 0 });
        }
      }
    }
    return found;
  }

递归地求解DFA。在derivateAll()的效果是找到所有状态，并找到每个状态shift和GOTO的状态。利用derivateState()求解每个状态，在每个状态中对每个项目再次进行移进，构建新的项目。调用findMore()求解这个新项目的项目集规范族，判断当前项目集规范族构成的状态是否出现过，若没出现过则构造新的状态。

int derivateState(int isid, char c);
void derivateAll(int sid) {
  if (Ss[sid].end) return;
  std::set<char> input_c;
  for (auto& p : Ss[sid].Is) {
    input_c.insert(Gs[p.gid].right[p.i]);
  }
  for (auto& c : input_c) {
    int nxtsid = derivateState(sid, c);
    if (nxtsid == -1) continue;
    // assert(table[sid][charToId[c]].mt == UNKNOWN);
    if (VN.count(c)) {    // 是非终结符
      table[sid][charToId[c]].mt = GOTO;
      table[sid][charToId[c]].nxtsid = nxtsid;
    }
    else {    // 是终结符
      table[sid][charToId[c]].mt = ADDS;
      table[sid][charToId[c]].nxtsid = nxtsid;
    }
  }
}
int derivateState(int isid, char c) {
  if (Ss[isid].end) return -1;
  state ts;
  bool isend = false;
  for (auto& p : Ss[isid].Is) {
    if (Gs[p.gid].right[p.i] == c) {
      ts.Is.push_back({ p.gid,p.i + 1 });
      if (Gs[p.gid].right.length() == p.i + 1) {
        isend = ts.end = true;
      }
    }
  }
  if (ts.Is.size() == 0) return -1;
  ts.findMore();
  int sid;
  bool rec = false;
  if (IsToId.count(ts.Is)) {
    sid = IsToId[ts.Is];
    rec = true;
  }
  else {
    IsToId[ts.Is] = sid = scnt++;
    ts.sid = sid;
    Ss.push_back(ts);
    printState(sid);
  }
  if (!rec) derivateAll(sid);   
  return sid;
}

对文法进行分析的过程，与上文中的流程图是完全一致的。

stack<int> statusStack;
stack<char> symbolStack;
void LR0Analysis() {
  inputStr += '#';
  int p = 0;
  cout << endl << inputStr << endl;
  cout << setw(20) << "状态栈" << setw(20) << "符号栈" << setw(20) << "输入串" << setw(20) << "动作" << endl;
  statusStack.push(0);
  symbolStack.push('#');
  while (1) {
    int status = statusStack.top();
    char nextChar = inputStr[p];
    int nextStatus = -1;
    if (LRTable[status].count(nextChar)) {
      string info = LRTable[status][nextChar];
      display(p,inputStr,info);
      if (info == "ACC")
        break;
      if (info[0] == 's') {//移进状态
        nextStatus = stoi(info.substr(1));
        statusStack.push(nextStatus);
        symbolStack.push(nextChar);
        p++;
      }
      else if (info[0] == 'r') {
        nextStatus = stoi(info.substr(1));
        for (int i = 0; i < G[nextStatus].second.size(); i++) {
          symbolStack.pop();
          statusStack.pop();
        }
        char temp = G[nextStatus].first;
        symbolStack.push(temp);
        int s = statusStack.top();
        statusStack.push(stoi(LRTable[s][temp]));
      }
      else {
        break;
      }
    }
    else {
      cout << "ERROR";
      return;
    }
  }
}