Skip to content

Commit 7ba76bb

Browse files
noob77777noob77777
authored
Removed: using Entity (#14)
1 parent 832e82a commit 7ba76bb

File tree

8 files changed

+51
-38
lines changed

8 files changed

+51
-38
lines changed

‎src/grammar/grammar.cpp‎

Lines changed: 6 additions & 4 deletions
Original file line numberDiff line numberDiff line change
@@ -260,16 +260,18 @@ std::string Rule::ToString() const {
260260
return ss.str();
261261
}
262262

263-
bool Rule::HasPrefix(const Entity &prefix) const {
263+
bool Rule::HasPrefix(const Rule &prefix) const {
264264
// Takes care of even EPSILON too.
265-
if (prefix.size() > entities_.size()) {
265+
if (prefix.GetEntities().size() > entities_.size()) {
266266
return false;
267267
}
268-
for (int i = 0; i < static_cast<int>(prefix.size()); i++) {
269-
if (entities_[i] != prefix[i]) {
268+
269+
for (int i = 0; i < static_cast<int>(prefix.GetEntities().size()); i++) {
270+
if (entities_[i] != prefix.GetEntities()[i]) {
270271
return false;
271272
}
272273
}
274+
273275
return true;
274276
}
275277

‎src/include/grammar/grammar.h‎

Lines changed: 6 additions & 7 deletions
Original file line numberDiff line numberDiff line change
@@ -9,7 +9,6 @@
99
namespace jucc {
1010
namespace grammar {
1111
const char EPSILON[] = "EPSILON";
12-
using Entity = std::vector<std::string>;
1312

1413
class Rule {
1514
/**
@@ -18,21 +17,21 @@ class Rule {
1817
* Example:
1918
* For production: E : F + E => { "F", "+", "E" } is a rule.
2019
*/
21-
Entity entities_;
20+
std::vector<std::string> entities_;
2221

2322
public:
2423
Rule() = default;
25-
explicit Rule(Entity entities) : entities_(std::move(entities)) {}
26-
[[nodiscard]] const Entity &GetEntities() const { return entities_; }
27-
void SetEntities(const Entity &entities) { Rule::entities_ = entities; }
24+
explicit Rule(std::vector<std::string> entities) : entities_(std::move(entities)) {}
25+
[[nodiscard]] const std::vector<std::string> &GetEntities() const { return entities_; }
26+
void SetEntities(const std::vector<std::string> &entities) { Rule::entities_ = entities; }
2827
[[nodiscard]] std::string ToString() const;
2928

3029
/**
31-
* Takes an Entity and checks if the entries of the Entity is a perfect
30+
* Takes an Rule and checks if the entries of the Rule is a perfect
3231
* prefix of the this->entities_ or not.
3332
* @return a boolean after checking if param is actually a prefix or not.
3433
*/
35-
[[nodiscard]] bool HasPrefix(const Entity & /*prefix*/) const;
34+
[[nodiscard]] bool HasPrefix(const Rule & /*prefix*/) const;
3635
};
3736

3837
using Rules = std::vector<grammar::Rule>;

‎src/include/symbol_table/symbol_table.h‎

Lines changed: 10 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -16,11 +16,13 @@ struct Node {
1616
* obtained during tokenization
1717
*/
1818
std::string identifier_;
19+
1920
/**
2021
* Used to store the data type of the identifier
2122
* One of int or float
2223
*/
2324
std::string data_type_;
25+
2426
/**
2527
* Used to store the nesting level of scoping
2628
* Deeper the nesting, higher the scope
@@ -41,10 +43,12 @@ struct Node {
4143
* a0_ has 0 level , a1_ has 1 level and so on ...
4244
*/
4345
int nesting_level_;
46+
4447
/**
4548
* The pointer to the next node.
4649
*/
4750
Node *next_;
51+
4852
/**
4953
* Constructor for node class
5054
*/
@@ -60,22 +64,27 @@ class LinkedList {
6064

6165
public:
6266
LinkedList() = default;
67+
6368
/**
6469
* Allocates memory for a new Node and returns it after initializing.
6570
*/
6671
static Node *CreateNewNode(std::string it_, std::string dt_, int nt_);
72+
6773
/**
6874
* Adds a new node at the starting of the linked list
6975
*/
7076
void AddNewNode(std::string it_, std::string dt_, int nt_);
77+
7178
/**
7279
* Deletes the first node of the linked list
7380
*/
7481
void DeleteStartingNode();
82+
7583
/**
7684
* Returns true if linked list is empty or vice-versa
7785
*/
7886
bool IsEmpty();
87+
7988
/**
8089
* returns head_
8190
*/
@@ -88,6 +97,7 @@ class SymbolTable {
8897
* in different nesting levels in the program
8998
*/
9099
std::unordered_map<std::string, LinkedList> hash_table_;
100+
91101
/**
92102
* A vector to store different duplicate symbols found in the input
93103
*/

‎src/include/utils/left_factoring.h‎

Lines changed: 2 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -12,9 +12,9 @@ grammar::Productions RemoveLeftFactors(const grammar::Production & /*prod*/);
1212

1313
/**
1414
* Finds longest prefix which is most common to the rules of the productions.
15-
* @return a grammar Entity which can be used as a core of grammar::Rule.
15+
* @return a grammar Rule which can be used as a core of grammar::Rule.
1616
*/
17-
grammar::Entity LongestCommonPrefix(const grammar::Production & /*prod*/);
17+
grammar::Rule LongestCommonPrefix(const grammar::Production & /*prod*/);
1818

1919
} // namespace jucc::utils
2020

‎src/include/utils/trie/memory_efficient_trie.h‎

Lines changed: 6 additions & 6 deletions
Original file line numberDiff line numberDiff line change
@@ -19,8 +19,8 @@ class Trie {
1919
// Creates a trie for set of Rules where each entity is used as a key.
2020
std::unordered_map<std::string, Trie *> nodes_;
2121

22-
grammar::Entity keys_list_; // Stores the prefix list of entities upto the current entity.
23-
int count_; // Number of occurrences of the current entity after insertion of a set of Rules.
22+
std::vector<std::string> keys_list_; // Stores the prefix list of entities upto the current entity.
23+
int count_; // Number of occurrences of the current entity after insertion of a set of Rules.
2424

2525
Trie();
2626
};
@@ -51,10 +51,10 @@ class TrieManager {
5151
[[nodiscard]] Trie *GetMaster() const;
5252

5353
/**
54-
* Insert a particular grammar Entity into the master_.
55-
* @param grammar::Entity &
54+
* Insert a particular grammar Rule into the master_.
55+
* @param grammar::Rule &
5656
*/
57-
void Insert(const grammar::Entity & /*entities*/);
57+
void Insert(const grammar::Rule & /*rule*/);
5858

5959
/**
6060
* Insert a whole production into the trie node master_.
@@ -67,7 +67,7 @@ class TrieManager {
6767
* Rule entities.
6868
*/
6969
// NOLINTNEXTLINE
70-
static void GreedyPreorder(Trie * /*head*/, int & /*len*/, grammar::Entity & /*max_str*/, bool /*is_prime_head*/);
70+
static void GreedyPreorder(Trie * /*head*/, int & /*len*/, grammar::Rule & /*max_str*/, bool /*is_prime_head*/);
7171

7272
/**
7373
* Virtual Destructor performs garbage collection where created memory gets released.

‎src/utils/left_factoring.cpp‎

Lines changed: 12 additions & 9 deletions
Original file line numberDiff line numberDiff line change
@@ -13,7 +13,7 @@ grammar::Productions RemoveLeftFactors(const grammar::Production &prod) {
1313
bool state_not_updated = false;
1414
auto current_prod = prod;
1515
while (!state_not_updated) {
16-
auto max_common_prefix = utils::LongestCommonPrefix(current_prod);
16+
auto max_common_prefix = utils::LongestCommonPrefix(current_prod).GetEntities();
1717
if (max_common_prefix.empty()) {
1818
state_not_updated = true;
1919
continue;
@@ -26,29 +26,31 @@ grammar::Productions RemoveLeftFactors(const grammar::Production &prod) {
2626
grammar::Rules parent_dash_rules;
2727

2828
// insert the commonE' prod
29-
grammar::Entity common_factor_with_dash(max_common_prefix.begin(), max_common_prefix.end());
29+
std::vector<std::string> common_factor_with_dash(max_common_prefix.begin(), max_common_prefix.end());
3030
// push E' after the common part
3131
common_factor_with_dash.emplace_back(parent_dash);
3232
parent_rules.emplace_back(grammar::Rule(common_factor_with_dash));
3333

3434
bool has_epsilon_inserted = false;
3535
// produce two production after matching
3636
for (const auto &rule : current_prod.GetRules()) {
37-
if (!rule.HasPrefix(max_common_prefix)) {
37+
if (!rule.HasPrefix(grammar::Rule(max_common_prefix))) {
3838
parent_rules.emplace_back(rule);
3939
} else {
40-
auto new_entities = grammar::Entity(rule.GetEntities().begin() + static_cast<int>(max_common_prefix.size()),
41-
rule.GetEntities().end());
40+
auto new_entities = std::vector<std::string>(
41+
rule.GetEntities().begin() + static_cast<int>(max_common_prefix.size()), rule.GetEntities().end());
4242
if (new_entities.empty()) {
4343
has_epsilon_inserted = true;
4444
new_entities.emplace_back(std::string(grammar::EPSILON));
4545
}
46-
parent_dash_rules.push_back(grammar::Rule(new_entities));
46+
parent_dash_rules.emplace_back(new_entities);
4747
}
4848
}
49+
4950
if (!has_epsilon_inserted) {
50-
parent_dash_rules.emplace_back(grammar::Entity{std::string(grammar::EPSILON)});
51+
parent_dash_rules.emplace_back(std::vector<std::string>{std::string(grammar::EPSILON)});
5152
}
53+
5254
// do this recursive
5355
prods.push_back(grammar::Production(parent, parent_rules));
5456
current_prod = grammar::Production(parent_dash, parent_dash_rules);
@@ -57,10 +59,11 @@ grammar::Productions RemoveLeftFactors(const grammar::Production &prod) {
5759
return prods;
5860
}
5961

60-
grammar::Entity LongestCommonPrefix(const grammar::Production &prod) {
62+
grammar::Rule LongestCommonPrefix(const grammar::Production &prod) {
6163
TrieManager trie_manager;
6264
trie_manager.InsertAll(prod);
63-
grammar::Entity common_prefixes;
65+
66+
grammar::Rule common_prefixes;
6467
int len = 1;
6568
TrieManager::GreedyPreorder(trie_manager.GetMaster(), len, common_prefixes, true);
6669

‎src/utils/trie/memory_efficient_trie.cpp‎

Lines changed: 6 additions & 6 deletions
Original file line numberDiff line numberDiff line change
@@ -6,10 +6,10 @@ Trie::Trie() { count_ = 0; }
66

77
TrieManager::TrieManager() { master_ = NewTrieNode(); }
88

9-
void TrieManager::Insert(const grammar::Entity &entities) {
9+
void TrieManager::Insert(const grammar::Rule &rule) {
1010
auto *head = master_;
11-
grammar::Entity till_keys;
12-
for (const auto &entity : entities) {
11+
std::vector<std::string> till_keys;
12+
for (const auto &entity : rule.GetEntities()) {
1313
till_keys.push_back(entity);
1414
if (head->nodes_.find(entity) == head->nodes_.end()) {
1515
head->nodes_[entity] = NewTrieNode();
@@ -22,11 +22,11 @@ void TrieManager::Insert(const grammar::Entity &entities) {
2222

2323
void TrieManager::InsertAll(const grammar::Production &prod) {
2424
for (const auto &rule : prod.GetRules()) {
25-
Insert(rule.GetEntities());
25+
Insert(rule);
2626
}
2727
}
2828

29-
void TrieManager::GreedyPreorder(Trie *head, int &len, grammar::Entity &max_str, bool is_prime_head) {
29+
void TrieManager::GreedyPreorder(Trie *head, int &len, grammar::Rule &max_str, bool is_prime_head) {
3030
if (head == nullptr) {
3131
return;
3232
}
@@ -35,7 +35,7 @@ void TrieManager::GreedyPreorder(Trie *head, int &len, grammar::Entity &max_str,
3535
if (head->count_ >= len && head->count_ != 1) {
3636
len = head->count_;
3737
state_changed = true;
38-
max_str = head->keys_list_;
38+
max_str.SetEntities(head->keys_list_);
3939
}
4040

4141
if (state_changed || is_prime_head) {

‎test/utils/trie/trie_test.cpp‎

Lines changed: 3 additions & 4 deletions
Original file line numberDiff line numberDiff line change
@@ -17,9 +17,8 @@ TEST(trie, trie1) {
1717
jucc::utils::TrieManager tm;
1818
tm.InsertAll(p);
1919

20-
grammar::Entity ent;
20+
grammar::Rule rule;
2121
int len = 1;
22-
jucc::utils::TrieManager::GreedyPreorder(tm.GetMaster(), len, ent, true);
23-
auto rule1 = grammar::Rule(ent);
24-
ASSERT_EQ(rule1.ToString(), "ieS");
22+
jucc::utils::TrieManager::GreedyPreorder(tm.GetMaster(), len, rule, true);
23+
ASSERT_EQ(rule.ToString(), "ieS");
2524
}

0 commit comments

Comments
 (0)