1. 首页
  2. 文章中心
  3. 编译原理

编译原理实验-递归下降语法分析器的构建

125 阅读 0 评论
我是靠谱客的博主 可靠爆米花，这篇文章主要介绍编译原理实验-递归下降语法分析器的构建，现在分享给大家，希望可以做个参考。

实验目的：
针对给定的上下文无关文法，编制一个递归下降分析程序。

分析：

  • 递归下降语法分析的前提是保证LL（1）文法

递归下降的思路就是暴力dfs。对每个程序直接不管三七二十一搜进去，只要能搜到就继续搜。搜不到就return搜其他的。

先看文法：

复制代码
1
2
3
4
5
6
①	: lexp->atom|list
②	：atom->number|identifier
③	：list->(lexp-seq)
④	：lexp-seq->lexp-seq lexp|lexp

很明显左递归，先消除一下

复制代码
1
2
3
4
5
6
7
8

①	: lexp->atom|list
②	：atom->number|identifier
③	：list->(lexp-seq)
④	：lexp-seq->lexp lexp-seq’
⑤	: lexp-seq’->lexp lexp-seq’|ε

然后直接对input字符流开始递归调用。

复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
#include<stdio.h>
#include<cstdlib>
#include<string.h>
#define maxn 1000
using namespace std;
int idx=0;
char str[maxn];
int lexp();
void atom();
void list();
void lexp_sep();
void lexp_sep_();
int lexp(){
	if( (str[idx]>='0'&&str[idx]<='9')||(str[idx]>='a'&&str[idx]<='z') ){
		printf("lexp->atomn");
		atom();
		return 1;
	}
	else if(str[idx]=='('){
		printf("lexp->listn");
		list();
		return 1;
	}
	else return 0;
}
void atom(){
	if(str[idx]>='0'&&str[idx]<='9'){
		printf("atom->numbern");
		idx++;
	}
	else if(str[idx]>='a'&&str[idx]<='z'){
		printf("atom->identifiern");
		idx++;
	}
}
void list(){
	if(str[idx]!='('){
		printf("list()error!n");
		exit(-1);
	}
	printf("list->(lexp_seq)n");
	idx++;
	lexp_sep();
	if(str[idx]!=')'){
		printf("list()error!n");
		exit(-1);
	}
	idx++;
}
void lexp_sep(){
	printf("lexp_sep->lexp lexp_seq'n");
	lexp();
	lexp_sep_();
}
void lexp_sep_(){
	if(lexp()==1){
		lexp_sep_();
	}
	else return;	
}
int main(int argc,char* argv[]){
	scanf("%s",str);
	int len=strlen(str);
	str[len++]='$';str[len]='';
	lexp();	
	if(str[idx]=='$') printf("accept!n");
	else printf("wrong answer!n");
	return 0;
}

测试数据：

复制代码
1
2
(a(b(2))c)

输出结果：

复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
lexp->list
list->(lexp_seq)
lexp_sep->lexp lexp_seq'
lexp->atom
atom->identifier
lexp->list
list->(lexp_seq)
lexp_sep->lexp lexp_seq'
lexp->atom
atom->identifier
lexp->list
list->(lexp_seq)
lexp_sep->lexp lexp_seq'
lexp->atom
atom->number
lexp->atom
atom->identifier
accept!

可以看到匹配是能成功的，但是对于想要我们输出该语法树就存在问题了。

经过思考发现，直接递归下降分析是无法完成语法树的构建输出的，虽然能匹配正确结果。
原因在于其需要判定递归有效才会输出，因此在决定是否进入的时候不能保证输出此次进去还是不进去。单纯一次递归有效可以用栈判定，但是多次就不行了。
因此需要构建first集合和follow集合来构建预测分析表。

当然cyc给每个token额外加了括号来直接dfs搜保证了正确的输出。在这里膜一下

在这里插入图片描述

在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
#include<iostream>
#include<stack>
#include<algorithm>
#include<string>
using namespace std;
stack<string>input;
stack<string>st;
bool number(const string& s){
  for(int i=0;i<(int)s.size();i++){
      if(!(s[i]>='0'&&s[i]<='9')) return false;
  }
  return true;
}
bool identifier(const string& s){
  for(int i=0;i<(int)s.size();i++){
      if(!(s[i]>='a'&&s[i]<='z')) return false;
  }
  return true;
}
int main(){
    input.push("$");
    string s;cin>>s;
    for(int i=(int)s.size()-1;i>=0;i--){
       string tmp;tmp+=s[i];
       input.push(tmp);
    }
    st.push("$");
    st.push("lexp");
    while(st.size()>1){
       string now=st.top();st.pop();
       string cnt=input.top();
       if(now=="lexp"){
         if(cnt=="("){
           cout<<"lexp  -> list"<<endl;
           st.push("list");
         } 
         else if(number(cnt)){
            cout<<"lexp -> atom"<<endl;
            st.push("atom");
         }
         else if(identifier(cnt)){
            cout<<"lexp -> atom"<<endl; 
            st.push("atom");
         }
         else{
            cout<<"lexp()->next error!"<<endl;
            exit(-1);
         }
       }
       else if(now=="atom"){
         if(number(cnt)){
            cout<<"atom -> number"<<endl;
            input.pop();  
         }
         else if(identifier(cnt)){
            cout<<"atom -> identifier"<<endl;
            input.pop();
         }
         else{
            cout<<"atom()->next error!"<<endl;
            exit(-1);
         }
       }
       else if(now=="list"){
         if(cnt=="("){
            cout<<"list -> ( lexp-seq )"<<endl;
            input.pop(); 
            st.push(")");
            st.push("lexp-seq");
         }
         else{
           cout<<"list()-> next errpr!"<<endl;
           exit(-1);
         }
       }
       else if(now=="lexp-seq"){
         if(cnt=="("||number(cnt)||identifier(cnt)){
            cout<<"lexp-seq -> lexp lexp-seq'"<<endl;
            st.push("lexp-seq'");
            st.push("lexp");
         } 
         else{
           cout<<"lexp-seq()->next error!"<<endl;
           exit(-1);
         }
       }
       else if(now=="lexp-seq'"){
         if(cnt=="("||number(cnt)||identifier(cnt)){
            cout<<"lexp-seq'  -> lexp lexp-seq'"<<endl; 
            st.push("lexp-seq'");
            st.push("lexp");
         }
         else{
            cout<<"lexp-seq'  -> NULL"<<endl; 
         }
       }
       else if(now==")"&&cnt==")"){
          input.pop(); 
       }
       else{
          cout<<"Wrong answer"<<endl;
          exit(-1);
       }
    }
    cout<<"Accept!"<<endl;
}

输入：

复制代码
1
2
(a(b(2))c)

python生成图片：
在这里插入图片描述

最后

以上就是可靠爆米花最近收集整理的关于编译原理实验-递归下降语法分析器的构建的全部内容，更多相关编译原理实验-递归下降语法分析器内容请搜索靠谱客的其他文章。

本图文内容来源于网友提供，作为学习参考使用，或来自网络收集整理，版权属于原作者所有。
点赞(83)

相关文章

《编译原理》实验二-递归下降语法分析器的构建-实验报告一、实验要求二、实验方案三、预估问题四、内容和步骤五、实验结果六、实验结论
《编译原理》实验二-递归下降语法分析器的构建-实验报告一、实验要求二、实验方案三、预估问题四、内容和步骤五、实验结果六、实验结论
C语言实现计算器（基于EBNF表达式和递归下降思想）
C语言实现计算器（基于EBNF表达式和递归下降思想）
编译原理-递归下降分析器
编译原理-递归下降分析器
编译原理实验二 递归下降语法分析器的构建
编译原理实验二 递归下降语法分析器的构建
编译原理实验-递归下降语法分析器的构建
编译原理实验-递归下降语法分析器的构建
编译原理｜递归下降分析子程序
编译原理｜递归下降分析子程序
【编译原理与技术】递归下降语法分析器（C++实现）内容：具体实现：运行结果：
【编译原理与技术】递归下降语法分析器（C++实现）内容：具体实现：运行结果：
消除文法的左递归和回溯1.自上而下分析2.直接左递归的消除3.直接左递归例题4.间接左递归的消除5.间接左递归例题6.消除回溯
消除文法的左递归和回溯1.自上而下分析2.直接左递归的消除3.直接左递归例题4.间接左递归的消除5.间接左递归例题6.消除回溯

评论列表共有 0 条评论

立即
投稿
返回
顶部