Спасибо за ваше глубокое объяснение, вы были абсолютно правы, это больше, чем я хотел бы программировать сам, но в настоящее время не смог. Большое спасибо!

ичок в программировании на C ++ и хочу использоватьcparse библиотека нашел здесьhttps://github.com/cparse/cparse в моем проекте. Я хочу интерпретировать строки пользовательского ввода, как "a*(b+3)«(для переменныхa а такжеb) и использовать его как функцию несколько раз для разных наборов ввода.

Например, принимая текстовый файл в качестве ввода с 2double числа в строке мой код напишет новый файл с результатом "a*(b+3)«на каждой строке (при условииa это первое число иb это второй).

Моя проблема возникает, когда я пытаюсь включитьcparse библиотека из мерзавца Я наивно следовал инструкциям по установке (будучи новичком в git):

$ cd cparse
$ make release

Но я не могу использовать команду make, поскольку я использую Windows. Я попытался скачать ZIP-файл и скопировать.cpp а также.h файлы в проект напрямую и используя«включить существующий» опция в visual studio, но получаю огромное количество ошибок компилятора и не могу заставить код работать сам.

Я что-то упускаю из виду? Как мне заставить его работать?

В противном случае, есть ли другой способ проанализировать строки ввода пользователя и использовать их в качестве функций?

 Daniel H26 окт. 2017 г., 17:17
@JohnZwinck Нет никаких указаний на то, что ОП вообще использует Python, и «используйте совершенно разные языки программирования, о которых вы можете знать, а можете и не знать» - это редко полезный совет.
 user004226 окт. 2017 г., 16:54
Загрузите MinGW64 и установите его в своей системе.
 IInspectable26 окт. 2017 г., 22:20
@user: Отлично. Теперь у вас есть две проблемы.

Ответы на вопрос(1)

Решение Вопроса

есть ли другой способ проанализировать строки ввода пользователя и использовать их в качестве функций?

Я хотел бы ответить на эту часть вашего вопроса, потому что у меня есть ощущение, что полнофункциональный синтаксический анализатор C может быть слишком тяжелым для того, что может быть вашим намерением. (Кстати, как только вы запустили синтаксический анализатор C - как обработать его вывод? Динамическое связывание?)

Вместо этого я хочу показать вам, как создать простой калькулятор (с анализатором рекурсивного спуска) самостоятельно. Для документации методов, которые я буду использовать, я настоятельно рекомендуюКомпиляторы (принципы, методы и инструменты), Aho, Lam, Sethi, Ullman (более известный как «Книги о драконах») и особенноГлава 4.

Крошечный калькулятор проект

Далее я опишу пример решения по частям.

Языковой дизайн

Прежде чем начать писать компилятор или интерпретатор, разумно определить язык, который должен быть принят. Я хочу использовать очень ограниченное подмножество C: выражений, состоящих из

C как числа с плавающей точкой (константы)C как идентификаторы (переменные)унарные операторы+ а также-бинарные операторы+, -, *, а также/скобки()точка с запятой; (отмечать конец выражения обязательно).

Пробелы (включая разрывы строк) будут просто игнорироваться, но могут использоваться для разделения вещей, а также для улучшения читаемости человеком. Комментарии, похожие на C или C ++ (и много другого), я не думал, чтобы исходный код был минимальным. (За все это я получил около 500 строк.)

Конкретный пример OP будет соответствовать этому языку с добавленной точкой с запятой:

a*(b+3);

Будет поддерживаться только один тип:double, Таким образом, мне не нужны типы или какие-либо объявления, которые делают вещи проще.

Прежде чем я начал рисоватьграмматика этого языка, я думал о «цели» компиляции и решил сделать классы для ...

Абстрактное синтаксическое дерево

Сначала - класс для хранения переменных:

// storage of variables

class Var {
  private:
    double _value;
  public:
    Var(): _value() { }
    ~Var() = default;
    double get() const { return _value; }
    void set(double value) { _value = value; }
};

Переменные предоставляют хранилище для значения, но не для идентификатора. Последний хранится отдельно, так как он не нужен для фактического использования переменной, а только для ее поиска по имени:

typedef std::map<std::string, Var> VarTable;

Использованиеstd::map автоматизирует создание переменной. Как известно из многих языков высокого уровня, переменная начинает существовать при первом обращении к ней.

Абстрактное синтаксическое дерево это

древовидное представление абстрактной синтаксической структуры исходного кода, написанного на языке программирования. Каждый узел дерева обозначает конструкцию, встречающуюся в исходном коде.

Я взял этот текст из вышеупомянутой связанной статьи Википедии - не мог сказать, что это короче. В следующих моих классах для AST:

// abstract syntax tree -> storage of "executable"

namespace AST {

class Expr {
  protected:
    Expr() = default;
  public:
    virtual ~Expr() = default;
  public:
    virtual double solve() const = 0;
};

class ExprConst: public Expr {
  private:
    double _value;
  public:
    ExprConst(double value): Expr(), _value(value) { }
    virtual ~ExprConst() = default;
    virtual double solve() const { return _value; }
};

class ExprVar: public Expr {
  private:
    Var *_pVar;
  public:
    ExprVar(Var *pVar): Expr(), _pVar(pVar) { }
    virtual ~ExprVar() = default;
    virtual double solve() const { return _pVar->get(); }
};

class ExprUnOp: public Expr {
  protected:
    Expr *_pArg1;
  protected:
    ExprUnOp(Expr *pArg1): Expr(), _pArg1(pArg1) { }
    virtual ~ExprUnOp() { delete _pArg1; }
};

class ExprUnOpNeg: public ExprUnOp {
  public:
    ExprUnOpNeg(Expr *pArg1): ExprUnOp(pArg1) { }
    virtual ~ExprUnOpNeg() = default;
    virtual double solve() const
    {
      return -_pArg1->solve();
    }
};

class ExprBinOp: public Expr {
  protected:
    Expr *_pArg1, *_pArg2;
  protected:
    ExprBinOp(Expr *pArg1, Expr *pArg2):
      Expr(), _pArg1(pArg1), _pArg2(pArg2)
    { }
    virtual ~ExprBinOp() { delete _pArg1; delete _pArg2; }
};

class ExprBinOpAdd: public ExprBinOp {
  public:
    ExprBinOpAdd(Expr *pArg1, Expr *pArg2): ExprBinOp(pArg1, pArg2) { }
    virtual ~ExprBinOpAdd() = default;
    virtual double solve() const
    {
      return _pArg1->solve() + _pArg2->solve();
    }
};

class ExprBinOpSub: public ExprBinOp {
  public:
    ExprBinOpSub(Expr *pArg1, Expr *pArg2): ExprBinOp(pArg1, pArg2) { }
    virtual ~ExprBinOpSub() = default;
    virtual double solve() const
    {
      return _pArg1->solve() - _pArg2->solve();
    }
};

class ExprBinOpMul: public ExprBinOp {
  public:
    ExprBinOpMul(Expr *pArg1, Expr *pArg2): ExprBinOp(pArg1, pArg2) { }
    virtual ~ExprBinOpMul() = default;
    virtual double solve() const
    {
      return _pArg1->solve() * _pArg2->solve();
    }
};

class ExprBinOpDiv: public ExprBinOp {
  public:
    ExprBinOpDiv(Expr *pArg1, Expr *pArg2): ExprBinOp(pArg1, pArg2) { }
    virtual ~ExprBinOpDiv() = default;
    virtual double solve() const
    {
      return _pArg1->solve() / _pArg2->solve();
    }
};

Таким образом, используя классы AST, представление выборкиa*(b+3) было бы

VarTable varTable;
Expr *pExpr
= new ExprBinOpMul(
    new ExprVar(&varTable["a"]),
    new ExprBinOpAdd(
      new ExprVar(&varTable["b"]),
      new ExprConst(3)));

Примечание:

Нет класса, полученного изExpr представлять скобки() потому что это просто не нужно. Обработка скобок учитывается при построении самого дерева. Обычно операторы с более высоким приоритетом становятся потомками операторов с более низким приоритетом. В результате первые вычисляются перед последними. В приведенном выше примере, экземплярExprBinOpAdd является потомком экземпляраExprBinOpMul (хотя приоритет умножения выше, чем приоритет сложения), что следует из правильного рассмотрения скобок.

Помимо хранения проанализированного выражения, это дерево можно использовать для вычисления выражения, вызываяExpr::solve() метод корневого узла:

double result = pExpr->solve();

Наличие бэкэнда для нашегоКрошечный калькуляторДалее идет внешний интерфейс.

Грамматика

Формальный язык лучше всего описываетсяграмматика.

program
  : expr Semicolon program
  | <empty>
  ;

expr
  : addExpr
  ;

addExpr
  : mulExpr addExprRest
  ;

addExprRest
  : addOp mulExpr addExprRest
  | <empty>
  ;

addOp
  : Plus | Minus
  ;

mulExpr
  : unaryExpr mulExprRest
  ;

mulExprRest
  : mulOp unaryExpr mulExprRest
  | <empty>
  ;

mulOp
  : Star | Slash
  ;

unaryExpr
  : unOp unaryExpr
  | primExpr
  ;

unOp
  : Plus | Minus
  ;

primExpr
  : Number
  | Id
  | LParen expr RParen
  ;

с начальным символомprogram.

Правила содержат

символы терминала (начиная с заглавной буквы) инетерминальные символы (начинающиеся со строчной буквы)двоеточие (:) отделить левую сторону от правой (нетерминал с левой стороны может расширяться до символов с правой стороны).вертикальные полосы (|) для разделения альтернатив<empty> символ расширения до нуля (используется для завершения рекурсии).

Из символов терминала я выведу токены для сканера.

Нетерминальные символы будут преобразованы в функции парсера.

РазделениеaddExpr а такжеmulExpr сделано намеренно. Таким образом, приоритет мультипликативных операторов над аддитивными операторами будет «записан» в самой грамматике. Очевидно, что константы с плавающей точкой, идентификаторы переменных или выражения в скобках (принимаются вprimExpr) будет иметь наивысший приоритет.

Правила содержат только правильные рекурсии. Это требование для синтаксических анализаторов с рекурсивным спуском (как я теоретически изучал в книгах о Dragon и из практического опыта в отладчике, пока полностью не понял причину этого). Реализация левого рекурсивного правила в синтаксическом анализаторе с рекурсивным спуском приводит к неразрывным рекурсиям, которые, в свою очередь, заканчиваютсяПереполнение стека.

Сканер

Обычно компилятор разделяется на сканер и парсер.

Сканер обрабатывает входной поток символов и группирует символы вместе в токены. Токены используются в качестве терминальных символов в парсере.

Для вывода токенов я сделал класс. В моих профессиональных проектах он дополнительно хранит точную позицию файла, чтобы обозначить его происхождение. Это удобно для пометки созданных объектов ссылками на исходный код, а также вывода сообщений об ошибках и отладочной информации. (... опущено здесь, чтобы сохранить его как можно меньше ...)

// token class - produced in scanner, consumed in parser
struct Token {
  // tokens
  enum Tk {
    Plus, Minus, Star, Slash, LParen, RParen, Semicolon,
    Number, Id,
    EOT, Error
  };
  // token number
  Tk tk;
  // lexem as floating point number
  double number;
  // lexem as identifier
  std::string id;

  // constructors.
  explicit Token(Tk tk): tk(tk), number() { }
  explicit Token(double number): tk(Number), number(number) { }
  explicit Token(const std::string &id): tk(Id), number(), id(id) { }
};

Для специальных токенов есть два перечислителя:

EOT ... конец текста (отмечает конец ввода)Error ... генерируется для любого персонажа, который не помещается ни в один другой токен.

Токены используются как выходные данные самого сканера:

// the scanner - groups characters to tokens
class Scanner {
  private:
    std::istream &_in;
  public:
    // constructor.
    Scanner(std::istream &in): _in(in) { }
    /* groups characters to next token until the fi,rst character
     * which does not match (or end-of-file is reached).
     */
    Token scan()
    {
      char c;
      // skip white space
      do {
        if (!(_in >> c)) return Token(Token::EOT);
      } while (isspace(c));
      // classify character and build token
      switch (c) {
        case '+': return Token(Token::Plus);
        case '-': return Token(Token::Minus);
        case '*': return Token(Token::Star);
        case '/': return Token(Token::Slash);
        case '(': return Token(Token::LParen);
        case ')': return Token(Token::RParen);
        case ';': return Token(Token::Semicolon);
        default:
          if (isdigit(c)) {
            _in.unget(); double value; _in >> value;
            return Token(value);
          } else if (isalpha(c) || c == '_') {
            std::string id(1, c);
            while (_in >> c) {
              if (isalnum(c) || c == '_') id += c;
              else { _in.unget(); break; }
            }
            return Token(id);
          } else {
            _in.unget();
            return Token(Token::Error);
          }
      }
    }
};

Сканер используется в парсере.

Парсер
class Parser {
  private:
    Scanner _scanner;
    VarTable &_varTable;
    Token _lookAhead;

  private:
    // constructor.
    Parser(std::istream &in, VarTable &varTable):
      _scanner(in), _varTable(varTable), _lookAhead(Token::EOT)
    {
      scan(); // load look ahead initially
    }

    // calls the scanner to read the next look ahead token.
    void scan() { _lookAhead = _scanner.scan(); }

    // consumes a specific token.
    bool match(Token::Tk tk)
    {
      if (_lookAhead.tk != tk) {
        std::cerr << "SYNTAX ERROR! Unexpected token!" << std::endl;
        return false;
      }
      scan();
      return true;
    }

    // the rules:

    std::vector<AST::Expr*> parseProgram()
    {
      // right recursive rule
      // -> can be done as iteration
      std::vector<AST::Expr*> pExprs;
      for (;;) {
        if (AST::Expr *pExpr = parseExpr()) {
          pExprs.push_back(pExpr);
        } else break;
        // special error checking for missing ';' (usual error)
        if (_lookAhead.tk != Token::Semicolon) {
          std::cerr << "SYNTAX ERROR: Semicolon expected!" << std::endl;
          break;
        }
        scan(); // consume semicolon
        if (_lookAhead.tk == Token::EOT) return pExprs;
      }
      // error handling
      for (AST::Expr *pExpr : pExprs) delete pExpr;
      pExprs.clear();
      return pExprs;
    }

    AST::Expr* parseExpr()
    {
      return parseAddExpr();
    }

    AST::Expr* parseAddExpr()
    {
      if (AST::Expr *pExpr1 = parseMulExpr()) {
        return parseAddExprRest(pExpr1);
      } else return nullptr; // ERROR!
    }

    AST::Expr* parseAddExprRest(AST::Expr *pExpr1)
    {
      // right recursive rule for left associative operators
      // -> can be done as iteration
      for (;;) {
        switch (_lookAhead.tk) {
          case Token::Plus:
            scan(); // consume token
            if (AST::Expr *pExpr2 = parseMulExpr()) {
              pExpr1 = new AST::ExprBinOpAdd(pExpr1, pExpr2);
            } else {
              delete pExpr1;
              return nullptr; // ERROR!
            }
            break;
          case Token::Minus:
            scan(); // consume token
            if (AST::Expr *pExpr2 = parseMulExpr()) {
              pExpr1 = new AST::ExprBinOpSub(pExpr1, pExpr2);
            } else {
              delete pExpr1;
              return nullptr; // ERROR!
            }
            break;
          case Token::Error:
            std::cerr << "SYNTAX ERROR: Unexpected character!" << std::endl;
            delete pExpr1;
            return nullptr;
          default: return pExpr1;
        }
      }
    }

    AST::Expr* parseMulExpr()
    {
      if (AST::Expr *pExpr1 = parseUnExpr()) {
        return parseMulExprRest(pExpr1);
      } else return nullptr; // ERROR!
    }

    AST::Expr* parseMulExprRest(AST::Expr *pExpr1)
    {
      // right recursive rule for left associative operators
      // -> can be done as iteration
      for (;;) {
        switch (_lookAhead.tk) {
          case Token::Star:
            scan(); // consume token
            if (AST::Expr *pExpr2 = parseUnExpr()) {
              pExpr1 = new AST::ExprBinOpMul(pExpr1, pExpr2);
            } else {
              delete pExpr1;
              return nullptr; // ERROR!
            }
            break;
          case Token::Slash:
            scan(); // consume token
            if (AST::Expr *pExpr2 = parseUnExpr()) {
              pExpr1 = new AST::ExprBinOpDiv(pExpr1, pExpr2);
            } else {
              delete pExpr1;
              return nullptr; // ERROR!
            }
            break;
          case Token::Error:
            std::cerr << "SYNTAX ERROR: Unexpected character!" << std::endl;
            delete pExpr1;
            return nullptr;
          default: return pExpr1;
        }
      }
    }

    AST::Expr* parseUnExpr()
    {
      // right recursive rule for right associative operators
      // -> must be done as recursion
      switch (_lookAhead.tk) {
        case Token::Plus:
          scan(); // consume token
          // as a unary plus has no effect it is simply ignored
          return parseUnExpr();
        case Token::Minus:
          scan();
          if (AST::Expr *pExpr = parseUnExpr()) {
            return new AST::ExprUnOpNeg(pExpr);
          } else return nullptr; // ERROR!
        default:
          return parsePrimExpr();
      }
    }

    AST::Expr* parsePrimExpr()
    {
      AST::Expr *pExpr = nullptr;
      switch (_lookAhead.tk) {
        case Token::Number:
          pExpr = new AST::ExprConst(_lookAhead.number);
          scan(); // consume token
          break;
        case Token::Id: {
          Var &var = _varTable[_lookAhead.id]; // find or create
          pExpr = new AST::ExprVar(&var);
          scan(); // consume token
        } break;
        case Token::LParen:
          scan(); // consume token
          if (!(pExpr = parseExpr())) return nullptr; // ERROR!
          if (!match(Token::RParen)) {
            delete pExpr; return nullptr; // ERROR!
          }
          break;
        case Token::EOT:
          std::cerr << "SYNTAX ERROR: Premature EOF!" << std::endl;
          break;
        case Token::Error:
          std::cerr << "SYNTAX ERROR: Unexpected character!" << std::endl;
          break;
        default:
          std::cerr << "SYNTAX ERROR: Unexpected token!" << std::endl;
      }
      return pExpr;
    }

  public:

    // the parser function
    static std::vector<AST::Expr*> parse(
      std::istream &in, VarTable &varTable)
    {
      Parser parser(in, varTable);
      return parser.parseProgram();
    }
};

По сути, синтаксический анализатор состоит в основном из набора функций правил (согласно правилам грамматики), которые вызывают друг друга. Класс вокруг функций правила отвечает за управление некоторым глобальным контекстом синтаксического анализатора. Следовательно, единственный публичный методclass Parser является

static std::vector<AST::Expr*> Parser::parse();

который создает экземпляр (с закрытым конструктором) и вызывает функциюParser::parseProgram() соответствующий начальному символуprogram.

Внутренне парсер вызываетScanner::scan() метод, чтобы заполнить его жетон прогнозирования.

Это сделано вParser::scan() который вызывается всегда, когда токен должен быть использован.

Если присмотреться, то становится очевидным, как правила были переведены в функции парсера:

Каждый нетерминал на левой стороне становится функцией разбора. (Посмотрев поближе в исходном коде, вы поймете, что я не сделал этого точно. Некоторые из правил были «встроены». - С моей точки зрения, я вставил несколько дополнительных правил, чтобы упростить грамматику, которую я не делал » Я не собираюсь трансформироваться с самого начала. Извините.)

Альтернативы (|) реализованы какswitch (_lookAhead.tk), Таким образом, каждая метка регистра соответствует первому терминалу (ам) (токену), до которого может расширяться самый левый символ. (Я полагаю, что именно поэтому он называется «синтаксический анализатор прогнозирования» - решения о применении правил всегда принимаются на основе маркера прогнозирования.) Книга драконов содержит тему о наборах FIRST-FOLLOW, которая объясняет это более подробно.

Для терминальных символовParser::scan() называется. В особых случаях его заменяютParser::match() если ожидается только один терминал (токен).

Для нетерминальных символов выполняется вызов соответствующей функции.

Последовательности символов просто выполняются как последовательности вышеуказанных вызовов.

Обработка ошибок этого парсера - самая простая, которую я когда-либо делал. Это может / должно быть сделано гораздо больше поддержки (вкладывая больше усилий, то есть дополнительные строки кода). (... но здесь я попытался сделать его минимальным ...)

Положить вместе

Для тестирования и демонстрации я подготовилmain() функция с некоторыми встроенными примерами (исходный код программы и данные для обработки):

// a sample application

using namespace std;

int main()
{
  // the program:
  const char *sourceCode =
    "1 + 2 * 3 / 4 - 5;\n"
    "a + b;\n"
    "a - b;\n"
    "a * b;\n"
    "a / b;\n"
    "a * (b + 3);\n";
  // the variables
  const char *vars[] = { "a", "b" };
  enum { nVars = sizeof vars / sizeof *vars };
  // the data
  const double data[][nVars] = {
    { 4.0, 2.0 },
    { 2.0, 4.0 },
    { 10.0, 5.0 },
    { 42, 6 * 7 }
  };
  // compile program
  stringstream in(sourceCode);
  VarTable varTable;
  vector<AST::Expr*> program = Parser::parse(in, varTable);
  if (program.empty()) {
    cerr << "ERROR: Compile failed!" << endl;
    string line;
    if (getline(in, line)) {
      cerr << "Text at error: '" << line << "'" << endl;
    }
    return 1;
  }
  // apply program to the data
  enum { nDataSets = sizeof data / sizeof *data };
  for (size_t i = 0; i < nDataSets; ++i) {
    const char *sep = "";
    cout << "Data Set:" << endl;
    for (size_t j = 0; j < nVars; ++j, sep = ", ") {
      cout << sep << vars[j] << ": " << data[i][j];
    }
    cout << endl;
    // load data
    for (size_t j = 0; j < nVars; ++j) varTable[vars[j]].set(data[i][j]);
    // perform program
    cout << "Compute:" << endl;
    istringstream in(sourceCode);
    for (const AST::Expr *pExpr : program) {
      string line; getline(in, line);
      cout << line << ": " << pExpr->solve() << endl;
    }
    cout << endl;
  }
  // clear the program
  for (AST::Expr *pExpr : program) delete pExpr;
  program.clear();
  // done
  return 0;  
}

Я скомпилировал и протестировал на VS2013 (Windows 10) и получил:

Data Set:
a: 4, b: 2
Compute:
1 + 2 * 3 / 4 - 5;: -2.5
a + b;: 6
a - b;: 2
a * b;: 8
a / b;: 2
a * (b + 3);: 20

Data Set:
a: 2, b: 4
Compute:
1 + 2 * 3 / 4 - 5;: -2.5
a + b;: 6
a - b;: -2
a * b;: 8
a / b;: 0.5
a * (b + 3);: 14

Data Set:
a: 10, b: 5
Compute:
1 + 2 * 3 / 4 - 5;: -2.5
a + b;: 15
a - b;: 5
a * b;: 50
a / b;: 2
a * (b + 3);: 80

Data Set:
a: 42, b: 42
Compute:
1 + 2 * 3 / 4 - 5;: -2.5
a + b;: 84
a - b;: 0
a * b;: 1764
a / b;: 1
a * (b + 3);: 1890

Пожалуйста, учтите, что сам синтаксический анализатор игнорирует любые пробелы и переносы строк. Тем не менее, чтобы упростить форматирование выходных данных, я должен использовать одно выражение с точкой с запятой в строке. будет сложно связать строки исходного кода с соответствующими скомпилированными выражениями. (Помните мое примечание выше оToken к которому может быть добавлена ​​ссылка на исходный код (также называемая позицией файла).)

Полный образец

... с исходным кодом и тестовым прогоном можно найти наideone.

 James Simpson02 нояб. 2017 г., 10:02
Спасибо за ваше глубокое объяснение, вы были абсолютно правы, это больше, чем я хотел бы программировать сам, но в настоящее время не смог. Большое спасибо!

Ваш ответ на вопрос