一、目的

通过设计、编制、调试一个递归下降语法分析程序，实现对词法分析程序所提供的单词序列进行语法检查和结构分析，掌握常用的语法分析方法。通过本实验，应达到以下目标：

(1) 掌握从源程序文件中读取有效字符的方法和产生源程序的内部表示文件的方法。

(2)掌握语法分析的实现方法。

(3)上机调试编出的语法分析程序。

二、过程

2.1 了解背景

递归下降法是语法分析中最易懂的一种方法。它的主要原理是，对每个非终结符按其产生式结构构造相应语法分析子程序，其中终结符产生匹配命令，而非终结符则产生过程调用命令。因为文法递归相应子程序也递归，所以称这种方法为递归子程序下降法或递归下降法。其中子程序的结构与产生式结构几乎是一致的。

递归下降分析程序的实现思想是：识别程序由一组子程序组成。每个子程序对应于一个非终结符号。每一个子程序的功能是：选择正确的右部，扫描完相应的字。在右部中有非终结符号时，调用该非终结符号对应的子程序来完成。

自上向下分析过程中，如果带回溯，则分析过程是穷举所有可能的推导，看是否能推导出待检查的符号串。分析速度慢。而无回溯的自上向下分析技术，可根据输入串的当前符号以及各产生式右部首符，选择某非终结符的产生式，效率高，且不易出错。无回溯的自上向下分析技术可用的先决条件是：无左递归和无回溯。即：假设 A 的全部产生式为 Aα1|α2|……|αn ，则必须满足如下条件才能保证可以唯一的选择合适的产生式First(Aαi)∩First(Aαj)=Φ,当 i≠j.

无左递归：既没有直接左递归，也没有间接左递归。

无回溯：对于人以非中介符号 U 的产生式右部 x1 | x2 | ...| x**n ，其对应的字的首终结符号两两不相交。

如果一个文法不含回路（形如 P  P 的推导），也不含以  为右部的产生式，那么可以通过执行消除左递归的算法消除文法的一切左递归。

2.2 程序基本架构

2.3 实验内容

完成以下描述算术表达式的LL(1)文法的递归下降分析程序构造

G[E]:

E →TE′

E′→+TE′|ε

T →FT′

T′→*FT′|ε

F →(E)|i

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

要求具有如下功能：

\1) 从文件读入算术表达式/或者从终端输入

\2) 总控函数分析算术表达式；

\3) 根据分析结果正误，分别给出不同信息

2.3.1 步骤一

根据First集合的定义求文法中每个产生式的First集合，判断是否满足递归下降法分析条件，若不满足用消除左递归和消除公共前缀等文法等价变化算法对文法进行变换，使其满足递归下降法的要求。（这部分可以手动计算好，不需要编程序求）

分析表

非终结符	输入符号
	i	+	*	(	)	$
E	E →TE′			E →TE′	synch	synch
E′		E′→+TE′			E′→ε	E′→ε
T	T →FT′	synch		T →FT′	synch	synch
T′		T′→ε	T′→*FT′		T′→ε	T′→ε
F	F →i	synch	synch	F →(E)	synch	synch

2.3.2 步骤二

构造递归下降语法分析程序

采用递归子程序方法进行语法分析,对文法中的每个非终结符号按其产生式结构产生相应的语法分析子程序,完成相应的识别任务。其中终结符产生匹配命令，非终结符则产生调用命令。每次进入子程序之前都预先读入一个单词。因为使用了递归下降方法,所以程序结构和层次清晰明了,易于手工实现,且时空效率较高。实际的语法分析工作,从调用总程序的分析子程序开始，根据产生式进行递归调用各个分析子程序。

2.3.2.1 实现功能：从文件读入算术表达式/或者从终端输入

在main函数中实现

int main(){
    int x;
    while(1){
        cout << "请选择输入算术表达式的方式：" << endl;
        cout << "   1.从math.txt文件中读入" << endl;
        cout << "   2.从终端输入" << endl;
        cout << "请选择方式对应数字：" << endl;
        cin >> x;
        if (x == 1)
        {
            ifstream file("math.txt"); // 打开文件
            if (file.is_open())
            {                       // 检查文件是否打开
                getline(file, str); // 逐行读入文件内容
                file.close();       // 关闭文件
                break;
            }
            else
            {
                cout << "打开文件失败" << endl;
                exit(0); // 结束程序
            }
    }else if(x==2){
        cin >> str;
        break;
    }else{
        cout << "请输入有效数字(1,2)!!!!\n\n" << endl;
        continue;
    }

    }
    str.push_back('$');
    cout << "读取的算术表达式如下：" << endl;
    cout << str << endl;
    for (int i = 0; i < (int)str.length();i++){
        if(str[i]=='(')
            le++;
        if(str[i]==')')
            ri++;
    }
        cout << "\n\n\n处理结果如下:" << endl;
    E();
    
    return 0;
}

2.3.2.2 实现功能：总控函数分析算术表达式

E非终结符函数

根据同步记号分析表进行不同字符的判别与转化,并报告出相应错误

void E(){
    switch(str[0]){
        case 'i':
            stack.pop_back();//弹出E
            stack.append("E'T");//将TE'压入栈
            cout << "转换所用产生式:E -> TE'" << endl;
            cout << "目前栈：" << stack << endl;
            cout << "当前还未匹配成功的表达式：" << str << endl;
            cout << endl;
            T();
            E1();
            break;
        case '+':
            error++;
            cout << "出错: + 运算符需有两个操作数，跳过 + " << endl;
            str = str.substr(1);
            cout << "目前栈：" << stack << endl;
            cout << "当前还未匹配成功的表达式：" << str << endl;
            cout << endl;
            E();
            break;
        case '*':
            error++;
            cout << "出错: * 运算符需有两个操作数，跳过 * " << endl;
            str = str.substr(1);
            cout << "目前栈：" << stack << endl;
            cout << "当前还未匹配成功的表达式：" << str << endl;
            cout << endl;
            E();
            break;
        case '(':
            
            stack.pop_back();//弹出E
            stack.append("E'T");//将TE'压入栈
            cout << "转换所用产生式:E -> TE'" << endl;
            cout << "目前栈：" << stack << endl;
            cout << "当前还未匹配成功的表达式：" << str << endl;
            cout << endl;
            T();
            E1();
            break;
        case ')':
            
            error++;
            cout << "出错: ')'在E的同步记号集合中,无需跳过,E被弹出 " << endl;
            stack.pop_back();
            cout << "目前栈：" << stack << endl;
            cout << "当前还未匹配成功的表达式：" << str << endl;
            cout << endl;
            //////
            break;
        case '$':
            error++;
            cout << "出错: '$'在E的同步记号集合中,无需跳过,E被弹出 " << endl;
            stack.pop_back();
            cout << "目前栈：" << stack << endl;
            cout << "当前还未匹配成功的表达式：" << str << endl;
            cout << endl;
            //////
            break;
        default:
            error++;
            cout << "出错: 未知输入" << endl;
            exit(0);
            break;
    }
}

E‘非终结符函数

根据同步记号分析表进行不同字符的判别与转化,并报告出相应错误

void E1(){
    switch(str[0]){
        case 'i':
            error++;
            cout << "出错: 两个操作数间无运算符,跳过 i " << endl;
            str = str.substr(1);
            cout << "目前栈：" << stack << endl;
            cout << "当前还未匹配成功的表达式：" << str << endl;
            cout << endl;
            E1();
            break;
        case '+':
            stack.pop_back();//弹出E'
            stack.pop_back();
            stack.append("E'T+");//将+TE'压入栈
            cout << "转换所用产生式:E' -> +TE'" << endl;
            cout << "目前栈：" << stack << endl;
            cout << "当前还未匹配成功的表达式：" << str << endl;
            stack.pop_back();
            str = str.substr(1);//匹配成功,弹出
            cout << endl;
            T();
            E1();
            break;
        case '*':
            error++;
            cout << "出错: * 运算符需有两个操作数,跳过 * " << endl;
            str = str.substr(1);
            cout << "目前栈：" << stack << endl;
            cout << "当前还未匹配成功的表达式：" << str << endl;
            cout << endl;
            E1();
            break;
        case '(':
            
            error++;
            cout << "出错: 左括号( 需有右括号) 配对, 跳过 ( " << endl;
            str = str.substr(1);
            cout << "目前栈：" << stack << endl;
            cout << "当前还未匹配成功的表达式：" << str << endl;
            cout << endl;
            E1();
            break;
        case ')':
            
            stack.pop_back();//弹出E'
            stack.pop_back();
            cout << "转换所用产生式:E' -> 空" << endl;
            cout << "目前栈：" << stack << endl;
            cout << "当前还未匹配成功的表达式：" << str << endl;
            cout << endl;
            stack.pop_back();
            str = str.substr(1);//匹配成功，弹出
            /////
            break;
        case '$':
            stack.pop_back();//弹出E'
            stack.pop_back();
            cout << "转换所用产生式:E' -> 空" << endl;
            cout << "目前栈：" << stack << endl;
            cout << "当前还未匹配成功的表达式：" << str << endl;
            cout << endl;
            ///////
            
            if(ri<le){
                cout << "错误:存在左括号缺少右括号进行配对" << endl;
            }else if(ri>le){
                cout << "错误:存在右括号缺少左括号进行配对" << endl;
            }
            cout << "分析完成" << endl;
            exit(0);
            /////
            break;

        default:
            error++;
            cout << "出错: 未知输入" << endl;
            exit(0);
            break;
    }
}

T非终结符函数

根据同步记号分析表进行不同字符的判别与转化,并报告出相应错误

void T(){
    switch(str[0]){
        case 'i':
            stack.pop_back();//弹出T
            stack.append("T'F");//将FT'压入栈
            cout << "转换所用产生式:T -> FT'" << endl;
            cout << "目前栈：" << stack << endl;
            cout << "当前还未匹配成功的表达式：" << str << endl;
            cout << endl;
            F();
            T1();
            break; 
        case '+':
            error++;
            cout << "出错: '+'在T的同步记号集合中,无需跳过,T被弹出 " << endl;
            stack.pop_back();
            cout << "目前栈：" << stack << endl;
            cout << "当前还未匹配成功的表达式：" << str << endl;
            cout << endl;
            //////
            break;
        case '*':
            error++;
            cout << "出错: * 运算符需有两个操作数, 跳过 * " << endl;
            str = str.substr(1);
            cout << "目前栈：" << stack << endl;
            cout << "当前还未匹配成功的表达式：" << str << endl;
            cout << endl;
            T();
            break;
        case '(':
            
            stack.pop_back();//弹出T
            stack.append("T'F");//将FT'压入栈
            cout << "转换所用产生式:T -> FT'" << endl;
            cout << "目前栈：" << stack << endl;
            cout << "当前还未匹配成功的表达式：" << str << endl;
            cout << endl;
            F();
            T1();
            break;
        case ')':
            
            error++;
            cout << "出错: ')'在T的同步记号集合中,无需跳过,T被弹出 " << endl;
            stack.pop_back();
            cout << "目前栈：" << stack << endl;
            cout << "当前还未匹配成功的表达式：" << str << endl;
            cout << endl;
            //////
            break;
        case '$':
            error++;
            cout << "出错: '$'在T的同步记号集合中,无需跳过,T被弹出 " << endl;
            stack.pop_back();
            cout << "目前栈：" << stack << endl;
            cout << "当前还未匹配成功的表达式：" << str << endl;
            cout << endl;
            //////
            break;
        default:
            error++;
            cout << "出错: 未知输入" << endl;
            exit(0);
            break;
    }
}

T'非终结符函数

根据同步记号分析表进行不同字符的判别与转化,并报告出相应错误

void T1(){
    switch(str[0]){
        case 'i':
            error++;
            cout << "出错: 两个操作数间无运算符, 跳过 i " << endl;
            str = str.substr(1);
            cout << "目前栈：" << stack << endl;
            cout << "当前还未匹配成功的表达式：" << str << endl;
            cout << endl;
            T1();
            break;
        case '+':
            stack.pop_back();//弹出T'
            stack.pop_back();
            cout << "转换所用产生式:T' -> 空" << endl;
            cout << "目前栈：" << stack << endl;
            cout << "当前还未匹配成功的表达式：" << str << endl;
            cout << endl;
            /////
            E1();
            break;
        case '*':
            stack.pop_back();//弹出T'
            stack.pop_back();
            stack.append("T'F*");//将*FT'压入栈
            cout << "转换所用产生式:T' -> *FT'" << endl;
            cout << "目前栈：" << stack << endl;
            cout << "当前还未匹配成功的表达式：" << str << endl;
            str = str.substr(1);
            stack.pop_back();//匹配成功，弹出
            cout << endl;
            F();
            T1();
            break;
        case '(':
            
            error++;
            cout << "出错:左括号( 需要有右括号) 匹配,  跳过 ( " << endl;
            str = str.substr(1);
            cout << "目前栈：" << stack << endl;
            cout << "当前还未匹配成功的表达式：" << str << endl;
            cout << endl;
            T1();
            break;
        case ')':
            
            stack.pop_back();//弹出T'
            stack.pop_back();
            cout << "转换所用产生式:T' -> 空" << endl;
            cout << "目前栈：" << stack << endl;
            cout << "当前还未匹配成功的表达式：" << str << endl;
            cout << endl;
            E1();
            /////
            break;
        case '$':
            stack.pop_back();//弹出T'
            stack.pop_back();
            cout << "转换所用产生式:T' -> 空" << endl;
            cout << "目前栈：" << stack << endl;
            cout << "当前还未匹配成功的表达式：" << str << endl;
            cout << endl;
            E1();
            /////
            break;
        default:
            error++;
            cout << "出错: 未知输入" << endl;
            exit(0);
            break;
    }
}

F非终结符函数

根据同步记号分析表进行不同字符的判别与转化,并报告出相应错误

void F(){
    switch(str[0]){
        case 'i':
            stack.pop_back();//弹出F
            stack.append("i");//将i压入栈
            cout << "转换所用产生式:F -> i" << endl;
            cout << "目前栈：" << stack << endl;
            cout << "当前还未匹配成功的表达式：" << str << endl;
            str = str.substr(1);
            stack.pop_back();//匹配成功，弹出
            cout << endl;
            T1();
            break;
        case '+':
            error++;
            cout << "出错: '+'在F的同步记号集合中,无需跳过,F被弹出 " << endl;
            stack.pop_back();
            cout << "目前栈：" << stack << endl;
            cout << "当前还未匹配成功的表达式：" << str << endl;
            cout << endl;
            //////
            break;
        case '*':
            error++;
            cout << "出错: '*'在F的同步记号集合中,无需跳过,F被弹出 " << endl;
            stack.pop_back();
            cout << "目前栈：" << stack << endl;
            cout << "当前还未匹配成功的表达式：" << str << endl;
            cout << endl;
            //////
            break;
        case '(':
            
            stack.pop_back();//弹出F
            stack.append(")E(");//将(E)压入栈
            cout << "转换所用产生式:F -> (E)" << endl;
            cout << "目前栈：" << stack << endl;
            cout << "当前还未匹配成功的表达式：" << str << endl;
            stack.pop_back();
            str = str.substr(1);//匹配成功，弹出
            cout << endl;
            E();
            break;
        case ')':
            
            error++;
            cout << "出错: ')'在F的同步记号集合中,无需跳过,F被弹出 " << endl;
            stack.pop_back();
            cout << "目前栈：" << stack << endl;
            cout << "当前还未匹配成功的表达式：" << str << endl;
            cout << endl;
            //////
            break;
        case '$':
            error++;
            cout << "出错: '$'在F的同步记号集合中,无需跳过,F被弹出 " << endl;
            stack.pop_back();
            cout << "目前栈：" << stack << endl;
            cout << "当前还未匹配成功的表达式：" << str << endl;
            cout << endl;
            //////
            break;
        default:
            error++;
            cout << "出错: 未知输入" << endl;
            exit(0);
            break;
    }
}

三、结果

当输入 +i*+i算术表达式时

当输入(i+i)算术表达式时

当输入算术表达式i*(i+i

四、讨论与分析

优点：递归下降分析法简单、直观，易于构造分析程序。

缺点：对文法要求高，必须是LL(1)文法，同时由于递归调用较多，影响分析器的效率。

自顶向下分析就是从文法的开始符触发并寻找出这样一个推导序列：推导出的句子恰好为输入符号串；或者说，能否从根节点出发向下生长出一颗语法树，其叶节点组成的句子恰好为输入符号串。显然，语法树的每一步生长（每一步推导）都以能否与输入符号串匹配为准，如果最终句子得到识别，则证明输入符号串为该文发的一个句子；否则，输入符号串不是该文法的句子。

递归下降分析法是一种自顶向下的分析方法，文法的每个非终结符对应一个递归过程（函数）。分析过程就是从文法开始符触发执行一组递归过程（函数），这样向下推到直到推出句子；或者说从根节点出发，自顶向下为输入串寻找一个最左匹配序列，建立一颗语法树。

五、总结

通过本次实验对递归下降词法分析器的结构，过程有了更进一步的了解，通过学习书本和试验原理书上的内容，对它的工作原理，具体实行步骤有了进一步的掌握，由于本次试验是测试性试验，所以要求输出的结果是成功与否，输入一个句型，进过分析，判断它是否合法，主要内容在于其判断过程中。本次试验不光提高了自己的编程能力，同时提高了对递归下降的了解。

标签：文法,终结符,递归,程序,synch,语法分析,子程序
From： https://www.cnblogs.com/ywx1207/p/17870992.html

递归下降语法分析程序

一、目的

二、过程

2.1 了解背景

2.2 程序基本架构

2.3 实验内容

2.3.1 步骤一

2.3.2 步骤二

2.3.2.1 实现功能：从文件读入算术表达式/或者从终端输入

2.3.2.2 实现功能：总控函数分析算术表达式

三、结果

四、讨论与分析

五、总结

相关文章

赞助商

阅读排行