Как написать лексер (оболочка) вручную - PullRequest
Новая
       34

Как написать лексер (оболочка) вручную

5 голосов
/ 31 марта 2011

Я работаю над оболочкой, небольшой оболочкой, похожей на bash, без сценариев (если while ...) Я должен сделать лексер / парсер (LL) вручную.

Итак, лексерпреобразует команду ( char * cmd ) в связанный список ( t_list * list ).А анализатор LL преобразует связанный список ( t_list * list ) в AST (двоичное дерево t_btree * root ) с грамматикой

Итак, я знаю, как сделать анализатор LL, но не знаю, как токенизировать мою команду.

Например: ps | grep ls >> file ; make && ./a.out

=> 'ps' '|' 'grep' 'ls' '>>' 'file' ';' ''make '&&' './a.out'

Спасибо.

(я не хочу использовать генератор)

1 Ответ

6 голосов
/ 31 марта 2011

(Это объясняет идею, подсказанную Spudd86 ).

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

  • Общее состояние
  • Внутри имени файла
  • Внутри && токена
  • Внутри ||token

Для каждого состояния и следующего входного символа вы должны решить, что является следующим состоянием, и выводить ли токен.Например:

  • Текущее состояние: Общее ;символ: x => следующее состояние: имя-внутреннего файла
  • Текущее состояние: имя-внутреннего-файла ;символ: пробел => следующее состояние: Общее ;вывести токен
  • Текущее состояние: inside-file-name ;символ: & => следующее состояние: внутри - && ;вывести токен
  • Текущее состояние: внутри - && ;символ: & => следующее состояние: Общее ;вывести токен
  • Текущее состояние: внутри - && ;символ: x => следующее состояние: Общее ;синтаксическая ошибка
  • ... (ad nauseum)

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

Редактирование: некоторый код (извините, если синтаксис испорчен; я обычно программирую на C ++) 

enum state {
    STATE_GENERAL,
    STATE_IN_FILENAME,
    ...
};

// Many characters are treated the same (e.g. 'x' and 'y') - so use categories
enum character_category
{
    CHAR_GENERAL, // can appear in filenames
    CHAR_WHITESPACE = ' ',
    CHAR_AMPERSAND = '&',
    CHAR_PIPE = '|',
    CHAR_EOF = EOF,
    ...
};

character_category translate(int c)
{
    switch (c) {
    case '&': return CHAR_AMPERSAND;
    case ' ': case '\t': case '\n': return CHAR_WHITESPACE;
    ...
    default: return CHAR_GENERAL;
    }
}

void do_stuff()
{
    character_category cat;
    state current_state = STATE_GENERAL;
    state next_state;
    char token[100];
    char token_length = 0;
    do {
        int c = getchar();
        cat = translate(c);
        // The following implements a switch on 2 variables
        int selector = 1000 * current_state + cat;

        switch (selector)
        {
        case 1000 * STATE_GENERAL + CHAR_GENERAL:
            next_state = STATE_IN_FILENAME;
            token[token_length++] = c; // append a character to a filename token
            break;

        case 1000 * STATE_GENERAL + CHAR_WHITESPACE:
            next_state = STATE_GENERAL; // do nothing
            break;

        case 1000 * STATE_GENERAL + CHAR_PIPE:
            next_state = STATE_IN_OR_TOKEN; // the first char in '||' or just '|'
            break;

        // Much repetitive code already; define a macro for the case constants?
        // Have to cover all states and all character categories; good luck...

        case 1000 * STATE_IN_FILENAME + EOF:
        case 1000 * STATE_IN_FILENAME + CHAR_WHITESPACE:
            next_state = STATE_GENERAL;
            printf("Filename token: %s\n", token);
            break;

        default:
            printf("Bug\n"); // forgot one of the cases?
        }

        current_state = next_state;

    } while (cat != CHAR_EOF);
}
...