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

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

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

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

（3）选择最有代表性的语法分析方法，如递归下降分析法、预测分析法； 选择对各种常见程序语言都具备的语法结构，如赋值语句，特别是表达式，作为分析对象。

1.2 实验内容

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

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

::= [+|-]{ }

::= { }

::= || ‘(’‘)’

::= +|-

::= *|/

::= =|#|=

1.3 实验要求

（1）将实验一“词法分析”的输出结果，作为表达式语法分析器的输入，

进行语法解析，对于语法正确的表达式，报告“语法正确”；对于语

法错误的表达式，报告“语法错误”， 指出错误原因。

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

（3）采用递归下降分析法或者采用预测分析法实现语法分析。

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

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

B：表达式 C：乘法运算符

J：加法运算符 N：无符号整数

X：项 S：标识符

Y：因子 G：关系运算符

（2）文法如下

B->JX(JX)|X(JX)

X->Y(CY)*

Y->S|N|(B)

J->+|-

C->*|/

G->=|#|=

2.2 根据文法画相应的语法图

（1）表达式

图1 表达式—语法图

（2）项

图2 项—语法图

（3）因子

图3 因子—语法图

2.3 判断是否是LL(1)文法—求First、Follow集

（1）改文法没有左递归。

（2）各非终结符的First、Follow集如下所示

（3）根据LL(1)文法的判断规则可知，该文法满足LL(1)文法的条件，所以该文法是LL(1)文法。

2.4 递归下降子程序

（1）表达式

PROCEDUER B;
BEGIN
  IF SYM = '+' OR SYM = '-' THEN ADVANCE;
  ELSE IF SYM 在 First(X) THEN
  BEGIN
    ADVANCE;
    X;
  END
  ELSE ERROR; 
  WHILE SYM = '+' OR SYM = '-' THEN
  BEGIN
    ADVANCE;
    X;
  END
END

（2）项

PROCEDUER X;
BEGIN
  IF SYM 在 First(Y) THEN
  BEGIN
    ADVANCE;
    Y;
  END
  ELSE ERROR; 
  WHILE SYM = '*' OR SYM = '/' THEN ADVANCE;
  IF SYM 在 First(Y) THEN
  BEGIN 
    ADVANCE;
    Y;
  END
  ELSE ERROR;
END

（3）因子

PROCEDUER Y;
BEGIN
  IF SYM = '(' THEN
  BEGIN
    ADVANCE;
    B;
    ADVANCE;
    IF SYM = ')' THEN ADVANCE;
    ELSE ERROR;
  END
  ELSE IF SYM 在 First(Y) THEN ADVANCE;
  ELSE ERROR;
END

3 算法流程

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

首先逐行扫描单词符号二元组，然后遍历串的每一个字符，判断字符是不是+或-、*或/、因子的first集，再进行下一步的判断，选择进行表达式分析、项分析和因子分析，并输出相应的语句。如果不符合这几种情况，将会归入出错处理。完整算法流程如下图所示。

图4 算法流程图

4 源程序

#include
#include
#include
using namespace std; 

#define L 8 

void fac_aly();
void all_aly();

string input_str[L];//存储单词符号
int str_i = 0;//访问input_str的下标

//字符串数组下标往前移
void str_i_adv()
{
  str_i++;
  if(str_i > L-1)
  {
    cout