29700705556

Committed 19 Jul 2026 07:29PM UTC coverage: 90.76% (+0.2%) from 90.53%

Build # 29700705556

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

485 of 494 new or added lines in 16 files covered. (98.18%)

17 existing lines in 6 files now uncovered.

5275 of 5812 relevant lines covered (90.76%)

352127.06 hits per line

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

98.67

/src/parser/GeneratedParsingTable.cpp

#include "GeneratedParsingTable.h"

#include "Action.h"

#include <algorithm>
#include <fstream>
#include <memory>
#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) {
        std::vector<int> candidates;
        for (const auto candidate : terminals) {
            if (lookaheadActionTable.hasCorrectiveAction(state, candidate)) {
                candidates.push_back(candidate);
            }
        }
        if (candidates.empty()) {
            // Registers grammar for bare errors; no per-state empty candidate storage.
            lookaheadActionTable.setErrorCandidates(state, nullptr, grammar);
        } else {
            lookaheadActionTable.setErrorCandidates(
                    state,
                    std::make_shared<const std::vector<int>>(std::move(candidates)),
                    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<StateSymbolKey, 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 <utility>
9	#include <vector>
10
11	namespace parser {
12
13	GeneratedParsingTable::GeneratedParsingTable(const Grammar* grammar, AutomatonKind kind) :	6✔
14	ParsingTable(grammar),
15	firstTable { *grammar }	6✔
16	{
17	CanonicalCollection canonicalCollection { firstTable, *this->grammar, kind };	6✔
18
19	computeActionTable(canonicalCollection);	6✔
20	computeGotoTable(canonicalCollection);	6✔
21	computeErrorActions(canonicalCollection.stateCount());	6✔
22	}	6✔
23
24	GeneratedParsingTable::~GeneratedParsingTable() {	10✔
25	}	10✔
26
27	void GeneratedParsingTable::computeActionTable(const CanonicalCollection& canonicalCollection) {	6✔
28	size_t stateCount = canonicalCollection.stateCount();	6✔
29	lookaheadActionTable.reserve(stateCount);	6✔
30	lookaheadActionTable.setStateCount(stateCount);	6✔
31	const int topRuleId = grammar->getTopRule().getId();	6✔
32	const int endSymbol = grammar->getEndSymbol();	6✔
33	for (parse_state currentState = 0; currentState < stateCount; ++currentState) {	5,096✔
34	const auto& setOfItemsForCurrentState = canonicalCollection.setOfItemsAtState(currentState);	5,090✔
35	for (const auto& item : setOfItemsForCurrentState) {	99,012✔
36	if (item.hasUnvisitedSymbols()) {	93,922✔
37	const auto nextExpectedSymbolForItem = item.nextUnvisitedSymbol();	90,944✔
38	if (grammar->isTerminal(nextExpectedSymbolForItem)) {	90,944✔
39	lookaheadActionTable.addAction(	41,046✔
40	currentState,
41	nextExpectedSymbolForItem,
42	Action::shift(canonicalCollection.goTo(currentState, nextExpectedSymbolForItem)));	82,092✔
43	}
44	} else if ((item.getProduction().getId() == topRuleId)	2,978✔
45	&& item.hasLookahead(endSymbol, *grammar)) {	2,978✔
46	lookaheadActionTable.addAction(	6✔
47	currentState,
48	endSymbol,
49	Action::accept());	12✔
50	} else {
51	const Production& production = item.getProduction();	2,972✔
52	const auto& lookaheadBits = item.lookaheads();	2,972✔
53	const std::size_t terminalCount = grammar->terminalCount();	2,972✔
54	for (std::size_t bit = 0; bit < terminalCount; ++bit) {	258,564✔
55	if (lookaheadBits.test(bit)) {	255,592✔
56	lookaheadActionTable.addAction(	56,098✔
57	currentState,
58	grammar->terminalIdFromBit(bit),	56,098✔
59	Action::reduce(production, this));	112,196✔
60	}
61	}
62	}
63	}
64	}
65	}	6✔
66
67	void GeneratedParsingTable::computeGotoTable(const CanonicalCollection& canonicalCollection) {	6✔
68	const auto& transitions = canonicalCollection.computedTransitions();	6✔
69	gotoTable.reserve(transitions.size());	6✔
70	// Copy only nonterminal transitions; terminal gotos are shifts in the action table.
71	for (const auto& entry : transitions) {	51,752✔
72	if (!grammar->isTerminal(entry.first.second)) {	51,746✔
73	gotoTable[entry.first] = entry.second;	21,960✔
74	}
75	}
76	}	6✔
77
78	void GeneratedParsingTable::computeErrorActions(size_t stateCount) {	6✔
79	const auto& terminals = grammar->getTerminalIDs();	6✔
80	for (std::size_t state = 0; state < stateCount; ++state) {	5,096✔
81	std::vector<int> candidates;	5,090✔
82	for (const auto candidate : terminals) {	442,830✔
83	if (lookaheadActionTable.hasCorrectiveAction(state, candidate)) {	437,740✔
84	candidates.push_back(candidate);	56,098✔
85	}
86	}
87	if (candidates.empty()) {	5,090✔
88	// Registers grammar for bare errors; no per-state empty candidate storage.
89	lookaheadActionTable.setErrorCandidates(state, nullptr, grammar);	2,118✔
90	} else {
91	lookaheadActionTable.setErrorCandidates(	2,972✔
92	state,
93	std::make_shared<const std::vector<int>>(std::move(candidates)),	5,944✔
94	grammar);
95	}
96	}	5,090✔
97	}	6✔
98
99	void GeneratedParsingTable::persistToFile(std::string fileName) const {	2✔
100	std::ofstream tableOutput { fileName };	2✔
101	if (!tableOutput.is_open()) {	2✔
UNCOV 102	throw std::runtime_error { "Unable to create parsing table output file! fileName: " + fileName + "\n" };	×
103	}
104
105	size_t stateCount = lookaheadActionTable.size();	2✔
106	tableOutput << stateCount << std::endl;	2✔
107	tableOutput << "%%" << std::endl;	2✔
108	for (std::size_t i = 0; i < stateCount; i++) {	800✔
109	for (auto& terminal : grammar->getTerminalIDs()) {	69,426✔
110	tableOutput << lookaheadActionTable.action(i, terminal).serialize() << "\n";	68,628✔
111	}
112	}
113	tableOutput << "%%" << std::endl;	2✔
114
115	// Stable order for checked-in table identity tests.
116	std::vector<std::pair<StateSymbolKey, parse_state>> gotos(gotoTable.begin(), gotoTable.end());	2✔
117	std::sort(gotos.begin(), gotos.end(), [](const auto& left, const auto& right) {	2✔
118	if (left.first.first != right.first.first) {	41,936✔
119	return left.first.first < right.first.first;	26,934✔
120	}
121	return left.first.second < right.first.second;	15,002✔
122	});
123	for (const auto& entry : gotos) {	3,290✔
124	tableOutput << entry.first.first << " " << entry.first.second << " " << entry.second << "\n";	3,288✔
125	}
126	}	2✔
127
128	} // namespace parser

rieske / trans / 29700705556

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