Calculator  Step 3
Public Types | Public Member Functions | Private Member Functions | Private Attributes | List of all members
parser Class Reference

#include <parse.hpp>

Public Types

enum  kind : int {
  eof, identifier, number, plus ='+',
  minus ='-', times ='*', slash ='/', lparen = '(',
  rparen =')', equal ='='
}
 

Public Member Functions

 parser (std::istream &input)
 
bool get_expr (node &result)
 

Private Member Functions

std::string charify (char c)
 
bool get_number (std::string const &token, node &result)
 
bool get_add_expr (node &result)
 
bool get_mul_expr (node &result)
 
bool get_primary (node &result)
 
bool get_unary (node &result)
 
kind get_token (std::string &token)
 
void get_identifier (std::string &identifier)
 
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 30 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 

Definition at line 36 of file parse.hpp.

Constructor & Destructor Documentation

parser::parser ( std::istream &  input)

Constructor. Save the input stream.

Parameters
inputThe input stream

Definition at line 6 of file parse.cpp.

7 : input_(input),
8  ctype_(std::use_facet<std::ctype<char> >(input.getloc())),
9  token_(),
10  kind_()
11 {}
std::string token_
One token push-back.
Definition: parse.hpp:143
std::istream & input_
Share the input stream.
Definition: parse.hpp:141
kind kind_
The kind of token that was pushed back.
Definition: parse.hpp:144
std::ctype< char > const & ctype_
Cache the ctype facet for checking character categories.
Definition: parse.hpp:142

Member Function Documentation

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

Convert a characer to a readable form.

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

Definition at line 13 of file parse.cpp.

References isprint().

Referenced by get_identifier(), and get_token().

14 {
15  if (c == '\a') return R"('\a')";
16  if (c == '\b') return R"('\b')";
17  if (c == '\f') return R"('\f')";
18  if (c == '\n') return R"('\n')";
19  if (c == '\r') return R"('\r')";
20  if (c == '\t') return R"('\t')";
21  if (c == '\v') return R"('\v')";
22  if (c == '\'') return R"('\'')";
23  if (c == '\\') return R"('\\')";
24 
25  if (isprint(c))
26  return std::string{"\'"} + std::string(1,c) + "\'";
27  else {
28  std::ostringstream stream{};
29  stream << "'\\x" << std::hex;
30  stream.fill('0');
31  stream.width(2);
32  stream << (std::char_traits<char>::to_int_type(c) & 0xFF) << '\'';
33  return stream.str();
34  }
35 }
bool isprint(char c) const
Definition: parse.hpp:139
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
resultStore the result here
Returns
true to continue parsing or false to stop (end of file or error)

Definition at line 178 of file parse.cpp.

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

Referenced by get_expr().

179 {
180  if (not get_mul_expr(result))
181  return false;
182  std::string token{};
183  while (kind k = get_token(token)) {
184  if (k != '+' and k != '-') {
185  push_back(token, k);
186  return true;
187  } else {
188  node right{};
189  if (not get_mul_expr(right))
190  throw parse_error{"syntax error: unterminated expression. Expected a multiplicative-expression after " + token};
191  result = node(result, k, right);
192  }
193  }
194  return true;
195 }
Definition: node.hpp:16
void push_back(std::string const &token, kind k)
Definition: parse.hpp:118
kind get_token(std::string &token)
Definition: parse.cpp:56
kind
Definition: parse.hpp:36
bool get_mul_expr(node &result)
Definition: parse.cpp:200
bool parser::get_expr ( node result)

Read one expression and store the parse tree in result.

Parameters
resultWhere to store the parse tree.
Returns
true to continue or false to end the loop
Exceptions
parse_errorfor various syntax and other errors

Definition at line 143 of file parse.cpp.

References eof, get_add_expr(), get_token(), identifier, and push_back().

Referenced by get_primary().

144 {
145  std::string token{};
146  kind k(get_token(token));
147  if (k == eof)
148  return false;
149 
150  if (k == identifier and token == "var") {
151  std::string name{};
152  // Define a variable.
153  k = get_token(name);
154  if (k != identifier)
155  throw parse_error{"syntax error: expected IDENTIFIER, but got " + name};
156  k = get_token(token);
157  if (k != '=')
158  throw parse_error{"syntax error: expected =, but got " + token};
159  if (not get_add_expr(result))
160  throw parse_error{"syntax error: expected additive-exprssion in assignment"};
161  result = node(node{std::move(name)}, result);
162  return true;
163  }
164 
165  if (k == identifier and token == "quit")
166  std::exit(0);
167 
168  push_back(token, k);
169  if (not get_add_expr(result))
170  throw parse_error{"syntax error: expected an additive-expression"};
171 
172  return true;
173 }
Definition: node.hpp:16
void push_back(std::string const &token, kind k)
Definition: parse.hpp:118
kind get_token(std::string &token)
Definition: parse.cpp:56
kind
Definition: parse.hpp:36
bool get_add_expr(node &result)
Definition: parse.cpp:178
void parser::get_identifier ( std::string &  identifier)
private

Parse an identifer.

Parameters
identifierStore the identifier here.
Precondition
first input character is alphabetic

Definition at line 37 of file parse.cpp.

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

Referenced by get_token().

38 {
39  identifier.clear();
40  char c{};
41  if (not input_.get(c))
42  return;
43  if (not isalpha(c))
44  throw parse_error{"syntax error: expected alphabetic, got " + charify(c)};
45  identifier += c;
46  while (input_.get(c)) {
47  if (not isalnum(c)) {
48  input_.unget();
49  return;
50  }
51  identifier += c;
52  }
53  return;
54 }
std::string charify(char c)
Definition: parse.cpp:13
bool isalpha(char c) const
Definition: parse.hpp:124
std::istream & input_
Share the input stream.
Definition: parse.hpp:141
bool isalnum(char c) const
Definition: parse.hpp:129
bool parser::get_mul_expr ( node result)
private

Parse a multiplicative expression.

MUL_EXPR ::= UNARY | MUL_EXPR + UNARY | MUL_EXPR - UNARY
Parameters
resultStore the result here
Returns
true to continue parsing or false to stop (end of file or error)

Definition at line 200 of file parse.cpp.

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

Referenced by get_add_expr().

201 {
202  if (not get_unary(result))
203  return false;
204  std::string token{};
205  while (kind k = get_token(token)) {
206  if (k != '*' and k != '/') {
207  push_back(token, k);
208  return true;
209  } else {
210  node right{};
211  if (not get_unary(right))
212  throw parse_error{"syntax error: unterminated expression. Expected a unary-expression after " + token};
213  result = node(result, k, right);
214  }
215  }
216  return true;
217 }
Definition: node.hpp:16
void push_back(std::string const &token, kind k)
Definition: parse.hpp:118
bool get_unary(node &result)
Definition: parse.cpp:222
kind get_token(std::string &token)
Definition: parse.cpp:56
kind
Definition: parse.hpp:36
bool parser::get_number ( std::string const &  token,
node result 
)
private

Parse a floating number.

Parameters
tokenThe token to parse
resultStore the number here
Returns
true if token is a valid number or false for an error

Definition at line 129 of file parse.cpp.

Referenced by get_primary().

130 {
131  std::istringstream stream{token};
132  // If the value overflows or is otherwise invalid, return false.
133  double value;
134  if (not (stream >> value))
135  return false;
136  result = node(value);
137  return true;
138 }
Definition: node.hpp:16
bool parser::get_primary ( node result)
private

Parse a primary expression.

PRIMARY ::= NUMBER | IDENTIFIER | '(' EXPR ')'
Parameters
resultStore the result here
Returns
true to continue parsing or false to stop (end of file or error)

Definition at line 244 of file parse.cpp.

References eof, get_expr(), get_number(), get_token(), identifier, and number.

Referenced by get_unary().

245 {
246  std::string token{};
247  if (kind k = get_token(token)) {
248  if (k == '(') {
249  if (not get_expr(result))
250  return false;
251  k = get_token(token);
252  if (k == eof)
253  throw parse_error{"syntax error: EOF when expecting ')'"};
254  else if (k != ')')
255  throw parse_error{"syntax error: expected ')', but got " + token};
256  else
257  return true;
258  } else if (k == number) {
259  if (not get_number(token, result))
260  throw parse_error{"Invalid numeric literal: " + token};
261  return true;
262  } else if (k == identifier) {
263  result = node{std::move(token)};
264  return true;
265  } else {
266  throw parse_error{"syntax error: expected a primary, but got " + token};
267  }
268  }
269  return false;
270 }
bool get_expr(node &result)
Definition: parse.cpp:143
Definition: node.hpp:16
kind get_token(std::string &token)
Definition: parse.cpp:56
kind
Definition: parse.hpp:36
bool get_number(std::string const &token, node &result)
Definition: parse.cpp:129
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
tokenStore the text of the token here.
Returns
the token kind

Definition at line 56 of file parse.cpp.

References charify(), eof, get_identifier(), identifier, input_, isalpha(), kind_, number, and token_.

Referenced by get_add_expr(), get_expr(), get_mul_expr(), get_primary(), and get_unary().

57 {
58  if (not token_.empty())
59  {
60  token = token_;
61  kind result(kind_);
62  token_.clear();
63  kind_ = eof;
64  return result;
65  }
66 
67  char c{};
68  if (not (input_ >> c))
69  return eof;
70  if (isalpha(c)) {
71  input_.unget();
72  get_identifier(token);
73  return identifier;
74  }
75 
76  // Get a numeric literal.
77  token.clear();
78  if (c == '+' or c == '-' or c == '*' or c == '/' or c == '%' or c == '(' or c == ')' or c == '=') {
79  token += c;
80  return static_cast<kind>(c);
81  }
82 
83  if (c < '0' or c > '9') {
84  input_.unget();
85  throw parse_error{"syntax error: expected digit, got " + charify(c)};
86  }
87  while (c >= '0' and c <= '9') {
88  token += c;
89  if (not input_.get(c))
90  return number;
91  }
92  if (c == '.') {
93  token += c;
94  if (not input_.get(c))
95  throw parse_error{"unterminated number: expected digit after the decimal point"};
96  if (c < '0' or c > '9') {
97  input_.unget();
98  throw parse_error{"syntax error: expected digit after decimal point, got " + charify(c)};
99  }
100  while (c >= '0' and c <= '9') {
101  token += c;
102  if (not input_.get(c))
103  return number;
104  }
105  }
106  if (c == 'e' or c == 'E') {
107  token += c;
108  if (not input_.get(c))
109  throw parse_error{"unterminated number: expected digit in the exponent"};
110  if (c == '-' or c == '+') {
111  token += c;
112  if (not input_.get(c))
113  throw parse_error{"unterminated number: expected digit after sign in the exponent"};
114  }
115  if (c < '0' or c > '9') {
116  input_.unget();
117  throw parse_error{"syntax error: expected digit in the exponent, got " + charify(c)};
118  }
119  while (c >= '0' and c <= '9') {
120  token += c;
121  if (not input_.get(c))
122  return number;
123  }
124  }
125  input_.unget();
126  return number;
127 }
void get_identifier(std::string &identifier)
Definition: parse.cpp:37
std::string charify(char c)
Definition: parse.cpp:13
bool isalpha(char c) const
Definition: parse.hpp:124
std::string token_
One token push-back.
Definition: parse.hpp:143
std::istream & input_
Share the input stream.
Definition: parse.hpp:141
kind kind_
The kind of token that was pushed back.
Definition: parse.hpp:144
kind
Definition: parse.hpp:36
bool parser::get_unary ( node result)
private

Parse a unary expression.

UNARY ::= '-' PRIMARY | '+' PRIMARY | PRIMARY
Parameters
resultStore the result here
Returns
true to continue parsing or false to stop (end of file or error)

Definition at line 222 of file parse.cpp.

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

Referenced by get_mul_expr().

223 {
224  std::string token{};
225  if (kind k = get_token(token)) {
226  if (k == '-') {
227  if (not get_primary(result))
228  return false;
229  result = node(k, result);
230  return true;
231  } else if (k == '+') {
232  return get_primary(result);
233  } else {
234  push_back(token, k);
235  return get_primary(result);
236  }
237  }
238  return false;
239 }
Definition: node.hpp:16
void push_back(std::string const &token, kind k)
Definition: parse.hpp:118
bool get_primary(node &result)
Definition: parse.cpp:244
kind get_token(std::string &token)
Definition: parse.cpp:56
kind
Definition: parse.hpp:36
bool parser::isalnum ( char  c) const
inlineprivate

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

Parameters
cThe character to test.

Definition at line 129 of file parse.hpp.

References ctype_.

Referenced by get_identifier().

129 { return ctype_.is(ctype_.alnum, c); }
std::ctype< char > const & ctype_
Cache the ctype facet for checking character categories.
Definition: parse.hpp:142
bool parser::isalpha ( char  c) const
inlineprivate

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

Parameters
cThe character to test.

Definition at line 124 of file parse.hpp.

References ctype_.

Referenced by get_identifier(), and get_token().

124 { return ctype_.is(ctype_.alpha, c); }
std::ctype< char > const & ctype_
Cache the ctype facet for checking character categories.
Definition: parse.hpp:142
bool parser::isdigit ( char  c) const
inlineprivate

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

Parameters
cThe character to test.

Definition at line 134 of file parse.hpp.

References ctype_.

134 { return ctype_.is(ctype_.digit, c); }
std::ctype< char > const & ctype_
Cache the ctype facet for checking character categories.
Definition: parse.hpp:142
bool parser::isprint ( char  c) const
inlineprivate

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

Parameters
cThe character to test.

Definition at line 139 of file parse.hpp.

References ctype_.

Referenced by charify().

139 { return ctype_.is(ctype_.print, c); }
std::ctype< char > const & ctype_
Cache the ctype facet for checking character categories.
Definition: parse.hpp:142
void parser::push_back ( std::string const &  token,
kind  k 
)
inlineprivate

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

Parameters
tokenThe token to push back.
kThe kind of token being pushed back

Definition at line 118 of file parse.hpp.

References kind_, and token_.

Referenced by get_add_expr(), get_expr(), get_mul_expr(), and get_unary().

118 { token_ = token; kind_ = k; }
std::string token_
One token push-back.
Definition: parse.hpp:143
kind kind_
The kind of token that was pushed back.
Definition: parse.hpp:144

Member Data Documentation

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

Cache the ctype facet for checking character categories.

Definition at line 142 of file parse.hpp.

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

std::istream& parser::input_
private

Share the input stream.

Definition at line 141 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 144 of file parse.hpp.

Referenced by get_token(), and push_back().

std::string parser::token_
private

One token push-back.

Definition at line 143 of file parse.hpp.

Referenced by get_token(), and push_back().


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