Skip to content

Commit ac60d77

Browse files
bisakhmondalbisakhmondal
authored
Single Interface for Non Ambiguous CFG (#23)
* sometime writing code is itself ambiguous🥽 * tests
1 parent 98c387e commit ac60d77

File tree

6 files changed

+92
-12
lines changed

6 files changed

+92
-12
lines changed

‎src/include/main/jucc.h‎

Lines changed: 1 addition & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -9,9 +9,7 @@
99
#include "lexer/lexer.h"
1010
#include "parser/parser.h"
1111
#include "parser/parsing_table.h"
12-
#include "utils/first_follow.h"
13-
#include "utils/left_factoring.h"
14-
#include "utils/left_recursion.h"
12+
#include "utils/utils.h"
1513

1614
namespace jucc {
1715
/**

‎src/include/utils/utils.h‎

Lines changed: 28 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,28 @@
1+
#ifndef JUCC_UTILS_UTILS_H
2+
#define JUCC_UTILS_UTILS_H
3+
4+
#include <string>
5+
#include <vector>
6+
7+
#include "grammar/grammar.h"
8+
#include "utils/first_follow.h"
9+
#include "utils/left_factoring.h"
10+
#include "utils/left_recursion.h"
11+
#include "utils/trie/memory_efficient_trie.h"
12+
13+
namespace jucc {
14+
namespace utils {
15+
/**
16+
* Makes the grammar non ambiguous.
17+
* @return A set of production free from left recursions and left factors.
18+
*/
19+
grammar::Productions RemoveAllPossibleAmbiguity(const grammar::Productions & /*prods*/);
20+
21+
/**
22+
* @returns a list of parents from the given set of productions.
23+
*/
24+
std::vector<std::string> GetAllNonTerminals(const grammar::Productions & /*prods*/);
25+
26+
} // namespace utils
27+
} // namespace jucc
28+
#endif

‎src/main/main.cpp‎

Lines changed: 5 additions & 5 deletions
Original file line numberDiff line numberDiff line change
@@ -1,4 +1,4 @@
1-
/*-------------------------------------------------------------------------
1+
/**-------------------------------------------------------------------------
22
*
33
* main.cpp
44
* Stub main() routine for the jucc executable.
@@ -21,7 +21,7 @@
2121
*/
2222

2323
#include "main/jucc.h"
24-
/*
24+
/**
2525
* jucc begins execution here.
2626
*/
2727
auto main(int argc, char *argv[]) -> int {
@@ -52,16 +52,16 @@ auto main(int argc, char *argv[]) -> int {
5252
return 0;
5353
}
5454

55-
jucc::grammar::Productions productions = grammar_parser.GetProductions();
55+
jucc::grammar::Productions raw_productions = grammar_parser.GetProductions();
5656

57-
// TODO(bisakh,abhiskek) : Add code for removing left factors and left recursion
57+
jucc::grammar::Productions productions = jucc::utils::RemoveAllPossibleAmbiguity(raw_productions);
5858

5959
auto nullables = jucc::utils::CalcNullables(productions);
6060
auto firsts = jucc::utils::CalcFirsts(productions, nullables);
6161
auto follows = jucc::utils::CalcFollows(productions, firsts, nullables, grammar_parser.GetStartSymbol());
6262

6363
auto terminals = grammar_parser.GetTerminals();
64-
auto non_terminals = grammar_parser.GetNonTerminals();
64+
auto non_terminals = jucc::utils::GetAllNonTerminals(productions);
6565

6666
jucc::parser::ParsingTable parsing_table = jucc::parser::ParsingTable(terminals, non_terminals);
6767
parsing_table.SetFirsts(firsts);

‎src/utils/first_follow.cpp‎

Lines changed: 0 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -1,6 +1,5 @@
11
#include "utils/first_follow.h"
22

3-
#include <algorithm>
43
#include <functional>
54

65
#include "utils/left_factoring.h"

‎src/utils/utils.cpp‎

Lines changed: 24 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,24 @@
1+
#include "utils/utils.h"
2+
3+
namespace jucc::utils {
4+
grammar::Productions RemoveAllPossibleAmbiguity(const grammar::Productions &prods) {
5+
grammar::Productions clean;
6+
for (const auto &prod : prods) {
7+
for (const grammar::Production &lr_free : RemoveDirectLeftRecursion(prod)) {
8+
// non ambiguous grammars
9+
grammar::Productions nag = RemoveLeftFactors(lr_free);
10+
clean.insert(clean.end(), nag.begin(), nag.end());
11+
}
12+
}
13+
return clean;
14+
}
15+
16+
std::vector<std::string> GetAllNonTerminals(const grammar::Productions &prods) {
17+
std::vector<std::string> non_terminals;
18+
for (const auto &prod : prods) {
19+
non_terminals.push_back(prod.GetParent());
20+
}
21+
return non_terminals;
22+
}
23+
24+
} // namespace jucc::utils

‎test/utils/utils_test.cpp‎

Lines changed: 34 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -1,7 +1,6 @@
1+
#include "utils/utils.h"
2+
13
#include "gtest/gtest.h"
2-
#include "utils/first_follow.h"
3-
#include "utils/left_factoring.h"
4-
#include "utils/left_recursion.h"
54

65
namespace grammar = jucc::grammar;
76
namespace utils = jucc::utils;
@@ -583,3 +582,35 @@ TEST(utils, CalcFollows2) {
583582
ASSERT_EQ(res.at("T'"), std::vector<std::string>({utils::STRING_ENDMARKER, ")", "+"}));
584583
ASSERT_EQ(res.at("F"), std::vector<std::string>({utils::STRING_ENDMARKER, ")", "*", "+"}));
585584
}
585+
586+
TEST(utils, RemoveAllAmbiguity0) {
587+
// E -> ieStSt | a | b | ieStP
588+
grammar::Production p;
589+
p.SetParent("E");
590+
p.SetRules({grammar::Rule({"i", "e", "S", "t", "S", "t"}), grammar::Rule({"a"}), grammar::Rule({"b"}),
591+
grammar::Rule({"i", "e", "S", "t", "P"})});
592+
593+
auto lf_removed = utils::RemoveAllPossibleAmbiguity({p});
594+
auto non_terminals = utils::GetAllNonTerminals(lf_removed);
595+
596+
ASSERT_EQ(lf_removed.size(), 2);
597+
// output
598+
// E -> ieStE' | a | b |
599+
// E' -> St | P | epsilon
600+
ASSERT_EQ(non_terminals.size(), 2);
601+
ASSERT_EQ(non_terminals[0], "E");
602+
ASSERT_EQ(non_terminals[1], "E'");
603+
ASSERT_EQ(lf_removed[0].GetParent(), "E");
604+
ASSERT_EQ(lf_removed[1].GetParent(), "E" + std::string(utils::DASH));
605+
606+
ASSERT_EQ(lf_removed[0].GetRules().size(), 3);
607+
ASSERT_EQ(lf_removed[1].GetRules().size(), 3);
608+
609+
ASSERT_EQ(lf_removed[0].GetRules()[0].ToString(), "ieStE'");
610+
ASSERT_EQ(lf_removed[0].GetRules()[1].ToString(), "a");
611+
ASSERT_EQ(lf_removed[0].GetRules()[2].ToString(), "b");
612+
613+
ASSERT_EQ(lf_removed[1].GetRules()[0].ToString(), "St");
614+
ASSERT_EQ(lf_removed[1].GetRules()[1].ToString(), "P");
615+
ASSERT_EQ(lf_removed[1].GetRules()[2].ToString(), std::string(grammar::EPSILON));
616+
}

0 commit comments

Comments
 (0)