这是有关如何构建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的信息，请继续关注吧。
