Jtdylktuy

As an exercise, I wrote a simple context free parser modeled from a pushdown automaton for chemical formulas such as NO2 or Fe(NO3)3.

To explain a bit about the decisions made:

1. The state functions (pstart, pchem and pnum) are lambdas because they carry around a lot of context. They could be methods of a class, it doesn't really matter.




2. The state functions have the input character injected because I realized halfway that I have to process some more after the line ended and I don't want to duplicate the state functions.

I am mostly concerned about the general messiness of the parser. There is no obvious way to know where variables are mutated, control flow is all over the place and consequently I find it difficult to reason about the program. Is there a better code structure?

Finally, I'd like to know if I caught all illegal syntax. Note repeating chemicals like NN is allowed.

#include<iostream>

#include<stack>

#include<unordered_map>

#include<string>

#include<iterator>



using namespace std::literals;



enum class state_t { start, num, chem, error };



double parse(std::string line, const std::unordered_map<std::string, double>& m)

{

    auto b = line.begin(), e = line.end();

    std::stack<double> stk;

    int num = 0;

    std::string chem;

    state_t state = state_t::start;



    auto pstart = [&](char c) {

        if(std::isupper(c))

        {

            chem = ""s + c;

            state = state_t::chem;

            return true;

        }

        else if(std::isdigit(c))

        {

            if(stk.empty())

                state = state_t::error;

            else

            {

                num = c - '0';

                state = state_t::num;

                return true;

            }

        }

        else if(c == '(')

        {

            stk.push(-1);

            return true;

        }

        else if(c == ')')

        {

            double sum = 0;

            while(!stk.empty() && stk.top() > 0)

            {

                sum += stk.top();

                stk.pop();

            }

            if(stk.empty())

                state = state_t::error;

            else

            {

                stk.pop();

                stk.push(sum);

                return true;

            }

        }

        else

            state = state_t::error;



        return false;

    };



    auto pnum = [&](char c) {

        if(std::isdigit(c))

        {

            num = 10 * num + c - '0';

            return true;

        }

        else

        {

            stk.top() *= num;

            state = state_t::start;

        }

        return false;

    };



    auto pchem = [&](char c){

        if(std::islower(c))

        {

            chem += c;

            return true;

        }

        else

        {

            if(auto it = m.find(chem); it != m.end())

            {

                stk.push(it->second);

                state = state_t::start;

            }

            else

                state = state_t::error;

        }

        return false;

    };



    while(b != e)

    {

        switch(state)

        {

        case state_t::start:

            if(pstart(*b))

                b++;

            break;

        case state_t::num:

            if(pnum(*b))

                b++;

            break;

        case state_t::chem:

            if(pchem(*b))

                b++;

            break;

        default:

            return -1;

        }

    }



    switch(state)

    {

    case state_t::num:

        pnum('n');

        break;

    case state_t::chem:

        pchem('n');

        break;

    }



    if(state == state_t::error)

        return -1;



    double sum = 0;

    while(!stk.empty() && stk.top() > 0)

    {

        sum += stk.top();

        stk.pop();

    }

    if(stk.size() > 0)  // expected ')'

        return -1;



    return sum;

}



int main()

{

    std::unordered_map<std::string, double> m;

    m["Na"] = 23.5;

    m["Cl"] = 35.5;

    m["O"] = 16;

    m["N"] = 14;

    m["Fe"] = 55.8;



    std::string line;

    while(getline(std::cin, line))

        std::cout << parse(std::move(line), m) << 'n';

}

Using a state machine is fine, but is usually harder to get right than writing the parser with focus on the grammar. You're also mixing a computation with the parsing which adds more information to consider when analyzing the code.
I would recommend to separate the parser code from the computation and then writing the parser strictly following the grammar you want to parse. I'll try to illustrate what I mean by giving a simplified version of your parser. Say you have a grammar:

formula = *(group)

group = element [ count ]

element = uppercase [ lowercase ]

count = "0" .. "9"

You can now give a function for each non-terminal:

// formula = *(group)   ; * becomes while (...) ...

std::list<group> parse_formula(std::stringstream& s)

{

    std::list<group> rv;



    while (!s.eof())

    {

        rv.push_back(parse_group(s));

    }



    return rv;

}



// group = element [ count ]

group parse_group(std::stringstream& s)

{

    group g;

    group.element = parse_element(s);

    try

    {

        group.count = parse_count(s);

    }

    catch (const parse_failed&)

    {

        group = 1;

    }

}



// element = uppercase [lowercase]

std::string parse_element(std::stringstream& s)

{

    if (!std::isupper(s.peek()))

    {

        throw parse_failed(...);

    }



    std::string element = s.get();;



    if (std::islower(s.peek()))

    {

        s.get(ch);

        element += ch;

    }



    return element;

}



// count = [0-9]

unsigned parse_count(std::stringstream& s)

{ 

    if (!std::isdigit(s.peek()))

    {

        throw parse_failed(...);

    }



    unsigned rv; 

    s >> rv; // this actually violates the grammar as it reads multiple digits

    return rv;

}

You can then iterate over the list of groups and compute the sum.

Lambdas Too Complex

You say that the reason behind your lambdas is that they carry a lot of state around, but it is mutating plenty of it as well. Extracting your lambdas into methods in their own right would make it easier to keep track of where your state is used and where it is mutated.

Methods Should Calculate Or Mutate, Not Both

Lambdas that calculate something and then mutate something else are notoriously difficult to debug and maintain. When you create your methods, it should either calculate something (such as the atomic weight) or change something (such as changing your state).

Variable Names Unclear

Names like pstart, num and m do not tell me anything about the purpose of these variables. There is nothing wrong with LongVariableNamesThatExplainWhatTheyAreDoing.