Алгоритм присвоения индексов if-the-else связке.

[jenya7]

Запнулся на такой алгоритмической проблеме - присвоить индексы.
В прстом случае это тривиально

if (flg0 == 2) then //1
    var4=1;
else  //1
    var4=2;

Но если это вложенные выражения

if (flg0 == 2) then //1
{ //1
    if (flg1 == 1) then //2
        var4=1;
    else //2
    { //2
        if (flg2 == 3) then //3
        {//3
            var5=1;
        }//3
    }//2
}//1
else //1 
    var5=2;

Как отслеживать "потерянные" else и } ?
Я разбиваю выражения на токены

switch (token.type)
{
     case If:  
         expr[expr_size].type = EXPR_TYPE_IF; 
         expr[expr_size].idx++;
     break;
     case Then: 
         expr[expr_size].type = EXPR_TYPE_THEN; 
         expr[expr_size].idx++;
     break;
     case Else: 
        expr[expr_size].type = EXPR_TYPE_ELSE;
        expr[expr_size].idx++;
     break;
     case BlockStart: 
         expr[expr_size].type = EXPR_TYPE_STBLK;  
         expr[expr_size].idx++;
      break;
     case BlockEnd:   
         expr[expr_size].type = EXPR_TYPE_ENDBLK; 
         expr[expr_size].idx++;
     break;
}

Но expr[expr_size].idx++; это примитивный случай а в сложном (nested) выражении он не подходит.

[Cuprum5]

Сообщение от jenya7

if(flg0 == 2)  //1
{  //1
    if(flg1 == 1)

- then не пишется.

[jenya7]

Сообщение от Cuprum5

- then не пишется.

ну это да. у меня basic like скрипт а парсер скрипта я пишу в С, но можно и без then, хотя это не критично.

[Пётр Седов]

jenya7, зачем вы какие-то индексы назначаете? Обычно такой код parse-ят рекурсивным спуском, с построением AST (abstract syntax tree):

#include <assert.h>
#include <string.h>
#include <stdio.h>
#include <stdlib.h>

// лексический анализатор: преобразует текст в последовательность token-ов

enum token_type_t {
  _token_type_undef,
  _token_type_if,
  _token_type_then,
  _token_type_else,
  _token_type_name,
  _token_type_int,
  _token_type_l_paren,
  _token_type_r_paren,
  _token_type_l_brace,
  _token_type_r_brace,
  _token_type_equals,
  _token_type_assignment,
  _token_type_semicolon,
  _token_type_end_of_text,
};

const char* _text = NULL;
int _line_number;
token_type_t _cur_token_type;
int _cur_token_start, _cur_token_end;

void skip_token();
void scan_error();

void lex_init(const char* text) {
  _text = text;
  _line_number = 1;
  _cur_token_type = _token_type_undef;
  _cur_token_end = 0;
  skip_token();
}

bool is_letter_or_underscore(char elem) {
  return (('a' <= elem) && (elem <= 'z')) || (('A' <= elem) && (elem <= 'Z')) || (elem == '_');
}

bool is_digit(char elem) {
  return ('0' <= elem) && (elem <= '9');
}

bool is_letter_or_underscore_or_digit(char elem) {
  return is_letter_or_underscore(elem) || is_digit(elem);
}

void skip_token() {
  assert(_cur_token_type != _token_type_end_of_text);

  // пропускаем пробелы
  int pos = _cur_token_end;
  for (;;) {
    switch (_text[pos]) {
    case ' ':
    case '\t':
    case '\r':
      break;
    case '\n':
      _line_number++;
      break;
    default:
      goto out_of_loop;
    }
    pos++;
  }
out_of_loop:
  // TODO: пропустить комментарии

  _cur_token_start = pos;
  char first_elem = _text[pos];
  switch (first_elem) {
  case '\0':
    _cur_token_type = _token_type_end_of_text;
    _cur_token_end = pos;
    break;
  case '(':
    _cur_token_type = _token_type_l_paren;
    _cur_token_end = pos + 1;
    break;
  case ')':
    _cur_token_type = _token_type_r_paren;
    _cur_token_end = pos + 1;
    break;
  case '{':
    _cur_token_type = _token_type_l_brace;
    _cur_token_end = pos + 1;
    break;
  case '}':
    _cur_token_type = _token_type_r_brace;
    _cur_token_end = pos + 1;
    break;
  case '=':
    if (_text[pos + 1] == '=') {
      _cur_token_type = _token_type_equals;
      _cur_token_end = pos + 2;
    } else {
      _cur_token_type = _token_type_assignment;
      _cur_token_end = pos + 1;
    }
    break;
  case ';':
    _cur_token_type = _token_type_semicolon;
    _cur_token_end = pos + 1;
    break;
  default:
    if (is_letter_or_underscore(first_elem)) {
      do {
        pos++;
      } while (is_letter_or_underscore_or_digit(_text[pos]));
      _cur_token_end = pos;
      int len = _cur_token_end - _cur_token_start;
      if ((len == 2) && (memcmp(_text + _cur_token_start, "if", 2) == 0)) {_cur_token_type = _token_type_if;}
      else if ((len == 4) && (memcmp(_text + _cur_token_start, "then", 4) == 0)) {_cur_token_type = _token_type_then;}
      else if ((len == 4) && (memcmp(_text + _cur_token_start, "else", 4) == 0)) {_cur_token_type = _token_type_else;}
      else {_cur_token_type = _token_type_name;}
    } else if (is_digit(first_elem)) {
      _cur_token_type = _token_type_int;
      do {
        pos++;
      } while (is_digit(_text[pos]));
      _cur_token_end = pos;
    } else {
      scan_error();
    }
  }
}

token_type_t cur_token_type() {
  return _cur_token_type;
}

void check_cur_token_is(token_type_t token_type) {
  if (_cur_token_type != token_type) {
    scan_error();
  }
}

char* cur_token_name() {
  assert(_cur_token_type == _token_type_name);
  int len = _cur_token_end - _cur_token_start;
  char* name = new char[len + 1];
  memcpy(name, _text + _cur_token_start, len);
  name[len] = '\0';
  return name;
}

int cur_token_int() {
  assert(_cur_token_type == _token_type_int);
  int value = _text[_cur_token_start] - '0';
  for (int p = _cur_token_start + 1; p < _cur_token_end; p++) {
    value = value * 10 + (_text[p] - '0');
  }
  return value;
}

void scan_error() {
  fprintf(stderr, "Error in line %i.\n", _line_number);
  exit(1);
}

// синтаксический анализатор: преобразует последовательность token-ов в AST (abstract syntax tree)

enum statement_type_t {
  _statement_type_undef,
  _statement_type_assignment,
  _statement_type_if,
  _statement_type_compound,
  _statement_type_empty,
};

struct statement_t {
  statement_type_t type;
};

struct assignment_statement_t : statement_t {
  char* var_name;
  int value;
};

struct if_statement_t : statement_t {
  char* var_name;
  int compare_value;
  statement_t* true_statement;
  statement_t* false_statement;
};

struct statement_list_node_t {
  statement_list_node_t* next;
  statement_t* statement;
};

struct compound_statement_t : statement_t {
  statement_list_node_t* first; // связный список
};

statement_t* scan_statement() {
  switch (cur_token_type()) {
  case _token_type_name: {
    assignment_statement_t* statement = new assignment_statement_t;
    statement->type = _statement_type_assignment;
    statement->var_name = cur_token_name();
    skip_token(); // имя
    check_cur_token_is(_token_type_assignment);
    skip_token(); // "="
    check_cur_token_is(_token_type_int);
    statement->value = cur_token_int();
    skip_token(); // число
    check_cur_token_is(_token_type_semicolon);
    skip_token(); // ";"
    return statement;
  }
  case _token_type_if: {
    if_statement_t* statement = new if_statement_t;
    statement->type = _statement_type_if;
    skip_token(); // "if"
    check_cur_token_is(_token_type_l_paren);
    skip_token(); // "("
    check_cur_token_is(_token_type_name);
    statement->var_name = cur_token_name();
    skip_token(); // имя
    check_cur_token_is(_token_type_equals);
    skip_token(); // "=="
    check_cur_token_is(_token_type_int);
    statement->compare_value = cur_token_int();
    skip_token(); // число
    check_cur_token_is(_token_type_r_paren);
    skip_token(); // ")"
    check_cur_token_is(_token_type_then);
    skip_token(); // "then"
    statement->true_statement = scan_statement();
    if (cur_token_type() == _token_type_else) {
      skip_token(); // "else"
      statement->false_statement = scan_statement();
    } else {
      statement->false_statement = NULL;
    }
    return statement;
  }
  case _token_type_l_brace: {
    compound_statement_t* statement = new compound_statement_t;
    statement->type = _statement_type_compound;
    skip_token(); // "{"
    statement_list_node_t** link = &statement->first;
    while (cur_token_type() != _token_type_r_brace) {
      statement_list_node_t* n = new statement_list_node_t;
      n->statement = scan_statement();
      // добавляем *n в список
      *link = n;
      link = &n->next;
    }
    skip_token(); // "}"
    // завершаем список
    *link = NULL;
    return statement;
  }
  case _token_type_semicolon: {
    statement_t* statement = new statement_t;
    statement->type = _statement_type_empty;
    skip_token(); // ";"
    return statement;
  }
  default: {
    scan_error();
    return NULL;
  }
  }
}

int main() {
  lex_init(
    "if (flg0 == 2) then\n"
    "{\n"
    "    if (flg1 == 1) then\n"
    "        var4=1;\n"
    "    else\n"
    "    {\n"
    "        if (flg2 == 3) then\n"
    "        {\n"
    "            var5=1;\n"
    "        }\n"
    "    }\n"
    "}\n"
    "else\n"
    "    var5=2;");
  statement_t* s = scan_statement();
  check_cur_token_is(_token_type_end_of_text);
  // TODO: освободить *s
  return 0;
}

На exception safety не заморачивался, всё равно у вас C .
P. S. Привет беженцам с sql.ru .

[jenya7]

Пётр Седов,
спасибо. попробую такой подход.