c++ - Analizando cadenas de entrada del usuario usando la biblioteca cparse de git

windows parsing

Question

Soy nuevo en la programación de c ++ y deseo utilizar la biblioteca cparse que se encuentra aquí https://github.com/cparse/cparse en mi proyecto. Quiero interpretar cadenas de entrada de usuario como " a*(b+3) " (para las variables a y b ) y usarlo como una función repetidamente en diferentes conjuntos de entrada.

Por ejemplo, tomando un archivo de texto como entrada con 2 números double por línea, mi código escribirá un nuevo archivo con el resultado de " a*(b+3) " en cada línea (suponiendo que a es el primer número b es el segundo )

Mi problema surge cuando intento incluir la biblioteca cparse de git. Seguí las instrucciones de configuración ingenuamente (siendo nuevo en git):

$ cd cparse
$ make release

Pero no puedo usar el comando make ya que estoy usando windows. Intenté descargar el archivo zip y copiar los archivos .cpp y .h directamente en el proyecto y usar la opción "incluir existente" en Visual Studio, pero obtuve una gran cantidad de errores de compilación y no puedo hacer que el código funcione por mí mismo.

¿Me estoy perdiendo el punto de alguna manera? ¿Cómo hago para que funcione?

De lo contrario, ¿hay otra manera de analizar cadenas de entrada de usuario y usarlas como funciones?

Answer 1

De lo contrario, ¿hay otra manera de analizar cadenas de entrada de usuario y usarlas como funciones?

Me gustaría responder a esta parte de su pregunta porque tengo la sensación de que un analizador C completo podría ser demasiado pesado para lo que podría ser su intención. (Por cierto, una vez que ejecuta el analizador C, ¿cómo procesar su salida? ¿Enlace dinámico?)

En cambio, quiero mostrarle cómo construir una calculadora simple (con analizador de descenso recursivo) por su cuenta. Para la documentación de las técnicas que utilizaré, recomiendo encarecidamente los compiladores (principios, técnicas y herramientas) de Aho, Lam, Sethi, Ullman (mejor conocidos como "libros del dragón") y especialmente el Capítulo 4 .

The Tiny Calculator Project

A continuación describo mi solución de muestra parte por parte.

Diseño de lenguaje

Antes de comenzar a escribir un compilador o intérprete, es razonable definir un lenguaje que sea aceptado. Quiero usar un subconjunto muy limitado de C: expresiones que consisten en

• C como números de coma flotante (constantes)
• C como identificadores (variables)
• operadores unarios + y -
• operadores binarios + , - , * y /
• paréntesis ()
• punto ; coma (para marcar el final de una expresión, obligatorio).

Los espacios en blanco (incluidos los saltos de línea) simplemente se ignorarán, pero se pueden usar para separar cosas y para mejorar la legibilidad humana. Comentarios similares a C o C ++ (y muchos otros azúcares) No consideré mantener el código fuente lo más mínimo posible. (Por todo eso, obtuve casi 500 líneas).

El ejemplo específico del OP se ajustará a este idioma con un punto y coma agregado:

a*(b+3);

Solo se admitirá un tipo: double . Por lo tanto, no necesito tipos ni ninguna declaración que facilite las cosas.

Antes de comenzar a esbozar la grammar de este lenguaje, estaba pensando en el "objetivo" de la compilación y decidí hacer clases para ...

Un árbol de sintaxis abstracta

Al principio, una clase para almacenar variables:

// storage of variables

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

Las variables proporcionan almacenamiento para un valor pero no para el identificador. Este último se almacena por separado, ya que no es necesario para el uso real de una variable, sino solo para encontrarlo por su nombre:

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

El uso de un std::map automatiza la creación de una variable. Como se sabe de muchos lenguajes de alto nivel, una variable comienza a existir cuando se accede por primera vez.

El árbol de sintaxis abstracta es un

Una representación en árbol de la estructura sintáctica abstracta del código fuente escrita en un lenguaje de programación. Cada nodo del árbol denota una construcción que ocurre en el código fuente.

Tomé este texto del artículo de Wikipedia vinculado anteriormente, no podría decirlo más corto. A continuación mis clases para el 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();
    }
};

Por lo tanto, utilizando las clases AST, la representación de la muestra a*(b+3) sería

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

Nota:

No hay una clase derivada de Expr para representar los paréntesis () porque esto simplemente no es necesario. El procesamiento de paréntesis se considera al construir el árbol en sí. Normalmente, los operadores con mayor prioridad se convierten en hijos de los operadores con menor prioridad. Como resultado, los primeros se calculan antes que los segundos. En el ejemplo anterior, la instancia de ExprBinOpAdd es un elemento secundario de la instancia de ExprBinOpMul (aunque la precedencia de multiplicar es mayor que la precedencia de agregar) que resulta de la consideración adecuada de los paréntesis.

Además de almacenar una expresión analizada, este árbol se puede usar para calcular la expresión llamando al Expr::solve() del nodo raíz:

double result = pExpr->solve();

Tener un back-end para nuestra Calculadora Tiny , el siguiente es el front-end.

Una gramática

Un lenguaje formal se describe mejor mediante una grammar .

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
  ;

con program inicio de símbolos.

Las reglas contienen

• símbolos terminales (comenzando con letras mayúsculas) y
• símbolos no terminales (comenzando con minúsculas)
• dos puntos (:) para separar el lado izquierdo del lado derecho (no terminal en el lado izquierdo puede expandirse a los símbolos en el lado derecho).
• barras verticales ( | ) para separar alternativas
• un símbolo <empty> para expandirse a nada (utilizado para terminar las recursiones).

A partir de los símbolos de terminal, derivaré los tokens para el escáner.

Los símbolos no terminales se transformarán en las funciones del analizador.

La separación de addExpr y mulExpr se ha hecho intencionalmente. Por lo tanto, la precedencia de los operadores multiplicativos sobre los operadores aditivos se "quemará" en la gramática misma. Obviamente, las constantes de coma flotante, los identificadores de variables o las expresiones entre paréntesis (aceptados en primExpr ) tendrán mayor prioridad.

Las reglas contienen solo recursiones correctas. Este es un requisito para los analizadores de descenso recursivo (como aprendí teóricamente en los libros del Dragón y de las experiencias prácticas en el depurador hasta que entendí completamente la razón). La implementación de una regla recursiva izquierda en un analizador de descenso recursivo da como resultado recursiones no terminadas que, a su vez, terminan con un .

El escáner

Es habitual dividir el compilador en un escáner y un analizador.

El escáner procesa la secuencia de caracteres de entrada y agrupa los caracteres en tokens. Los tokens se usan como símbolos terminales en el analizador.

Para la salida de tokens, hice una clase. En mis proyectos profesionales, almacena adicionalmente la posición exacta del archivo para denotar su origen. Esto es conveniente para etiquetar objetos creados con referencias de código fuente, así como cualquier salida de mensajes de error e información de depuración. (... dejado aquí para mantenerlo lo más mínimo posible ...)

// 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) { }
};

Hay dos enumeradores para tokens especiales:

• EOT ... fin del texto (observa el final de la entrada)
• Error ... generado para cualquier personaje que no cabe en ningún otro token.

Los tokens se utilizan como salida del escáner real:

// 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 first 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);
          }
      }
    }
};

El escáner se usa en el analizador.

El analizador

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();
    }
};

Básicamente, el analizador consiste esencialmente en un grupo de funciones de reglas (de acuerdo con las reglas gramaticales) que se llaman entre sí. La clase alrededor de las funciones de la regla es responsable de administrar un contexto de analizador global. Por lo tanto, el único método público de la class Parser es

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

que construye una instancia (con el constructor privado) y llama a la función Parser::parseProgram() correspondiente al program símbolo de inicio.

Internamente, el analizador llama al método Scanner::scan() para llenar su token de anticipación.

Esto se hace en Parser::scan() que se llama siempre cuando se debe consumir un token.

Mirando más de cerca, se hace visible un patrón de cómo las reglas se han traducido a las funciones del analizador:

• Cada no terminal en el lado izquierdo se convierte en una función de análisis. (Mirando más de cerca en el código fuente, te darás cuenta de que no hice esto exactamente. Algunas de las reglas han sido "integradas". Desde mi punto de vista, inserté algunas reglas adicionales para simplificar la gramática que no hice No tengo intención de transformar desde el principio. Lo siento.

• Las alternativas ( | ) se implementan como switch (_lookAhead.tk) . Por lo tanto, cada etiqueta de caso corresponde al primer terminal (token) (token (s)) a la que puede expandirse el símbolo más a la izquierda. (Creo que es por eso que se llama "analizador de anticipación": las decisiones de aplicar las reglas siempre se toman en base al token de anticipación). El libro del dragón tiene un tema sobre los conjuntos FIRST-FOLLOW que explica esto con más detalle.

• Para símbolos de terminal, se llama a Parser::scan() . En casos especiales, se reemplaza por Parser::match() si se espera exactamente un terminal (token).

• Para símbolos no terminales, se realiza la llamada de la función correspondiente.

• Las secuencias de símbolos se realizan simplemente como secuencias de las llamadas anteriores.

El manejo de errores de este analizador es el más simple que he hecho. Podría / debería hacerse mucho más apoyo (invirtiendo más esfuerzo, es decir, líneas de código adicionales). (... pero aquí intenté mantenerlo mínimo ...)

Juntar

Para pruebas y demostraciones, preparé una función main() con algunas muestras integradas (código fuente del programa y datos para procesar):

// 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;  
}

Compilé y probé en VS2013 (Windows 10) y obtuve:

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

Tenga en cuenta que el analizador mismo ignora los espacios y los saltos de línea. Sin embargo, para simplificar el formato de salida de muestra, tengo que usar una expresión terminada en punto y coma por línea. De lo contrario, será difícil asociar las líneas del código fuente con las expresiones compiladas correspondientes. (Recuerde mi nota anterior sobre el Token al que se podría agregar una referencia de código fuente (también conocida como posición del archivo)).

La muestra completa

... con código fuente y prueba de ejecución se puede encontrar en ideone .