Skip to content

Commit 9b8fc47

Browse files
bisakhmondalbisakhmondal
authored
left-factoring update (#49)
1 parent d948bdd commit 9b8fc47

File tree

2 files changed

+34
-15
lines changed

2 files changed

+34
-15
lines changed

‎src/utils/left_factoring.cpp‎

Lines changed: 0 additions & 6 deletions
Original file line numberDiff line numberDiff line change
@@ -31,7 +31,6 @@ grammar::Productions RemoveLeftFactors(const grammar::Production &prod) {
3131
common_factor_with_dash.emplace_back(parent_dash);
3232
parent_rules.emplace_back(grammar::Rule(common_factor_with_dash));
3333

34-
bool has_epsilon_inserted = false;
3534
// produce two production after matching
3635
for (const auto &rule : current_prod.GetRules()) {
3736
if (!rule.HasPrefix(grammar::Rule(max_common_prefix))) {
@@ -40,17 +39,12 @@ grammar::Productions RemoveLeftFactors(const grammar::Production &prod) {
4039
auto new_entities = std::vector<std::string>(
4140
rule.GetEntities().begin() + static_cast<int>(max_common_prefix.size()), rule.GetEntities().end());
4241
if (new_entities.empty()) {
43-
has_epsilon_inserted = true;
4442
new_entities.emplace_back(std::string(grammar::EPSILON));
4543
}
4644
parent_dash_rules.emplace_back(new_entities);
4745
}
4846
}
4947

50-
if (!has_epsilon_inserted) {
51-
parent_dash_rules.emplace_back(std::vector<std::string>{std::string(grammar::EPSILON)});
52-
}
53-
5448
// do this recursive
5549
prods.push_back(grammar::Production(parent, parent_rules));
5650
current_prod = grammar::Production(parent_dash, parent_dash_rules);

‎test/utils/utils_test.cpp‎

Lines changed: 34 additions & 9 deletions
Original file line numberDiff line numberDiff line change
@@ -108,23 +108,49 @@ TEST(utils, LeftFactoring0) {
108108
ASSERT_EQ(lf_removed.size(), 2);
109109
// output
110110
// E -> ieStE' | a | b |
111-
// E' -> St | P | epsilon
111+
// E' -> St | P
112112
ASSERT_EQ(lf_removed[0].GetParent(), "E");
113113
ASSERT_EQ(lf_removed[1].GetParent(), "E" + std::string(utils::DASH));
114114

115115
ASSERT_EQ(lf_removed[0].GetRules().size(), 3);
116-
ASSERT_EQ(lf_removed[1].GetRules().size(), 3);
116+
ASSERT_EQ(lf_removed[1].GetRules().size(), 2);
117117

118118
ASSERT_EQ(lf_removed[0].GetRules()[0].ToString(), "ieStE'");
119119
ASSERT_EQ(lf_removed[0].GetRules()[1].ToString(), "a");
120120
ASSERT_EQ(lf_removed[0].GetRules()[2].ToString(), "b");
121121

122122
ASSERT_EQ(lf_removed[1].GetRules()[0].ToString(), "St");
123123
ASSERT_EQ(lf_removed[1].GetRules()[1].ToString(), "P");
124-
ASSERT_EQ(lf_removed[1].GetRules()[2].ToString(), std::string(grammar::EPSILON));
125124
}
126125

127126
TEST(utils, LeftFactoring1) {
127+
// E -> ieStSt | a | b | ieSt
128+
grammar::Production p;
129+
p.SetParent("E");
130+
p.SetRules({grammar::Rule({"i", "e", "S", "t", "S", "t"}), grammar::Rule({"a"}), grammar::Rule({"b"}),
131+
grammar::Rule({"i", "e", "S", "t"})});
132+
133+
auto lf_removed = utils::RemoveLeftFactors(p);
134+
135+
ASSERT_EQ(lf_removed.size(), 2);
136+
// output
137+
// E -> ieStE' | a | b |
138+
// E' -> St | epsilon
139+
ASSERT_EQ(lf_removed[0].GetParent(), "E");
140+
ASSERT_EQ(lf_removed[1].GetParent(), "E" + std::string(utils::DASH));
141+
142+
ASSERT_EQ(lf_removed[0].GetRules().size(), 3);
143+
ASSERT_EQ(lf_removed[1].GetRules().size(), 2);
144+
145+
ASSERT_EQ(lf_removed[0].GetRules()[0].ToString(), "ieStE'");
146+
ASSERT_EQ(lf_removed[0].GetRules()[1].ToString(), "a");
147+
ASSERT_EQ(lf_removed[0].GetRules()[2].ToString(), "b");
148+
149+
ASSERT_EQ(lf_removed[1].GetRules()[0].ToString(), "St");
150+
ASSERT_EQ(lf_removed[1].GetRules()[1].ToString(), std::string(grammar::EPSILON));
151+
}
152+
153+
TEST(utils, LeftFactoring2) {
128154
// E -> ieStSt | a | b
129155
grammar::Production p;
130156
p.SetParent("E");
@@ -603,33 +629,32 @@ TEST(utils, CalcFollows2) {
603629
}
604630

605631
TEST(utils, RemoveAllAmbiguity0) {
606-
// E -> ieStSt | a | b | ieStP
632+
// E -> ieStSt | a | b | ieSt
607633
grammar::Production p;
608634
p.SetParent("E");
609635
p.SetRules({grammar::Rule({"i", "e", "S", "t", "S", "t"}), grammar::Rule({"a"}), grammar::Rule({"b"}),
610-
grammar::Rule({"i", "e", "S", "t", "P"})});
636+
grammar::Rule({"i", "e", "S", "t"})});
611637

612638
auto lf_removed = utils::RemoveAllPossibleAmbiguity({p});
613639
auto non_terminals = utils::GetAllNonTerminals(lf_removed);
614640

615641
ASSERT_EQ(lf_removed.size(), 2);
616642
// output
617643
// E -> ieStE' | a | b |
618-
// E' -> St | P | epsilon
644+
// E' -> St | epsilon
619645
ASSERT_EQ(non_terminals.size(), 2);
620646
ASSERT_EQ(non_terminals[0], "E");
621647
ASSERT_EQ(non_terminals[1], "E'");
622648
ASSERT_EQ(lf_removed[0].GetParent(), "E");
623649
ASSERT_EQ(lf_removed[1].GetParent(), "E" + std::string(utils::DASH));
624650

625651
ASSERT_EQ(lf_removed[0].GetRules().size(), 3);
626-
ASSERT_EQ(lf_removed[1].GetRules().size(), 3);
652+
ASSERT_EQ(lf_removed[1].GetRules().size(), 2);
627653

628654
ASSERT_EQ(lf_removed[0].GetRules()[0].ToString(), "ieStE'");
629655
ASSERT_EQ(lf_removed[0].GetRules()[1].ToString(), "a");
630656
ASSERT_EQ(lf_removed[0].GetRules()[2].ToString(), "b");
631657

632658
ASSERT_EQ(lf_removed[1].GetRules()[0].ToString(), "St");
633-
ASSERT_EQ(lf_removed[1].GetRules()[1].ToString(), "P");
634-
ASSERT_EQ(lf_removed[1].GetRules()[2].ToString(), std::string(grammar::EPSILON));
659+
ASSERT_EQ(lf_removed[1].GetRules()[1].ToString(), std::string(grammar::EPSILON));
635660
}

0 commit comments

Comments
 (0)