29699540882

Committed 19 Jul 2026 06:54PM UTC coverage: 90.709% (+0.2%) from 90.53%

Build # 29699540882

Build Type

Pull #46

github

Committed by

rieske

Commit Message

Experimental parser generator optimization

Pull Request Pull Request #46: Experimental parser generator optimization

Coverage Stats

453 of 465 new or added lines in 16 files covered. (97.42%)

1 existing line in 1 file now uncovered.

5272 of 5812 relevant lines covered (90.71%)

320203.21 hits per line

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

98.61

/src/parser/GeneratedParsingTable.cpp

#include "GeneratedParsingTable.h"

#include "Action.h"

#include <algorithm>
#include <fstream>
#include <memory>
#include <optional>
#include <utility>
#include <vector>

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();
                const auto& lookaheadBits = item.lookaheads();
                const std::size_t terminalCount = grammar->terminalCount();
                for (std::size_t bit = 0; bit < terminalCount; ++bit) {
                    if (lookaheadBits.test(bit)) {
                        lookaheadActionTable.addAction(
                                currentState,
                                grammar->terminalIdFromBit(bit),
                                Action::reduce(production, this));
                    }
                }
            }
        }
    }
}

void GeneratedParsingTable::computeGotoTable(const CanonicalCollection& canonicalCollection) {
    const auto& transitions = canonicalCollection.computedTransitions();
    gotoTable.reserve(transitions.size());
    // Copy only nonterminal transitions; terminal gotos are shifts in the action table.
    for (const auto& entry : transitions) {
        if (!grammar->isTerminal(entry.first.second)) {
            gotoTable[entry.first] = entry.second;
        }
    }
}

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.hasCorrectiveAction(state, candidate)) {
                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;

    // Stable order for checked-in table identity tests.
    std::vector<std::pair<GotoKey, parse_state>> gotos(gotoTable.begin(), gotoTable.end());
    std::sort(gotos.begin(), gotos.end(), [](const auto& left, const auto& right) {
        if (left.first.first != right.first.first) {
            return left.first.first < right.first.first;
        }
        return left.first.second < right.first.second;
    });
    for (const auto& entry : gotos) {
        tableOutput << entry.first.first << " " << entry.first.second << " " << entry.second << "\n";
    }
}

} // namespace parser

1	#include "GeneratedParsingTable.h"
2
3	#include "Action.h"
4
5	#include <algorithm>
6	#include <fstream>
7	#include <memory>
8	#include <optional>
9	#include <utility>
10	#include <vector>
11
12	namespace parser {
13
14	GeneratedParsingTable::GeneratedParsingTable(const Grammar* grammar, AutomatonKind kind) :	8✔
15	ParsingTable(grammar),
16	firstTable { *grammar }	8✔
17	{
18	CanonicalCollection canonicalCollection { firstTable, *this->grammar, kind };	8✔
19
20	computeActionTable(canonicalCollection);	8✔
21	computeGotoTable(canonicalCollection);	8✔
22	computeErrorActions(canonicalCollection.stateCount());	8✔
23	}	8✔
24
25	GeneratedParsingTable::~GeneratedParsingTable() {	14✔
26	}	14✔
27
28	void GeneratedParsingTable::computeActionTable(const CanonicalCollection& canonicalCollection) {	8✔
29	size_t stateCount = canonicalCollection.stateCount();	8✔
30	lookaheadActionTable.reserve(stateCount);	8✔
31	lookaheadActionTable.setStateCount(stateCount);	8✔
32	const int topRuleId = grammar->getTopRule().getId();	8✔
33	const int endSymbol = grammar->getEndSymbol();	8✔
34	for (parse_state currentState = 0; currentState < stateCount; ++currentState) {	3,462✔
35	const auto& setOfItemsForCurrentState = canonicalCollection.setOfItemsAtState(currentState);	3,454✔
36	for (const auto& item : setOfItemsForCurrentState) {	53,334✔
37	if (item.hasUnvisitedSymbols()) {	49,880✔
38	const auto nextExpectedSymbolForItem = item.nextUnvisitedSymbol();	47,772✔
39	if (grammar->isTerminal(nextExpectedSymbolForItem)) {	47,772✔
40	lookaheadActionTable.addAction(	21,258✔
41	currentState,
42	nextExpectedSymbolForItem,
43	Action::shift(canonicalCollection.goTo(currentState, nextExpectedSymbolForItem)));	42,516✔
44	}
45	} else if ((item.getProduction().getId() == topRuleId)	2,108✔
46	&& item.hasLookahead(endSymbol, *grammar)) {	2,108✔
47	lookaheadActionTable.addAction(	8✔
48	currentState,
49	endSymbol,
50	Action::accept());	16✔
51	} else {
52	const Production& production = item.getProduction();	2,100✔
53	const auto& lookaheadBits = item.lookaheads();	2,100✔
54	const std::size_t terminalCount = grammar->terminalCount();	2,100✔
55	for (std::size_t bit = 0; bit < terminalCount; ++bit) {	152,352✔
56	if (lookaheadBits.test(bit)) {	150,252✔
57	lookaheadActionTable.addAction(	39,802✔
58	currentState,
59	grammar->terminalIdFromBit(bit),	39,802✔
60	Action::reduce(production, this));	79,604✔
61	}
62	}
63	}
64	}
65	}
66	}	8✔
67
68	void GeneratedParsingTable::computeGotoTable(const CanonicalCollection& canonicalCollection) {	8✔
69	const auto& transitions = canonicalCollection.computedTransitions();	8✔
70	gotoTable.reserve(transitions.size());	8✔
71	// Copy only nonterminal transitions; terminal gotos are shifts in the action table.
72	for (const auto& entry : transitions) {	29,088✔
73	if (!grammar->isTerminal(entry.first.second)) {	29,080✔
74	gotoTable[entry.first] = entry.second;	12,626✔
75	}
76	}
77	}	8✔
78
79	void GeneratedParsingTable::computeErrorActions(size_t stateCount) {	8✔
80	const auto& terminals = grammar->getTerminalIDs();	8✔
81	for (std::size_t state = 0; state < stateCount; ++state) {	3,462✔
82	auto candidateTerminals = std::make_shared<std::vector<int>>();	3,454✔
83	for (const auto candidate : terminals) {	250,332✔
84	if (lookaheadActionTable.hasCorrectiveAction(state, candidate)) {	246,878✔
85	candidateTerminals->push_back(candidate);	39,802✔
86	}
87	}
88	lookaheadActionTable.setErrorCandidates(state, std::move(candidateTerminals), grammar);	3,454✔
89	}	3,454✔
90	}	8✔
91
92	void GeneratedParsingTable::persistToFile(std::string fileName) const {	2✔
93	std::ofstream tableOutput { fileName };	2✔
94	if (!tableOutput.is_open()) {	2✔
NEW 95	throw std::runtime_error { "Unable to create parsing table output file! fileName: " + fileName + "\n" };	×
96	}
97
98	size_t stateCount = lookaheadActionTable.size();	2✔
99	tableOutput << stateCount << std::endl;	2✔
100	tableOutput << "%%" << std::endl;	2✔
101	for (std::size_t i = 0; i < stateCount; i++) {	800✔
102	for (auto& terminal : grammar->getTerminalIDs()) {	69,426✔
103	tableOutput << lookaheadActionTable.action(i, terminal).serialize() << "\n";	68,628✔
104	}
105	}
106	tableOutput << "%%" << std::endl;	2✔
107
108	// Stable order for checked-in table identity tests.
109	std::vector<std::pair<GotoKey, parse_state>> gotos(gotoTable.begin(), gotoTable.end());	2✔
110	std::sort(gotos.begin(), gotos.end(), [](const auto& left, const auto& right) {	2✔
111	if (left.first.first != right.first.first) {	41,936✔
112	return left.first.first < right.first.first;	26,934✔
113	}
114	return left.first.second < right.first.second;	15,002✔
115	});
116	for (const auto& entry : gotos) {	3,290✔
117	tableOutput << entry.first.first << " " << entry.first.second << " " << entry.second << "\n";	3,288✔
118	}
119	}	2✔
120
121	} // namespace parser

rieske / trans / 29699540882

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