parser Class Reference

#include <parse.hpp>

Public Types
enum	kind : int {   eof, identifier, integer, floating_point,   string, plus ='+', minus ='-', times ='*',   slash ='/', lparen = '(', rparen =')', equal ='=',   comma =',' }

Public Member Functions
	parser (std::istream &input)
bool	get_statement (std::ostream &output)

Private Member Functions
std::string	charify (char c)
bool	get_float (std::string const &token, node &result)
bool	get_integer (std::string const &token, node &result)
bool	get_expr (node &result)
bool	get_add_expr (node &result)
bool	get_mul_expr (node &result)
bool	get_primary (node &result)
bool	get_unary (node &result)
void	get_definition (std::string &name, identifier_list &parameters, node &definition)
kind	get_token (std::string &token)
void	get_identifier (std::string &identifier)
void	get_expr_list (node_list &result)
template<class OutputIterator >
OutputIterator	get_namelist (OutputIterator output)
void	get_escape (std::string &str)
void	get_string (std::string &result, char delimiter)
void	push_back (std::string const &token, kind k)
bool	isalpha (char c) const
bool	isalnum (char c) const
bool	isdigit (char c) const
bool	isprint (char c) const

Private Attributes
std::istream &	input_
	Share the input stream. More...
std::ctype< char > const &	ctype_
	Cache the ctype facet for checking character categories. More...
std::string	token_
	One token push-back. More...
kind	kind_
	The kind of token that was pushed back. More...

Detailed Description

Parser class template. The parser reads tokens from an input stream. A token can be a keyword, numeric literal, identifier, or symbol (operator or punctuator). Symbols can have multiple characters (e.g., :=).

Because the recursive-descent parser can examine too many tokens from the input stream, it keeps a push-back token. Once the parser knows it has gone too far, it pushes back the most recently read token. The next call to get_token() retrieves the pushed-back token.

Only one push-back is available, which limits the complexity of the syntax.

Definition at line 26 of file parse.hpp.

Member Enumeration Documentation

enum parser::kind : int

Token kind. Declare a name for each single-character token, to ensure the enumerated type can represent any operator or punctuator character.

Enumerator
eof
identifier
integer
floating_point
string
plus
minus
times
slash
lparen
rparen
equal
comma

Definition at line 32 of file parse.hpp.

            : int { eof, identifier, integer, floating_point, string,
    plus='+', minus='-', times='*', slash='/', lparen = '(', rparen=')', equal='=',
    comma=','};

Constructor & Destructor Documentation

parser::parser

(

std::istream &

input

)

Constructor. Save the input stream.

Parameters

input

The input stream

Definition at line 10 of file parse.cpp.

: input_(input),
  ctype_(std::use_facet<std::ctype<char> >(input.getloc())),
  token_(),
  kind_()
{}

Member Function Documentation

std::string parser::charify ( char  c )

private

Convert a characer to a readable form.

Parameters

c	The character

Returns

A C++-style character literal that ensures c is readable.

Definition at line 17 of file parse.cpp.

References isprint().

Referenced by get_identifier(), and get_token().

{
  if (c == '\a') return R"('\a')";
  if (c == '\b') return R"('\b')";
  if (c == '\f') return R"('\f')";
  if (c == '\n') return R"('\n')";
  if (c == '\r') return R"('\r')";
  if (c == '\t') return R"('\t')";
  if (c == '\v') return R"('\v')";
  if (c == '\'') return R"('\'')";
  if (c == '\\') return R"('\\')";

  if (isprint(c))
    return std::string{"\'"} + std::string(1,c) + "\'";
  else {
    std::ostringstream stream{};
    stream << "'\\x" << std::hex;
    stream.fill('0');
    stream.width(2);
    stream << (std::char_traits<char>::to_int_type(c) & 0xFF) << '\'';
    return stream.str();
  }
}

bool parser::get_add_expr ( node &  result )

private

Parse an addition expression

ADD_EXPR ::= MUL_EXPR | ADD_EXPR + MUL_EXPR | ADD_EXPR - MUL_EXPR

Parameters

result

Store the result here

Returns

true to continue parsing or false to stop (end of file or error)

Definition at line 312 of file parse.cpp.

References get_mul_expr(), get_token(), and push_back().

Referenced by get_expr().

{
  if (not get_mul_expr(result))
    return false;
  std::string token{};
  while (kind k = get_token(token)) {
    if (k != '+' and k != '-') {
      push_back(token, k);
      return true;
    } else {
      node right{};
      if (not get_mul_expr(right))
        throw syntax_error{"unterminated expression. Expected a multiplicative-expression after " + token};
      result = node(result, k, right);
    }
  }
  return true;
}

void parser::get_definition ( std::string &  name, identifier_list &  parameters, node &  definition  )

private

Parse a function or variable definition A variable is just like a function that takes no parameters.

DEFINITION ::= DEF IDENTIFIER OPT_PARAMETERS '=' EXPR
OPT_PARAMETERS ::= emtpy | '(' OPT_IDENTIFIER_LIST ')'
OPT_IDENTIFIER_LIST ::=  empty | IDENTIFIER_LIST
IDENTIFIER_LIST ::= IDENTIFIER | IDENTIFIER_LIST ',' IDENTIFIER

Parameters

[out]	name	Store the variable or function name here
[out]	parameters	Store the list of parameter names here
[out]	definition	Store the definition expression here

Definition at line 241 of file parse.cpp.

References get_expr(), get_namelist(), get_token(), and identifier.

Referenced by get_statement().

{
  // Define a variable.
  kind k = get_token(name);
  if (k != identifier)
    throw syntax_error{"expected IDENTIFIER, got " + name};

  std::string token{};
  k = get_token(token);
  if (k == '(') {
    get_namelist(std::back_inserter(parameters));
    k = get_token(token);
  }

  if (k != '=')
    throw syntax_error{"expected = in definition, got " + token};

  if (not get_expr(definition))
    throw syntax_error{"expected exprssion in assignment"};
}

void parser::get_escape ( std::string &  str )

private

Interpret a backslash escape sequence. The caller must have read the backslash already.

Parameters

[out]

str

Write the string equivalent of the escape sequence at the end of this string

Definition at line 41 of file parse.cpp.

References ctype_, and input_.

Referenced by get_string().

{
  char c;
  if (not input_.get(c))
    throw syntax_error{"incomplete escape"};
  if (c == '\n')
    return;

  if (c == 'a')
    str += '\a';
  else if (c == 'b')
    str += '\b';
  else if (c == 'n')
    str += '\n';
  else if (c == 'f')
    str += '\f';
  else if (c == 'r')
    str += '\r';
  else if (c == 't')
    str += '\t';
  else if (c == 'v')
    str += '\v';
  else if (c == 'x') {
    // hexadecimal sequence
    std::string digits{};
    while(input_.get(c) and ctype_.is(ctype_.xdigit, c))
      digits += c;
    if (input_)
      input_.unget();
    unsigned long value{std::stoul(digits, nullptr, 16)};
    str += static_cast<char>(static_cast<unsigned char>(value));
  } else if (c >= '0' and c <= '7') {
    // octal sequence
    std::string digits{};
    for (int i = 0; i < 3 and input_.get(c) and c >= '0' and c <= '7'; ++i)
      digits += c;
    if (input_ or c < '0' or c > '7')
      input_.unget();
    int value{std::stoi(digits, nullptr, 8)};
    str += static_cast<char>(static_cast<unsigned char>(value));
  } else {
    str += c;
  }
}

bool parser::get_expr ( node &  result )

private

Parse an expression

Parameters

result

Store the result here

Returns

true to continue parsing or false to stop (end of file or error)

Definition at line 307 of file parse.cpp.

References get_add_expr().

Referenced by get_definition(), get_expr_list(), get_primary(), and get_statement().

{
  return get_add_expr(result);
}

void parser::get_expr_list ( node_list &  result )

private

Parse a comma-separated expression list.

Parameters

[out]

result

Store the result here

Definition at line 371 of file parse.cpp.

References get_expr(), get_token(), and push_back().

Referenced by get_primary().

{
  result.clear();
  std::string token{};
  while (kind k = get_token(token)) {
    if (k == ')')
      return;
    push_back(token, k);
    node expr{};
    if (not get_expr(expr))
      throw syntax_error{"unexpected end of line in function argument"};
    result.push_back(expr);
    k = get_token(token);
    if (k == ')')
      return;
    else if (k != ',')
      throw syntax_error{"expected comma in argument list, got " + token};
  }
  throw syntax_error{"unexpected end of line in function argument list"};
}

bool parser::get_float ( std::string const &  token, node &  result  )

private

Parse a floating number.

Parameters

token	The token to parse
result	Store the number here

Returns

true if token is a valid number or false for an error

Definition at line 230 of file parse.cpp.

Referenced by get_primary().

{
  std::istringstream stream{token};
  // If the value overflows or is otherwise invalid, return false.
  double value{};
  if (not (stream >> value))
    return false;
  result = node{number{value}};
  return true;
}

void parser::get_identifier ( std::string &  identifier )

private

Parse an identifer.

Parameters

identifier

Store the identifier here.

Precondition

first input character is alphabetic

Definition at line 102 of file parse.cpp.

References charify(), input_, isalnum(), and isalpha().

Referenced by get_token().

{
  identifier.clear();
  char c{};
  if (not input_.get(c))
    return;
  if (not isalpha(c))
    throw syntax_error{"expected alphabetic, got " + charify(c)};
  identifier += c;
  while (input_.get(c)) {
    if (not isalnum(c)) {
      input_.unget();
      return;
    }
    identifier += c;
  }
  return;
}

bool parser::get_integer ( std::string const &  token, node &  result  )

private

Parse an integer.

Parameters

token	The token to parse
result	Store the number here

Returns

true if token is a valid number or false for an error

Definition at line 219 of file parse.cpp.

Referenced by get_primary().

{
  std::istringstream stream{token};
  // If the value overflows or is otherwise invalid, return false.
  long long value{};
  if (not (stream >> value))
    return false;
  result = node{number{value}};
  return true;
}

bool parser::get_mul_expr ( node &  result )

private

Parse a multiplicative expression.

MUL_EXPR ::= UNARY | MUL_EXPR + UNARY | MUL_EXPR - UNARY

Parameters

result

Store the result here

Returns

true to continue parsing or false to stop (end of file or error)

Definition at line 331 of file parse.cpp.

References get_token(), get_unary(), and push_back().

Referenced by get_add_expr().

{
  if (not get_unary(result))
    return false;
  std::string token{};
  while (kind k = get_token(token)) {
    if (k != '*' and k != '/') {
      push_back(token, k);
      return true;
    } else {
      node right{};
      if (not get_unary(right))
        throw syntax_error{"unterminated expression. Expected a unary-expression after " + token};
      result = node(result, k, right);
    }
  }
  return true;
}

template<class OutputIterator >

OutputIterator parser::get_namelist ( OutputIterator  output )

private

Parse a list of parameter names. Names are identifiers, separated by commas. The list can be empty. This is a template so the container type is unimportant. Any output iterator will do.

Parameters

[out]

output

Store the identifiers here

Returns

a copy of output after storing all the identifiers

Definition at line 216 of file parse.hpp.

References get_token(), and identifier.

Referenced by get_definition().

{
  std::string token{};
  while (kind k = get_token(token)) {
    if (k == ')')
      return output;
    else if (k != identifier)
      throw syntax_error{"expected function parameter, got " + token};
    else {
      *output = token;
      ++output;

      k = get_token(token);
      if (k == ')')
        return output;
      if (k != ',')
        throw syntax_error{"expected comma in function paramter list, got " + token};
    }
  }
  throw syntax_error{"unexpected end of line in function parameter list"};
}

bool parser::get_primary ( node &  result )

private

Parse a primary expression.

PRIMARY ::= NUMBER | IDENTIFIER | '(' EXPR ')' | FUNCTION_CALL
FUNCTION_CALL ::= IDENTIFIER '(' OPT_EXPR_LIST ')'
OPT_EXPR_LIST ::= empty | EXPR_LIST
EXPR_LIST ::= EXPR | EXPR_LIST ',' EXPR

Parameters

result

Store the result here

Returns

true to continue parsing or false to stop (end of file or error)

Definition at line 392 of file parse.cpp.

References eof, floating_point, get_expr(), get_expr_list(), get_float(), get_integer(), get_token(), identifier, integer, and push_back().

Referenced by get_unary().

{
  std::string token{};
  kind k = get_token(token);
  if (k == eof)
    return false;

  if (k == '(') {
    // Parenthesized expression
    if (not get_expr(result))
      throw syntax_error{"expected expression, got end of line"};
    k = get_token(token);
    if (k != ')')
      throw syntax_error{"expected ')', got " + token};
    else
      return true;
  }

  if (k == integer) {
    // Integer literal
    if (not get_integer(token, result))
      throw syntax_error{"Invalid integer literal: " + token};
    return true;
  }

  if (k == floating_point) {
    // Integer literal
    if (not get_float(token, result))
      throw syntax_error{"Invalid integer literal: " + token};
    return true;
  }

  if (k == identifier) {
    // Identifier: variable or function call
    std::string next{};
    k = get_token(next);
    if (k == '(') {
        // function call
      node_list arguments{};
      get_expr_list(arguments);
      result = node{std::move(token), std::move(arguments)};
    } else {
      static const node_list no_arguments;
      // Variable reference or function call with no arguments
      push_back(next, k);
      result = node{std::move(token), no_arguments};
    }
    return true;
  }
  throw syntax_error{"expected a primary, got " + token};
}

bool parser::get_statement

(

std::ostream &

output

)

Read one statement and store the parse tree in result. If the statement is an assignment or function definition, store the variable or function. If the statement is an expression, print the result to output.

STATEMENT ::= DEFINITION | QUIT | EXPR | SAVE | LOAD
SAVE ::= "save" FILENAME
LOAD ::= "load" FILENAME
FILENAME ::= quoted-string

Parameters

output

The output stream.

Returns

true to continue or false to end the loop

Exceptions

parse_error

for various syntax and other errors

Definition at line 262 of file parse.cpp.

References eof, node::evaluate(), get_definition(), get_expr(), get_token(), identifier, load_library(), push_back(), save_library(), and set_function().

{
  std::string token{};
  kind k(get_token(token));
  if (k == eof)
    return false;

  if (k == identifier and token == "def") {
    node definition{};
    identifier_list parameters{};
    get_definition(token, parameters, definition);
    set_function(token, node{std::move(parameters), definition});
    return true;
  }

  if (k == identifier and token == "quit")
    std::exit(0);

  if (k == identifier and token == "save") {
    std::string filename{};
    if (get_token(filename) != string)
      throw syntax_error{"expected FILENAME after save, got " + token};
    save_library(filename);
    output << "Library saved to " << filename << '\n';
  }

  if (k == identifier and token == "load") {
    std::string filename{};
    if (get_token(filename) != string)
      throw syntax_error{"expected FILENAME after load, got " + token};
    load_library(filename);
    output << "Library loaded from " << filename << '\n';
  }
  // Otherwise, the statement must be an expression.
  push_back(token, k);
  node n{};
  if (not get_expr(n))
    return false;
  else {
    // Evaluate the expression and print the result.
    output << n.evaluate() << '\n';
    return true;
  }
}

void parser::get_string ( std::string &  result, char  delimiter  )

private

Parse a quoted string. The caller passes the quote character in the delimiter argument.

Parameters

[out]	result	Store the token here.
[in]	delimiter	The quote character (' or ")

Definition at line 86 of file parse.cpp.

References get_escape(), and input_.

Referenced by get_token().

{
  char c{};
  while (input_.get(c)) {
    if (c == delimiter)
      return;
    else if (c == '\\')
      get_escape(result);
    else if (c == '\n')
      throw syntax_error{"unterminated string"};
    else
      result += c;
  }
  throw syntax_error{"unterminated string"};
}

parser::kind parser::get_token ( std::string &  token )

private

Parse a token. A token can be a keyword, a literal or a symbol.

TOKEN ::= IDENTIFIER | NUMBER | SYMBOL | STRING
IDENTIIFER ::= ALPHA (ALPHA | DIGIT)*
NUMBER ::= INTEGER | FLOATING-POINT
INTEGER ::= DIGIT+
FLOATING_POINT ::= DIGIT+ '.' DIGITS+ ('E' SIGN? DIGITS+)? | DIGIT+ ('.' DIGITS+)? 'E' SIGN? DIGITS+
SYMBOL ::= '+' | '-' | '*' | '/' | '%' | '(' | ')' | '=' | ','

Parameters

token

Store the text of the token here.

Returns

the token kind

Definition at line 130 of file parse.cpp.

References charify(), eof, floating_point, get_identifier(), get_string(), identifier, input_, integer, isalpha(), kind_, string, and token_.

Referenced by get_add_expr(), get_definition(), get_expr_list(), get_mul_expr(), get_namelist(), get_primary(), get_statement(), and get_unary().

{
  if (not token_.empty())
  {
    kind result(kind_);
    token = token_;

    token_.clear();
    kind_ = eof;

    return result;
  }

  char c{};
  if (not (input_ >> c)) {
    token = "end of line";
    return eof;
  }
  if (isalpha(c)) {
    input_.unget();
    get_identifier(token);
    return identifier;
  }

  if (c == '\'' or c == '"') {
    // Quoted string
    token.clear();
    get_string(token, c);
    return string;
  }

  // Get a numeric literal.
  token.clear();
  if (c == '+' or c == '-' or c == '*' or c == '/' or c == '%' or c == '(' or c == ')' or c == '=' or c == ',') {
    token += c;
    return static_cast<kind>(c);
  }

  if (c < '0' or c > '9') {
    input_.unget();
    throw syntax_error{"expected digit, got " + charify(c)};
  }

  kind k = integer;

  while (c >= '0' and c <= '9') {
    token += c;
    if (not input_.get(c))
      return k;
  }
  if (c == '.') {
    k = floating_point;
    token += c;
    if (not input_.get(c))
      throw syntax_error{"unterminated number: expected digit after the decimal point"};
    if (c < '0' or c > '9') {
      input_.unget();
      throw syntax_error{"expected digit after decimal point, got " + charify(c)};
    }
    while (c >= '0' and c <= '9') {
      token += c;
      if (not input_.get(c))
        return k;
    }
  }
  if (c == 'e' or c == 'E') {
    k = floating_point;
    token += c;
    if (not input_.get(c))
      throw syntax_error{"unterminated number: expected digit in the exponent"};
    if (c == '-' or c == '+') {
      token += c;
      if (not input_.get(c))
        throw syntax_error{"unterminated number: expected digit after sign in the exponent"};
    }
    if (c < '0' or c > '9') {
      input_.unget();
      throw syntax_error{"expected digit in the exponent, got " + charify(c)};
    }
    while (c >= '0' and c <= '9') {
      token += c;
      if (not input_.get(c))
        return k;
    }
  }
  input_.unget();
  return k;
}

bool parser::get_unary ( node &  result )

private

Parse a unary expression.

UNARY ::= '-' PRIMARY | '+' PRIMARY | PRIMARY

Parameters

result

Store the result here

Returns

true to continue parsing or false to stop (end of file or error)

Definition at line 350 of file parse.cpp.

References eof, get_primary(), get_token(), and push_back().

Referenced by get_mul_expr().

{
  std::string token{};
  kind k = get_token(token);
  if (k == eof)
    return false;
  if (k == '-') {
    if (not get_primary(result))
      throw syntax_error{"expected primary after unary " + token + ", got end of line"};
    result = node(k, result);
    return true;
  } else if (k == '+') {
    if (not get_primary(result))
      throw syntax_error{"expected primary after unary +, got end of line"};
    return true;
  } else {
    push_back(token, k);
    return get_primary(result);
  }
}

bool parser::isalnum ( char  c ) const

inlineprivate

Return true if c is alphanumeric. Use the locale of the input stream.

Parameters

c	The character to test.

Definition at line 190 of file parse.hpp.

References ctype_.

Referenced by get_identifier().

{ return ctype_.is(ctype_.alnum, c); }

bool parser::isalpha ( char  c ) const

inlineprivate

Return true if c is alphabetic. Use the locale of the input stream.

Parameters

c	The character to test.

Definition at line 185 of file parse.hpp.

References ctype_.

Referenced by get_identifier(), and get_token().

{ return ctype_.is(ctype_.alpha, c); }

bool parser::isdigit ( char  c ) const

inlineprivate

Return true if c is a digit. Use the locale of the input stream.

Parameters

c	The character to test.

Definition at line 195 of file parse.hpp.

References ctype_.

{ return ctype_.is(ctype_.digit, c); }

bool parser::isprint ( char  c ) const

inlineprivate

Return true if c is printable. Use the locale of the input stream.

Parameters

c	The character to test.

Definition at line 200 of file parse.hpp.

References ctype_.

Referenced by charify().

{ return ctype_.is(ctype_.print, c); }

void parser::push_back ( std::string const &  token, kind  k  )

private

Push back a token. The next call to get_token() will return the pushed-back token.

Parameters

token	The token to push back.
k	The kind of token being pushed back

Definition at line 121 of file parse.cpp.

References eof, kind_, and token_.

Referenced by get_add_expr(), get_expr_list(), get_mul_expr(), get_primary(), get_statement(), and get_unary().

{
  kind_ = k;
  if (kind_ == eof)
    token_ = "end of line";
  else
    token_ = token;
}

Member Data Documentation

std::ctype<char> const& parser::ctype_

private

Cache the ctype facet for checking character categories.

Definition at line 203 of file parse.hpp.

Referenced by get_escape(), isalnum(), isalpha(), isdigit(), and isprint().

std::istream& parser::input_

private

Share the input stream.

Definition at line 202 of file parse.hpp.

Referenced by get_escape(), get_identifier(), get_string(), and get_token().

kind parser::kind_

private

The kind of token that was pushed back.

Definition at line 205 of file parse.hpp.

Referenced by get_token(), and push_back().

std::string parser::token_

private

One token push-back.

Definition at line 204 of file parse.hpp.

Referenced by get_token(), and push_back().

---

The documentation for this class was generated from the following files:

• parse.hpp
• parse.cpp