c - 如何手工编写(shell)词法分析器

Question

我正在开发一个 shell，一个类似 bash 的小 shell，没有脚本(if while ...)我必须手工制作词法分析器/解析器 (LL)。

因此词法分析器会将命令(char *cmd)转换为链表(t_list *list)。LL 解析器会将链表 (t_list *list) 转换为具有 grammar 的 AST(二叉树 t_btree *root)

所以，我知道如何制作 LL 解析器，但我不知道如何标记我的命令。

例如:ps | grep ls >> 文件；制作 && ./a.out

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

谢谢。

(我不想使用任何生成器)

Answer 1

(这解释了 Spudd86 暗示的想法)。

您需要实现一个有限状态机。有以下几种状态:

• 一般状态
• 在文件名中
• 在 && token 中
• 在|| token 中

对于每个状态和下一个输入字符，您必须决定下一个状态是什么，以及是否输出 token 。例如:

• 当前状态:一般；字符:x => 下一个状态:inside-file-name
• 当前状态:inside-file-name； character: space => next state: General;输出 token
• 当前状态:inside-file-name；字符:& => 下一个状态:inside-&&；输出 token
• 当前状态:内部-&&；字符:& => 下一个状态:一般；输出 token
• 当前状态:内部-&&；字符:x => 下一个状态:一般；语法错误
• ...(令人作呕)

制定所有规则是一项非常无聊的工作(当您必须调试生成的代码时乐趣才开始)，因此大多数人使用代码生成器来完成这项工作。

---

编辑:一些代码(抱歉，如果语法搞砸了；我通常用 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);
}