29685214814

Committed 19 Jul 2026 11:29AM UTC coverage: 90.794% (+0.3%) from 90.53%

Build # 29685214814

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

492 of 500 new or added lines in 17 files covered. (98.4%)

16 existing lines in 6 files now uncovered.

5286 of 5822 relevant lines covered (90.79%)

309852.94 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 <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) {
    size_t stateCount = canonicalCollection.stateCount();
    gotoTable.reserve(stateCount * 4);
    const auto& nonterminals = grammar->getNonterminalIDs();
    for (parse_state state = 0; state < stateCount; ++state) {
        for (const auto nonterminal : nonterminals) {
            if (const auto stateTo = canonicalCollection.findGoTo(state, nonterminal)) {
                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;

    // 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	size_t stateCount = canonicalCollection.stateCount();	8✔
70	gotoTable.reserve(stateCount * 4);	8✔
71	const auto& nonterminals = grammar->getNonterminalIDs();	8✔
72	for (parse_state state = 0; state < stateCount; ++state) {	3,462✔
73	for (const auto nonterminal : nonterminals) {	192,138✔
74	if (const auto stateTo = canonicalCollection.findGoTo(state, nonterminal)) {	188,684✔
75	gotoTable[{ state, nonterminal }] = *stateTo;	12,626✔
76	}
77	}
78	}
79	}	8✔
80
81	void GeneratedParsingTable::computeErrorActions(size_t stateCount) {	8✔
82	const auto& terminals = grammar->getTerminalIDs();	8✔
83	for (std::size_t state = 0; state < stateCount; ++state) {	3,462✔
84	auto candidateTerminals = std::make_shared<std::vector<int>>();	3,454✔
85	for (const auto candidate : terminals) {	250,332✔
86	if (lookaheadActionTable.hasAction(state, candidate)	740,634✔
87	&& lookaheadActionTable.action(state, candidate).isCorrective()) {	246,878✔
88	candidateTerminals->push_back(candidate);	39,802✔
89	}
90	}
91	lookaheadActionTable.setErrorCandidates(state, std::move(candidateTerminals), grammar);	3,454✔
92	}	3,454✔
93	}	8✔
94
95	void GeneratedParsingTable::persistToFile(std::string fileName) const {	2✔
96	std::ofstream tableOutput { fileName };	2✔
97	if (!tableOutput.is_open()) {	2✔
UNCOV 98	throw std::runtime_error { "Unable to create parsing table output file! fileName: " + fileName + "\n" };	×
99	}
100
101	size_t stateCount = lookaheadActionTable.size();	2✔
102	tableOutput << stateCount << std::endl;	2✔
103	tableOutput << "%%" << std::endl;	2✔
104	for (std::size_t i = 0; i < stateCount; i++) {	800✔
105	for (auto& terminal : grammar->getTerminalIDs()) {	69,426✔
106	tableOutput << lookaheadActionTable.action(i, terminal).serialize() << "\n";	68,628✔
107	}
108	}
109	tableOutput << "%%" << std::endl;	2✔
110
111	// Stable order for checked-in table identity tests.
112	std::vector<std::pair<GotoKey, parse_state>> gotos(gotoTable.begin(), gotoTable.end());	2✔
113	std::sort(gotos.begin(), gotos.end(), [](const auto& left, const auto& right) {	2✔
114	if (left.first.first != right.first.first) {	48,234✔
115	return left.first.first < right.first.first;	33,514✔
116	}
117	return left.first.second < right.first.second;	14,720✔
118	});
119	for (const auto& entry : gotos) {	3,290✔
120	tableOutput << entry.first.first << " " << entry.first.second << " " << entry.second << "\n";	3,288✔
121	}
122	}	2✔
123
124	} // namespace parser

rieske / trans / 29685214814

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