#include <parse.hpp>

Public Types
enum	kind : int { eof, identifier, number, 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	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 25 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
number
plus
minus
times
slash
lparen
rparen
equal
comma

Definition at line 31 of file parse.hpp.

             : int { eof, identifier, number,
     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 213 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 157 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"};
 }

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 208 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 272 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"};
 }

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 41 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_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 232 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 193 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_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 146 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_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 293 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{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

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

References eof, node::evaluate(), get_definition(), get_expr(), get_token(), identifier, push_back(), 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);
 
   // 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;
   }
 }

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

References charify(), eof, get_identifier(), identifier, input_, isalpha(), kind_, number, 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;
   }
 
   // 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;
 }

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

References ctype_.

Referenced by get_identifier().

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

parser::ctype_

std::ctype< char > const & ctype_

Cache the ctype facet for checking character categories.

Definition: parse.hpp:180

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

References ctype_.

Referenced by get_identifier(), and get_token().

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

parser::ctype_

std::ctype< char > const & ctype_

Cache the ctype facet for checking character categories.

Definition: parse.hpp:180

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

References ctype_.

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

parser::ctype_

std::ctype< char > const & ctype_

Cache the ctype facet for checking character categories.

Definition: parse.hpp:180

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

References ctype_.

Referenced by charify().

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

parser::ctype_

std::ctype< char > const & ctype_

Cache the ctype facet for checking character categories.

Definition: parse.hpp:180

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

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

std::istream& parser::input_

private

Share the input stream.

Definition at line 179 of file parse.hpp.

Referenced by get_identifier(), and get_token().

kind parser::kind_

private

The kind of token that was pushed back.

Definition at line 182 of file parse.hpp.

Referenced by get_token(), and push_back().

std::string parser::token_

private

One token push-back.

Definition at line 181 of file parse.hpp.

Referenced by get_token(), and push_back().

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

Public Types

Public Member Functions

Private Member Functions

Private Attributes

Detailed Description

Member Enumeration Documentation

Constructor & Destructor Documentation

Member Function Documentation

Member Data Documentation