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
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
|
#include <vector>
#include <map>
#include <utility>
#include <vector>
#include <iostream>
using namespace std;
typedef std::pair<char,char> Key;
struct E
{
vector<char> h;
Key get() {
char second = h.back();
h.pop_back();
char first = h.back();
h.pop_back();
return make_pair(first, second);
}
bool good() { return h.size() > 1; }
char add(char c) { h.push_back(c); }
};
struct P
{
std::map<Key, char> actionTable_;
P()
{
createActionTable();
}
void r(E& e)
{
cout << "before: ";
for (auto it: e.h)
cout << it;
cout << endl;
bool stop = false;
while (e.good() && !stop) {
pair<char,char> k = e.get();
char action = actionTable_[k];
switch (action) {
case 'L':
e.add('f');
break;
case 'R':
e.add('f');
stop = true;
break;
case 'S':
e.add(k.first);
e.add(k.second);
stop = true;
break;
case 'I':
default:
e.add('u');
stop = true;
break;
}
}
cout << " after: ";
for (auto it: e.h)
cout << it;
cout << endl;
cout << "--" << endl;
}
void createActionTable()
{
// u ->
actionTable_[Key('u','u')] = 'S'; // Shift
actionTable_[Key('u','f')] = 'S';
actionTable_[Key('u','l')] = 'S';
actionTable_[Key('u','r')] = 'I'; // Illegal
// f ->
actionTable_[Key('f','f')] = 'S'; // ambiguous
actionTable_[Key('f','l')] = 'S';
actionTable_[Key('f','r')] = 'R'; // Right-reduce
// l ->
actionTable_[Key('l','f')] = 'L'; // Left-reduce
actionTable_[Key('l','l')] = 'S';
actionTable_[Key('l','r')] = 'I';
// r ->
actionTable_[Key('r','f')] = 'I';
actionTable_[Key('r','l')] = 'I';
actionTable_[Key('r','r')] = 'I';
}
};
int main(void)
{
E e;
P p;
/*e.add('u');
p.r(e);
e.add('l');
p.r(e);
e.add('l');
p.r(e);
e.add('f');
p.r(e);
e.add('r');
p.r(e);*/
string s("frllllfrlllllllf");
for (auto it: s) {
e.add(it);
p.r(e);
}
return 0;
}
|
