This repository has been archived by the owner on Feb 27, 2020. It is now read-only.
-
Notifications
You must be signed in to change notification settings - Fork 0
/
parser.h
211 lines (194 loc) · 6.35 KB
/
parser.h
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
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
#pragma once
struct Syntax_error
{
};
// Grammar parser. Parses productions and stores them in EBNF form. Then simplifies them
// to simple CFG on request.
struct Parser
{
Scanner& scn_; // The scanner being used
ProductionList prods_; // The list of productions parsed
public:
Parser(Scanner& scn)
: scn_{ scn }
{
}
const ProductionList& productions() const { return prods_; }
void syntax_error(const std::string& msg)
{
scn_.show_line();
printf("%s(%zu): error: %s\n", scn_.filename(), scn_.lineno(), msg.c_str());
throw Syntax_error{};
}
void require(Tok t)
{
if (scn_.token() == t)
scn_.get();
else
{
std::string msgbuf;
msgbuf += "expected ";
msgbuf += Scanner::string_for_token(t);
msgbuf += " but got ";
msgbuf += scn_.curr_token_str();
syntax_error(msgbuf);
}
}
bool next_is(Tok t) const { return scn_.token() == t; }
Tok token() const { return scn_.token(); }
void gettoken() { scn_.get(); }
// Parse a single terminal or non-terminal
Item* scan_name_or_symbol()
{
if (next_is(Tok::id))
{
auto name = scn_.identifier();
gettoken();
return new NonTerminal{ name };
}
else if (next_is(Tok::literal))
{
auto lit = scn_.literal();
scn_.get();
return new Terminal{ lit };
}
else
{
using namespace std::literals;
syntax_error("unexpected token "s + scn_.curr_token_str());
return new Epsilon{}; // not reached.
}
}
// Parse { ... } ( ... ) or [ ... ]
GroupedItemSequence* scan_grouped_items()
{
auto group_clause = new GroupedItemSequence{ token() };
gettoken();
group_clause->contents = scan_alternatives();
require(group_clause->group_kind() == Tok::lbrace
? Tok::rbrace
: group_clause->group_kind() == Tok::lbrack ? Tok::rbrack : Tok::rparen);
return group_clause;
}
// Parse a general item on the RHS of a production.
Item* scan_production_item()
{
if (next_is(Tok::lbrace) || next_is(Tok::lbrack) || next_is(Tok::lparen))
{
return scan_grouped_items();
}
return scan_name_or_symbol();
}
// Parse a sequence of items. If more than 1 item exists build an ItemSequence.
// Else, return just the item.
Item* scan_production_item_seq()
{
auto item = scan_production_item();
if (!(next_is(Tok::id) || next_is(Tok::literal) || next_is(Tok::lbrace) || next_is(Tok::lbrack) || next_is(Tok::lparen)))
{
return item;
}
auto result = new ItemSequence;
result->sequence.push_back(item);
while (next_is(Tok::id) || next_is(Tok::literal) || next_is(Tok::lbrace) || next_is(Tok::lbrack) || next_is(Tok::lparen))
{
item = scan_production_item();
if (auto items = item->only_if<ItemSequence>())
{
// Concatenate sequences.
result->sequence.insert(
result->sequence.end(), items->sequence.begin(), items->sequence.end());
}
else
{
result->sequence.push_back(item);
}
}
return result;
}
// Parse one of alt1 | alt2 ...
Item* scan_single_alternative()
{
if (next_is(Tok::epsilon))
{
auto item = new Epsilon{};
gettoken();
return item;
}
auto seq = scan_production_item_seq();
return seq;
}
// Parse <alpha>| <beta> | ...
// If there is a single alternative, build and ItemSequence, otherwise build
// Alternatives.
Item* scan_alternatives()
{
auto prodalt = scan_single_alternative();
if (!next_is(Tok::alt))
{
return prodalt;
}
Alternatives* alt = new Alternatives;
alt->alternatives.push_back(prodalt);
while (next_is(Tok::alt))
{
gettoken();
prodalt = scan_single_alternative();
alt->alternatives.push_back(prodalt);
}
return alt;
}
// Parse a production in EBNF form.
Production* scan_production()
{
auto nonterm = scn_.token() == Tok::id ? scn_.identifier() : ""; // guard against erroneous input
auto line = scn_.lineno();
require(Tok::id);
require(Tok::colon);
auto altlist = scan_alternatives();
require(Tok::semi);
return new Production{ new NonTerminal{ nonterm }, altlist, Location{ line } };
}
// Parse the entire grammar file.
void parse()
{
// The grammar file is in the EBNF format, specified below in EBNF:
// Productions = Production { Production }
// Production = NonTerminal ':' Alternatives ';'
// NonTerminal = Identifier
// Alternatives = SingleAlternative { '|' SingleAlternative }
// SingleAlternative = ProductionItemSeq | 'EPSILON'
// ProductionItemSeq = ProductionItem { ProductionItem }
// ProductionItem = NameOrSymbol | ProductionItemSeqClause
// ProductionItemSeqClause = '{' Alternatives '}' | '[' Alternatives ']' |
// '(' Alternatives ')' NameOrSymbol = Identifier | LiteralInQuotes
auto prod = scan_production();
prods_.push_back(prod);
while (next_is(Tok::id))
{
prod = scan_production();
prods_.push_back(prod);
}
}
void test_lexer()
{
for (;;)
{
printf("%s\n", scn_.curr_token_str().c_str());
if (scn_.token() == Tok::eof)
break;
scn_.get();
}
}
template <typename List>
static std::string to_string(const List& prodlist)
{
std::string buf;
for (auto prod : prodlist)
{
buf += prod->to_string();
buf += '\n';
}
return buf;
}
};