Teuchos - Trilinos Tools Package  Version of the Day
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
Teuchos_Grammar.cpp
1 #include "Teuchos_Grammar.hpp"
2 
3 #include <Teuchos_Assert.hpp>
4 #include <set>
5 #include <iostream>
6 
7 #include "Teuchos_vector.hpp"
8 #include "Teuchos_Parser.hpp"
9 
10 namespace Teuchos {
11 
12 int get_nnonterminals(Grammar const& g) {
13  return g.nsymbols - g.nterminals;
14 }
15 
16 bool is_terminal(Grammar const& g, int symbol) {
17  TEUCHOS_DEBUG_ASSERT(0 <= symbol);
18  TEUCHOS_DEBUG_ASSERT(symbol <= g.nsymbols);
19  return symbol < g.nterminals;
20 }
21 
22 bool is_nonterminal(Grammar const& g, int symbol) {
23  return !is_terminal(g, symbol);
24 }
25 
26 int as_nonterminal(Grammar const& g, int symbol) {
27  return symbol - g.nterminals;
28 }
29 
30 int find_goal_symbol(Grammar const& g) {
31  std::set<int> nonterminals_in_rhss;
32  for (int i = 0; i < Teuchos::size(g.productions); ++i) {
33  const Grammar::Production& p = at(g.productions, i);
34  for (int j = 0; j < Teuchos::size(p.rhs); ++j) {
35  const int s = at(p.rhs, j);
36  TEUCHOS_DEBUG_ASSERT(0 <= s);
37  if (is_nonterminal(g, s)) nonterminals_in_rhss.insert(s);
38  }
39  }
40  int result = -1;
41  for (int s = g.nterminals; s < g.nsymbols; ++s) {
42  if (!nonterminals_in_rhss.count(s)) {
43  TEUCHOS_TEST_FOR_EXCEPTION(result != -1, ParserFail,
44  "ERROR: there is more than one root nonterminal ("
45  << at(g.symbol_names, result) << " [" << result << "] and "
46  << at(g.symbol_names, s) << " [" << s << "]) in this grammar\n");
47  result = s;
48  }
49  }
50  TEUCHOS_TEST_FOR_EXCEPTION(result == -1, ParserFail,
51  "ERROR: the root nonterminal is unclear for this grammar\n"
52  "usually this means all nonterminals appear in the RHS of a production\n"
53  "and can be fixed by adding a new nonterminal root2, root2 -> root\n");
54  return result;
55 }
56 
57 void add_end_terminal(Grammar& g) {
58  for (int i = 0; i < Teuchos::size(g.productions); ++i) {
59  Grammar::Production& prod = at(g.productions, i);
60  if (is_nonterminal(g, prod.lhs)) prod.lhs++;
61  for (int j = 0; j < Teuchos::size(prod.rhs); ++j) {
62  int& rhs_symb = at(prod.rhs, j);
63  if (is_nonterminal(g, rhs_symb)) rhs_symb++;
64  }
65  }
66  g.symbol_names.insert(g.symbol_names.begin() + g.nterminals, "EOF");
67  g.nterminals++;
68  g.nsymbols++;
69 }
70 
71 int get_end_terminal(Grammar const& g) {
72  return g.nterminals - 1;
73 }
74 
75 void add_accept_production(Grammar& g) {
76  int goal_symbol = find_goal_symbol(g);
77  Grammar::Production p;
78  p.lhs = g.nsymbols;
79  p.rhs.push_back(goal_symbol);
80  g.productions.push_back(p);
81  g.symbol_names.push_back("ACCEPT");
82  g.nsymbols++;
83 }
84 
85 int get_accept_production(Grammar const& g) {
86  return Teuchos::size(g.productions) - 1;
87 }
88 
89 int get_accept_nonterminal(Grammar const& g) {
90  return g.nsymbols - 1;
91 }
92 
93 std::ostream& operator<<(std::ostream& os, Grammar const& g) {
94  os << "symbols:\n";
95  for (int i = 0; i < Teuchos::size(g.symbol_names); ++i) {
96  os << i << ": " << at(g.symbol_names, i) << "\n";
97  }
98  os << "productions:\n";
99  for (int i = 0; i < Teuchos::size(g.productions); ++i) {
100  const Grammar::Production& prod = at(g.productions, i);
101  os << i << ": " << prod.lhs << " ::=";
102  for (int j = 0; j < Teuchos::size(prod.rhs); ++j) {
103  int symb = at(prod.rhs, j);
104  os << ' ' << symb;
105  }
106  os << '\n';
107  }
108  os << '\n';
109  return os;
110 }
111 
112 }
#define TEUCHOS_TEST_FOR_EXCEPTION(throw_exception_test, Exception, msg)
Macro for throwing an exception with breakpointing to ease debugging.
Declares Teuchos::Parser, ParserFail and make_lalr1_parser.