Cómo escribir un lexer (shell) a mano

Question

Estoy trabajando en un shell, un pequeño shell como bash, sin secuencias de comandos (si es que ...) Tengo que hacer el analizador/analizador (LL) por mano.

Así que el analizador léxico transformará el comando (char * cmd) a una lista enlazada (t_list * Lista). Y el analizador LL transformará la lista enlazada (t_list * Lista) a un AST (árbol binario t_btree * raíz) con un grammar

lo tanto, sé cómo hacer que el analizador sintáctico LL pero don' Sé cómo tokenizar mi comando.

Por ejemplo: ps | grep ls >> file ; make && ./a.out

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

Gracias.

(no quiero utilizar cualquier generador)

Answer 1

(Esto explica la idea insinuado por Spudd86).

Debe implementar una máquina de estado finito. Existen los siguientes estados:

• estado general
• Dentro de un nombre de archivo
• Dentro de la && símbolo
• Dentro de la || símbolo

Para cada estado y el siguiente carácter de entrada, se tiene que decidir cuál es el siguiente estado y si debe generar un token.Por ejemplo:

• Estado actual: General; Carácter: x => siguiente estado: interior-file-name
• Estado actual: interior-file-name; carácter: espacio => estado siguiente: General; muestra el token
• Estado actual: dentro-nombre-archivo; carácter: & => estado siguiente: dentro de & &; salida el token
• Estado actual: dentro- & &; carácter: & => estado siguiente: General; salida el token
• Estado actual: dentro- & &; carácter: x => estado siguiente: General; error de sintaxis
• ... (hasta la saciedad)

Es mucho trabajo aburrido de trabajar a cabo todas las reglas (la diversión comienza cuando se debe depurar el código resultante), por lo que la mayoría de las personas usan generadores de código para hacer eso .

---

Editar: algo de código (lo siento si la sintaxis está en mal estado en marcha, por lo general el programa en 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); 
}