【编译原理】自下而上语法分析（C/C++源码+实验报告）

1 实验目的和内容 1.1 实验目的

（1）给出 PL/0 文法规范，要求编写 PL/0 语言的语法分析程序。

（2）通过设计、编制、调试一个典型的自下而上语法分析程序，实现对词法分析程序所提供的单词序列进行语法检查和结构分析，进一步掌握常用的语法分析方法。

（3）选择最有代表性的语法分析方法，如算符优先分析法、LR 分析法；或者调研语法分析器的自动生成工具 YACC 的功能与工作原理，使用YACC 生成一个自底向上的语法分析器。

1.2 实验内容

（1）已给 PL/0 语言文法，构造表达式部分的语法分析器。

（2）分析对象〈算术表达式〉的 BNF 定义如下：

::= [+|-]{ }

::= { }

::= || ‘(’‘)’

::= +|-

::= *|/

::= =|#|=

1.3 实验要求

（1）将实验一“词法分析”的输出结果，作为表达式语法分析器的输入，进行语法解析，对于语法正确的表达式，报告“语法正确”；对于语法错误的表达式，报告“语法错误”， 指出错误原因。

（2）把语法分析器设计成一个独立一遍的过程。

（3）采用算符优先分析法或者 LR 分析法实现语法分析；或者调研语法分析器的自动生成工具 YACC 的功能与工作原理，使用 YACC 生成一个自底向上的语法分析器。

2 设计思想 2.1 根据BNF描述该文法

（1）对BNF中的各对象简称如下

E：表达式

T：项

F：因子

i：ident

n：number

（2）文法如下

2.2 根据文法写出LR（0）项目集规范族

项目集规范族如下所示，一共有16个状态。

2.3 根据项目集规范族画出识别活前缀的DFA

活前缀是指规范句型的一个前缀，这种前缀不含句柄之后的任何符号。在上面的项目集中一共有四种项目，分别是归约项目、接受项目、移进项目和待约项目，根据以下两条规则来构造识别文法所以活前缀的DFA。

(1)若状态i为X->X1…Xi-1Xi…Xn，状态j为X->X1…Xi-1XiXi+1…Xn，则从状态i画一条标志为Xi的有向边到状态j；

(2)若状态i为X->α.Aβ，A为非终结符，则从状态i画一条ε边到所有状态A->.γ。

图1 识别活前缀的DFA

2.4 判断该文法是否是LR（0）文法

(1)对于I1，Follow(S)={#}，与+、-不冲突；

(2)对于I2，Follow(E)={+,-,),#}，与*、/不冲突；

(3)对于I12，Follow(E)={+,-,),#}，与*、/不冲突。

综上，该文法不存在移进归约冲突，所以是LR(0)文法。

2.5 构造LR（0）分析表 状态ActionActionActionActionActionActionActionActionActionGotoGotoGoto状态+-*/()in#ETF0S4S5S61231S7S8acc2r1r2S9S10r1r13r4r4r4r4r4r44S4S5S611235r8r8r8r8r8r86r9r9r9r9r9r97r4r5r61238r4r5r61339r4r5r61410r4r5r61511S7S8S1612r2r2S9S10r2r213r3r3S9S10r3r314r5r5r5r5r5r515r6r6r6r6r6r616r7r7r7r7r7r7 3 算法流程

语法分析程序的输入是一个个单词符号的二元组，输出是一个个语法单位，它的任务是在词法分析识别出单词符号串的基础上，分析并判定程序的语法结构是否符合语法规则。

首先逐行扫描单词符号二元组，然后遍历串的每一个字符，判断是否匹配结果，再进行下一步的判断，选择对比分析表，进行归约，把对应的字母和状态压入栈中，并输出相应的语句。如果不符合这几种情况，将会归入出错处理。完整算法流程如下图所示。

图2 算法流程图

4 源程序

#include
using namespace std;

//构造结构体---二元组
struct Two_tuples
{
  string type;//词法分析的类型
  string value;//词法分析的值
};

string input;//全局变量定义输入
Two_tuples result[200];//存放词法分析二元组
int k = 0;//输入二元组时访问下标
bool ans = true;//存放判断结果
int fh[101],zt[101];//符号栈，状态栈

bool target_judge(string input , string str) //判断是否和目标串匹配
{
  //首先匹配长度，看长度是否一致
  if(input.length()!=str.length()) return false;
  //长度一致，逐个匹配字符
  else
  {
    for(unsigned int i=0;i>str)
  {
    //定义指针访问
    const char *d = "(),";
    char *p;
    //临时存放字符串，便于分割处理
    char buf[101];
    strcpy(buf,str.c_str()); //字符串转成数组
    //开始处理每个二元组
    p = strtok(buf,d);
    int i = 0;
    //把输入的二元组存储到结构体中
    while(p)
    {
      if(i%2==0) result[k].type = p;
      else result[k].value = p;
      i++;
      p = strtok(NULL,d);
    }
    k++;
  }
  result[k].type = "#";
}
 

//在LR分析表中判断是哪个目标串（0--8）
int chart(string str)
{
  if(target_judge("plus",str)) return 0;
  else if(target_judge("minus",str)) return 1;
  else if(target_judge("times",str)) return 2;
  else if(target_judge("slash",str)) return 3;
  else if(target_judge("lparen",str)) return 4;
  else if(target_judge("rparen",str)) return 5;
  else if(target_judge("ident",str)) return 6;
  else if(target_judge("number",str)) return 7;
  else if(target_judge("#",str)) return 8;
  else return -1;
} 

//ETF归约（9--11）
int gy_1(int num)
{
  //E---表达式
  if(num - 100 == 1) return 9;
  else if(num - 100 == 2) return 9;
  else if(num - 100 == 3) return 9;
  //T---项
  else if(num - 100 == 4) return 10;
  else if(num - 100 == 5) return 10;
  else if(num - 100 == 6) return 10;
  //F---因子
  else if(num - 100 == 7) return 11;
  else if(num - 100 == 8) return 11;
  else if(num - 100 == 9) return 11; 
  else return -1;
} 

//gy_1中规约后约几项
int gy_2(int num)
{
  //E---表达式
  if(num - 100 == 1) return 1;
  else if(num - 100 == 2) return 3;
  else if(num - 100 == 3) return 3;
  //T---项
  else if(num - 100 == 4) return 1;
  else if(num - 100 == 5) return 3;
  else if(num - 100 == 6) return 3;
  //F---因子
  else if(num - 100 == 7) return 3;
  else if(num - 100 == 8) return 1;
  else if(num - 100 == 9) return 1; 
  else return -1;
} 

int main()
{
  input_cf(); //输入词法分析结果
  //LR分析表，其中大于100为归，小于100为移进
  int LR_chart[17][12]={{0,0,0,0,4,0,5,6,0,1,2,3},
                        {7,8,0,0,0,0,0,0,100,0,0,0},
                        {101,101,9,10,0,1,0,0,101,0,0,0},
                        {104,104,104,104,0,104,0,0,104,0,0,0},
                        {0,0,0,0,4,0,5,6,0,11,2,3},
                        {108,108,108,108,0,108,0,0,108,0,0,0},
                        {109,109,109,109,0,109,0,0,109,0,0,0},
                        {0,0,0,0,4,0,5,6,0,0,12,3},
                        {0,0,0,0,4,0,5,6,0,0,13,3},
                        {0,0,0,0,4,0,5,6,0,0,0,14},
                        {0,0,0,0,4,0,5,6,0,0,0,15},
                        {7,8,0,0,0,16,0,0,0,0,0,0},
                        {102,102,9,10,0,102,0,0,102,0,0,0},
                        {103,103,9,10,0,103,0,0,103,0,0,0},
                        {105,105,105,105,0,105,0,0,105,0,0,0},
                        {106,106,106,106,0,106,0,0,106,0,0,0},
                        {107,107,107,107,0,107,0,0,107,0,0,0}}; 
  int i = 0 , j = 0; //访问栈下标
  fh[0] = 8 , zt[0] = 0;//初值
  while(LR_chart[zt[j]][chart(result[i].type)]!=100)
  {
    //判断错误
    if(LR_chart[zt[j]][chart(result[i].type)]==0)
    {
      ans = false;
      break;
    }
    //移进
    else if(LR_chart[zt[j]][chart(result[i].type)]