Код Lexer + Parser для моего языка программирования «Reedoo»

Я работаю над своим собственным языком программирования, как хобби на протяжении последних нескольких месяцев, называется Reedoo. Он реализован в чистом C ++ 11 и использует только библиотеки, которые поставляются с C ++; нет внешних. Я никогда не изучал компьютерную науку, но до сих пор я проработал около 2 недель разработки программного обеспечения в школе, но это все.

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

В настоящее время язык действительно очень маленький. Он имеет инструкцию «print», переменные, выражение, комментарии и выражения if.

Вот ссылка на код GitHub .

Вот простая программа, демонстрирующая все возможности:

if "Hello World" == "Hello World" and "Reedoo" == "reedoo" {
    print "This part of the block shouldn't run"
} else {
    print "This should be displayed in the console."
    print 10 + 2 * (5 + 4)    # Example of expression evaluation and a comment
}

Как это работает, в настоящее время:

В Reedoo есть ручной лексический сканер, который сканирует и вводит файл .rdo и идентифицирует токены. Вот маркеры из этой программы выше:

if
cond:string:"Hello World" eqeq string:"Hello World" and string:"Reedoo" eqeq string:"reedoo" 
opencb
print
string:"This part of the block shouldn't run"
sc
closecb
else
cond:string:"Hello World" eqeq string:"Hello World" and string:"Reedoo" eqeq string:"reedoo" 
opencb
print
string:"This should be displayed in the console."
sc
print
expr:(10+2*(5+4))
sc
closecb
sc

Каждый токен находится в отдельной строке. Точка «sc» означает «двоеточие», лексер вводит полуколоны вместо новых линий. Когда lexer находит условие, например, в выражении if, он добавляет части условия вместе, пока не найдет открытый курсор фигурной скобки.

Анализатор

Затем синтаксический анализатор берет токены, и один за другим их объединяет, пока он не соответствует одному из шаблонов в синтаксическом анализаторе. Парсер также написан вручную.

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

При оценке условий парсер выполняет другую функцию, которая возвращает либо true, либо false.

Переменные

Переменные сохраняются на карте C ++.

Я также широко использую векторы во всех аспектах lexer /parser и связанных с ними функций. Это плохо для производительности?

Наконец, парсер просто выполняет код, когда он его видит. Я не знаю достаточно о деревьях, чтобы реализовать его.

Мне просто хотелось бы получить некоторые отзывы о моем проекте. Я хотел бы знать, правильно ли я буду поступать правильно.

Вот код лексера:

#include <iostream>
#include <string>
#include <cstring>
#include <vector>

#include "lexer.h"

/* Definitions */
/* These are our constants, these are defined as constant at the start of the program so
   that if anything goes wrong in the execution of the code we can always display the
   right kind of errors. */
#define IO_ERROR "[IO ERROR] "
#define SYNTAX_ERROR "[SYNTAX ERROR] "
#define ASSIGN_ERROR "[ASSIGN ERROR] "

using namespace std;

/* Global Variables */
/* Not all of these are actual "keywords" that can be used in programs.
   They are called keywords because they are reserved, either because they
   are specified as keywords in the grammar or because they are reserved by
   the interpreter for internal use. */
std::string reserved[14] = { "print", "string", "sc", "variable", "eq", "undefined", "nl", "num", "expr", "eof", "if", "else", "and", "or" };
/* We store lex_tokens in a vector, we could use an array but specifying an arrays
   size at runtime is technically impossible and the work arounds are a pain. */
std::vector<std::string> lnums;

//string s;

int lnum = 1;
int ecount = 0;

bool rdo_is_reserved(string tok) {
  int i;
  for (i = 0; i < 9;i++) {
    if (tok == reserved[i])
      return true;
    else
      return false;
  }
  return false;
}

vector<string> lex(string prog) {
  std::vector<std::string> lex_tokens;
  int i = 0;
  int start_ce = 0;
  string tok = "";
  string n = "";
  string expr = "";
  bool state = 0;
  bool expr_started = 0;
  bool is_expr = 0;
  bool var_started = 0;
  bool sl_comment_started = 0;
  bool unquoted_str_fnd = false;
  bool block_started = false;
  bool condstarted = false;
  string s = "";
  string v = "";
  string ce = "";
  string condition = "";

  for(i = 0; i < prog.size(); ++i) {
    tok += prog[i];
      if (tok == " " and state == 0) {
        tok = "";
        if (n != "") {
          //is_expr = 1;
          //lex_tokens.push_back(reserved[7] + ":" + n);
        }
        n = "";
        if (v != "") {
          lex_tokens.push_back(reserved[3] + ":\"" + v + "\"");
        }
        v = "";
        var_started = 0;
      } else if (tok == ";" and state == 0) {
        tok = "";
        if (expr.length() >= expr.length()-1) {
          if (expr.substr(expr.length()-1) == "+" or expr.substr(expr.length()-1) == "-" or expr.substr(expr.length()-1) == "/" or expr.substr(expr.length()-1) == "*") {
            if (lnum == 0)
              lnum++;
            cout << SYNTAX_ERROR << "Numbers and expressions must not end with an opperator [line " << lnum << "]" << endl;
            /* If the error count goes about 0, the program immediately exits. This prevents crashes and provides a better user experience. */
            ecount++;
          }
        }
        if (expr != "" and is_expr == 1) {
          lex_tokens.push_back(reserved[8] + ":(" + expr + ")");
        } else if (n != "" and is_expr == 0) {
          lex_tokens.push_back(reserved[7] + ":" + expr);
        }
        if (v != "") {
          lex_tokens.push_back(reserved[3] + ":\"" + v + "\"");
        }
        if (lex_tokens.back() != "sc") {
          lex_tokens.push_back(reserved[2]); 
        }        
        v = "";
        var_started = 0;
        n = "";
        expr = "";
        is_expr = 0;
      } 
      /* Single-line comments */
      else if (tok == "#" and state == 0) {
        /* Start of a single-line comment means end of an expression */
        if (expr != "" and is_expr == 1) {
            lex_tokens.push_back(reserved[8] + ":(" + expr + ")");
          } else if (n != "" and is_expr == 0) {
            lex_tokens.push_back(reserved[7] + ":" + expr);
          }
          /* Also means end of variables */
          if (v != "") {
            lex_tokens.push_back(reserved[3] + ":\"" + v + "\"");
          }
          /* If sl_comment_started doesn't already equal 1, set it to 1 */
        if (sl_comment_started == 0) {
          sl_comment_started = 1;
        }
        v = "";
        var_started = 0;
        n = "";
        expr = "";
        is_expr = 0;
      } else if (sl_comment_started == 1) {
        if (tok == "\n") {
          sl_comment_started = 0;
          if (lex_tokens.size() != 0) {
          if (lex_tokens.back() != "sc") {
            lex_tokens.push_back(reserved[2]); 
          } 
        }
        }
        tok = "";
      } else if (tok == "\r") {
        tok = "";
      } else if (tok == "\t") {
        tok = "";
      } else if (tok == "\n" and state == 1) {

        cout << SYNTAX_ERROR << "EOL found inside of string. [line " << lnum << "]" << endl;
        ecount++;

      } else if (tok == "\n" and state == 0) {

        if (state == 0) {
          tok = "";
          if (expr.length() >= expr.length()-1) {
            if (expr.substr(expr.length()-1) == "+" or expr.substr(expr.length()-1) == "-" or expr.substr(expr.length()-1) == "/" or expr.substr(expr.length()-1) == "*") {
              if (lnum == 0)
                lnum++;
              cout << SYNTAX_ERROR << "Numbers and expressions must not end with an opperator [line " << lnum << "]" << endl;
              /* If the error count goes about 0, the program immediately exits. This prevents crashes and provides a better user experience. */
              ecount++;
            }
          }
          lnum++;
          if (expr != "" and is_expr == 1) {
            lex_tokens.push_back(reserved[8] + ":(" + expr + ")");
          } else if (n != "" and is_expr == 0) {
            lex_tokens.push_back(reserved[7] + ":" + expr);
          }
          if (v != "") {
            lex_tokens.push_back(reserved[3] + ":\"" + v + "\"");
          }
          if (lex_tokens.back() != "sc" and lex_tokens.back() != "opencb") {
            lex_tokens.push_back(reserved[2]); 
          }       
          v = "";
          var_started = 0;
          n = "";
          expr = "";
          is_expr = 0;
        }
      } else if (tok == "%") {
        if (var_started == 0)
          var_started = 1;
      } else if (var_started == 1) {
        v += tok;
        tok = "";
      } else if (tok == "0" or tok == "1" or tok == "2" or tok == "3" or tok == "4" or tok == "5" 
        or tok == "6" or tok == "7" or tok == "8" or tok == "9") {
        if (state == 0) {
          n += tok;
          expr += tok;
        } else {
          s += tok;
        }
        tok = "";
      } else if (tok == "+" or tok == "-" or tok == "*" or tok == "/" or tok == "(" or tok == ")") {
        if (state == 0) {
          expr += tok;
          is_expr = 1;
          tok = "";
          n = "";
        }
      } else if (tok == "=" and state == 0) {
        if (lex_tokens.back() == "eq") {
          if (condstarted == false) {
            lex_tokens.back() = "eqeq";
          } else {
            condition += "eqeq ";
            lex_tokens.pop_back();
          } 
        } else {
        lex_tokens.push_back("eq");
        }
        tok = "";
      } else if (tok == reserved[12] and state == 0) {
          if (condstarted == false) {
            lex_tokens.push_back("and");
          } else {
            condition += "and ";
          } 
        tok = "";
      } else if (tok == reserved[13] and state == 0) {
          if (condstarted == false) {
            lex_tokens.push_back("or");
          } else {
            condition += "or ";
          }
        tok = "";
      } else if (tok == reserved[10]) {
        lex_tokens.push_back(reserved[10]);
        condstarted = true;
        condition = "cond:";
        tok = "";
      } else if (tok == reserved[11]) {
        lex_tokens.push_back(reserved[11]);
        tok = "";
      } else if (tok == "{") {
        block_started = true;
        condstarted = false;
        lex_tokens.push_back(condition);
        lex_tokens.push_back("opencb");
        tok = "";
      } else if (tok == "}") {
        if (expr != "" and is_expr == 1) {
            lex_tokens.push_back(reserved[8] + ":(" + expr + ")");
          } else if (n != "" and is_expr == 0) {
            lex_tokens.push_back(reserved[7] + ":" + expr);
          }
          if (v != "") {
            lex_tokens.push_back(reserved[3] + ":\"" + v + "\"");
          }
          v = "";
        var_started = 0;
        n = "";
        expr = "";
        is_expr = 0;
        if (lex_tokens.back() != "opencb" and lex_tokens.back() != "sc") {
          lex_tokens.push_back("sc");
        }
        lex_tokens.push_back("closecb");
        block_started = false;
        tok = "";
      } else if (tok == reserved[0]) {
        lex_tokens.push_back(reserved[0]);
        tok = "";
      } else if (tok == "\"") {

        if (state == 0) {
          state = 1;
        } else if (state == 1) {
          state = 0;
          if (condstarted == false) {
            lex_tokens.push_back(reserved[1] + ":" + s + "\"");
          } else {
            condition += reserved[1] + ":" + s + "\" ";
          }
          s = "";
          tok = "";
        }
      } else if (state == 1) {
        s += tok;
        tok = "";
      } 

      if (ecount > 0) {
        exit(1);
      }

  }
  //cout << lex_tokens.size() << endl;
  for (i = 0; i < lex_tokens.size();i++) {
    //cout << lex_tokens[i] << endl;
  }
  return lex_tokens;
}

Это довольно долго, но я объясню, как это работает. Существует переменная, называемая tok. tok получает 1 символ дольше каждый раз, пока цикл работает до тех пор, пока он не будет равен одному из ключевых слов из массива reserved.

Строки аналогичны. Переменная s используется для хранения строки по мере ее идентификации, когда вся строка идентифицирована, токен помещается в вектор токенов.

Опять же, числа идентифицируются так же, как строки. Единственная разница в том, что используется эта переменная n.

Условия также идентифицируются аналогично этому. Когда найдено ключевое слово if, lexer предполагает, что все последующее за ним является частью условия, пока не появится токен closecb.

Анализатор

#include <iostream>
#include <string>
#include <fstream>
#include <sstream>
#include <vector>
#include <cstdlib>
#include <cstdio>
#include <algorithm>
#include <functional>


#include "parser.h"
#include "variables.h"
#include "reedoo.h"
#include "io.h"
#include "cond.h"

using namespace std;

void parse(vector<string> tokens) {
  int errcount = 0;
  int linenum = 1;
  int i = 0;
  bool cond = false;
  int cond_result = 2;

  while (i < tokens.size()) {

    TOP:if (tokens[i] + " " + tokens[i+1] == "print sc") {
      cout << SYNTAX_ERROR << "'print' supplied without anything to print [line " << linenum << "]" << endl;
      errcount++;
      i+=2;
      break;
    }

    if (tokens[i] + " " + tokens[i+1].substr(0,6) + " " + tokens[i+2] == "print string sc" or
        tokens[i] + " " + tokens[i+1].substr(0,3) + " " + tokens[i+2] == "print num sc" or
        tokens[i] + " " + tokens[i+1].substr(0,4) + " " + tokens[i+2] == "print expr sc" or
        tokens[i] + " " + tokens[i+1].substr(0,8) + " " + tokens[i+2] == "print variable sc") {
      if (tokens[i+1].substr(0,8) == "variable") {
        doPRINT(goGETVAR(tokens[i+1]));
      } else {
        doPRINT(tokens[i+1]);
      }
      i+=3;
    } else if (tokens[i].substr(0,8) + " " + tokens[i+1] + " " + tokens[i+2].substr(0,3) + " " + tokens[i+3] == "variable eq num sc" or
        tokens[i].substr(0,8) + " " + tokens[i+1] + " " + tokens[i+2].substr(0,6) + " " + tokens[i+3] == "variable eq string sc" or
        tokens[i].substr(0,8) + " " + tokens[i+1] + " " + tokens[i+2].substr(0,4) + " " + tokens[i+3] == "variable eq expr sc" or
        tokens[i].substr(0,8) + " " + tokens[i+1] + " " + tokens[i+2].substr(0,8) + " " + tokens[i+3] == "variable eq variable sc") {
      doASSIGN(tokens[i],tokens[i+2]);
      i+=4;
    } else if (tokens[i] + " " + tokens[i+1].substr(0,4) + " " + tokens[i+2] == "if cond opencb") {
      //cout << eval_cond(tokens[i+1].substr(5)) << endl;
        cond_result = eval_cond(tokens[i+1].substr(5));
        if (eval_cond(tokens[i+1].substr(5))) {
            // Run true block
            //cout << "TOKENS: " << tokens[i+1].substr(5) << eval_cond(tokens[i+1].substr(5)) << endl;
            //i+=3;
        } else {

            //cout << "TOKENS: " << tokens[i+1].substr(5) << eval_cond(tokens[i+1].substr(5)) << endl;
            while (tokens[i] != "closecb") {
              i++;
            }
            i++;

        }
        i+=3;
    } else if (tokens[i] == "closecb") {
        if (tokens[i+1] == "else") {
          i+=1;
          if (cond_result == 0) {

          }
        } else {
          i+=2;
        }
    } else {
        break;
    }

    if (i >= tokens.size()-2) {
      break;
    }

    if (errcount > 0) {
      break;
    }
  }
}

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

Затем синтаксический анализатор нажимает итератор, так что, например, если оператор, идентифицированный парсером, был длинным 3-мя токенами, синтаксический анализатор нажимает итератор на 3 токена.

29 голосов | спросил Francis 15 thEurope/Moscowp30Europe/Moscow09bEurope/MoscowMon, 15 Sep 2014 22:05:41 +0400 2014, 22:05:41

2 ответа


18

Стиль C

Хорошо, первое, что я должен сказать, это то, что ваш код очень похож на C. Первое действие здесь - переместить все эти свободные функции и глобалы в два класса C ++, Lexer и Parser.


Еще один C-код вашего кода - объявить переменные поверх функции. lex() является чемпионом при этом с 18 переменными, сложенными в верхней части функции. Абсолютно не делайте этого в C ++. Объявите переменную в своей точке использования, ограничивая область видимости var.

Внутри цикла должны быть объявлены счетчики для циклов:

int i;
for (i = 0; i < prog.size(); ++i) // poor practice
----
for (int i = 0; i < prog.size(); ++i) // much better

И еще одна привычка старой школы C - использовать код /**/ (многострочные комментарии) везде. Почему бы не использовать гораздо более практичный // для одиночных лайнеров? В настоящее время одиночный комментарий даже действителен в C.


#define IO_ERROR "[IO ERROR] "
#define SYNTAX_ERROR "[SYNTAX ERROR] "
#define ASSIGN_ERROR "[ASSIGN ERROR] "

Эти макросы тоже не очень приятны. Вы должны предпочесть const std::string или const char[]. Для переменных /констант, которые скопированы в файл, это хорошо чтобы объявить их внутри неназванного пространства имен, эффективно создавая константы в области файлов:

namespace 
{
    const std::string IO_ERROR     { "[IO ERROR] "     };
    const std::string SYNTAX_ERROR { "[SYNTAX ERROR] " };
    const std::string ASSIGN_ERROR { "[ASSIGN ERROR] " };
}

Другие глобальные группы, которые вы должны сделать, должны быть членами класса, но если они были чтобы оставаться как глобальные, тогда они также должны быть обернуты неназванным пространством имен.

using namespace std

Это уже упоминалось, и я за это. Не использовать пространство имен std потому что это побеждает цель пространства имен, что позволяет имена сосуществуют без столкновений.

Возможная ошибка?

bool rdo_is_reserved(string tok) {
  int i;
  for (i = 0; i < 9;i++) {
    if (tok == reserved[i])
      return true;
    else
      return false;
  }
  return false;
}

Эта функция выполняет итерацию от 0 до 8, однако массив reserved имеет 14 элементов. Это намеренно или ошибка? Но эта функция бесполезна в любом случае, поскольку стандартная библиотека предоставляет std::find() , который предназначен для такого рода линейных поисков и передает намерения гораздо более четко.

Комментарии оставшиеся строки

if (n != "") {
  //is_expr = 1;
  //lex_tokens.push_back(reserved[7] + ":" + n);
}

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

Большие функции

Функция lex() - массивный зверь. Я бы не хотел быть бедным программистом которому поручено изменить его или исправить ошибку, вызванную им. Эта функция требует срочного рефакторинга. Его следует разбить на несколько вспомогательных методов.

Вызов exit()

lex() также вызывает

exit (1) в своем теле. Это немного грубо, не так ли? Завершение такой программы, без очистки или сообщения об ошибке. Вместо этого следует выбросить исключение . Это C ++, и у нас есть гораздо более современные способы обработки ошибок, плюс с исключением, что у вызывающего есть возможность восстановления после ошибки, если это возможно.

exit(1) и потерянная метка

У вас есть метка внутри функции goto, parse(), которую я ожидаюв паре с оператором TOP:. Тем не менее, я не смог найти ни одного goto внутри функции. Итак, что же делает этот ярлык?

Поскольку вы никогда не учились в CS-школе, вам может не быть известно о статусе goto ... Позволяет просто сказать, что это довольно противоречиво. Я на самом деле не думаю, что goto по-прежнему имеет место в современном C ++, как я уже говорил, язык имеет исключения и автоматическое управление ресурсами, поэтому goto довольно устарел .

goto s

Ваш код также заполнен вызовами cout, большинство из них закомментировано. Вы не должны использовать его непосредственно внутри таких функций, как вы. Большинство пользователей не будет требовать подробный вывод при каждом выполнении программы. Если они вам понадобятся для отладки лучше использовать эти вызовы в макрос, который можно отключить во время компиляции, например:

cout

Или используйте лучшую, более зрелую библиотеку журналов. Сделайте поиск, и вы найдете массу хороших вариантов.

ответил glampert 16 thEurope/Moscowp30Europe/Moscow09bEurope/MoscowTue, 16 Sep 2014 03:18:34 +0400 2014, 03:18:34
12

Это будет довольно большой проект. Я попытаюсь дать вам несколько подсказок (я написал что-то вроде компилятора ECMA-262 /JavaScript и iterpreter с пользовательским байтовым кодом в качестве школьного проекта) .

Если вы действительно планируете развивать большой язык, вам следует, вероятно, узнать о LEX , YACC и BISON , но вам придется узнать формальную грамматику для парсеров .

Если вы хорошо разбираетесь в пробной версии и ошибке, ваш Lexar неплох, но я бы посоветовал начать писать некоторые пользовательские классы и перечисления вместо всех этих строк:

std::string reserved[14] = { "print", "string", "sc", "variable", "eq", "undefined",
    "nl", "num", "expr", "eof", "if", "else", "and", "or" };

Вы должны использовать некоторые константы, чтобы сделать ваш код читаемым и поддерживаемым:

enum LaxarWords {
    lxPrint, lxString, lxSemiColon, ...

Затем вы можете сразу использовать их для создания некоторого байт-кода вместо текстового представления. Это не требование, а личный намек - я на самом деле начал с небольших алгоритмов калькулятора, инфикса до постфикса и инфикса до префикса, оценки экспрессии и, наконец, закончил ECMA-262. В байтовом коде я создал использованную префиксную нотацию, примерно такую:

while (больше (var ("x"), const ("0")), code (декремент (var ("x"))))

Это можно переписать в некоторый байт-код и рекурсивно выполнить (используя, например, массив указателей функций). Нет необходимости в байтовом коде, хорошие классы /структуры с указателями должны делать.

Когда я читаю ваш код, я заметил using namespace std;, но std::string и std::vector). Вероятно, вам следует выбрать, хотите ли вы использовать префикс std:: или поместить некоторый using std::string и т. Д. Вы можете столкнуться с неожиданными проблемами с помощью using namespace std.

Parser

void parse(vector<string> tokens) {
  .
  .
  .
  while (i < tokens.size()) {

    TOP:if (tokens[i] + " " + tokens[i+1] == "print sc") {

Это не выглядит хорошо:

  1. Во-первых, вам нужно скопировать весь vector, используя const vector<string>& должно быть лучше, если вам не нужно менять токены внутри синтаксический анализатор.
  2. Вы получаете доступ к вектору мимо конца
  3. Поместите метку TOP: на отдельной строке, пожалуйста, это выглядит довольно уродливо.

Этот IF определенно нуждается в некоторой работе, какой-то помощник синтаксического анализа (например, get_word) и отдельный if(current_token == "print") { ... (выборка строки к некоторой переменной).

if (tokens[i] + " " + tokens[i+1].substr(0,6) + " " + tokens[i+2] == "print string sc" or
        tokens[i] + " " + tokens[i+1].substr(0,3) + " " + tokens[i+2] == "print num sc" or
        tokens[i] + " " + tokens[i+1].substr(0,4) + " " + tokens[i+2] == "print expr sc" or
        tokens[i] + " " + tokens[i+1].substr(0,8) + " " + tokens[i+2] == "print variable sc") {
ответил firda 15 thEurope/Moscowp30Europe/Moscow09bEurope/MoscowMon, 15 Sep 2014 23:49:57 +0400 2014, 23:49:57

Похожие вопросы

Популярные теги

security × 330linux × 316macos × 2827 × 268performance × 244command-line × 241sql-server × 235joomla-3.x × 222java × 189c++ × 186windows × 180cisco × 168bash × 158c# × 142gmail × 139arduino-uno × 139javascript × 134ssh × 133seo × 132mysql × 132