递归下降语法分析设计原理与实现

﹏ヽ暗。殇╰゛Y 2024-03-30 14:53 82阅读 0赞

目录  
一、 理论传授 2  
二、 目标任务 2  
三、 任务分析 2  
四、 实验原理分析 2  
五、 程序功能描述 3  
六、 程序结构描述 3  
七、 实验结果及测试 8

一、 理论传授  
语法分析的设计方法和实现原理；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）递归下降分析程序应能发现简单的语法错误；  
（3）设计两个测试用例（尽可能完备，正确和出错），并给出测试结果；  
（4）选做：如有可能，考虑如何用文法描述 C 语言的 if 语句，使整个文法仍  
然为 LL（1）文法，并使得你的递归下降程序可以分析赋值语句和 if 语句。

三、 任务分析  
重点解决 LL(1)文法到递归子程序框图的设计。

四、实验原理分析  
递归下降法的主要原理是，对每个非终结符按其产生式结构构造相应语法分析子程序，其中终结符产生匹配命令，而非终结符则产生过程调用命令。因为文法递归相应子程序也递归，所以称这种方法为递归子程序下降法或递归下降法。  
递归下降分析程序的实现思想是：识别程序由一组子程序组成。每个子程序对应于一个非终结符号。每一个子程序的功能是：选择正确的右部，扫描完相应的字。在右部中有非终结符号时，调用该非终结符号对应的子程序来完成。  
无回溯的自上向下分析技术可用的先决条件是：无左递归和无回溯。即：假设A的全部产生式为Aα1|α2|……|αn ，则必须满足如下条件才能保证可以唯一的选择合适的产生式  
First(Aαi)∩First(Aαj)=Φ,当i≠j.  
无左递归：既没有直接左递归，也没有间接左递归。  
无回溯：对于人以非中介符号U的产生式右部，其对应的字的首终结符号两两不相交。  
如果一个文法不含回路（形如的推导），也不含以为右部的产生式，那么可以通过执行消除左递归的算法消除文法的一切左递归。

五、程序功能描述  
1、将二元式序列文件作为程序的输入；  
2、对输入的字符串做出正确的递归下降分析判断，判断其是否是给定文法的算术表达式；  
3、能发现简单的错误，例如非法字符输入和合法输入但其中某处推导中出现的语法错误等；

#include "pch.h"
    #define _CRT_SECURE_NO_WARNINGS
    /****************************************************
    研究型专题2：递归下降语法分析设计原理与实现
    ***************************************************
    
    **************单词符号及其分类编码****************
    单词符号	种别码
    =               1
    (				2
    )				3
    +				4
    -				5
    *				6
    /				7
    i				8
    #				9
    ***************************************************/
    #include<stdio.h>
    #include<iostream>
    #include<stdlib.h>
    #include<conio.h>
    using namespace std;
    #define MAX 100
    char token[MAX];
    char token1[MAX];		//用于检测文件输入是否匹配
    char token2[MAX];
    char current;
    int i = 0;
    
    void S();
    void E();
    void E1();
    void T();
    void A();
    void F();//函数推导过程
    void T1();
    void M();
    void V();
    void error(char *c);    //提出语法错误
    void error1();  //提出非法输入错误
    
    void init()		//初始化
    {
        
    	current = token[i];
    }
    
    void judge(char ch, int i)		//判断文件读取内容是否合法，包括检查非法字符和不匹配现象
    {
        
    	switch (ch)
    	{
        
    	case '1':
    		if (token[i] != '=')
    			error1();
    		break;
    	case '2':
    		if (token[i] != '(')
    			error1();
    		break;
    	case '3':
    		if (token[i] != ')')
    			error1();
    		break;
    	case '4':
    		if (token[i] != '+')
    			error1();
    		break;
    	case '5':
    		if (token[i] != '-')
    			error1();
    		break;
    	case '6':
    		if (token[i] != '*')
    			error1();
    		break;
    	case '7':
    		if (token[i] != '/')
    			error1();
    		break;
    	case '8':
    		if (token[i] != 'i')
    			error1();
    		break;
    	case '9':
    		if (token[i] != '#')
    			error1();
    		break;
    	default:
    		error1();
    		break;
    	}
    }
    
    void advance()		//读取下一个字符
    {
        
    	if (i == MAX)
    		exit(0);
    	current = token[++i];
    }
    
    void S()
    {
        
    	if (current == 'i')
    	{
        
    		V();
    		if (current == '=')
    		{
        
    			advance();
    			E();
    		}
    	}
    	else
    		error(const_cast<char*>("S"));
    }
    
    void E()
    {
        
    	if (current == 'i' || current == '(')
    	{
        
    		T();
    		E1();
    	}
    	else
    		error(const_cast<char*>("E"));
    }
    
    void E1()
    {
        
    	if (current == '+' || current == '-')
    	{
        
    		A();
    		T();
    		E1();
    	}
    	else
    		if (!(current == ')' || current == '#'))
    			error(const_cast<char*>("E1"));
    }
    
    void T()
    {
        
    	if (current == 'i' || current == '(')
    	{
        
    		F();
    		T1();
    	}
    	else
    		error(const_cast<char*>("T"));
    }
    
    void T1()
    {
        
    	if (current == '*' || current == '/')
    	{
        
    		M();
    		F();
    		T1();
    	}
    	else
    		if (!(current == ')' || current == '#' || current == '+' || current == '-'))
    			error(const_cast<char*>("T1"));
    }
    
    void M()
    {
        
    	if (current == '*')
    		advance();
    	else
    		if (current == '/')
    			advance();
    		else
    			error(const_cast<char*>("M"));
    }
    
    void A()
    {
        
    	if (current == '+')
    		advance();
    	else
    		if (current == '-')
    			advance();
    		else
    			error(const_cast<char*>("A"));
    }
    
    void F()
    {
        
    	if (current == '(')
    	{
        
    		advance();
    		E();
    		if (current == ')')
    			advance();
    	}
    	else
    		if (current == 'i')
    			advance();
    		else
    			error(const_cast<char*>("F"));
    }
    
    void V()
    {
        
    	if (current == 'i')
    		advance();
    	else
    		error(const_cast<char*>("V"));
    }
    
    void error(char *c)
    {
        
    	printf("%s 处有语法错误\n", c);
    	cout << "输入串不是该文法定义的算术表达式!" << endl;
    	exit(0);
    }
    
    void error1()
    {
        
    	cout << "非法输入错误！" << endl;
    	cout << "输入串不是该文法定义的算术表达式!" << endl;
    	exit(0);
    }
    
    void readFile()
    {
        
    	int j = 1;
    	int i = 0;
    	FILE *fp;
    	if ((fp = fopen("input2.txt", "r")) == NULL)
    	{
        
    		cout << "文件打开失败！" << endl;
    		exit(0);
    	}
    	token1[0] = fgetc(fp);
    	while (!feof(fp))
    	{
        
    		token1[j++] = fgetc(fp);
    		if ((j % 5) == 0)
    		{
        
    			token2[i] = token1[j - 4];
    			token[i] = token1[j - 2];
    			judge(token2[i], i);
    			i++;
    		}
    	}
    	if ((j - 1) % 5 != 0) {
        
    		error1();
    	}
    	cout << "读入字符串为：" << token << endl;
    }
    
    int main()
    {
        
    	readFile();
    	init();
    	S();
    	if (current == '#')
    		cout << "输入串是该文法定义的算术表达式!" << endl;
    	return 1;
    }

![在这里插入图片描述][abcbfac06d1c47e4b7e9b88c4ef1b12f.png_pic_center]  
![在这里插入图片描述][0253dd6af6d946dfa311cabd9e64cc5a.png_pic_center]  
![在这里插入图片描述][4da385aac4604c85852a4dc5fd187fde.png_pic_center]  
![在这里插入图片描述][e065bb94c02e4cff8458e41e1133925b.png_pic_center]  
![在这里插入图片描述][c6533159c57647d78772cda4645ebaac.png_pic_center]  
![在这里插入图片描述][1773ff883ed841dcb74b3f1144748cad.png_pic_center]  
![在这里插入图片描述][ca9ca57aa3a248f28c5e44ccb70e5c42.png_pic_center]  
![在这里插入图片描述][e1e4f03e6dc44decae6ab43d9eab4d64.png_pic_center]  
![在这里插入图片描述][60d94b1a61ff4309b572d139dd508164.png_pic_center]

[abcbfac06d1c47e4b7e9b88c4ef1b12f.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/715fcb21e01e4945a75ce32833412384.png
[0253dd6af6d946dfa311cabd9e64cc5a.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/50caa80e408244a1801aed086bd27075.png
[4da385aac4604c85852a4dc5fd187fde.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/90575f79e3ad410397439b70b117327e.png
[e065bb94c02e4cff8458e41e1133925b.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/714fdce15ff74fefa6ca1e1d0dcf8018.png
[c6533159c57647d78772cda4645ebaac.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/e38a54278d02416e8d836148cfcb0102.png
[1773ff883ed841dcb74b3f1144748cad.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/7ee586d1ef0b4f828a2f535e56c369ca.png
[ca9ca57aa3a248f28c5e44ccb70e5c42.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/3c5f8f2e70b643c09e49e3a20a5a48a4.png
[e1e4f03e6dc44decae6ab43d9eab4d64.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/a9b9158c54e34738bd48117ee5921401.png
[60d94b1a61ff4309b572d139dd508164.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/4c1ff179d46e4e2788eea127ef892d5c.png