Skip to content

parser optimization step One #300

New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Merged
lefticus merged 3 commits into from
Dec 1, 2016
Merged

parser optimization step One #300

Show file tree
Hide file tree
Changes from all commits
Commits
Show all changes
3 commits
Select commit Hold shift + click to select a range
c42477f
parser optimization step One
niXman Nov 3, 2016
745e0c0
parser optimization step Two
niXman Nov 4, 2016
1ea91fa
parser optimization Three
niXman Nov 7, 2016
File filter

Filter by extension

Filter by extension
Conversations
Failed to load comments.
Loading
Jump to
Jump to file
Failed to load files.
Loading
Diff view
Diff view
105 changes: 35 additions & 70 deletions include/chaiscript/language/chaiscript_algebraic.hpp
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -7,6 +7,8 @@
#ifndef CHAISCRIPT_ALGEBRAIC_HPP_
#define CHAISCRIPT_ALGEBRAIC_HPP_

#include "../utility/fnv1a.hpp"

#include <string>

namespace chaiscript
Expand Down Expand Up @@ -51,76 +53,39 @@ namespace chaiscript

static Opers to_operator(const std::string &t_str, bool t_is_unary = false)
{
if (t_str == "==")
{
return Opers::equals;
} else if (t_str == "<") {
return Opers::less_than;
} else if (t_str == ">") {
return Opers::greater_than;
} else if (t_str == "<=") {
return Opers::less_than_equal;
} else if (t_str == ">=") {
return Opers::greater_than_equal;
} else if (t_str == "!=") {
return Opers::not_equal;
} else if (t_str == "=") {
return Opers::assign;
} else if (t_str == "++") {
return Opers::pre_increment;
} else if (t_str == "--") {
return Opers::pre_decrement;
} else if (t_str == "*=") {
return Opers::assign_product;
} else if (t_str == "+=") {
return Opers::assign_sum;
} else if (t_str == "-=") {
return Opers::assign_difference;
} else if (t_str == "&=") {
return Opers::assign_bitwise_and;
} else if (t_str == "|=") {
return Opers::assign_bitwise_or;
} else if (t_str == "<<=") {
return Opers::assign_shift_left;
} else if (t_str == ">>=") {
return Opers::assign_shift_right;
} else if (t_str == "%=") {
return Opers::assign_remainder;
} else if (t_str == "^=") {
return Opers::assign_bitwise_xor;
} else if (t_str == "<<") {
return Opers::shift_left;
} else if (t_str == ">>") {
return Opers::shift_right;
} else if (t_str == "%") {
return Opers::remainder;
} else if (t_str == "&") {
return Opers::bitwise_and;
} else if (t_str == "|") {
return Opers::bitwise_or;
} else if (t_str == "^") {
return Opers::bitwise_xor;
} else if (t_str == "~") {
return Opers::bitwise_complement;
} else if (t_str == "+") {
if (t_is_unary) {
return Opers::unary_plus;
} else {
return Opers::sum;
}
} else if (t_str == "-") {
if (t_is_unary) {
return Opers::unary_minus;
} else {
return Opers::difference;
}
} else if (t_str == "/") {
return Opers::quotient;
} else if (t_str == "*") {
return Opers::product;
} else {
return Opers::invalid;
}
const auto op_hash = utility::fnv1a_32(t_str.c_str());
switch (op_hash) {
case utility::fnv1a_32("=="): { return Opers::equals; }
case utility::fnv1a_32("<"): { return Opers::less_than; }
case utility::fnv1a_32(">"): { return Opers::greater_than; }
case utility::fnv1a_32("<="): { return Opers::less_than_equal; }
case utility::fnv1a_32(">="): { return Opers::greater_than_equal; }
case utility::fnv1a_32("!="): { return Opers::not_equal; }
case utility::fnv1a_32("="): { return Opers::assign; }
case utility::fnv1a_32("++"): { return Opers::pre_increment; }
case utility::fnv1a_32("--"): { return Opers::pre_decrement; }
case utility::fnv1a_32("*="): { return Opers::assign_product; }
case utility::fnv1a_32("+="): { return Opers::assign_sum; }
case utility::fnv1a_32("-="): { return Opers::assign_difference; }
case utility::fnv1a_32("&="): { return Opers::assign_bitwise_and; }
case utility::fnv1a_32("|="): { return Opers::assign_bitwise_or; }
case utility::fnv1a_32("<<="): { return Opers::assign_shift_left; }
case utility::fnv1a_32(">>="): { return Opers::assign_shift_right; }
case utility::fnv1a_32("%="): { return Opers::assign_remainder; }
case utility::fnv1a_32("^="): { return Opers::assign_bitwise_xor; }
case utility::fnv1a_32("<<"): { return Opers::shift_left; }
case utility::fnv1a_32(">>"): { return Opers::shift_right; }
case utility::fnv1a_32("%"): { return Opers::remainder; }
case utility::fnv1a_32("&"): { return Opers::bitwise_and; }
case utility::fnv1a_32("|"): { return Opers::bitwise_or; }
case utility::fnv1a_32("^"): { return Opers::bitwise_xor; }
case utility::fnv1a_32("~"): { return Opers::bitwise_complement; }
case utility::fnv1a_32("+"): { return t_is_unary ? Opers::unary_plus : Opers::sum; }
case utility::fnv1a_32("-"): { return t_is_unary ? Opers::unary_minus : Opers::difference; }
case utility::fnv1a_32("/"): { return Opers::quotient; }
case utility::fnv1a_32("*"): { return Opers::product; }
default: { return Opers::invalid; }
}
}

};
Expand Down
173 changes: 94 additions & 79 deletions include/chaiscript/language/chaiscript_parser.hpp
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -23,6 +23,7 @@
#include "chaiscript_common.hpp"
#include "chaiscript_optimizer.hpp"
#include "chaiscript_tracer.hpp"
#include "../utility/fnv1a.hpp"

#if defined(CHAISCRIPT_UTF16_UTF32)
#include <locale>
Expand Down Expand Up @@ -225,10 +226,18 @@ namespace chaiscript
return operators;
}

static constexpr const char * const m_multiline_comment_begin = "/*";
static constexpr const char * const m_multiline_comment_end = "*/";
static constexpr const char * const m_singleline_comment = "//";
static constexpr const char * const m_annotation = "#";
static constexpr const char m_multiline_comment_begin[] = "/*";
static constexpr const char m_multiline_comment_end[] = "*/";
static constexpr const char m_singleline_comment[] = "//";
static constexpr const char m_annotation[] = "#";
static constexpr const char m_cr_lf[] = "\r\n";
enum {
m_multiline_comment_begin_len = sizeof(m_multiline_comment_begin)-1
,m_multiline_comment_end_len = sizeof(m_multiline_comment_end)-1
,m_singleline_comment_len = sizeof(m_singleline_comment)-1
,m_annotation_len = sizeof(m_annotation)-1
,m_cr_lf_len = sizeof(m_cr_lf)-1
};

const std::array<std::array<bool, detail::lengthof_alphabet>, detail::max_alphabet> &m_alphabet = create_alphabet();
const std::vector<std::vector<std::string>> &m_operator_matches = create_operator_matches();
Expand Down Expand Up @@ -318,9 +327,10 @@ namespace chaiscript
return static_cast<size_t>(std::distance(m_pos, m_end));
}

char operator*() const {
const char& operator*() const {
if (m_pos == m_end) {
return '\0';
static const char ktmp ='\0';
return ktmp;
} else {
return *m_pos;
}
Expand Down Expand Up @@ -428,20 +438,30 @@ namespace chaiscript
}


/// Reads a symbol group from input if it matches the parameter, without skipping initial whitespace
#define Symbol_(t_s, len) \
( \
m_position.remaining() >= len \
? std::memcmp(t_s, &(*m_position), len) == 0 \
? ((m_position += len),true) \
:false \
:false \
)

/// Skips any multi-line or single-line comment
bool SkipComment() {
if (Symbol_(m_multiline_comment_begin)) {
if (Symbol_(m_multiline_comment_begin, m_multiline_comment_begin_len)) {
while (m_position.has_more()) {
if (Symbol_(m_multiline_comment_end)) {
if (Symbol_(m_multiline_comment_end, m_multiline_comment_end_len)) {
break;
} else if (!Eol_()) {
++m_position;
}
}
return true;
} else if (Symbol_(m_singleline_comment)) {
} else if (Symbol_(m_singleline_comment, m_singleline_comment_len)) {
while (m_position.has_more()) {
if (Symbol_("\r\n")) {
if (Symbol_(m_cr_lf, m_cr_lf_len)) {
m_position -= 2;
break;
} else if (Char_('\n')) {
Expand All @@ -452,9 +472,9 @@ namespace chaiscript
}
}
return true;
} else if (Symbol_(m_annotation)) {
} else if (Symbol_(m_annotation, m_annotation_len)) {
while (m_position.has_more()) {
if (Symbol_("\r\n")) {
if (Symbol_(m_cr_lf, m_cr_lf_len)) {
m_position -= 2;
break;
} else if (Char_('\n')) {
Expand Down Expand Up @@ -833,74 +853,77 @@ namespace chaiscript
const auto start = m_position;
if (Id_()) {

const auto text = Position::str(start, m_position);
auto text = Position::str(start, m_position);
const auto text_hash = utility::fnv1a_32(text.c_str());

if (validate) {
validate_object_name(text);
}

if (text == "true") {
m_match_stack.push_back(make_node<eval::Constant_AST_Node<Tracer>>(text, start.line, start.col, const_var(true)));
} else if (text == "false") {
m_match_stack.push_back(make_node<eval::Constant_AST_Node<Tracer>>(text, start.line, start.col, const_var(false)));
} else if (text == "Infinity") {
m_match_stack.push_back(make_node<eval::Constant_AST_Node<Tracer>>(text, start.line, start.col,
const_var(std::numeric_limits<double>::infinity())));
} else if (text == "NaN") {
m_match_stack.push_back(make_node<eval::Constant_AST_Node<Tracer>>(text, start.line, start.col,
const_var(std::numeric_limits<double>::quiet_NaN())));
} else if (text == "__LINE__") {
m_match_stack.push_back(make_node<eval::Constant_AST_Node<Tracer>>(text, start.line, start.col,
const_var(start.line)));
} else if (text == "__FILE__") {
m_match_stack.push_back(make_node<eval::Constant_AST_Node<Tracer>>(text, start.line, start.col,
const_var(m_filename)));
} else if (text == "__FUNC__") {
const std::string fun_name = [&]()->std::string{
switch (text_hash) {
case utility::fnv1a_32("true"): {
m_match_stack.push_back(make_node<eval::Constant_AST_Node<Tracer>>(std::move(text), start.line, start.col, const_var(true)));
} break;
case utility::fnv1a_32("false"): {
m_match_stack.push_back(make_node<eval::Constant_AST_Node<Tracer>>(std::move(text), start.line, start.col, const_var(false)));
} break;
case utility::fnv1a_32("Infinity"): {
m_match_stack.push_back(make_node<eval::Constant_AST_Node<Tracer>>(std::move(text), start.line, start.col,
const_var(std::numeric_limits<double>::infinity())));
} break;
case utility::fnv1a_32("NaN"): {
m_match_stack.push_back(make_node<eval::Constant_AST_Node<Tracer>>(std::move(text), start.line, start.col,
const_var(std::numeric_limits<double>::quiet_NaN())));
} break;
case utility::fnv1a_32("__LINE__"): {
m_match_stack.push_back(make_node<eval::Constant_AST_Node<Tracer>>(std::move(text), start.line, start.col,
const_var(start.line)));
} break;
case utility::fnv1a_32("__FILE__"): {
m_match_stack.push_back(make_node<eval::Constant_AST_Node<Tracer>>(std::move(text), start.line, start.col,
const_var(m_filename)));
} break;
case utility::fnv1a_32("__FUNC__"): {
std::string fun_name = "NOT_IN_FUNCTION";
for (size_t idx = m_match_stack.size() - 1; idx > 0; --idx)
{
if (m_match_stack[idx-1]->identifier == AST_Node_Type::Id
&& m_match_stack[idx-0]->identifier == AST_Node_Type::Arg_List) {
return m_match_stack[idx-1]->text;
fun_name = m_match_stack[idx-1]->text;
}
}
return "NOT_IN_FUNCTION";
}();

m_match_stack.push_back(make_node<eval::Constant_AST_Node<Tracer>>(text, start.line, start.col,
const_var(fun_name)));
} else if (text == "__CLASS__") {
const std::string fun_name = [&]()->std::string{
m_match_stack.push_back(make_node<eval::Constant_AST_Node<Tracer>>(std::move(text), start.line, start.col,
const_var(fun_name)));
} break;
case utility::fnv1a_32("__CLASS__"): {
std::string fun_name = "NOT_IN_CLASS";
for (size_t idx = m_match_stack.size() - 1; idx > 1; --idx)
{
if (m_match_stack[idx-2]->identifier == AST_Node_Type::Id
&& m_match_stack[idx-1]->identifier == AST_Node_Type::Id
&& m_match_stack[idx-0]->identifier == AST_Node_Type::Arg_List) {
return m_match_stack[idx-2]->text;
fun_name = m_match_stack[idx-2]->text;
}
}
return "NOT_IN_CLASS";
}();

m_match_stack.push_back(make_node<eval::Constant_AST_Node<Tracer>>(text, start.line, start.col,
const_var(fun_name)));
} else if (text == "_") {
m_match_stack.push_back(make_node<eval::Constant_AST_Node<Tracer>>(text, start.line, start.col,
Boxed_Value(std::make_shared<dispatch::Placeholder_Object>())));
} else {
m_match_stack.push_back(make_node<eval::Id_AST_Node<Tracer>>(
[&]()->std::string{
if (*start == '`') {
// 'escaped' literal, like an operator name
return Position::str(start+1, m_position-1);
} else {
return text;
}
}(),
start.line, start.col));
m_match_stack.push_back(make_node<eval::Constant_AST_Node<Tracer>>(std::move(text), start.line, start.col,
const_var(fun_name)));
} break;
case utility::fnv1a_32("_"): {
m_match_stack.push_back(make_node<eval::Constant_AST_Node<Tracer>>(std::move(text), start.line, start.col,
Boxed_Value(std::make_shared<dispatch::Placeholder_Object>())));
} break;
default: {
std::string val = std::move(text);
if (*start == '`') {
// 'escaped' literal, like an operator name
val = Position::str(start+1, m_position-1);
}
m_match_stack.push_back(make_node<eval::Id_AST_Node<Tracer>>(val, start.line, start.col));
} break;
}


return true;
} else {
return false;
Expand Down Expand Up @@ -1330,25 +1353,6 @@ namespace chaiscript
return retval;
}

/// Reads a symbol group from input if it matches the parameter, without skipping initial whitespace
bool Symbol_(const char *t_s) {
const auto len = strlen(t_s);

if (m_position.remaining() >= len) {
auto tmp = m_position;
for (size_t i = 0; m_position.has_more() && i < len; ++i) {
if (*tmp != t_s[i]) {
return false;
}
++tmp;
}
m_position = tmp;
return true;
}

return false;
}

bool is_operator(const std::string &t_s) const {
return std::any_of(m_operator_matches.begin(), m_operator_matches.end(),
[t_s](const std::vector<std::string> &opers) {
Expand All @@ -1363,7 +1367,7 @@ namespace chaiscript
bool Symbol(const char *t_s, const bool t_disallow_prevention=false) {
SkipWS();
const auto start = m_position;
bool retval = Symbol_(t_s);
bool retval = Symbol_(t_s, std::strlen(t_s));

// ignore substring matches
if (retval && m_position.has_more() && (t_disallow_prevention == false) && char_in_alphabet(*m_position,detail::symbol_alphabet)) {
Expand All @@ -1382,7 +1386,7 @@ namespace chaiscript
bool Eol_(const bool t_eos = false) {
bool retval = false;

if (m_position.has_more() && (Symbol_("\r\n") || Char_('\n'))) {
if (m_position.has_more() && (Symbol_(m_cr_lf, m_cr_lf_len) || Char_('\n'))) {
retval = true;
//++m_position.line;
m_position.col = 1;
Expand Down Expand Up @@ -2523,9 +2527,20 @@ namespace chaiscript
return m_match_stack.front();
}
};
template<typename Tracer, typename Optimizer>
constexpr const char ChaiScript_Parser<Tracer, Optimizer>::m_multiline_comment_begin[];
template<typename Tracer, typename Optimizer>
constexpr const char ChaiScript_Parser<Tracer, Optimizer>::m_multiline_comment_end[];
template<typename Tracer, typename Optimizer>
constexpr const char ChaiScript_Parser<Tracer, Optimizer>::m_singleline_comment[];
template<typename Tracer, typename Optimizer>
constexpr const char ChaiScript_Parser<Tracer, Optimizer>::m_annotation[];
template<typename Tracer, typename Optimizer>
constexpr const char ChaiScript_Parser<Tracer, Optimizer>::m_cr_lf[];
}
}

#undef Symbol_

#if defined(CHAISCRIPT_MSVC) && defined(CHAISCRIPT_PUSHED_MIN_MAX)
#undef CHAISCRIPT_PUSHED_MIN_MAX
Expand Down
Loading