29684795945

Committed 19 Jul 2026 11:15AM UTC coverage: 90.771% (+0.2%) from 90.53%

Build # 29684795945

Build Type

Pull #46

github

Committed by

rieske

Commit Message

Experimental parser genrator optimization

Pull Request Pull Request #46: Experimental parser generator optimization

Coverage Stats

467 of 475 new or added lines in 14 files covered. (98.32%)

16 existing lines in 6 files now uncovered.

5272 of 5808 relevant lines covered (90.77%)

233275.02 hits per line

Source File
Press 'n' to go to next uncovered line, 'b' for previous

98.53

/src/parser/GeneratedParsingTable.cpp

#include "GeneratedParsingTable.h"

#include "Action.h"

#include <fstream>
#include <memory>
#include <optional>

namespace parser {

GeneratedParsingTable::GeneratedParsingTable(const Grammar* grammar, AutomatonKind kind) :
    ParsingTable(grammar),
    firstTable { *grammar }
{
    CanonicalCollection canonicalCollection { firstTable, *this->grammar, kind };

    computeActionTable(canonicalCollection);
    computeGotoTable(canonicalCollection);
    computeErrorActions(canonicalCollection.stateCount());
}

GeneratedParsingTable::~GeneratedParsingTable() {
}

void GeneratedParsingTable::computeActionTable(const CanonicalCollection& canonicalCollection) {
    size_t stateCount = canonicalCollection.stateCount();
    lookaheadActionTable.reserve(stateCount);
    lookaheadActionTable.setStateCount(stateCount);
    const int topRuleId = grammar->getTopRule().getId();
    const int endSymbol = grammar->getEndSymbol();
    for (parse_state currentState = 0; currentState < stateCount; ++currentState) {
        const auto& setOfItemsForCurrentState = canonicalCollection.setOfItemsAtState(currentState);
        for (const auto& item : setOfItemsForCurrentState) {
            if (item.hasUnvisitedSymbols()) {
                const auto nextExpectedSymbolForItem = item.nextUnvisitedSymbol();
                if (grammar->isTerminal(nextExpectedSymbolForItem)) {
                    lookaheadActionTable.addAction(
                            currentState,
                            nextExpectedSymbolForItem,
                            Action::shift(canonicalCollection.goTo(currentState, nextExpectedSymbolForItem)));
                }
            } else if ((item.getProduction().getId() == topRuleId)
                    && item.hasLookahead(endSymbol, *grammar)) {
                lookaheadActionTable.addAction(
                        currentState,
                        endSymbol,
                        Action::accept());
            } else {
                const Production& production = item.getProduction();
                for (const int lookahead : item.getLookaheads(*grammar)) {
                    lookaheadActionTable.addAction(
                            currentState,
                            lookahead,
                            Action::reduce(production, this));
                }
            }
        }
    }
}

void GeneratedParsingTable::computeGotoTable(const CanonicalCollection& canonicalCollection) {
    size_t stateCount = canonicalCollection.stateCount();
    const auto& nonterminals = grammar->getNonterminalIDs();
    for (parse_state state = 0; state < stateCount; ++state) {
        for (const auto nonterminal : nonterminals) {
            std::optional<parse_state> stateTo = canonicalCollection.findGoTo(state, nonterminal);
            if (stateTo) {
                gotoTable[state][nonterminal] = *stateTo;
            }
        }
    }
}

void GeneratedParsingTable::computeErrorActions(size_t stateCount) {
    const auto& terminals = grammar->getTerminalIDs();
    for (std::size_t state = 0; state < stateCount; ++state) {
        auto candidateTerminals = std::make_shared<std::vector<int>>();
        for (const auto candidate : terminals) {
            if (lookaheadActionTable.hasAction(state, candidate)
                    && lookaheadActionTable.action(state, candidate).isCorrective()) {
                candidateTerminals->push_back(candidate);
            }
        }
        lookaheadActionTable.setErrorCandidates(state, std::move(candidateTerminals), grammar);
    }
}

void GeneratedParsingTable::persistToFile(std::string fileName) const {
    std::ofstream tableOutput { fileName };
    if (!tableOutput.is_open()) {
        throw std::runtime_error { "Unable to create parsing table output file! fileName: " + fileName + "\n" };
    }

    size_t stateCount = lookaheadActionTable.size();
    tableOutput << stateCount << std::endl;
    tableOutput << "%%" << std::endl;
    for (std::size_t i = 0; i < stateCount; i++) {
        for (auto& terminal : grammar->getTerminalIDs()) {
            tableOutput << lookaheadActionTable.action(i, terminal).serialize() << "\n";
        }
    }
    tableOutput << "%%" << std::endl;

    for (const auto& stateGotos : gotoTable) {
        for (const auto& nonterminalGotoState : stateGotos.second) {
            tableOutput << stateGotos.first << " " << nonterminalGotoState.first << " " << nonterminalGotoState.second << "\n";
        }
    }
}

} // namespace parser

1	#include "GeneratedParsingTable.h"
2
3	#include "Action.h"
4
5	#include <fstream>
6	#include <memory>
7	#include <optional>
8
9	namespace parser {
10
11	GeneratedParsingTable::GeneratedParsingTable(const Grammar* grammar, AutomatonKind kind) :	8✔
12	ParsingTable(grammar),
13	firstTable { *grammar }	8✔
14	{
15	CanonicalCollection canonicalCollection { firstTable, *this->grammar, kind };	8✔
16
17	computeActionTable(canonicalCollection);	8✔
18	computeGotoTable(canonicalCollection);	8✔
19	computeErrorActions(canonicalCollection.stateCount());	8✔
20	}	8✔
21
22	GeneratedParsingTable::~GeneratedParsingTable() {	14✔
23	}	14✔
24
25	void GeneratedParsingTable::computeActionTable(const CanonicalCollection& canonicalCollection) {	8✔
26	size_t stateCount = canonicalCollection.stateCount();	8✔
27	lookaheadActionTable.reserve(stateCount);	8✔
28	lookaheadActionTable.setStateCount(stateCount);	8✔
29	const int topRuleId = grammar->getTopRule().getId();	8✔
30	const int endSymbol = grammar->getEndSymbol();	8✔
31	for (parse_state currentState = 0; currentState < stateCount; ++currentState) {	3,462✔
32	const auto& setOfItemsForCurrentState = canonicalCollection.setOfItemsAtState(currentState);	3,454✔
33	for (const auto& item : setOfItemsForCurrentState) {	53,334✔
34	if (item.hasUnvisitedSymbols()) {	49,880✔
35	const auto nextExpectedSymbolForItem = item.nextUnvisitedSymbol();	47,772✔
36	if (grammar->isTerminal(nextExpectedSymbolForItem)) {	47,772✔
37	lookaheadActionTable.addAction(	21,258✔
38	currentState,
39	nextExpectedSymbolForItem,
40	Action::shift(canonicalCollection.goTo(currentState, nextExpectedSymbolForItem)));	42,516✔
41	}
42	} else if ((item.getProduction().getId() == topRuleId)	2,108✔
43	&& item.hasLookahead(endSymbol, *grammar)) {	2,108✔
44	lookaheadActionTable.addAction(	8✔
45	currentState,
46	endSymbol,
47	Action::accept());	16✔
48	} else {
49	const Production& production = item.getProduction();	2,100✔
50	for (const int lookahead : item.getLookaheads(*grammar)) {	41,902✔
51	lookaheadActionTable.addAction(	39,802✔
52	currentState,
53	lookahead,
54	Action::reduce(production, this));	79,604✔
55	}	2,100✔
56	}
57	}
58	}
59	}	8✔
60
61	void GeneratedParsingTable::computeGotoTable(const CanonicalCollection& canonicalCollection) {	8✔
62	size_t stateCount = canonicalCollection.stateCount();	8✔
63	const auto& nonterminals = grammar->getNonterminalIDs();	8✔
64	for (parse_state state = 0; state < stateCount; ++state) {	3,462✔
65	for (const auto nonterminal : nonterminals) {	192,138✔
66	std::optional<parse_state> stateTo = canonicalCollection.findGoTo(state, nonterminal);	188,684✔
67	if (stateTo) {	188,684✔
68	gotoTable[state][nonterminal] = *stateTo;	12,626✔
69	}
70	}
71	}
72	}	8✔
73
74	void GeneratedParsingTable::computeErrorActions(size_t stateCount) {	8✔
75	const auto& terminals = grammar->getTerminalIDs();	8✔
76	for (std::size_t state = 0; state < stateCount; ++state) {	3,462✔
77	auto candidateTerminals = std::make_shared<std::vector<int>>();	3,454✔
78	for (const auto candidate : terminals) {	250,332✔
79	if (lookaheadActionTable.hasAction(state, candidate)	740,634✔
80	&& lookaheadActionTable.action(state, candidate).isCorrective()) {	246,878✔
81	candidateTerminals->push_back(candidate);	39,802✔
82	}
83	}
84	lookaheadActionTable.setErrorCandidates(state, std::move(candidateTerminals), grammar);	3,454✔
85	}	3,454✔
86	}	8✔
87
88	void GeneratedParsingTable::persistToFile(std::string fileName) const {	2✔
89	std::ofstream tableOutput { fileName };	2✔
90	if (!tableOutput.is_open()) {	2✔
UNCOV 91	throw std::runtime_error { "Unable to create parsing table output file! fileName: " + fileName + "\n" };	×
92	}
93
94	size_t stateCount = lookaheadActionTable.size();	2✔
95	tableOutput << stateCount << std::endl;	2✔
96	tableOutput << "%%" << std::endl;	2✔
97	for (std::size_t i = 0; i < stateCount; i++) {	800✔
98	for (auto& terminal : grammar->getTerminalIDs()) {	69,426✔
99	tableOutput << lookaheadActionTable.action(i, terminal).serialize() << "\n";	68,628✔
100	}
101	}
102	tableOutput << "%%" << std::endl;	2✔
103
104	for (const auto& stateGotos : gotoTable) {	228✔
105	for (const auto& nonterminalGotoState : stateGotos.second) {	3,514✔
106	tableOutput << stateGotos.first << " " << nonterminalGotoState.first << " " << nonterminalGotoState.second << "\n";	3,288✔
107	}
108	}
109	}	2✔
110
111	} // namespace parser

rieske / trans / 29684795945

Source File Press 'n' to go to next uncovered line, 'b' for previous

Source File
Press 'n' to go to next uncovered line, 'b' for previous