如何构建一个Linux Shell（三）

这是有关如何构建Linux Shell的教程的第三部分。在本教程的上半部分，我们实现了词法扫描器。现在，让我们将目光转向解析器。回顾一下，解析器是命令行解释器的一部分，它调用词法扫描器以检索令牌，然后从这些令牌中构造一个抽象语法树或AST。这个AST是我们将传递给执行者的东西，好吧，被执行。

　　解析简单命令

我们的解析器将仅包含一个函数， parse_simple_command()。在本教程的后续部分中，我们将添加更多功能以使我们的Shell能够解析循环和条件表达式。

因此，让我们开始对解析器进行编码。您可以先创建一个名为parser.h 在源目录中，您将在其中添加以下代码：

#ifndef PARSER_H

#define PARSER_H

#include "scanner.h" /* struct token_s */

#include "source.h" /* struct source_s */

struct node_s *parse_simple_command(struct token_s *tok);

#endif

没什么，只是声明我们唯一的解析器功能。

接下来，建立 parser.c 并添加以下代码：

#include

#include "shell.h"

#include "parser.h"

#include "scanner.h"

#include "node.h"

#include "source.h"

struct node_s *parse_simple_command(struct token_s *tok)

{

if(!tok)

{

return NULL;

}

struct node_s *cmd = new_node(NODE_COMMAND);

if(!cmd)

{

free_token(tok);

return NULL;

}

struct source_s *src = tok->src;

do

{

if(tok->text[0] == ' ')

{

free_token(tok);

break;

}

struct node_s *word = new_node(NODE_VAR);

if(!word)

{

free_node_tree(cmd);

free_token(tok);

return NULL;

}

set_node_val_str(word, tok->text);

add_child_node(cmd, word);

free_token(tok);

} while((tok = tokenize(src)) != &eof_token);

return cmd;

}

很简单，对吧?要解析一个简单的命令，我们只需要调用tokenize() 检索输入令牌，一个接一个，直到我们得到一个换行符(我们在以下行中对其进行测试： if(tok->text[0] == ' '))，或者我们到达输入的结尾(我们知道当我们收到 eof_token令牌。请参阅上一清单底部附近的循环条件表达式。我们使用输入令牌来创建AST，它是一个树状结构，其中包含有关命令组件的信息。详细信息应足以使执行程序正确执行命令。例如，下图显示了简单命令的AST外观。

命令的AST中的每个节点都必须包含有关其表示的输入令牌的信息（例如原始令牌的文本）。该节点还必须包含指向其子节点（如果该节点是根节点）及其兄弟节点（如果该节点是子节点）的指针。因此，我们需要定义另一个结构，struct node_s，我们将用它来表示AST中的节点。

继续创建一个新文件， node.h，并向其中添加以下代码：

#ifndef NODE_H

#define NODE_H

enum node_type_e

{

NODE_COMMAND, /* simple command */

NODE_VAR, /* variable name (or simply, a word) */

};

enum val_type_e

{

VAL_SINT = 1, /* signed int */

VAL_UINT, /* unsigned int */

VAL_SLLONG, /* signed long long */

VAL_ULLONG, /* unsigned long long */

VAL_FLOAT, /* floating point */

VAL_LDOUBLE, /* long double */

VAL_CHR, /* char */

VAL_STR, /* str (char pointer) */

};

union symval_u

{

long sint;

unsigned long uint;

long long sllong;

unsigned long long ullong;

double sfloat;

long double ldouble;

char chr;

char *str;

};

struct node_s

{

enum node_type_e type; /* type of this node */

enum val_type_e val_type; /* type of this node's val field */

union symval_u val; /* value of this node */

int children; /* number of child nodes */

struct node_s *first_child; /* first child node */

struct node_s *next_sibling, *prev_sibling; /*

* if this is a child node, keep

* pointers to prev/next siblings

*/

};

struct node_s *new_node(enum node_type_e type);

void add_child_node(struct node_s *parent, struct node_s *child);

void free_node_tree(struct node_s *node);

void set_node_val_str(struct node_s *node, char *val);

　　#endif

的 node_type_e枚举定义了我们的AST节点的类型。目前，我们只需要两种类型。第一种类型表示简单命令的AST的根节点，而第二种类型表示简单命令的子节点（包含命令名称和参数）。在本教程的下一部分中，我们将向该枚举添加更多节点类型。

的 val_type_e枚举表示我们可以存储在给定节点结构中的值的类型。对于简单的命令，我们仅使用字符串（VAL_STR枚举类型）。在本系列的稍后部分，我们将在处理其他类型的复杂命令时使用其他类型。

的 symval_uunion表示我们可以存储在给定节点结构中的值。每个节点只能具有一种类型的值，例如字符串或数字值。我们通过引用适当的联合成员来访问节点的值（sint 对于带符号的长整数， str 用于字符串等）。

的 struct node_s结构代表AST节点。它包含一些字段，这些字段告诉我们有关节点类型，节点值的类型以及值本身的信息。如果这是根节点，则children 字段包含子节点的数量，并且 first_child 指向第一个子节点（否则它将是 NULL）。如果这是一个子节点，我们可以按照以下步骤遍历AST节点：next_sibling 和 prev_sibling 指针。

如果要检索节点的值，则需要检查 val_type 字段，然后根据我们在其中找到的内容，访问 val领域。对于简单命令，所有节点都将具有以下属性：

.type => NODE_COMMAND (根节点)或 NODE_VAR （命令名称和参数列表）

.val_type => VAL_STR

.val.str =>指向字符串值的指针

现在让我们编写一些函数来帮助我们处理节点结构。

创建一个名为 node.c 并添加以下代码：

#include

#include

#include

#include

#include "shell.h"

#include "node.h"

#include "parser.h"

struct node_s *new_node(enum node_type_e type)

{

struct node_s *node = malloc(sizeof(struct node_s));

if(!node)

{

return NULL;

}

memset(node, 0, sizeof(struct node_s));

node->type = type;

return node;

}

void add_child_node(struct node_s *parent, struct node_s *child)

{

if(!parent || !child)

{

return;

}

if(!parent->first_child)

{

parent->first_child = child;

}

else

{

struct node_s *sibling = parent->first_child;

while(sibling->next_sibling)

{

sibling = sibling->next_sibling;

}

sibling->next_sibling = child;

child->prev_sibling = sibling;

}

parent->children++;

}

void set_node_val_str(struct node_s *node, char *val)

{

node->val_type = VAL_STR;

if(!val)

{

node->val.str = NULL;

}

else

{

char *val2 = malloc(strlen(val)+1);

if(!val2)

{

node->val.str = NULL;

}

else

{

strcpy(val2, val);

node->val.str = val2;

}

}

}

void free_node_tree(struct node_s *node)

{

if(!node)

{

return;

}

struct node_s *child = node->first_child;

while(child)

{

struct node_s *next = child->next_sibling;

free_node_tree(child);

child = next;

}

if(node->val_type == VAL_STR)

{

if(node->val.str)

{

free(node->val.str);

}

}

free(node);

}

的 new_node() 函数创建一个新节点并将其设置为 type 领域。

的 add_child_node() 函数通过添加新的子节点并增加根节点的扩展来扩展简单命令的AST children领域。如果根节点没有子节点，则将新的子节点分配给first_child根节点的字段。否则，该孩子将被添加到孩子列表的末尾。

的 set_node_val_str()函数将节点的值设置为给定的字符串。它将字符串复制到新分配的内存空间，然后设置val_type 和 val.str字段。将来，我们将定义类似的函数，以使我们可以将节点值设置为不同的数据类型，例如整数和浮点数。

的 free_node_tree()函数释放节点结构使用的内存。如果节点有子节点，则以递归方式调用该函数以释放每个子节点。

解析器就这些了。现在让我们编写命令执行器。

　　执行简单命令

与解析器类似，执行程序将仅包含一个函数， do_simple_command()。在本教程的后续部分中，我们将添加更多功能以使我们能够执行各种命令，例如循环和条件表达式。

创建一个名为 executor.h，并添加以下代码：

#ifndef BACKEND_H

#define BACKEND_H

#include "node.h"

char *search_path(char *file);

int do_exec_cmd(int argc, char **argv);

int do_simple_command(struct node_s *node);

#endif

只是一些功能原型。现在创建executor.c 并定义以下功能：

#include

#include

#include

#include

#include

#include

#include

#include "shell.h"

#include "node.h"

#include "executor.h"

char *search_path(char *file)

{

char *PATH = getenv("PATH");

char *p = PATH;

char *p2;

while(p && *p)

{

p2 = p;

while(*p2 && *p2 != ':')

{

p2++;

}

int plen = p2-p;

if(!plen)

{

plen = 1;

}

int alen = strlen(file);

char path[plen+1+alen+1];

strncpy(path, p, p2-p);

path[p2-p] = '';

if(p2[-1] != '/')

{

strcat(path, "/");

}

strcat(path, file);

struct stat st;

if(stat(path, &st) == 0)

{

if(!S_ISREG(st.st_mode))

{

errno = ENOENT;

p = p2;

if(*p2 == ':')

{

p++;

}

continue;

}

p = malloc(strlen(path)+1);

if(!p)

{

return NULL;

}

strcpy(p, path);

return p;

}

else /* file not found */

{

p = p2;

if(*p2 == ':')

{

p++;

}

}

}

errno = ENOENT;

return NULL;

}

int do_exec_cmd(int argc, char **argv)

{

if(strchr(argv[0], '/'))

{

execv(argv[0], argv);

}

else

{

char *path = search_path(argv[0]);

if(!path)

{

return 0;

}

execv(path, argv);

free(path);

}

return 0;

}

static inline void free_argv(int argc, char **argv)

{

if(!argc)

{

return;

}

while(argc--)

{

free(argv[argc]);

}

}

int do_simple_command(struct node_s *node)

{

if(!node)

{

return 0;

}

struct node_s *child = node->first_child;

if(!child)

{

return 0;

}

int argc = 0;

long max_args = 255;

char *argv[max_args+1]; /* keep 1 for the terminating NULL arg */

char *str;

while(child)

{

str = child->val.str;

argv[argc] = malloc(strlen(str)+1);

if(!argv[argc])

{

free_argv(argc, argv);

return 0;

}

strcpy(argv[argc], str);

if(++argc >= max_args)

{

break;

}

child = child->next_sibling;

}

argv[argc] = NULL;

pid_t child_pid = 0;

if((child_pid = fork()) == 0)

{

do_exec_cmd(argc, argv);

fprintf(stderr, "error: failed to execute command: %s ", strerror(errno));

if(errno == ENOEXEC)

{

exit(126);

}

else if(errno == ENOENT)

{

exit(127);

}

else

{

exit(EXIT_FAILURE);

}

}

else if(child_pid < 0)

{

fprintf(stderr, "error: failed to fork command: %s ", strerror(errno));

return 0;

}

int status = 0;

waitpid(child_pid, &status, 0);

free_argv(argc, argv);

return 1;

}

的 search_path() 函数采用命令名称，然后搜索目录中列出的目录 $PATH变量以尝试查找命令的可执行文件。的$PATH 变量包含用逗号分隔的目录列表，例如 /bin:/usr/bin。对于每个目录，我们通过在目录名称后附加命令名称来创建路径名，然后调用stat()查看是否存在具有给定路径名的文件（为简单起见，我们不检查该文件是否实际可执行，或者我们是否具有执行该文件的足够权限）。如果文件存在，则假定它包含我们要执行的命令，然后返回该命令的完整路径名。如果我们在第一个文件中找不到文件$PATH 目录中，我们搜索第二，第三和其余 $PATH目录，直到找到可执行文件。如果我们无法通过搜索目录中的所有目录来查找命令$PATH， 我们回来 NULL（这通常意味着用户键入了无效的命令名称）。

的 do_exec_cmd() 函数通过调用执行命令 execv()用新的命令可执行文件替换当前过程映像。如果命令名称包含任何斜杠字符，我们将其视为路径名，然后直接调用execv()。否则，我们尝试通过调用来找到命令search_path()，它应该返回将传递给的完整路径名 execv()。

的 free_argv() 函数释放用于存储上次执行命令的参数列表的内存。

的 do_simple_command()函数是执行器中的主要功能。它接受命令的AST并将其转换为参数列表（请记住第零个参数，或者argv[0]，包含我们要执行的命令的名称）。

然后，该函数派生一个新的子进程。在子进程中，我们通过调用执行命令 do_exec_cmd()。如果命令执行成功，则此调用不应返回。如果返回，则表示发生了错误（例如，找不到命令，文件不可执行，内存不足等）。在这种情况下，我们将打印适当的错误消息并以非零退出状态退出。

在父过程中，我们称 waitpid()等待我们的子进程完成执行。然后，我们释放用于存储参数列表的内存并返回。

现在，为了将新代码合并到我们现有的shell中，您需要先更新 main() 通过删除读取的行来发挥作用 printf("%s ", cmd); 并将其替换为以下行：

struct source_s src;

src.buffer = cmd;

src.bufsize = strlen(cmd);

src.curpos = INIT_SRC_POS;

parse_and_execute(&src);

现在，在关闭前 main.c 文件，请转到文件的开头，并在最后一行之后添加以下行 #include 指示：

#include "source.h"

#include "parser.h"

#include "backend.h"

然后转到文件末尾( read_cmd()的函数定义)，并添加以下函数：

int parse_and_execute(struct source_s *src)

{

skip_white_spaces(src);

struct token_s *tok = tokenize(src);

if(tok == &eof_token)

{

return 0;

}

while(tok && tok != &eof_token)

{

struct node_s *cmd = parse_simple_command(tok);

if(!cmd)

{

break;

}

do_simple_command(cmd);

free_node_tree(cmd);

tok = tokenize(src);

}

return 1;

}

此功能使我们的Read-Eval-Print-Loop(REPL)的Eval-Print部分远离main()功能。首先跳过所有前导空格字符，然后解析并执行简单命令，一次执行一个命令，直到输入被消耗为止，然后再将控制权返回给REPL循环。main() 功能。

最后，不要忘记将以下包含和函数原型添加到您的 shell.h 文件，就在关闭之前 #endif 指示：

#include "source.h"

int parse_and_execute(struct source_s *src);

就是这样！现在让我们编译我们的shell。

　　编译外壳

让我们编译一下shell。打开您喜欢的终端仿真器，导航到源目录，并确保其中包含13个文件：

现在，使用以下命令编译shell：

gcc -o shell main.c source.c scanner.c parser.c node.c executor.c prompt.c

如果一切顺利 gcc 应该不输出任何东西，并且应该有一个名为 shell 在当前目录中：

现在通过运行来调用shell ./shell，然后尝试输入一些命令，例如 ls， ls -l和 echo Hello World!：

如您所见，无论我们在命令行中传递多少参数，我们的Shell现在都可以解析和执行简单的命令。好极了！

但是，如果您尝试执行如下命令 echo $PATH，您会发现结果不是您所期望的！这是因为我们的外壳不知道如何访问其环境，如何存储外壳变量以及如何执行单词扩展。这是我们将在本教程的下一部分中解决的问题。想了解更多关于Linux的信息，请继续关注中培教育吧。