reading s-expressions - problem with improper lists
Posted: Fri Sep 02, 2022 9:46 pm
I am writing the (rather simplistic) reader code for `L, and have managed to get it working in all of the tests I've written, except for one: the case of an improper list (a Lisp list in which the last pair is a an ordered pair - that is to say, the CDR of the last pair is an atom rather than a null pointer) with more than two members, such as
In the test results, it is coming out as simply
While this is a minor issue, it is still something I would like to resolve, and getting more eyes on a problem is always a good idea.
The Doctest test in question is:
Code: Select all
(foo bar . quux)Code: Select all
(foo bar quux)Code: Select all
#ifndef ATOM_H
#define ATOM_H
#include <string>
#include <cstdint>
class Atom
{
public:
Atom() {};
virtual ~Atom() {};
virtual std::string to_string() {return "";};
};
class Symbol: public Atom
{
private:
std::string literal;
public:
Symbol(std::string s): literal(s) {};
std::string value() {return literal;};
virtual std::string to_string() {return literal;};
};
class Dot: public Atom
{
private:
public:
Dot() {};
};
class RightParen: public Atom
{
private:
public:
RightParen() {};
};
class Number: public Atom
{
private:
public:
Number() {};
};
class Integer64: public Number
{
private:
long long literal;
public:
Integer64(long long i): literal(i) {};
long long value() {return literal;};
virtual std::string to_string() {return std::to_string(literal);};
};
class FP_Double: public Number
{
private:
double literal;
public:
FP_Double(double i): literal(i) {};
double value() {return literal;};
virtual std::string to_string() {return std::to_string(literal);};
};
class Pair: public Atom
{
protected:
Atom *car, *cdr;
public:
Pair(): car(nullptr), cdr(nullptr) {};
Pair(Atom* head): car(head), cdr(nullptr) {};
Pair(Atom* head, Atom* tail): car(head), cdr(tail) {};
virtual ~Pair();
virtual std::string to_string();
void set_car(Atom* a) {car = a;};
void set_cdr(Atom* a) {cdr = a;};
Atom* get_car() {return car;};
Atom* get_cdr() {return cdr;};
};
#endifCode: Select all
#include <iostream>
#include <string>
#include <typeinfo>
#include "atom.h"
Pair::~Pair()
{
if (car != nullptr)
{
delete car;
car = nullptr;
}
if (cdr != nullptr)
{
delete cdr;
cdr = nullptr;
}
}
std::string to_string_list_helper(Pair *p)
{
std::string midpoint = " . ";
if (p == nullptr)
{
return "";
}
if (p->get_car() == nullptr)
{
if (p->get_cdr() == nullptr)
{
return "";
}
else
{
return "()" + midpoint + p->get_cdr()->to_string();
}
}
else if (p->get_cdr() == nullptr)
{
return p->get_car()->to_string();
}
else
{
if (typeid(*(p->get_cdr())) == typeid(Pair))
{
return p->get_car()->to_string()
+ " " + to_string_list_helper(dynamic_cast<Pair *>(p->get_cdr()));
}
else
{
return p->get_car()->to_string() + midpoint + p->get_cdr()->to_string();
}
}
}
std::string Pair::to_string()
{
return "(" + to_string_list_helper(dynamic_cast<Pair *>(this)) + ")";
}
Code: Select all
#include <fstream>
#include <ios>
#include <iostream>
#include <string>
#include <sstream>
#include <typeinfo>
#include "atom.h"
#include "read.h"
void read_src_file(std::stringstream& src, std::ifstream& src_file)
{
while (src_file)
{
src << src_file.rdbuf();
}
}
Atom* read_expression(std::stringstream& src)
{
if (src.eof())
{
throw new unexpected_end_of_file_exception();
}
char ch;
src >> ch;
if (std::iswspace(ch))
{
return read_expression(src);
}
else if (ch == '.')
{
return new Dot();
}
else if (ch == '(')
{
return read_list(src);
}
else if (ch == ')')
{
return new RightParen();
}
else if (std::isdigit(ch))
{
return read_number(ch, src);
}
else
{
return (read_symbol(ch, src));
}
}
Atom* read_list(std::stringstream& src)
{
Atom* head = read_expression(src);
if (head == nullptr)
{
return nullptr;
}
if(typeid(*head) == typeid(RightParen))
{
return nullptr;
}
Atom* tail = read_expression(src);
if (typeid(*tail) == typeid(Dot))
{
return new Pair(head, read_expression(src));
}
else if(typeid(*tail) == typeid(RightParen))
{
return new Pair(head);
}
else
{
return new Pair(head, new Pair(tail, read_list(src)));
}
}
Atom* read_symbol(char start_ch, std::stringstream& src)
{
char ch = start_ch;
std::string ostr = "";
while (!src.eof())
{
ostr += ch;
char temp = src.peek();
if (std::iswspace(temp) || temp == '(' || temp == ')')
{
break;
}
src >> ch;
}
return new Symbol(ostr);
}
Atom* read_number(char start_ch, std::stringstream& src)
{
char ch = start_ch;
std::string ostr = "";
bool fp = false;
while (!src.eof())
{
if (ch == '.')
{
if (fp)
{
throw new invalid_numeric_value_exception();
}
else
{
fp = true;
}
}
ostr += ch;
char temp = src.peek();
if (std::isdigit(temp) || temp == '.')
{
src >> ch;
}
else
{
break;
}
}
if (fp)
{
return new FP_Double(std::strtod(ostr.c_str(), nullptr));
}
else
{
return new Integer64(std::strtol(ostr.c_str(), nullptr, 10));
}
}
Code: Select all
TEST_CASE("improper list of three elements")
{
std::stringstream src;
src << "(foo bar . quux)";
Atom* test = read_expression(src);
Pair* test_list = dynamic_cast<Pair*>(test);
CHECK(typeid(*(test_list->get_car())) == typeid(Symbol));
Symbol* test_car = dynamic_cast<Symbol*>(test_list->get_car());
CHECK(test_car->value() == "foo");
CHECK(typeid(*(test_list->get_cdr())) == typeid(Pair));
Pair* test_cdr = dynamic_cast<Pair*>(test_list->get_cdr());
Atom* test_cadr = test_cdr->get_car();
CHECK(typeid(*test_cadr) == typeid(Symbol));
Symbol* test_symbol = dynamic_cast<Symbol*>(test_cadr);
CHECK(test_symbol->value() == "bar");
Atom* test_cddr = test_cdr->get_cdr();
test_symbol = dynamic_cast<Symbol*>(test_cddr);
std::cout << typeid(*test_cddr).name() << std::endl;
CHECK(typeid(*test_cddr) == typeid(Symbol));
CHECK(test->to_string() == "(foo bar . quux)");
delete test;
}