mCRL2
Loading...
Searching...
No Matches
dparser.cpp
Go to the documentation of this file.
1// Author(s): Wieger Wesselink
2// Copyright: see the accompanying file COPYING or copy at
3// https://github.com/mCRL2org/mCRL2/blob/master/COPYING
4//
5// Distributed under the Boost Software License, Version 1.0.
6// (See accompanying file LICENSE_1_0.txt or copy at
7// http://www.boost.org/LICENSE_1_0.txt)
8//
11
12#include <d.h>
15#include <iomanip>
16#include <locale>
17
18extern "C"
19{
20 extern D_ParserTables parser_tables_mcrl2;
21}
22
23namespace mcrl2 {
24
25namespace core {
26
27std::string parse_node::add_context(const std::string& message) const
28{
29 return detail::add_context(&node->start_loc, message);
30}
31
33{
34 return node->symbol;
35}
36
38{
39 return d_get_number_of_children(node);
40}
41
42// 0 <= i < child_count()
44{
45 return parse_node(d_get_child(node, i));
46}
47
49{
50 return parse_node(d_find_in_tree(node, symbol));
51}
52
53std::string parse_node::string() const
54{
55 return std::string(node->start_loc.s, node->end - node->start_loc.s);
56}
57
58std::string parse_node::tree() const
59{
60 if (child_count() < 2)
61 return this->string();
62 std::stringstream result;
63 result << "(" << child(0).tree();
64 for (int i = 1; i < child_count(); ++i)
65 result << " " << child(i).tree();
66 result << ")";
67 return result.str();
68}
69
71{
72 return node->start_loc.col;
73}
74
76{
77 return node->start_loc.line;
78}
79
80std::string parse_node::pathname() const
81{
82 return std::string(node->start_loc.pathname);
83}
84
86{
87 if (parser)
88 {
89 free_D_ParseNode(parser, node);
90 }
91}
92
93// Prints a tree of
94std::string parser_table::tree(const core::parse_node& node) const
95{
96 std::stringstream result;
97 result << symbol_name(node) << "(";
98 if (node.child_count() == 0)
99 result << '"' << node.string() << '"';
100 else
101 result << tree(node.child(0));
102 for (int i = 1; i < node.child_count(); ++i)
103 result << " " << tree(node.child(i));
104 result << ")";
105 return result.str();
106}
107
108// Returns the number of symbols in the table
109unsigned int parser_table::symbol_count() const
110{
111 return m_table.nsymbols;
112}
113
114// Returns the name of the i-th symbol
115std::string parser_table::symbol_name(unsigned int i) const
116{
117 if (i >= m_table.nsymbols)
118 {
119 print();
120 std::ostringstream out;
121 out << "parser_table::symbol_name: index " << i << " out of bounds!";
122 throw std::runtime_error(out.str());
123 }
124 const char* name = m_table.symbols[i].name;
125 if (!name)
126 {
127 return "";
128 }
129 return std::string(name);
130}
131
132std::string parser_table::symbol_name(const parse_node& node) const
133{
134 return symbol_name(node.symbol());
135}
136
137// Returns the 'start symbol' of the i-th symbol
138int parser_table::start_symbol(unsigned int i) const
139{
140 return m_table.symbols[i].start_symbol;
141}
142
143// Returns true if the i-th symbol is of type D_SYMBOL_NTERM
144bool parser_table::is_term_symbol(unsigned int i) const
145{
146 return m_table.symbols[i].kind == D_SYMBOL_NTERM;
147}
148
149unsigned int parser_table::start_symbol_index(const std::string& name) const
150{
151 for (unsigned int i = 0; i < symbol_count(); i++)
152 {
153 if (is_term_symbol(i) && symbol_name(i) == name)
154 {
155 return start_symbol(i);
156 }
157 }
158 throw mcrl2::runtime_error("unknown start symbol '" + name + "'");
159 return 0;
160}
161
163{
164 std::clog << "--------------------" << std::endl;
165 std::clog << "- symbol table -" << std::endl;
166 std::clog << "--------------------" << std::endl;
167 for (unsigned int i = 0; i < symbol_count(); i++)
168 {
169 std::clog << std::setw(3) << i << " " << symbol_name(i) << std::endl;
170 }
171 std::clog << "--------------------" << std::endl;
172}
173
174parser::parser(D_ParserTables& tables, D_AmbiguityFn ambiguity_fn, D_SyntaxErrorFn syntax_error_fn, std::size_t max_error_message_count)
175 : m_table(tables)
176{
177 detail::set_dparser_max_error_message_count(max_error_message_count);
178 m_parser = new_D_Parser(&tables, 0);
179 m_parser->initial_globals = this;
180 m_parser->save_parse_tree = 1;
181 m_parser->initial_scope = nullptr;
182 m_parser->dont_use_greediness_for_disambiguation = 1;
183 m_parser->dont_use_height_for_disambiguation = 1;
184 if (ambiguity_fn)
185 {
186 m_parser->ambiguity_fn = ambiguity_fn;
187 }
188 if (syntax_error_fn)
189 {
190 m_parser->syntax_error_fn = syntax_error_fn;
191 }
192}
193
195{
196 free_D_Parser(m_parser);
197}
198
200{
201 return m_table;
202}
203
204unsigned int parser::start_symbol_index(const std::string& name) const
205{
206 return m_table.start_symbol_index(name);
207}
208
209parse_node parser::parse(const std::string& text, unsigned int start_symbol_index, bool partial_parses)
210{
212 m_parser->start_state = start_symbol_index;
213 m_parser->partial_parses = partial_parses ? 1 : 0;
214 D_ParseNode* result = dparse(m_parser, const_cast<char*>(text.c_str()), static_cast<int>(text.size()));
215 if (!result || m_parser->syntax_errors)
216 {
217 if (result != nullptr) {
218 free_D_ParseNode(m_parser, result);
219 }
220 throw mcrl2::runtime_error("syntax error");
221 }
222 return parse_node(result, m_parser);
223}
224
226{
227 m_table.print();
228}
229
230std::string parser::indent(unsigned int count) const
231{
232 return std::string(count, ' ');
233}
234
235std::string parser::truncate(const std::string& s, unsigned int max_size) const
236{
237 std::string result = s.substr(0, max_size);
238
239 // truncate at newline
240 std::string::size_type pos = result.find('\n');
241 if (pos != std::string::npos)
242 {
243 result = result.substr(0, pos);
244 }
245
246 return result;
247}
248
249void parser::print_tree(const parse_node& node, unsigned int level) const
250{
251 if (node)
252 {
253 std::string symbol = m_table.symbol_name(node.symbol());
254 std::string prefix = indent(2 * level);
255 std::cout << prefix << "--- " << symbol << " \"" << truncate(node.string()) << "\"" << std::endl;
256 for (int i = 0; i <= node.child_count(); i++)
257 {
258 print_tree(node.child(i), level + 1);
259 }
260 }
261}
262
264{
265 free_D_ParseNode(m_parser, node.node);
266}
267
269void parser::announce(D_ParseNode& node_ref)
270{
271 parse_node node(&node_ref);
272 std::cout << "parsed " << m_table.symbol_name(node.symbol()) << " " << node.string() << std::endl;
273}
274
275namespace detail {
276
277std::string add_context(const d_loc_t* loc, const std::string& message)
278{
279 std::stringstream s;
280 s << "Line " << loc->line << ", column " << loc->col << ": "
281 << message << std::endl;
282 char* beg = loc->s - loc->col;
283 char* end = loc->s;
284 while (*end != '\0' && *end != '\n' && *end != '\r')
285 {
286 ++end;
287 }
288 std::string line(beg, end);
289 s << " " << line << std::endl;
290 for (int i = 0; i < loc->col + 2; ++i)
291 {
292 s << ' ';
293 }
294 s << '^';
295 return s.str();
296}
297
298inline
299bool is_all_of_type(D_ParseNode* nodes[], int n, const char* type, const core::parser_table& table)
300{
301 for (int i = 0; i < n; i++)
302 {
303 core::parse_node node(nodes[i]);
304 if (table.symbol_name(node) != type)
305 {
306 return false;
307 }
308 }
309 return true;
310}
311
312inline
313void print_ambiguous_nodes(D_ParseNode* nodes[], int n, const char* type, const core::parser_table& table)
314{
315 mCRL2log(log::verbose) << "--- " << type << " ambiguity" << std::endl;
316 for (int i = 0; i < n; ++i)
317 {
318 core::parse_node vi(nodes[i]);
319 // mCRL2log(log::verbose) << vi.tree() << " " << table.tree(vi) << std::endl;
320 mCRL2log(log::verbose) << "ALT " << table.tree(vi) << std::endl;
321 }
322}
323
324inline
325void print_chosen_node(D_ParseNode* node, const core::parser_table& table)
326{
327 core::parse_node vi(node);
328 mCRL2log(log::verbose) << "CHOOSE " << table.tree(vi) << std::endl;
329}
330
332D_ParseNode* ambiguity_fn(struct D_Parser * /*p*/, int n, struct D_ParseNode **v)
333{
335
336 // resolve PbesExpr ambiguities
337 if (is_all_of_type(v, n, "PbesExpr", table))
338 {
339 D_ParseNode* result = nullptr;
340 for (int i = 0; i < n; i++)
341 {
342 core::parse_node node(v[i]);
343 if (table.symbol_name(node.child(0)) == "Id")
344 {
345 return v[i];
346 }
347 else if (table.symbol_name(node.child(0)) != "DataExpr")
348 {
349 result = v[i];
350 }
351 }
352 if (result)
353 {
354 return result;
355 }
356 return v[0];
357 }
358
359 // resolve ActFrm ambiguities
360 if (is_all_of_type(v, n, "ActFrm", table))
361 {
362//print_ambiguous_nodes(v, n, "ActFrm", table);
363 D_ParseNode* result = nullptr;
364 for (int i = 0; i < n; i++)
365 {
366 core::parse_node node(v[i]);
367 if (table.symbol_name(node.child(0)) == "MultAct")
368 {
369//print_chosen_node(v[i], table);
370 return v[i];
371 }
372 else if (table.symbol_name(node.child(0)) != "DataExpr")
373 {
374 result = v[i];
375 }
376 }
377 if (result)
378 {
379//print_chosen_node(result, table);
380 return result;
381 }
382//print_chosen_node(v[0], table);
383 return v[0];
384 }
385
386 // resolve StateFrm ambiguities
387 if (is_all_of_type(v, n, "StateFrm", table))
388 {
389//print_ambiguous_nodes(v, n, "StateFrm", table);
390 D_ParseNode* result = nullptr;
391 for (int i = 0; i < n; i++)
392 {
393 core::parse_node node(v[i]);
394 if (table.symbol_name(node.child(0)) == "Id")
395 {
396//print_chosen_node(v[i], table);
397 return v[i];
398 }
399 else if (table.symbol_name(node.child(0)) != "DataExpr")
400 {
401 result = v[i];
402 }
403 }
404 if (result)
405 {
406//print_chosen_node(result, table);
407 return result;
408 }
409//print_chosen_node(v[0], table);
410 return v[0];
411 }
412
413 // resolve RegFrm ambiguities
414 if (is_all_of_type(v, n, "RegFrm", table))
415 {
416//print_ambiguous_nodes(v, n, "RegFrm", table);
417 for (int i = 0; i < n; i++)
418 {
419 core::parse_node node(v[i]);
420 if (table.symbol_name(node.child(0)) == "RegFrm" || table.symbol_name(node.child(0)) == "(")
421 {
422//print_chosen_node(v[i], table);
423 return v[i];
424 }
425 }
426 }
427
428 // If we reach this point, then the ambiguity is unresolved. We print all
429 // ambiguities on the debug output, then throw an exception.
430 for (int i = 0; i < n; ++i)
431 {
432 core::parse_node vi(v[i]);
433 mCRL2log(log::verbose) << "Ambiguity: " << vi.tree() << std::endl;
434 mCRL2log(log::debug) << "Ambiguity: " << table.tree(vi) << std::endl;
435 }
436 throw mcrl2::runtime_error("Unresolved ambiguity.");
437}
438
439static void log_location(struct D_Parser *ap)
440{
441 // We recover information about the last parsed node by casting D_Parser to Parser, which
442 // is the structure that the dparser library internally uses to keep its administration in.
443 std::string after;
444 SNode *s = ((Parser*)ap)->snode_hash.last_all;
445 ZNode *z = s != nullptr ? s->zns.v[0] : nullptr;
446 while (z != nullptr && z->pn->parse_node.start_loc.s == z->pn->parse_node.end)
447 {
448 z = (z->sns.v && z->sns.v[0]->zns.v) ? z->sns.v[0]->zns.v[0] : nullptr;
449 }
450 if (z && z->pn->parse_node.start_loc.s != z->pn->parse_node.end)
451 {
452 after = std::string(z->pn->parse_node.start_loc.s, z->pn->parse_node.end);
453 }
454
455 std::string message = "syntax error";
456 if (!after.empty())
457 {
458 message = message + " after '" + after + "'";
459 }
460 mCRL2log(log::error) << add_context(&ap->loc, message) << std::endl;
461}
462
463void syntax_error_fn(struct D_Parser *ap)
464{
467 {
468 return;
469 }
470 log_location(ap);
471 if (ap->loc.s == nullptr)
472 {
473 mCRL2log(log::error) << "Unexpected end of input." << std::endl;
474 }
475 else
476 {
477 // Dive into the internals of dparser to recover some extra diagnostics.
478 Parser* p = (Parser*)ap;
479 if (p->pnode_hash.all && p->pnode_hash.all->latest)
480 {
481 core::parse_node n(&p->pnode_hash.all->latest->parse_node);
482 D_Symbol &s = p->t->symbols[n.symbol()];
483 if (s.kind == D_SYMBOL_INTERNAL)
484 {
485 /* DParser stores production rules in order: search for the corresponding nonterminal. */
486 int parentsym = n.symbol() - 1;
487 while (p->t->symbols[parentsym].kind == D_SYMBOL_INTERNAL)
488 --parentsym;
489 s = p->t->symbols[parentsym];
490 }
491
492 switch (s.kind)
493 {
494 case D_SYMBOL_STRING:
495 case D_SYMBOL_TOKEN:
496 {
497 std::locale loc;
498 mCRL2log(log::error) << "Unexpected "
499 << (std::isalpha(n.string()[0], loc) ? "keyword " : "")
500 << "'" << n.string() << "'" << std::endl;
501 }
502 break;
503 case D_SYMBOL_NTERM:
504 mCRL2log(log::error) << "Unexpected " << s.name << " '" << n.string() << "'" << std::endl;
505 break;
506 default:
507 // TODO: check if we can give more sensible output in the remaining cases.
508 break;
509 }
510 }
511 }
512}
513
514} // namespace detail
515
516void parser::custom_parse_error(const std::string& message) const
517{
520 {
521 return;
522 }
524 mCRL2log(log::error) << message << std::endl;
525}
526
527} // namespace core
528
529} // namespace mcrl2
530
Standard exception class for reporting runtime errors.
Definition exception.h:27
D_ParserTables parser_tables_mcrl2
D_ParserTables parser_tables_mcrl2
struct D_ParseNode *(* D_AmbiguityFn)(struct D_Parser *, int n, struct D_ParseNode **v)
Definition dparser.h:25
void(* D_SyntaxErrorFn)(struct D_Parser *)
Definition dparser.h:24
add your file description here.
#define mCRL2log(LEVEL)
mCRL2log(LEVEL) provides the stream used to log.
Definition logger.h:395
std::string add_context(const d_loc_t *loc, const std::string &message)
Definition dparser.cpp:277
static void log_location(struct D_Parser *ap)
Definition dparser.cpp:439
void syntax_error_fn(struct D_Parser *ap)
Custom syntax error function that prints both the line number and the column.
Definition dparser.cpp:463
bool is_all_of_type(D_ParseNode *nodes[], int n, const char *type, const core::parser_table &table)
Definition dparser.cpp:299
void increment_dparser_error_message_count()
Definition dparser.h:59
void set_dparser_max_error_message_count(std::size_t n)
Definition dparser.h:77
struct D_ParseNode * ambiguity_fn(struct D_Parser *, int, struct D_ParseNode **)
Function for resolving ambiguities in the '_ -> _ <> _' operator for process expressions.
Definition dparser.cpp:332
void print_chosen_node(D_ParseNode *node, const core::parser_table &table)
Definition dparser.cpp:325
void reset_dparser_error_message_count()
Definition dparser.h:53
std::size_t get_dparser_max_error_message_count()
Definition dparser.h:71
void print_ambiguous_nodes(D_ParseNode *nodes[], int n, const char *type, const core::parser_table &table)
Definition dparser.cpp:313
std::size_t get_dparser_error_message_count()
Definition dparser.h:65
@ verbose
Definition logger.h:35
A class that takes a linear process specification and checks all tau-summands of that LPS for conflue...
Definition indexed_set.h:72
Wrapper for D_ParseNode.
Definition dparser.h:86
parse_node child(int i) const
Definition dparser.cpp:43
int child_count() const
Definition dparser.cpp:37
D_ParseNode * node
Definition dparser.h:87
std::string pathname() const
Definition dparser.cpp:80
parse_node find_in_tree(int symbol) const
Definition dparser.cpp:48
std::string tree() const
Definition dparser.cpp:58
std::string add_context(const std::string &message) const
Definition dparser.cpp:27
std::string string() const
Definition dparser.cpp:53
Wrapper for D_ParserTables.
Definition dparser.h:117
D_ParserTables & m_table
Definition dparser.h:118
std::string symbol_name(unsigned int i) const
Definition dparser.cpp:115
std::string tree(const core::parse_node &node) const
Definition dparser.cpp:94
bool is_term_symbol(unsigned int i) const
Definition dparser.cpp:144
int start_symbol(unsigned int i) const
Definition dparser.cpp:138
unsigned int start_symbol_index(const std::string &name) const
Definition dparser.cpp:149
unsigned int symbol_count() const
Definition dparser.cpp:109
Wrapper for D_Parser and its corresponding D_ParserTables.
Definition dparser.h:148
parse_node parse(const std::string &text, unsigned int start_symbol_index=0, bool partial_parses=false)
Parses a string. N.B. The user is responsible for destruction of the returned value by calling destro...
Definition dparser.cpp:209
const parser_table & symbol_table() const
Definition dparser.cpp:199
void announce(D_ParseNode &node_ref)
Callback function for nodes in the parse tree.
Definition dparser.cpp:269
parser(D_ParserTables &tables, D_AmbiguityFn ambiguity_fn=nullptr, D_SyntaxErrorFn syntax_error_fn=nullptr, std::size_t max_error_message_count=1)
Definition dparser.cpp:174
void custom_parse_error(const std::string &message) const
Definition dparser.cpp:516
void print_symbol_table() const
Definition dparser.cpp:225
D_Parser * m_parser
Definition dparser.h:150
std::string indent(unsigned int count) const
Definition dparser.cpp:230
std::string truncate(const std::string &s, unsigned int max_size=20) const
Definition dparser.cpp:235
parser_table m_table
Definition dparser.h:149
void print_tree(const parse_node &node, unsigned int level=0) const
Definition dparser.cpp:249
unsigned int start_symbol_index(const std::string &name) const
Definition dparser.cpp:204
void destroy_parse_node(const parse_node &node)
Definition dparser.cpp:263