Teuchos - Trilinos Tools Package  Version of the Day
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
Teuchos_Language.cpp
1 #include "Teuchos_Language.hpp"
2 
3 #include <set>
4 #include <iostream>
5 #include <sstream>
6 #include <cstdlib>
7 #include <cstdarg>
8 
9 #include "Teuchos_vector.hpp"
10 #include "Teuchos_regex.hpp"
11 #include "Teuchos_Parser.hpp"
12 
13 namespace Teuchos {
14 
15 void Language::Token::operator()(std::string const& name_in, std::string const& regex_in) {
16  name = name_in;
17  regex = regex_in;
18 }
19 
20 Language::RHSBuilder::RHSBuilder(Production& prod_in):
21  prod(prod_in) {
22 }
23 
24 Language::RHSBuilder& Language::RHSBuilder::operator,(std::string const& rhs_item) {
25  prod.rhs.push_back(rhs_item);
26  return *this;
27 }
28 
29 Language::RHSBuilder& Language::RHSBuilder::operator>>(std::string const& rhs_item) {
30  prod.rhs.push_back(rhs_item);
31  return *this;
32 }
33 
34 Language::RHSBuilder Language::Production::operator()(std::string const& lhs_in) {
35  lhs = lhs_in;
36  return Language::RHSBuilder(*this);
37 }
38 
39 GrammarPtr make_grammar(Language const& language) {
40  std::map<std::string, int> symbol_map;
41  int nterminals = 0;
42  for (Language::Tokens::const_iterator it = language.tokens.begin();
43  it != language.tokens.end(); ++it) {
44  const Language::Token& token = *it;
45  TEUCHOS_TEST_FOR_EXCEPTION(token.name.empty(), ParserFail,
46  "ERROR: token " << it - language.tokens.begin() << " has an empty name\n");
47  symbol_map[token.name] = nterminals++;
48  }
49  int nsymbols = nterminals;
50  for (Language::Productions::const_iterator it = language.productions.begin();
51  it != language.productions.end(); ++it) {
52  const Language::Production& production = *it;
53  TEUCHOS_TEST_FOR_EXCEPTION(production.lhs.empty(), ParserFail,
54  "ERROR: production " << it - language.productions.begin() << " has an empty LHS name\n");
55  if (symbol_map.count(production.lhs)) continue;
56  symbol_map[production.lhs] = nsymbols++;
57  }
58  RCP<Grammar> out(new Grammar());
59  out->nsymbols = nsymbols;
60  out->nterminals = nterminals;
61  for (Language::Productions::const_iterator it = language.productions.begin();
62  it != language.productions.end(); ++it) {
63  const Language::Production& lang_prod = *it;
64  out->productions.push_back(Grammar::Production());
65  Grammar::Production& gprod = out->productions.back();
66  TEUCHOS_ASSERT(symbol_map.count(lang_prod.lhs));
67  gprod.lhs = symbol_map[lang_prod.lhs];
68  for (Language::RHS::const_iterator it2 = lang_prod.rhs.begin();
69  it2 != lang_prod.rhs.end(); ++it2) {
70  const std::string& lang_symb = *it2;
71  TEUCHOS_TEST_FOR_EXCEPTION(!symbol_map.count(lang_symb), ParserFail,
72  "RHS entry \"" << lang_symb <<
73  "\" is neither a nonterminal (LHS of a production) nor a token!\n");
74  gprod.rhs.push_back(symbol_map[lang_symb]);
75  }
76  }
77  out->symbol_names = make_vector<std::string>(nsymbols);
78  for (std::map<std::string, int>::const_iterator it = symbol_map.begin();
79  it != symbol_map.end(); ++it) {
80  const std::pair<std::string, int>& pair = *it;
81  at(out->symbol_names, pair.second) = pair.first;
82  }
83  add_end_terminal(*out);
84  add_accept_production(*out);
85  return out;
86 }
87 
88 std::ostream& operator<<(std::ostream& os, Language const& lang) {
89  for (Language::Tokens::const_iterator it = lang.tokens.begin();
90  it != lang.tokens.end(); ++it) {
91  const Language::Token& token = *it;
92  os << "token " << token.name << " regex \'" << token.regex << "\'\n";
93  }
94  std::set<std::string> nonterminal_set;
95  std::vector<std::string> nonterminal_list;
96  for (Language::Productions::const_iterator it = lang.productions.begin();
97  it != lang.productions.end(); ++it) {
98  const Language::Production& prod = *it;
99  if (!nonterminal_set.count(prod.lhs)) {
100  nonterminal_set.insert(prod.lhs);
101  nonterminal_list.push_back(prod.lhs);
102  }
103  }
104  for (std::vector<std::string>::const_iterator it = nonterminal_list.begin();
105  it != nonterminal_list.end(); ++it) {
106  const std::string& nonterminal = *it;
107  std::stringstream ss;
108  ss << nonterminal << " ::=";
109  std::string lead = ss.str();
110  os << lead;
111  for (std::string::iterator it2 = lead.begin(); it2 != lead.end(); ++it2) {
112  *it2 = ' ';
113  }
114  bool first = true;
115  for (Language::Productions::const_iterator it2 = lang.productions.begin();
116  it2 != lang.productions.end(); ++it2) {
117  const Language::Production& prod = *it2;
118  if (prod.lhs != nonterminal) continue;
119  if (first) first = false;
120  else os << " |\n" << lead;
121  for (Language::RHS::const_iterator it3 = prod.rhs.begin();
122  it3 != prod.rhs.end(); ++it3) {
123  const std::string& symb = *it3;
124  if (symb == "|") os << " '|'";
125  else os << " " << symb;
126  }
127  }
128  os << "\n";
129  }
130  os << "\n";
131  return os;
132 }
133 
134 void make_lexer(FiniteAutomaton& result, Language const& language) {
135  using std::swap;
136  for (int i = 0; i < Teuchos::size(language.tokens); ++i) {
137  const std::string& name = at(language.tokens, i).name;
138  const std::string& regex = at(language.tokens, i).regex;
139  if (i == 0) {
140  regex::make_dfa(result, name, regex, i);
141  } else {
142  FiniteAutomaton b;
143  regex::make_dfa(b, name, regex, i);
144  unite(result, result, b);
145  }
146  }
147  make_deterministic(result, result);
148  simplify(result, result);
149 }
150 
151 static void make_indent_info(IndentInfo& out, Language const& language) {
152  out.is_sensitive = false;
153  out.indent_token = -1;
154  out.dedent_token = -1;
155  out.newline_token = -1;
156  for (int tok_i = 0; tok_i < Teuchos::size(language.tokens); ++tok_i) {
157  const Language::Token& token = at(language.tokens, tok_i);
158  if (token.name == "INDENT") {
159  TEUCHOS_TEST_FOR_EXCEPTION(out.indent_token != -1, ParserFail,
160  "error: Language has two or more INDENT tokens\n");
161  out.indent_token = tok_i;
162  out.is_sensitive = true;
163  } else if (token.name == "DEDENT") {
164  TEUCHOS_TEST_FOR_EXCEPTION(out.dedent_token != -1, ParserFail,
165  "error: Language has two or more DEDENT tokens\n");
166  out.dedent_token = tok_i;
167  } else if (token.name == "NEWLINE") {
168  TEUCHOS_TEST_FOR_EXCEPTION(out.newline_token != -1, ParserFail,
169  "error: Language has two or more NEWLINE tokens\n");
170  out.newline_token = tok_i;
171  }
172  }
173  TEUCHOS_TEST_FOR_EXCEPTION(out.is_sensitive && out.indent_token == -1,
174  ParserFail,
175  "error: Indentation-sensitive language has no INDENT token\n");
176  TEUCHOS_TEST_FOR_EXCEPTION(out.is_sensitive && out.dedent_token == -1,
177  ParserFail,
178  "error: Indentation-sensitive language has no DEDENT token\n");
179  TEUCHOS_TEST_FOR_EXCEPTION(out.is_sensitive && out.newline_token == -1,
180  ParserFail,
181  "error: Indentation-sensitive language has no NEWLINE token\n");
183  (out.indent_token < out.newline_token ||
184  out.dedent_token < out.newline_token),
185  ParserFail,
186  "error: NEWLINE needs to come before all other indent tokens\n");
187 }
188 
190  RCP<ReaderTables> out(new ReaderTables());
191  make_lexer(out->lexer, language);
192  make_indent_info(out->indent_info, language);
193  GrammarPtr grammar = make_grammar(language);
194  out->parser = make_lalr1_parser(grammar);
195  return out;
196 }
197 
198 }
Parser make_lalr1_parser(GrammarPtr grammar, bool verbose)
Tries to create LALR(1) parser tables for a given grammar.
#define TEUCHOS_TEST_FOR_EXCEPTION(throw_exception_test, Exception, msg)
Macro for throwing an exception with breakpointing to ease debugging.
FiniteAutomaton lexer
lexer.
Declares Teuchos::Parser, ParserFail and make_lalr1_parser.
The main class for users to define a language using TeuchosParser.
void make_lexer(FiniteAutomaton &result, Language const &language)
construct a lexer for the Language tokens.
Parser and lexer tables specifying how to read a Language.
Tokens tokens
vector of tokens
ReaderTablesPtr make_reader_tables(Language const &language)
constructs ReaderTables for the given Language.
#define TEUCHOS_ASSERT(assertion_test)
This macro is throws when an assert fails.
Declares Teuchos::Language.