parser Class Reference

#include <parse.hpp>

List of all members.

Public Types
enum	kind {   eof, identifier, number, 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_number (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.
std::ctype< char > const &	ctype_
	Cache the ctype facet for checking character categories.
std::string	token_
	One token push-back.
kind	kind_
	The kind of token that was pushed back.

---

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 25 of file parse.hpp.

---

Member Enumeration Documentation

enum parser::kind

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
number
string
plus
minus
times
slash
lparen
rparen
equal
comma

Definition at line 31 of file parse.hpp.

            { eof, identifier, number, 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

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 246 of file parse.cpp.

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

Referenced by parse_loop().

{
  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(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;
  }
}

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 "\'\\a\'";
  if (c == '\b') return "\'\\b\'";
  if (c == '\f') return "\'\\f\'";
  if (c == '\n') return "\'\\n\'";
  if (c == '\r') return "\'\\r\'";
  if (c == '\t') return "\'\\t\'";
  if (c == '\v') return "\'\\v\'";
  if (c == '\'') return "\'\\'\'";
  if (c == '\\') return "\'\\\\\'";

  if (isprint(c))
    return std::string("\'") + 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_number	(	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 214 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(value);
  return true;
}

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 291 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);
}

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 296 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;
}

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 315 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;
}

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 376 of file parse.cpp.

References eof, get_expr(), get_expr_list(), get_number(), get_token(), identifier, number, 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 == number) {
    // Numeric literal
    if (not get_number(token, result))
      throw syntax_error("Invalid numeric 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(token, arguments);
    } else {
      static const node_list no_arguments;
      // Variable reference or function call with no arguments
      push_back(next, k);
      result = node(token);
    }
    return true;
  }
  throw syntax_error("expected a primary, got " + token);
}

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 334 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);
  }
}

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 225 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");
}

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 ::= 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, get_identifier(), get_string(), identifier, input_, isalpha(), kind_, number, 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 kind(c);
  }

  if (c < '0' or c > '9') {
    input_.unget();
    throw syntax_error("expected digit, got " + charify(c));
  }
  while (c >= '0' and c <= '9') {
    token += c;
    if (not input_.get(c))
      return number;
  }
  if (c == '.') {
    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 number;
    }
  }
  if (c == 'e' or c == 'E') {
    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 number;
    }
  }
  input_.unget();
  return number;
}

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;
}

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 355 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");
}

template<class OutputIterator>

OutputIterator parser::get_namelist

(

OutputIterator

output

)

[inline, 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 207 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");
}

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::strtoul(digits.c_str(), 0, 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();
    unsigned long value(std::strtoul(digits.c_str(), 0, 8));
    str += static_cast<char>(static_cast<unsigned char>(value));
  } else {
    str += c;
  }
}

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");
}

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;
}

bool parser::isalpha

(

char

c

)

const [inline, private]

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

Parameters:

c

The character to test.

Definition at line 176 of file parse.hpp.

References ctype_.

Referenced by get_identifier(), and get_token().

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

bool parser::isalnum

(

char

c

)

const [inline, private]

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

Parameters:

c

The character to test.

Definition at line 181 of file parse.hpp.

References ctype_.

Referenced by get_identifier().

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

bool parser::isdigit

(

char

c

)

const [inline, private]

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

Parameters:

c

The character to test.

Definition at line 186 of file parse.hpp.

References ctype_.

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

bool parser::isprint

(

char

c

)

const [inline, private]

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

Parameters:

c

The character to test.

Definition at line 191 of file parse.hpp.

References ctype_.

Referenced by charify().

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

---

Member Data Documentation

std::istream& parser::input_ [private]

Share the input stream.

Definition at line 193 of file parse.hpp.

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

std::ctype<char> const& parser::ctype_ [private]

Cache the ctype facet for checking character categories.

Definition at line 194 of file parse.hpp.

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

std::string parser::token_ [private]

One token push-back.

Definition at line 195 of file parse.hpp.

Referenced by get_token(), and push_back().

kind parser::kind_ [private]

The kind of token that was pushed back.

Definition at line 196 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

---