29701014723

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

Build # 29701014723

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

487 of 497 new or added lines in 19 files covered. (97.99%)

17 existing lines in 6 files now uncovered.

5269 of 5807 relevant lines covered (90.74%)

352430.51 hits per line

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

98.65

/src/parser/GeneratedParsingTable.cpp

#include "GeneratedParsingTable.h"

#include "Action.h"
#include "FirstTable.h"

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

namespace parser {

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

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

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

rieske / trans / 29701014723

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