Re: [boost] Yacc, lex, and C++

From: Rainer Deyke (root_at_[hidden])
Date: 2002-02-26 16:03:12

----- Original Message -----
From: "Kevin S. Van Horn" <kevin.vanhorn_at_[hidden]>
To: <boost_at_[hidden]>
Sent: Tuesday, February 26, 2002 10:50 AM
Subject: Re: [boost] Yacc, lex, and C++

> David Abrahams writes:
>
> > Most good C++ parsers use recursive descent, as I understand it.
>
> I don't think so.  A recursive descent parser has to be
nondeterministic
> -- and hence do LOTS of backtracking -- in order to parse
expressions
> involving infix operators.

I don't think so.  It's really quite trivial for a handwritten
recursive descent parser to parse infix expressions with no
backtracking and single token lookahead:

code_object parse_arithmetic_expression(iterator& iter, iterator end)
{
  code_object code = parse_term(iter);
  for (;;) {
    if (iter == end) return code;
    if (*iter == "+") {
      ++iter; // skip operator
      code = make_addition(code, parse_term(iter));
    } else if (*iter == "-") {
      ++iter; // skip operator
      code = make_addition(code, parse_term(iter));
    } else
      return code;
    }
  }
}

Or have I misunderstood you entirely?

--
Rainer Deyke | root_at_[hidden] | http://rainerdeyke.com