Spicy
grammar.h
1 // Copyright (c) 2020-2021 by the Zeek Project. See LICENSE for details.
2 
3 #pragma once
4 
5 #include <map>
6 #include <set>
7 #include <string>
8 #include <utility>
9 #include <vector>
10 
11 #include <spicy/compiler/detail/codegen/production.h>
12 
13 namespace spicy::detail::codegen {
14 
15 namespace production {
16 class Resolved;
17 using Unresolved = Resolved;
18 } // namespace production
19 
21 class Grammar {
22 public:
32  Grammar(std::string name, Location l = location::None) : _name(std::move(name)), _location(std::move(l)) {}
33  Grammar() = default;
34  Grammar(const Grammar&) = default;
35  Grammar(Grammar&&) = default;
36  ~Grammar() = default;
37  Grammar& operator=(Grammar&&) = default;
38  Grammar& operator=(const Grammar&) = default;
39 
44  const std::string& name() const { return _name; }
45 
47  const Location& location() const { return _location; }
48 
54  void resolve(production::Unresolved* r, Production p);
55 
57  const Production& resolved(const production::Resolved& r) const;
58 
64  Result<Nothing> setRoot(const Production& p);
65 
75  Result<Nothing> finalize();
76 
78  std::optional<Production> root() const {
79  if ( _root )
80  return _prods.at(*_root);
81 
82  return {};
83  }
84 
92  const std::map<std::string, Production>& productions() const { return _prods; }
93 
105  hilti::Result<std::set<Production>> lookAheadsForProduction(Production p,
106  std::optional<Production> parent = {}) const;
107 
112  bool needsLookAhead() const { return _needs_look_ahead; }
113 
119  void printTables(std::ostream& out, bool verbose = false);
120 
121 private:
122  void _addProduction(const Production& p);
123  void _simplify();
124  Result<Nothing> _computeTables();
125  Result<Nothing> _check();
126  std::set<Production> _computeClosure(const Production& p);
127  bool _add(std::map<std::string, std::set<std::string>>* tbl, const Production& dst,
128  const std::set<std::string>& src, bool changed);
129  bool _isNullable(const Production& p) const;
130  bool _isNullable(std::vector<Production>::const_iterator i, std::vector<Production>::const_iterator j) const;
131  std::set<std::string> _getFirst(const Production& p) const;
132  std::set<std::string> _getFirstOfRhs(const std::vector<Production>& rhs) const;
133  std::string _productionLocation(const Production& p) const;
134  std::vector<std::vector<Production>> _rhss(const Production& p) const;
135 
136  std::string _name;
137  Location _location;
138  std::optional<std::string> _root;
139 
140  // Computed by _computeTables()
141  bool _needs_look_ahead = false;
142  std::map<std::string, Production> _prods;
143  std::map<std::string, std::string> _resolved;
144  std::vector<std::string> _nterms;
145  std::map<std::string, bool> _nullable;
146  std::map<std::string, std::set<std::string>> _first;
147  std::map<std::string, std::set<std::string>> _follow;
148 };
149 
150 } // namespace spicy::detail::codegen
const Location & location() const
Definition: grammar.h:47
Definition: production.h:120
Definition: optional.h:79
bool needsLookAhead() const
Definition: grammar.h:112
const std::string & name() const
Definition: grammar.h:44
Grammar(std::string name, Location l=location::None)
Definition: grammar.h:32
Definition: unit.h:28
const std::map< std::string, Production > & productions() const
Definition: grammar.h:92
Definition: location.h:17
Definition: grammar.h:21
std::optional< Production > root() const
Definition: grammar.h:78
Definition: result.h:67