1
\$\begingroup\$

I've been working on an LR(1) parser, and I've just finished making the LR(1) item. I'm very rusty with C++, so any pointers (especially optimization and code structure) would be appreciated. Here are my files:

main.cpp:

#include <iostream>
#include <array>
#include <vector>
#include <unordered_map>
#include "lritem.cpp"

int main() {
    std::cout << std::boolalpha;
    LR1Item item = LR1Item(
        "expr",
        std::array<const char*, 3> {"alpha", "B", "beta"},
        std::array<const char*, 2> {"$", "beta"}, 0);
    item.move_forward();
    item.move_forward();
    std::vector<const char*> abc = item.first_of(std::unordered_map<const char*, std::array<const char*, 2>> {
        {"alpha", std::array<const char*, 2> {"B", "beta"}},
        {"B", std::array<const char*, 2> {"alpha", "beta"}},
        {"beta", std::array<const char*, 2> {"alpha", "B"}},
        {"$", std::array<const char*, 2> {"beta", "alpha"}}
    });
    std::cout << "[";
    for (const char* y: abc) {
        std::cout << y << ",";
    }
    std::cout << "]\n";
}

lritem.cpp:

#include <array>
#include <vector>
#include <unordered_map>
#include <algorithm>
#include "lritem.hpp"


template <std::size_t RHS_SIZE, std::size_t LA_SIZE>
bool LR1Item<RHS_SIZE, LA_SIZE>::is_final_item() const {
    // check if we are at the end of rhs
    return parsed_till == rhs.size();
}

template <std::size_t RHS_SIZE, std::size_t LA_SIZE>
const char* LR1Item<RHS_SIZE, LA_SIZE>::move_forward() {
    // return the symbol we are moving over, then
    // move forward
    return rhs[parsed_till++];
}

template <std::size_t RHS_SIZE, std::size_t LA_SIZE>
const char* LR1Item<RHS_SIZE, LA_SIZE>::get_neighbor() const {
    // return the symbol after the place we have parsed till
    return rhs[parsed_till];
}

template <std::size_t RHS_SIZE, std::size_t LA_SIZE>
template <std::size_t FIRST_SIZE>
std::vector<const char*> LR1Item<RHS_SIZE, LA_SIZE>::first_of(
            std::unordered_map<const char*, std::array<const char*, FIRST_SIZE>> first_sets) {
    if (parsed_till + 1 <= rhs.size() - 1) {
        std::vector<const char*> first = get_following_items(first_sets);
        // if we find ε ("" in this case) in the first set
        if (std::find(first.begin(), first.end(), "") != first.end()) {
            if (parsed_till + 1 > rhs.size() - 1) {
                // add all the lookahead symbols
                first.reserve(lookahead.size());
                for (const char* la: lookahead) {
                    first.push_back(la);
                }
            }
        }
        // remove ε ("" in this case)
        std::remove(first.begin(), first.end(), "");
        return first;
    } else {
        // if we are a final item, just return a vector version
        // of the lookahead
        return std::vector<const char*> (lookahead.begin(), lookahead.end());
    }
}

template <std::size_t RHS_SIZE, std::size_t LA_SIZE>
template <std::size_t FIRST_SIZE>
std::vector<const char*> LR1Item<RHS_SIZE, LA_SIZE>::get_following_items(
            std::unordered_map<const char*, std::array<const char*, FIRST_SIZE>> first_sets) {
    // set 'following' to all the items after the location after
    // we have parsed till; if there is no symbol after the location
    //  we have parsed till, set following to an empty vector
    std::vector<const char*> following = ((parsed_till + 1 > rhs.size()) ?
            std::vector<const char*> ():
            std::vector<const char*> (rhs.begin() + parsed_till + 1, rhs.end()));
    // extend all the symbols in the lookahead to 'following'
    for (const char* la: lookahead) {
        following.push_back(la);
    }
    int i = 0;
    for (const char* x: following) {
        // if 'x' is not nullable (does not have ε ("" in this case)),
        //then everything ahead of it is cut off, and we break out
        // of the loop
        if (std::find(first_sets[x].begin(), first_sets[x].end(), "") == first_sets[x].end()) {
            following = std::vector<const char*> (following.cbegin(), following.cbegin() + i + 1);
            break;
        }
        ++i;
    }
    // get the first sets of the symbols in 'following'
    std::vector<const char*> first;
    first.reserve(2 * following.size());
    for (const char* symbol: following) {
        for (const char* item: first_sets[symbol]) {
            first.push_back(item);
        }
    }
    return first;
}

lritem.hpp:

#ifndef LRUTIL_H
#define LRUTIL_H

#include <array>
#include <vector>
#include <unordered_map>


template <std::size_t RHS_SIZE, std::size_t LA_SIZE>
class LR1Item {
    private:
        const char* lhs;
        std::array<const char*, RHS_SIZE> rhs;
        std::array<const char*, LA_SIZE> lookahead;
        int parsed_till;

    public:
        LR1Item(const char* lhs,
                std::array<const char*, RHS_SIZE> rhs,
                std::array<const char*, LA_SIZE> lookahead,
                int parsed_till): lhs(lhs),
                                  rhs(rhs),
                                  lookahead(lookahead),
                                  parsed_till(parsed_till) {}

        bool is_final_item() const;
        const char* get_neighbor() const;
        const char* move_forward();

        template <std::size_t FIRST_SIZE>
        std::vector<const char*> first_of(
            std::unordered_map<const char*, std::array<const char*, FIRST_SIZE>> first_sets);

        template <std::size_t FIRST_SIZE>
        std::vector<const char*> get_following_items(
            std::unordered_map<const char*, std::array<const char*, FIRST_SIZE>> first_sets);
};

#endif
```
\$\endgroup\$
  • \$\begingroup\$ #include "lritem.cpp"? 0_o \$\endgroup\$ – bipll May 21 at 20:17
  • \$\begingroup\$ @bipll -- I'm not amazing with C++ :( Is there something incorrect with that line? \$\endgroup\$ – xilpex May 21 at 20:18
  • \$\begingroup\$ It's just, .cpp is a traditional extension for compiled source files, not the included headers. \$\endgroup\$ – bipll May 21 at 20:20
  • \$\begingroup\$ main.py? This isn't Python... \$\endgroup\$ – S.S. Anne May 21 at 22:01
  • \$\begingroup\$ I think you should #include "lritem.hpp" instead \$\endgroup\$ – S.S. Anne May 21 at 22:02
2
\$\begingroup\$
#ifndef LRUTIL_H

This doesn't match the name of the file. If your compiler supports #pragma once, it's easier to use that instead of manual header guards.


template <std::size_t RHS_SIZE, std::size_t LA_SIZE>
bool LR1Item<RHS_SIZE, LA_SIZE>::is_final_item() const { ...

Definitions for template functions should be in the header file, not in a cpp file.


int parsed_till;

You may be getting compiler warnings about comparing signed and unsigned numbers because of the type of this variable. Since this is an index, it would probably be better to use an unsigned type here (specifically std::size_t).


bool LR1Item::is_final_item() const

is_final_item implies that our index points at the final item (size() - 1). But we actually have an invalid index at this point. Perhaps is_at_end would be a better name.


const char* LR1Item::move_forward() {
    if (is_final_item()) // added check!
        throw std::runtime_error("Invalid call to move_forward()!");

    return rhs[parsed_till++];
}

I'd suggest adding a check in move_forward(), something like the above.


    template <std::size_t FIRST_SIZE>
    std::vector<const char*> first_of(
        std::unordered_map<const char*, std::array<const char*, FIRST_SIZE>> first_sets);

    template <std::size_t FIRST_SIZE>
    std::vector<const char*> get_following_items(
        std::unordered_map<const char*, std::array<const char*, FIRST_SIZE>> first_sets);

I think these two functions can both be const.


parsed_till + 1 <= rhs.size() - 1

Is this guaranteed to be safe? I don't see anything ensuring that rhs isn't empty...


first_sets[x].begin()

Note that unordered_map::operator[] will create a new entry at x if it doesn't already exist. We should probably use first_sets.find(x) instead.


Consider using std::string and std::vector instead of const char* and std::array. This might be slower, but the code will be much simpler (no array template sizes) and easier to use (no string lifetime / ownership issues).


Note: I haven't really checked the logic of what this actually does. I don't remember enough about parsers right now.

| improve this answer | |
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.