SLR(1)分析法

更新时间:2023-07-14 16:34:43 阅读: 评论:0

SLR(1)分析法
由于LR(0)的能⼒实在是太弱了。例如:
I = { X=>α·bβ,
  A=>α·,
  B=>α· }
这时候就存在两个冲突。
1、移进和规约的冲突;
2、规约和规约的冲突。
SLR(1)就是为了解决冲突⽽设计的,解决冲突的⽅法就是向后多看⼀个字符,这就是SLR(1)。
简⽽⾔之就是为每个⾮终结符,计算出它们的follow集。从⽽可以解决移进与规约、规约与规约的冲突了。
SLR(1)所说的多看⼀个字符在构造分析表的时候就根据follow集已经构造好了,分析程序和LR(0)是⼀样的,分析表不同。
具体实现如下:
拓⼴⽂法 G'[S']:
(0) S'→S
(1) S→ABC
(2) A→Aa
(3) A→a
(4) B→Bb
(5) B→b
(6) C→Cc
(7) C→c
1、计算初始状态的项⽬集
Q0=CLOSURE({S'→•S })={ S'→•S , S→•ABC, A→•Aa, A→•a };
2、计算每个状态的项⽬集
Q1=GO(Q0,a)=CLOSURE({A→a •})={ A→a• };
Q2=GO(Q0,S)=CLOSURE({S'→S •})={ S'→S • };
Q3=GO(Q0,A) = CLOSURE({S→A•BC, A→A•a}) = {S→A•BC, A→A•a, B→•Bb, B→•b}; Q4=GO(Q3,a)=CLOSURE({A→Aa• })={ A→Aa• }; Q5=GO(Q3,b)=CLOSURE({B→b• })={ B→b•};
Q6=GO(Q3,B)=CLOSURE({S→AB•C, B→B•b }) ={ S→AB•C, B→B•b , C→•Cc , C→•c }; Q7=GO(Q6,b)=CLOSURE({B→Bb •})={ B→Bb •}; Q8=GO(Q6,c)=CLOSURE({C→c •})={ C→c •};
Q9=GO(Q6,C)=CLOSURE({S→ABC•, C→C•c })={ S→ABC•, C→C•c }; Q10=GO(Q9,c)=CLOSURE({C→Cc• })={ C→Cc•};网络歌曲下载
3、构造识别可归约前缀的 DFA
4、计算⽂法的 FIRST 和 FOLLOW 集合
⾮终结符FIRST FOLLOW
S a#
A a a,b
B b b,c
C c c,#
状态节点 Q9= { S→ABC•, C→C•c }中存在存在移进-规约冲突。
{b}∩FOLLOW(S) ={b}∩{#}=Φ,因此⽂法是 SLR(1)⽂法。
5、构造 SLR(1)分析表
a b c#S A B C 0S123
1R3R3
2acc
3S4S56
4R2R2
5R5R5
6S7S89 7R4R4
8R7R7
9S10R1
10R6R6
实验程序:
1 #include<bits/stdc++.h>
2#define ROW 12
3#define COLUMN 9
我们可以在一起
4using namespace std;
5//产⽣式
6string products[8][2]={
7 {"S'","S"},
8 {"S","ABC"},
9 {"A","Aa"},
10 {"A","a"},
11 {"B","Bb"},
12 {"B","b"},
13 {"C","Cc"},
14 {"C","c"}
15 };
16//SLR(1)分析表
17string actiontable[ROW][COLUMN]={
18 {"","a","b","c","#","S","A","B","C"},
19 {"0","s1","","","","2","3","",""},
20 {"1","r3","r3","","","","","",""},
21 {"2","","","","acc","","","",""},
22 {"3","s4","s5","","","","","6",""},
23 {"4","r2","r2","","","","","",""},
我的人生理想24 {"5","","r5","r5","","","","",""},
25 {"6","","s7","s8","","","","","9"},
26 {"7","","r4","r4","","","","",""},
27 {"8","","","r7","r7","","","",""},
28 {"9","","","s10","r1","","","",""},
29 {"10","","","r6","r6","","","",""}
30 };
31 stack<int> sstatus; //状态栈
32 stack<char> schar; //符号栈
33struct Node{
34char type;
35int num;
36 };
37//打印步骤
38void print_step(int times){
39    stack<char> tmp2;
40    cout<<times<<tw(4);
41while(!pty()){
42char p();
43        schar.pop();
44        tmp2.push(t);王者名字大全女
45        cout<<t;
科学概念
46    }
47while(!pty()){
48int p();
49        tmp2.pop();
50        schar.push(t);
51    }
52 }
53//查表
54 Node Action_Goto_Table(int status,char a){ 55int row=status+1;
56string tmp;
57for(int j=1;j<COLUMN;j++){
58if(a==actiontable[0][j][0]){
59            tmp=actiontable[row][j];
60        }
61    }
62    Node ans;
63if(tmp[0]>='0'&&tmp[0]<='9'){
64int val=0;
气血虚弱的症状65for(int i=0;i<tmp.length();i++){
66            val=val*10+(tmp[i]-'0');
67        }
68        ans.num=val;
69        pe='';
70    }el if(tmp[0]=='s'){
71int val=0;
72for(int i=1;i<tmp.length();i++){
73            val=val*10+(tmp[i]-'0');
74        }
75        pe='s';
76        ans.num=val;
77    }el if(tmp[0]=='r'){
78int val=0;
79for(int i=1;i<tmp.length();i++){
80            val=val*10+(tmp[i]-'0');
81        }
82        pe='r';
83        ans.num=val;
84    }el if(tmp[0]=='a'){
85        pe='a';
86    }el{
87        pe='';
88    }
89return ans;
90 }
91//SLR(1)分析算法
92bool SLR1(string input){
93while(!pty()){
94        sstatus.pop();
95    }
96while(!pty()){
97        schar.pop();
98    }
99int times=0;
100bool flag=true;
101int st=0;
102    sstatus.push(st);
103    schar.push('#');
104int i=0;
105char a=input[i];
106while(true){
107        Node action=Action_Goto_Table(st,a); pe=='s'){
109            st=action.num;
110            sstatus.push(st);
111            schar.push(a);
112            a=input[++i];
113            print_step(++times);
114            cout<<tw(10)<<'s'<<st<<endl;
115
116        }el pe=='r'){
117int n=action.num;
118string ls=products[n][0];
119string rs=products[n][1];
120for(int j=0;j<rs.length();j++){
121                sstatus.pop();
122                schar.pop();
123            }
124            schar.push(ls[0]);
125            p();
126            action =Action_Goto_Table(st,ls[0]);
127            st=action.num;
128            sstatus.push(st);
129            print_step(++times);
130            cout<<tw(10)<<'r'<<""<<ls<<"->"<<rs<<endl; 131
132        }el pe=='a'){
德智体133            flag=true;
134break;
135        }el{
136            flag=fal;
137break;
138        }
139    }
140return flag;
141 }
142int main(){
桥的读后感143string input;
144while(cin>>input){
145if(SLR1(input)){
146            cout<<"syntax correct"<<endl;
147        }el{
148            cout<<"syntax error"<<endl;
149        }
150    }
151return0;
152 }

本文发布于:2023-07-14 16:34:43,感谢您对本站的认可!

本文链接:https://www.wtabcd.cn/fanwen/fan/89/1081390.html

版权声明:本站内容均来自互联网,仅供演示用,请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系,我们将在24小时内删除。

标签:构造   规约   状态   分析   冲突   网络   程序   理想
相关文章
留言与评论(共有 0 条评论)
   
验证码:
推荐文章
排行榜
Copyright ©2019-2022 Comsenz Inc.Powered by © 专利检索| 网站地图