LL(1)语法分析设计原理与实现——以赋值语句为例-Toy模板网

这篇具有很好参考价值的文章主要介绍了LL(1)语法分析设计原理与实现——以赋值语句为例。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

一、实验目的

语法分析的设计方法和实现原理；LL（1）分析表的构造；LL(1)分析过程；LL(1)分析器的构造；

二、实验内容

实现 LL(1)分析中控制程序（表驱动程序）；完成以下描述赋值语句的 LL(1) 文法的 LL(1)分析过程。

G[S]:S→V=E

E→TE′

E′→ATE′|ε

T→FT′

T′→MFT′|ε

F→ (E)|i

A→+|-

M→*|/

V→i

[设计说明] 终结符号 i 为用户定义的简单变量,即标识符的定义。

[设计要求]

（1）输入串应是词法分析的输出二元式序列，即某算术表达式“专题 1”的输出结果。输出为输入串是否为该文法定义的算术表达式的判断结果；

（2）LL(1)分析过程应能发现输入串出错；

（3）设计两个测试用例（尽可能完备，正确和出错），并给出测试结果；

（4）考虑根据 LL(1)文法编写程序构造 LL（1）分析表，包括 FIRST 集合和 FOLLOW 集合，并添加到你的 LL（1）分析程序中。

输出结果：

词法分析输入文件：

赋值语句的语法分析程序设计与实现,数据结构,算法,c++,编辑器

词法分析输出：

赋值语句的语法分析程序设计与实现,数据结构,算法,c++,编辑器

LL1文法分析结果：

先根据已知文法构造分析表：

赋值语句的语法分析程序设计与实现,数据结构,算法,c++,编辑器

读取文件进行LL1文法分析：

赋值语句的语法分析程序设计与实现,数据结构,算法,c++,编辑器

以下为实现该文法分析的全部代码，文件读取部分也可改为自行输入字符串，对主函数的like字符型数组进行更改即可。文章来源地址https://www.toymoban.com/news/detail-767785.html

#define  _CRT_SECURE_NO_WARNINGS  1
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<iostream>
#include <cassert>
#include<fstream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<stack>
using namespace std;
#define max_size 100

char LL_1[100][100]= {
  "S->V=E",
  "E->Te",
  "e->ATe|N", //E'用小e表示
  "T->Ft",    //T'用小t表示   
  "t->MFt|N",
  "F->(E)|i",
  "A->+|-",
  "M->*|/",
  "V->i"
};//文法数组

int num_ll = 9;//这里表示文法条数
//记录文法分析表格

char LL1[50][50][100];
char frist[100][100];//记录frist集数据
char follow[100][100];//记录follow集数据

char H[200]; //记录非终结符合
char L[200]; //记录终结符号
stack<char>cmp;//分析栈
char shizi[500], like[500];//从文件中读取字符串

int location_H(char c);//判断当前字符是否属于非终结符号
int location_L(char c);//判断当前字符是否属于终结符号
void add_HL(char ll[100][100]);//添加非终结符号与终结符号
int check(char l[100], char c);//在字符串中查找字符
void find_frist(char ll[100][100]);//第一遍寻找frist集的函数
void find_the_frist(int ll_index, char ll[100][100], int n_frist);//用作递归
void find_follow(char ll[100][100]);//用作寻找follow集
void make_table(char ll[100][100]);//用作构建表格
void print_table();//输出结果的函数
int findH(char a);//查找非终结符号
int findL(char b);//查找终结符号
int error(int i, int cnt, int len, char p[], char str[]);//出错处理
void analyze(char str[1000], int len);//LL1分析函数
void openthefile();//读取词法分析输出的函数

void LL_1table(char ll[100][100]) {
  add_HL(ll);
  find_frist(ll);
  find_follow(ll);
  make_table(ll);
  print_table();//输出结果函数
}

int check(char l[100], char c) {
  int temp = 0;
  for(int i = 0; i < strlen(l); i++) {
    if (c == l[i]) {
      temp = 1;
      break;
    }
  }
  return temp;
}
void add_HL(char ll[100][100]) {
  int H_index = 0;
  int L_index = 0;
  int temp = 0;
  int temp1 = 0;
  for (int i = 0; i < num_ll; i++) {//添加非终结符号
    H[H_index] = ll[i][0];
    H_index++;
  }
  for (int i = 0; i < num_ll; i++) {
    for (int j = 3; j < strlen(ll[i]); j++) {
      //由于文法开始前三个字符必定不为终结符号，所以从三号索引开始
      temp = 0;
      for (int k = 0; k < strlen(H); k++) {
        if (ll[i][j] == H[k] || ll[i][j] == '|' || ll[i][j] == 'N') {
          temp = 1;
          break;
        }
      }
      if (temp == 0) {
        temp1 = 0;
        for (int k = 0; k < strlen(L); k++) {
          //判断该非终结符号是否已经存在
          if (ll[i][j] == L[k]) {
            temp1 = 1;
            break;
          }
        }
        if (temp1 == 0) {
          L[L_index] = ll[i][j];//添加终结符号
          L_index++;
        }
      }
    }
  }
  L[strlen(L)] = '#';
}
int location_H(char c) {
  int location = -1;
  for (int i = 0; i < num_ll; i++) {
    if (c == H[i]) {
      location = i;
      break;
    }
  }
  return location;
}
int location_L(char c) {
  int location = -1;
  for (int i = 0; i < num_ll; i++) {
    if (c == L[i]) {
      location = i;
      break;
    }
  }
  return location;
}
void print_table() {
  cout << "------------------20231048 马云霄-----------------------" << endl;
  cout << "该文法的非终结符号集为：" << H << endl;
  cout << "该文法的终结符号集为：" << L << endl;
  cout << "-------------------------------------------------------" << endl;
  cout << "              frist集            follow集" << endl;
  for (int i = 0; i < num_ll; i++) {
    cout << "   符号 " << H[i] << " :      " << frist[i]<<"               " <<follow[i]<< endl;
  }
  cout << "-------------------------------------------------------" << endl;
  cout << "当前LL(1)分析表格为：" << endl;
  cout << "        ";
  for (int i = 0; i < strlen(L); i++) {
    cout << L[i] << "       ";
  }
  cout << endl;
  for (int i = 0; i < num_ll; i++) {
    cout << H[i] << ": ";
    for (int j = 0; j < strlen(L); j++) {
      if (strlen(LL1[i][j]) == 0) {
        strcpy(LL1[i][j], "null");
      }
      cout.width(8);
      cout.unsetf(ios::right);
      cout.fill(' ');
      cout <<LL1[i][j];
    }
    cout << endl;
  }
  cout << "-------------------------------------------------------" << endl;
}
void find_frist(char ll[100][100]) {
  int temp;
  int n_frist;//当前添加frist集元素位置
  int if_the_frist_word;//判断当前符号是否为第一个符号
  int location;//下次递归寻找的非终结符号的位置
  for (int i = 0; i < num_ll; i++) {
    n_frist = 0;
    if_the_frist_word = 0;
    for (int j = 3; j < strlen(ll[i]); j++) {
      if (if_the_frist_word == 0) {//判断当前符号是否为第一个符号
        temp = 0;//表示当前字符为非终结符号
        location = 0;
        for (int k = 0; k < strlen(H); k++) {
          if (H[k] == ll[i][j]) {
            location = k;
            temp = 1;
            break;
          }
        }
        if (temp == 0) {//如果当前字符为终结符号
          n_frist = strlen(frist[i]);
          frist[i][n_frist] = ll[i][j];
        }
        else {
          find_the_frist(location, ll, i);
        }
      }
      if_the_frist_word = 1;
      if (ll[i][j] == '|') {
        if_the_frist_word = 0;//或符号的下一个符号要进行识别
      }
    }
  }
}
void find_the_frist(int ll_index,char ll[100][100],int n_frist) {
  int if_the_frist_word = 0;
  int location;//表示当前找寻的非终结符号的位置
  int temp;
  int location_frist;
  for (int j = 3; j < strlen(ll[ll_index]); j++) {
    if (if_the_frist_word == 0) {//判断当前符号是否为第一个符号
      temp = 0;//表示当前字符为非终结符号
      location = 0;
      for (int k = 0; k < strlen(H); k++) {
        if (H[k] == ll[ll_index][j]) {
          temp = 1;
          location = k;
          break;
        }
      }
      if (temp == 0) {//如果当前字符为终结符号
        location_frist = strlen(frist[n_frist]);
        frist[n_frist][location_frist] = ll[ll_index][j];
      }
      else {
        find_the_frist(location, ll, n_frist);//递归寻找
      }
    }
    if_the_frist_word = 1;
    if (ll[ll_index][j] == '|') {
      if_the_frist_word = 0;//或符号的下一个符号要进行识别
    }
  }
}
void find_follow(char ll[100][100]) {
  follow[0][0] = '#';//为开始符号添加终结符
  int f_location;
  int ff_location;
  for (int i = 0; i < num_ll; i++) {
    for (int j = 3; j < strlen(ll[i])-1; j++) {
      if (location_H(ll[i][j]) != -1) {
        if (location_H(ll[i][j + 1]) == -1&&ll[i][j+1]!='|') {
          //如果后面字符为终结符，直接将其加入follow集
          if (check(follow[location_H(ll[i][j])], ll[i][j + 1]) == 0) {
            //判断当前字符是否已经存在
            f_location = strlen(follow[location_H(ll[i][j])]);
            follow[location_H(ll[i][j])][f_location] = ll[i][j + 1];
          }
        }
        else {
          //如果不是，则将其后面的非终结符号的frist集加入当前follow集
          f_location = strlen(frist[location_H(ll[i][j+1])]);
          for (int k = 0; k < f_location; k++) {
            if (frist[location_H(ll[i][j + 1])][k] != 'N') {
              //判断当前字符是否为空
              if (check(follow[location_H(ll[i][j])], frist[location_H(ll[i][j + 1])][k]) == 0) {
                ff_location = strlen(follow[location_H(ll[i][j])]);
                follow[location_H(ll[i][j])][ff_location] = frist[location_H(ll[i][j + 1])][k];
              }
            }
          }
        }
      }
    }
  }
  for (int i = 0; i < num_ll; i++) {
    for (int j = 3; j < strlen(ll[i]) - 1; j++) {
      if (location_H(ll[i][j]) != -1) {
        if (ll[i][j + 1] == '|') {
          //如果该非终结符号后续没有符号
          f_location = strlen(follow[location_H(ll[i][0])]);
          for (int k = 0; k < f_location; k++) {
              //判断当前字符是否为空
            if (check(follow[location_H(ll[i][j])], follow[location_H(ll[i][0])][k]) == 0) {
              ff_location = strlen(follow[location_H(ll[i][j])]);
              follow[location_H(ll[i][j])][ff_location] = follow[location_H(ll[i][0])][k];
            }
          }
        }
        else if (location_H(ll[i][j + 1]) != -1) {
          //如果后续为非终结符号
          if (check(frist[location_H(ll[i][j + 1])], 'N') == 1) {
            //该非终结符号可以推导出空
            f_location = strlen(follow[location_H(ll[i][0])]);
            for (int k = 0; k < f_location; k++) {
              //判断当前字符是否为空
              if (check(follow[location_H(ll[i][j])], follow[location_H(ll[i][0])][k]) == 0) {
                ff_location = strlen(follow[location_H(ll[i][j])]);
                follow[location_H(ll[i][j])][ff_location] = follow[location_H(ll[i][0])][k];
                //该符号的follow集加上推原符号的follow集的内容
              }
            }
          }
        }
      }
    }
    if (location_H(ll[i][strlen(ll[i]) - 1]) != -1) {
      //如果该符号为该文法的最后一个符号且为非终结符号
      f_location = strlen(follow[location_H(ll[i][0])]);
      for (int k = 0; k < f_location; k++) {
        //判断当前字符是否为空
        if (check(follow[location_H(ll[i][strlen(ll[i]) - 1])], follow[location_H(ll[i][0])][k]) == 0) {
          ff_location = strlen(follow[location_H(ll[i][strlen(ll[i]) - 1])]);
          follow[location_H(ll[i][strlen(ll[i]) - 1])][ff_location] = follow[location_H(ll[i][0])][k];
        }
      }
    }
  }
}
void make_table(char ll[100][100]) {
  int temp = 0;
  int w = 2;
  for (int i = 0; i < num_ll; i++) {
    if (check(ll[i], '|') == 0) {
      //当前检索文法中不含或
      for (int j = 0; j < strlen(frist[i]); j++) {//遍历当前frist集
        if (frist[i][j] == 'N') {
          continue;
        }
        for (int k = 1; k < strlen(ll[i]); k++) {
          LL1[i][location_L(frist[i][j])][k - 1] = ll[i][k];
        }
      }
    }
    else {
      //当前文法中含或，则需要判断填入哪条文法
      for (int j=0; j < strlen(frist[i]); j++) {
        if (frist[i][j] == 'N') {
          continue;
        }
        temp = 0;
        for (int k = 3; k < strlen(ll[i]); k++) {
          //遍历当前文法,由于前三个符号不使用,这里从3开始遍历
          if (temp == 0) {
            if (location_H(ll[i][k]) != -1) {
              //判断当前符号为终结符号还是非终结符号
              if (check(frist[location_H(ll[i][k])], frist[i][j]) == 1) {
                //如果当前符号为frist集取自其文法中该符号的frist集
                LL1[i][location_L(frist[i][j])][0] = '-';
                LL1[i][location_L(frist[i][j])][1] = '>';
                w = 2;//标记当前表格对应位置字符串长度
                for (int r = k; r < strlen(ll[i]); r++) {
                  //将对应文法放入当前表格
                  LL1[i][location_L(frist[i][j])][w] = ll[i][r];
                  w++;
                  if (ll[i][r + 1] == '|')
                    break;
                }
              }
            }
              else if (ll[i][k] != 'N' && ll[i][k] == frist[i][j]) {
                //当前符号为终结符号且不为空
                LL1[i][location_L(frist[i][j])][0] = '-';
                LL1[i][location_L(frist[i][j])][1] = '>';
                w = 2;
                for (int r = k; r < strlen(ll[i]); r++) {
                  LL1[i][location_L(frist[i][j])][w] = ll[i][r];
                  w++;
                  if (ll[i][r + 1] == '|')
                    break;
                }
              }
            }
          temp = 1;
          if (ll[i][k] == '|') {
            //只判断或符号后面的符号即可
            temp = 0;
          }
        }
      }
    }
  }
  for (int i = 0; i < num_ll; i++) {
    if (check(frist[i], 'N') == 1) {
      for (int j = 0; j < strlen(follow[i]); j++) {
        LL1[i][location_L(follow[i][j])][0] = '-';
        LL1[i][location_L(follow[i][j])][1] = '>';
        LL1[i][location_L(follow[i][j])][2] = '$';
      }
    }
  }
}

int findH(char a)
{
  for (int i = 0; i < strlen(H); i++)//找到对应行
  {
    if (a == H[i])
    {
      return i;
    }
  }
  return -1;
}
int findL(char b)
{
  for (int i = 0; i < strlen(L); i++)//找到对应列
  {
    if (b == L[i])
    {
      return i;
    }
  }
  return -1;
}
int error(int i, int cnt, int len, char p[], char str[])
{
  printf("%d\t\t%s\t\t", cnt, p);
  for (int q = i; q < len; q++)
  {
    cout << str[q];
  }
  printf("\t\t报错\n");
  return len;
}
void analyze(char str[1000], int len)
{
  int cnt = 1;//输出Step专用
  int i = 0;
  int temp = 1;
  char p[2000] = "#S";//输出stack专用
  int pindex = 2;
  printf("Step\t\tStack\t\tString\t\tRule\n");
  while (i < len)
  {
    int x, y;
    char ch = cmp.top();//读取栈顶元素
    if (check(H,ch)==1)
    {
      cmp.pop();
      x = findH(ch);//当前文法识别字符位置
      y = findL(str[i]);//当前字符位置
      if (x != -1 && y != -1)
      {
        int len2 = strlen(LL1[x][y]);
        if (strcmp(LL1[x][y], "null") == 0)
        {
          i = error(i, cnt, len, p, str);
          continue;
        }
        printf("%d\t\t%s\t\t", cnt, p);
        if (p[pindex - 1] != '#' && pindex>0&&temp!=0 )
        {
          p[pindex] = '\0';
          pindex--;
        }
        temp = 1;
        if (LL1[x][y][2] != '$')
        {
          for (int q = len2 - 1; q > 1; q--)
          {
            p[pindex] = LL1[x][y][q];
            cmp.push(LL1[x][y][q]);
            pindex++;
          }
        }
        if(pindex>0 && LL1[x][y][2] == '$')
        {
          p[pindex] = '\0';
          pindex--;
          temp = 0;
        }
        for (int q = i; q < len; q++)
        {
          cout << str[q];
        }
        printf("\t\t%c%s\n", ch, LL1[x][y]);
      }
      else
      {
        i = error(i, cnt, len, p, str);
        continue;
        ///未找到，报错
      }

    }
    else
    {
      if (ch == str[i])
      {
        cmp.pop();
        printf("%d\t\t%s\t\t", cnt, p);
        if (ch == '#' && str[i] == '#')
        {
          printf("#\t\t接受\n");
          return;
        }
        for (int q = i; q < len; q++)
        {
          cout << str[q];
        }
        printf("\t\t%c匹配\n", ch);
        p[pindex] = '\0';
        pindex--; 
        i++;
      }
      else
      {
        i = error(i, cnt, len, p, str);
        continue;
        ///报错
      }
    }
    cnt++;
  }
}
void openthefile() {
  cout << "读取文件可知输入语句：" << endl;
  FILE* fp;
  char buf[1000];
  if ((fp = fopen("E:\\desktop\\result.txt", "r")) != NULL) {
    while (fgets(buf, 1000, fp) != NULL)
    {
      int len = strlen(buf);
      printf("%s \n", buf);
      int flag = 0;

      for (int i = 0; i < len; i++) {
        if (buf[i] == '(' && flag == 0) {
          flag = 1;//识别符号
          for (int j = i + 1; j < len; j++) {
            if (buf[j] == ',') {
              shizi[strlen(shizi)]= buf[j + 1];
              if ((buf[j + 1] >= 'a' && buf[j + 1] <= 'z') ||
                (buf[j + 1] >= 'A' && buf[j + 1] <= 'Z')) {
                like[strlen(like)] += 'i';
              }
              else like[strlen(like)] = buf[j + 1];
              i = j + 1;
              break;
            }
          }
        }
        else if (flag == 1 && buf[i] == ')') {
          flag = 0;
        }
      }
    }
  }
  shizi[strlen(shizi)] = '#';
  like[strlen(like)] = '#';
  fclose(fp);
  cout << "-------------------------------------------------------" << endl;
  cout << "输入的语句为：" << shizi << endl;
  cout << "将其转化为：" << like << endl;
  cout << "-------------------------------------------------------" << endl;
}
int main()
{
  LL_1table(LL_1);
  openthefile();
  int len = strlen(like);
  cmp.push('#');
  cmp.push('S');
  analyze(like, len);
  return 0;
}

到了这里，关于LL(1)语法分析设计原理与实现——以赋值语句为例的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！