一、实验内容

1.实现LL(1)分析算法

2.输入：教材中的算术表达式文法；待分析的语句（如i+i*i）

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

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

二、实验目的

通过设计、编制、调试一个具体的文法分析程序，深入理解LL(1)预测分析法的基本分析原理，理解FIRST集、FOLLOW集的构造方法并对其加以实现，构造LL(1)预测分析表并利用分析表对语句、文法进行分析。

三、实验分析

书中算术表达式文法示例如下：

由于算术表达式文法不存在左公因子，所以无需消除回溯。

在程序实现时，可以消除文法中的或符号，即对其进行处理：

四、实验流程

4.1 整体流程

首先从文件中读入文法，识别出文法的终结符与非终结符，对文法进行消除左递归、消除回溯、消除或。再次识别出文法的终结符与非终结符，对每个符号与短语求出其FIRST集合与FOLLOW集合，自动分析生成建立分析表。输入待分析的文法，对其进行分析。整体流程如下图所示。

4.2 求FIRST

对字符或短语求FIRST集合时，往往需要用到递归。若在递归时发现c字符的FIRST集合已经求解完毕，则直接返回。若当前字符c是终结符，则FIRST集合为自己，返回。若不是终结符，则对其产生式进行遍历。若产生式中就是空字，则将空字加入FIRST集合。否则，遍历产生式的字符。递归的求解当前字符的FIRST集合，将该字符FIRST集合除了空字以外的元素加入。若该字符的FIRST集合存在空字，则遍历下一字符，如此循环。求解短语的FIRST集合的过程与求解某一非终结符的产生式的FIRST集合的流程是类似的。求FIRST集合的流程如下图。

4.3 求FOLLOW

4.4 求分析表并分析输入串

五、实验代码

5.1 数据结构

利用S表示文法的开始符，利用VN与VT分别表示非终结符与终结符。

字符的FIRST集合用map存储。map的键为字符，值为FIRST集合，用set存储。字符的FIRST集表被定义为：map> firstSet

短语的FIRST集合也用map存储。map的键为字符串，即短语。值为FIRST集合，用set存储。其被定义为：map> firstSetS

字符的FOLLOW集合用map存储。map的键为字符，值为FOLLOW集合，用set存储。字符的FOLLOW集表被定义为：map> followSet;

利用MAP表示产生式表，利用map存储。map的键为产生式的左部，值为产生式右部。因为一个非终结符可能有多个右部，所以值用vector存储，可以存储多个右部字符串。map> expressionSet;

预测分析表本体利用二维数组存储。vector> table;

文件读取到的文法、消左递归的文法、消除回溯的文法、增广的文法，可以用于求解FIRST与FOLLOW的文法存储在不同的变量名中。

vector<string> filebuffer;//文件读取的缓冲区
vector<string> expression_withoutrecursion;//消左递归
vector<string> expression_withoutback;//消完左递归和回溯
vector<string> inputExpression;//最后增广完成，用于进行分析的文法

5.2 部分核心算法设计

5.2.1 消除左递归与回溯并消除或

消除“或”时，同样需要找到每处”|”，并对含有”|”符号的字符串进行重新拼接处理。

void leftRecursion(){
  for (string str : filebuffer){
    if (str[0] == str[str.find('>') + 1]){
      char newch = 'A';
      for (newch = 'A'; newch <= 'Z'; newch++)
        if (VN.count(newch) == 0)
          break;
      VN.insert(newch);
      string newstr = "";
      string alpha = str.substr(4, str.find('|') - 4);
      //  cout << "\nalpha" << alpha << endl;
      //A->betaA'
      newstr = newstr + str[0] + (string)"->" + str.substr(str.find('|') + 1) + newch;
      expression_withoutrecursion.push_back(newstr);
      newstr = "";
      //A'->alphaA'|e
      newstr = newstr + newch + "->" + alpha + newch + "|" + 'e';
      //e表示空字符episilon
      VT.insert('e');
      expression_withoutrecursion.push_back(newstr);
    }
    else
      expression_withoutrecursion.push_back(str);
  }
  cout << "\n消除左递归：\n";
  for (string str : expression_withoutrecursion)
    cout << str << endl;
}
//消除回溯
void leftTraceback(){
  for (string str : expression_withoutrecursion){
    //发现回溯
    if (str[3] == str[str.find("|") + 1]){
      char newch = 'A';
      for (newch = 'A'; newch <= 'Z'; newch++)
        if (VN.count(newch) == 0)
          break;
      VN.insert(newch);
      string delta = "" + str[3];
      string newstr = "";
      //A->alphaA'
      newstr += str[0] + "->" + delta + newch;
      expression_withoutback.push_back(newstr);
      newstr = "";
      //A'->beta1|beta2
      string beta1 = str.substr(4, str.find('|') - 4);
      string beta2 = str.substr(str.find('|') + 1);
      newstr += newch + "->" + beta1 + '|' + beta2;
      expression_withoutback.push_back(newstr);
    }
    else
      expression_withoutback.push_back(str);
  }
  cout << "\n消除回溯：\n";
  for (string str : expression_withoutback)
    cout << str << endl;
}
//增广，删除竖线|
void deleteor(){
  for (string str : expression_withoutback){
    if (str.find('|') != string::npos){
      //将A->beta1|beta2拆成A->beta1和A->beta2
      string right1 = str.substr(3, str.find('|') - 3);
      //  cout << "right1" << right1 << endl;
      string newstr1 = "";
      newstr1 = str[0] + (string)"->" + right1;
      //  cout << "newstr1" << newstr1 << endl;
      inputExpression.push_back(newstr1);
      string right2 = str.substr(str.find('|') + 1);
      //  cout << "right2" << right2 << endl;
      string newstr2 = "";
      newstr2 += str[0] + (string)"->" + right2;
      //  cout << "newstr2" << newstr2 << endl;
      inputExpression.push_back(newstr2);
    }
    else
      inputExpression.push_back(str);
  }
  cout << "\n增广\n";
  for (string str : inputExpression)
    cout << str << endl;
}

5.2.2 求解FIRST

求字符与短语的FIRST集合的过程与4.2章节中的流程图是一致的。这是一个递归的过程。因为涉及到了求单个字符与短语，所以需要对函数进行重载。

//字符的求first集
void getFirst(char c){
  //已经求完了当前字符的first集
  if (firstSet.count(c))
    return;
  set<char> newset;
  //若c为终结符，则first为自己，结束
  if (VT.count(c)){
    newset.insert(c);
    firstSet[c] = newset;
    return;
  }
  for (string s : expressionSet[c]){
    //若存在X->e，将e加入
    if ('e' == c)
      newset.insert('e');
    else{
      for (char cur : s){
        if (!firstSet.count(cur))
          getFirst(cur);
        set<char> curFirst = firstSet[cur];
        for (auto curf : curFirst)
          newset.insert(curf);
        //将Y的first集合中的元素中不是e的加入
        if (!curFirst.count('e'))
          break;
        //如果加到了e，则循环回去，即X->Y1Y2..Yk时，Y1产生e，就需要加入Y2的first集合
      }
    }
  }
  firstSet[c] = newset;
}
//多个字符（字符串、短语）first集求法
void getFirst(string s){
  if (firstSetS.count(s))
    return;
  set<char> newset;
  int i = 0;
  while (i < s.length()){
    char cur = s[i];
    if (!firstSet.count(cur))
      getFirst(cur);
    //将当前字符的first集作为短语的first集
    set<char> rightSet = firstSet[cur];
    for (auto rs : rightSet)
      newset.insert(rs);
  //类似的，如果加到了e，则循环回去，即X->Y1Y2..Yk时，Y1产生e，就需要加入Y2的first集合
    if (rightSet.count('e'))
      i++;
    else
      break;
    //遍历完了当前语句后，将空字加入当前语句first集
    if (i == s.length())
      newset.insert('e');
  }
  firstSetS[s] = newset;
}

5.2.3 求解FOLLOW

求解FOLLOW集合的流程是迭代的。在调用初始化函数时，需要针对每一个字符反复的对其求解FOLLOW集合。

//求每个非终结符的follow
  for (char c : VN)
    getFollow(c);

求解某一字符FOLLOW集合的流程与章节4.3的流程图是一致的。

//某个字符的follow集合
void getFollow(char c){
  vector<string> list = expressionSet[c];
  set<char> leftFollowSet;
  if (followSet.count(c))
    leftFollowSet = followSet[c];
  //对文法开始符号，将#加入follow集合
  if (c == S)
    leftFollowSet.insert('#');
  for (char ch : VN) {
    for (string s : expressionSet[ch]) {
      for (int i = 0; i < s.length(); i++) {
        //若有A->aBb（a可为空），则将b加入B的follow集合
        if (c == s[i] && i + 1 < s.length() && VT.count(s[i + 1])) 
          leftFollowSet.insert(s[i + 1]);
      }
    }
  }
  followSet[c] = leftFollowSet;
  for (string s : list){
    int i = s.length() - 1;
    //对每个产生式从右往左遍历
    while (i >= 0)
     {
      char cur = s[i];
      //对于当前标识符B
  //对于当前标识符之后的字符，若是非终结符，则将这个非终结符的first集加入当前字符的follow集
      if (VN.count(cur)){
        string right = s.substr(i + 1);
        set<char> rightFirstSet;
        if (!followSet.count(cur)) 
          getFollow(cur);
        set<char> curFollowSet = followSet[cur];
        //若A->aB或A->aB\beta且\beta->e
        //则把follow(A)加到follow(B)
        if (right.length() == 0)
          for (auto lfs : leftFollowSet) 
            curFollowSet.insert(lfs);
        else
          //将若A->Bbeta，将B后的字符的first（除e）加入
          if (right.length() == 1)
            if (!firstSet.count(right[0])) 
              getFirst(right[0]);
            rightFirstSet = firstSet[right[0]];
          else
            if (!firstSetS.count(right))
              getFirst(right);
            rightFirstSet = firstSetS[right];
          for (char var : rightFirstSet)
            if (var != 'e')
              curFollowSet.insert(var);
          //若A->Bbeta且e属于first（beta），将follow（A）加入follow（B)
          if (rightFirstSet.count('e'))
            for (auto lfs : leftFollowSet)
              curFollowSet.insert(lfs);
        }
        followSet[cur] = curFollowSet;
      }
      i--;
     }
  }
}

5.2.4 文法分析

void analyzeLL(){
  cout << "\nLL分析过程\n";
  cout << setw(20) << "stack" << setw(10) << "input" << setw(20) << "expression";
  cout << endl;
  analyzeStack.push('#');
  //#入栈
  analyzeStack.push(S);
  //开始符入栈
  displayLL();
  char X = analyzeStack.top();
  while (X != '#'){
    char a = strInput[index];
    if (X == a){
      action = "";
      analyzeStack.pop();
      index++;
    }
    else if (VT.count(X))
      return;//找到终结符，出错
    else if (find(X, a) == "")
      return;
    else if (find(X, a) == "e"){
      analyzeStack.pop();
      action = "";
      action += X;
      action += "->e";
    }//空字，出栈
    else{//其余情况，需要按分析表对栈顶元素进行推导
      string str = find(X, a);
      if (str != ""){
        action = "";
        action += X;
        action += "->";
        action += str;
        analyzeStack.pop();
        int len = str.length();
        for (int i = len - 1; i >= 0; i--)
        analyzeStack.push(str[i]);//栈顶元素出栈，按分析表和下一字符将分析表中元素入栈
      }
      else
      {
        cout << "\nERROR!\n";//出错，直接返回
        return;
      }
    }
    X = analyzeStack.top();
    displayLL();
  }
}