東大の演習問題に挑戦

GCC

東大のアルゴリズムとデータ構造演習(リンク切れ)が面白そうなので演習問題を解いてみる。

課題1-A：シェルを実装せよ。


ガンバリマス。

方針

パイプもリダイレクトも無し。一番簡単そうな実装を目指します。

  • 1行取得は面倒なのでGNU getline使います。
  • fork,exec,waitを使って実装します。
  • execはexecvpを使うことにしました。
  • 引数の処理は、単語の先頭ポインタをargvに追加して、スペースか改行があったら\0で踏み潰していきます。

コーディング

#define _GNU_SOURCE

#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>

void prompt(void)
{
    printf("* ");
}

int main(void)
{
    /* 行の取得用 */
    char *line = NULL;
    size_t len = 0;
    ssize_t length;
    char *p;

    /* execに渡すやつ */
    char *argv[256];
    int argc;

    prompt();
    while ((length = getline(&line, &len, stdin)) != -1) {
        if (length > 1) { /* 改行のみの場合は無視 */
            argc = 0;
            argv[argc++] = line;

            /* 踏み潰しながらargvを作る */
            for (p = line; *p != '\0'; p++) {
                if (*p == ' ') {
                    *p = '\0';
                    argv[argc++] = p + 1;
                } else if (*p == '\n') {
                    *p = '\0';
                    argv[argc] = NULL; /* 改行区切り */
                }
            }

            if (fork() == 0) { /* 子プロセス */

                execvp(line, argv);

                /* エラーの時はここへ */
                fprintf(stderr, "起動できまっせん。\n");
                exit(EXIT_FAILURE);
            }

            wait(NULL);
        }
        prompt();
    }

    if (line)
        free(line);

    return EXIT_SUCCESS;
}

できたぁ〜。

プロンプトは「*」っす。

動かしてみる

% ./shell
* head -5 /etc/passwd
root:x:0:0:root:/root:/bin/zsh
bin:x:1:1:bin:/bin:/sbin/nologin
daemon:x:2:2:daemon:/sbin:/sbin/nologin
adm:x:3:4:adm:/var/adm:/sbin/nologin
lp:x:4:7:lp:/var/spool/lpd:/sbin/nologin
*

うは、動いてるよ!!

反省とか

  • 引数の処理がイマイチ。引数の処理を練り直したい。
    • 踏み潰し方だけではあんまり良くない。単語を区切るだけだけど、適当に構文解析したほうがいいかも。
  • パイプ、リダイレクトを実装してみたい。
  • ワイルドカードがホシィ。

シェル作るのは楽しいっす。

イマイチなので、パーサーを書いたバージョン

やっぱり、引数の処理が気に入らないので、パーサー書いた。

#define _GNU_SOURCE

#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>

void prompt(void)
{
    printf("* ");
}

/* パーサ */
void perse(char *p, char *argv[])
{
    int argc = 0;

    for (;;) {
        while (*p == ' ' || *p == '\t') { /* スペースは踏み潰しながらトバス */
            *p = '\0';
            p++;
        }
        if (*p == '\n' || *p == '\0') {   /* 改行ならしゅーりょー */
            *p = '\0';
            argv[argc] = NULL;
            return;
        }
        argv[argc++] = p;                 /* 単語の先頭ポインタを保存 */
        while (*p != ' ' && *p != '\t' && *p != '\n' && *p != '\0') { /* 単語らしきものを探す */
            p++;
        }
    }
}

int main(void)
{
    /* 行の取得用 */
    char *line = NULL;
    size_t len = 0;

    /* execに渡すやつ */
    char *argv[256];

    prompt();
    while (getline(&line, &len, stdin) != -1) {

        perse(line, argv); /* コマンドの解析 */

        if (argv[0] != NULL) { /* 引数チェック */
            if (fork() == 0) { /* 子プロセス */
                execvp(argv[0], argv);
                /* エラーの時はここへ */
                fprintf(stderr, "起動できまっせん。\n");
                exit(EXIT_FAILURE);
            } else {           /* 親父 */
                wait(NULL);
            }
        }

        prompt();
    }

    if (line)
        free(line);

    return EXIT_SUCCESS;
}

うん。スッキリ。これでビルトインコマンドが書けそうだ。

おっと、バグがあったのでちょっと修正。

更新履歴

  • 2013/02/09
    • 元ネタのリンクが切れてますね。残念。