如何用手写一个（外壳）词法分析器

Question

我正在使用一个shell，一个小型bash-like外壳，没有脚本（如果......） 我必须使词法分析器/解析器（LL）手。

让词法分析器将改变命令（字符* CMD）到链表（t_list *列表）。 而LL解析器将与grammar

所以变换链表（t_list *列表）至AST（二叉树t_btree *根），我知道如何使LL解析器，但我不不知道如何标记我的命令。

例如：ps | grep ls >> file ; make && ./a.out

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

感谢。

（我不希望使用任何发生器）

Answer 1

（这解释了Spudd86暗示的想法）。

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

• 一般状态
• 中的文件名
• 里面的&&令牌
• 里面的||令牌

对于每一个国家和一个输入字符，你必须决定什么是下一个状态，以及是否输出令牌。例如：

• 当前状态：一般;字符：X =>下一个状态：内部文件名称
• 当前状态：内部文件名称; character：space => next state：General;输出令牌
• 当前状态：里面文件名; character：& => next state：inside- & &;输出令牌
• 当前状态：inside- & &;字符：& =>下一个状态：通用;输出令牌
• 当前状态：inside- & &;字符：x =>下一个状态：通用;语法错误
• ...（广告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); 
}