代做CS252编程、代写C++设计程序

日期：2024-03-02 10:25

Lab 3 - Implementing a Shell

FAQ | Additional Notes | Grading Form P1 | Grading Form P2 | Final Grading Form

Updates

Any changes that need to be made to the handout / lab will be mentioned here.

Introduction

Getting Started

Part 1: Parsing and Executing Commands

Part 1A: Lex and Yacc - Accepting more complex commands

Part 1B: Executing commands

1B.1: Simple command process creation and execution

1B.2: File redirection

1B.3: Pipes

1B.4: isatty()

Testing

Submission

Part 2: Signal Handling, More Parsing, and Subshells

2.1: Ctrl-C

2.2: Zombie Elimination

2.3: Exit

2.4: Quotes

2.5: Escaping

2.6: Builtin Functions

2.7: Creating a Default Source File: “.shellrc”

2.8: Subshells

2.9: Process Substitution

Submission

Part 3: Expansions, Wildcards, and Line Editing

3.1: Environment variable expansion

3.2: Tilde expansion

3.3: Wildcarding

3.4: Edit mode

3.5: History

3.6: Path completion

3.7: Variable prompt

Submission

NOTE: Text in green indicates extra credit features.

Introduction

The goal of this project is to build a shell interpreter which combines behavior from common

shells including bash and csh. The project has been divided into parts. Some skeleton code has

been provided, so you will not be starting from scratch.

Getting Started

Login to a CS department machine (a lab machine or data.cs.purdue.edu), navigate to

your preferred directory, and run

Cd

cd cs252

tar -xvf /homes/cs252/Spring2024/lab3-shell-x86-Spring2024-if-while/lab3-test.tar

git clone /homes/cs252/sourcecontrol/work/$USER/lab3-src.git

cd lab3-src

Notice that the lab3-test/ and lab3-src/ are different directories.

Build the shell by typing make, and start it by typing ./shell. Type in some commands, for

example:

ls -al

ls -al aaa bbb > out

At this point, the shell does not have much implemented; notice what happens if you try to use

some shell features that you used in Lab 2. For example, try redirecting input or editing a typo in

a command.

Part 1: Parsing and Executing Commands

To begin, you will write a scanner and parser for your shell using the open source versions of

Lex and Yacc (Flex and Bison). Look through the skeleton code and try to understand how it

works. First, read the Makefile to understand how the program is built; notice that it is mostly

written in C++.

The file command.hh implements a data structure that represents a shell command. The struct

SimpleCommand implements an argument list for a simple command (i.e. a command of the

form mycmd arg1 arg2 arg3). When pipes are used, a command will be composed of

multiple SimpleCommands. The struct Command represents a list of simple commands.

Additionally, Command has fields which allow the user to specify files to use for input, output,

and error redirection.

Much of the provided code uses C style data structure; however, you may find it easier to

manage the code by making use of C++ features. Feel free to modify the skeleton code to make

better use of C++ types such as string, vector, map, etc. In fact, you may find that doing so

eases the memory management difficulty of this lab significantly.

Part 1A: Lex and Yacc - Accepting more complex commands

You will use Lex and Yacc to implement the grammar of your shell. See here and here for

tutorials on Lex and Yacc. Here is an updated manual for Flex

The skeleton shell initially implements only a very limited grammar:

cmd [arg]* [> filename]

The first objective for Part 1 is to modify shell.l and shell.y to support a more complex

grammar:

cmd [arg]* [| cmd [arg]* ]* [ [> filename] [< filename] [2> filename]

[>& filename] [>> filename] [>>& filename] ]* [&]

Insert the necessary code in shell.l and shell.y to fill in the Command struct. Make sure

that the Command struct is printed correctly.

Some example commands to test with are included in the table below:

ls

ls -al

ls -al aaa bbb cc

ls -al aaa bbb cc > outfile

ls | cat | grep

ls | cat | grep > out < inp

ls aaaa | grep cccc | grep jjjj ssss dfdffdf

ls aaaa | grep cccc | grep jjjj ssss dfdffdf >& out < in

httpd &

ls aaaa | grep cccc | grep jjjj ssss dfdffdf >>& out < in

Part 1B: Executing commands

Now you will implement the execution of simple commands, IO redirection, piping, and allowing

processes to run in the background.

1B.1: Simple command process creation and execution

For each simple command, create a new process using fork() and call execvp() to execute

the corresponding executable. If the Command is not set to execute in the background, then

your shell will have to wait for the last simple command to finish using waitpid(). Refer to the

man pages of these functions for information on their arguments and return values. Additionally,

we have provided the file cat_grep.cc as an example, which is a program that creates

processes and performs redirection.

After you have completed Part 1B.1, you should be able to execute commands such as:

ls -al

ls -al /etc &

1B.2: File redirection

If the the Command specifies files for IO redirection (of input, output, or error), then create those

files as necessary. To change the file descriptors to point to the specified files, you will need to

use dup2(). Note that file descriptors 0, 1, and 2 correspond to input, output, and error

respectively. See the example redirection in cat_grep.cc.

After you have completed Part 1B.2, you should be able to execute commands such as:

ls -al > out

cat -q cat 2> dog

ls

cat out

ls /tttt >& err

cat err

cat < out

cat < out > out2

cat out2

ls /tt >>& out2

Note:

● 2> the command redirects stderr to the specified file

● >& the command redirects both stdout and stderr to the specified file

● >> the command appends stdout to the specified file

● >>& the command appends both stdout and stderr to the specified file

1B.3: Pipes

Pipes are an interface that allow for inter-process communication. They have two ends, one for

reading and one for writing. Data which is written into the write end of the pipe is buffered until it

is read from the read end by another process.

Use pipe() to create a pipe that will redirect the output of one simple command to the input of

the next simple command. You will again need to use dup2() to handle the redirection. See the

example piping in cat_grep.cc.

After you have completed Part 1B.3, you should be able to execute commands such as:

ls -al | grep command

ls -al | grep command | grep command.o

ls -al | grep command

ls -al | grep command | grep command.o > out

cat out

1B.4: isatty()

When your shell uses a file as standard input your shell should not print a prompt. This is

important because your shell will be graded by redirecting small scripts into your shell and

comparing the output. Use the function isatty() to find out if the input comes from a file or

from a terminal.

Note: due to how the automated tests are built, you will need to complete this portion of part 1

before your shell will pass any of the automated tests.

Testing

Much of your shell will be graded using automatic testing, so make sure that your shell passes

the provided tests. Your grade for this lab will partially depend on the number of tests that pass.

The tests provided will be used for each part of the project, so don’t worry if you are unable to

pass all of the tests after finishing part 1.

See ~/cs252/lab3-test/README for an explanation of how to run the tests. The tests will

also give you an estimated grade. This grade is just an approximation. Other tests which are

not provided will be used as well during official grading; some points will also be awarded based

on a demo of your shell.

Submission

To turn in Part 1:

1. Login to a CS department machine

2. Navigate to your lab3-src directory

3. Run make clean

4. Run make to check that your shell builds correctly

5. Run git tag -f part1

6. Run git push -f origin part1

7. Run git show part1

8. The show command should show the diff from the most recent commit

Part 2: Signal Handling, More Parsing, and

Subshells

In Part 2, you will begin to add features that make your shell more useful and fully featured.

2.1: Ctrl-C

In csh, bash, and other common shells, you can type Ctrl-C to stop a running command; this

can be especially helpful if a command you are running takes longer to finish than expected or if

you are running a buggy program that falls into an infinite loop. This is accomplished by

generating a SIGINT signal which is passed on to the program currently being run. If Ctrl-C is

typed when no command is running, the current prompt is discarded and a fresh prompt is

printed. As-is, your shell will simply exit when Ctrl-C is typed and no command is running. Make

your shell behave as csh does with respect to Ctrl-C. See ctrl-c.cc for an example of detecting

and ignoring a SIGINT signal. Also see the man page for sigaction().

2.2: Zombie Elimination

Try running the following set of commands in the shell you have written:

ls &

ls &

ls &

ls &

/bin/ps -u <your-login> | grep defu

The last command shows all processes that show up as "defu" (for “defunct”). Such processes

are called zombie processes: they no longer run, but wait for the parent to acknowledge that

they have finished. Notice that each of the processes that are created in the background

become zombie processes.

To cleanup these processes you will have to set up a signal handler, like the one you used for

Ctrl-C, to catch the SIGCHLD signals that are sent to the parent when a child process finishes.

The signal handler will then call waitpid() to cleanup the zombie child. Check the man pages

for the waitpid() and sigaction() system calls. The shell should print the process ID of

the child when a process in the background exits in the form "[PID] exited."

2.3: Exit

Implement a special command called exit which will exit the shell when run. Note that exit

should not cause a new process to be created; it should be picked up by your shell during

parsing and cause your shell to exit. Also, make your shell print a goodbye message, like so:

myshell> exit

Good bye!!

bash$

2.4: Quotes

Add support for quotes in your shell. It should be possible to pass arguments with spaces if they

are surrounded by quotes. For example:

myshell> ls "command.cc Makefile"

command.cc Makefile not found

Here, "command.cc Makefile" is only one argument. You will need to remove the quotes

before using the argument they contain. Note: wildcard expansion will not be expected inside

quotes in the next part of the lab.

2.5: Escaping

Allow the escape character. Any character can be part of an argument if it comes immediately

after \, including special characters such as quotation marks (“”) and an ampersand (&). For

example:

myshell> echo \"Hello between quotes\"

"Hello between quotes"

myshell> echo this is an ampersand \&

this is an ampersand &

2.6: Builtin Functions

Certain commands you can run in csh or bash do not actually correspond to executables;

much like the exit command implemented for part 2.2, these commands are detected by the

shell during parsing to carry out certain special functions. Implement the following builtin

commands:

printenv Prints the environment variables of the shell. The environment variables of

a process are stored in the variable char **environ;, a

null-terminated array of strings. Refer to the man page for environ.

setenv A B Sets the environment variable A to value B. See article.

unsetenv A Un-sets environment variable A

source A Runs file A line-by-line, as though it were being typed into the shell by a

user. See Multiple Input Buffers or look at Flex manual

cd A Changes the current directory to A. If no directory is specified, default to

the home directory. See the man page for chdir().

You should be able to use builtins like any other commands (e.g. grep, cat, etc.), including with

redirection and piping.

2.7: Creating a Default Source File: “.shellrc” (Extra credit)

When your shell starts, it should attempt to do the equivalent of running “source

.shellrc”. (This feature will be considered extra credit).

2.8: Subshells

Sometimes a user will need to run a complex command that uses the output from one shell

command as the input of another. Any argument of the form $(command and args) will be

processed by another shell (the subshell) which is executed as a child process and the output

will be fed back into the original parent shell. For example:

● echo $(expr 1 + 1) will become echo 2

● echo a b > dir; ls $(cat dir) will list the contents of directories a and b

The example below further explains how your shell should interpret and processes commands

with and without backticks:

myshell> echo test

Lex & Yacc parses the command and executes it normally

myshell> echo $(ls)

Lex & Yacc parses the command, but must evaluate the ls command before the echo

command can be executed. Below is a step by step example of how a subshell command is

processed.

myshell> echo $(ls) “and more”

file1 file2 file3 and more

1. A command containing a subshell command is passed to the shell

Input buffer=echo $(ls) ”and more”

Command Word=

Arguments=

2. The shell parses the echo command normally.

Input buffer=echo $(ls) ”and more”

Command Word=echo

Arguments=

3. The shell parses the subshell command `ls`

Input buffer=echo $(ls) ”and more”

Command Word=echo

Arguments=

4. After executing the command in the subshell the input is injected at the head of the buffer

Input buffer=echo $(ls) file1 file2 file3 ”and more”

Command Word=echo

Arguments=

5. Finally the shell parses file1, file2, file3, and “and more” as the arguments to echo.

Input buffer=echo $(ls) file1 file2 file3 ”and more”

Command Word=echo

Arguments=file1, file2, file3, “and more”

You will implement this feature by

1. Scanning the command between backticks in shell.l

2. Calling your own shell as a child process and passing it the command as input. You will

need two pipes to communicate with the child process; one to pass the command to the

child, and the other to read the output from the child.

3. Reading the output from the child process and putting the characters of the output back

into the scanner’s buffer using the function yy_unput(int c) in reverse order. See the

FAQ for more details.

Hint: It is common for students to redirect the current shell’s stdin and stdout file descriptors to

communicate with the subshell process, however this is not necessary. The current shell can

communicate with the subshell by writing to the pipes directly.

IMPORTANT: Do not use the popen() call or a temporary file for the interprocess

communication. You must use the method discussed above.

Submission

To turn in Part 2:

1. Login to a CS department machine

2. Navigate to your lab3-src directory

3. Run make clean

4. Run make to check that your shell builds correctly

5. Run git tag -f part2

6. Run git push -f origin part2

7. Run git show part2

8. The show command should show the diff from the most recent commit

Part 3: Expansions, Wildcards, and Line Editing

The final part of the lab involves adding a few major usability features to your shell. You will allow

for your parser to expand a few types of input, handle wildcards, and implement a line editor that

allows you to do things like fixing typos and traversing a history of previously submitted

commands.

3.1: Environment variable expansion

You will implement environment variable expansion. Recall that in the previous part of the lab,

you allowed users to set and retrieve environmental variables using builtin functions. When a

string of the form ${var} appears in an argument, it will be expanded to the value that

corresponds to the variable var in the environment table. For example:

myshell> setenv A Hello

myshell> setenv B World

myshell> echo ${A} ${B}

Hello World

myshell> setenv C ap

myshell> setenv D les

myshell> echo I like ${C}p${D}

I like apples

Additionally, the following special expansions are required to be implemented:

${$} The PID of the shell process

${?} The return code of the last executed simple command (ignoring

commands sent to the background).

${!} PID of the last process run in the background

${_} The last argument in the fully expanded previous command

Note: this excludes redirects

${SHELL} The path of your shell executable.

Hint: realpath() can expand a relative path to an absolute path. You can

obtain the relative path to the shell in argv[0]

3.2: Tilde expansion

When the character "~" appears itself or before "/" it will be expanded to the home directory of the

current user. If "~" appears before a word, the characters after the "~" up to the first "/" will be

expanded to the home directory of the user with that login. For example:

ls ~ -- List the home directory

ls ~george -- List george's home directory

ls ~george/dir -- List subdirectory "dir" in george's directory

3.3: Wildcarding

In most shells, including bash and csh, you can use * and ? as wildcard characters in file and

directory names. The "*" wildcard matches 0 or more non-blank characters, except "." if it is the first

character in the file name. The "?" wildcard matches one non-blank character, except "." if it is the first

character in the file name. Try wildcarding in csh to see the results. You will implement wildcarding as

follows:

1. First, handle wildcarding only within the current directory.

○ Before you insert a new argument in the current simple command, check if the

argument has wild card (* or ?). If it does, then insert the file names that match the

wildcard (including their absolute paths).

○ Use opendir and readdir to get all the entries of the current directory (check the

man pages).

○ Use the functions regcomp and regexec to find the entries that match the wildcard.

Check the example provided in regular.cc to see how to do this. Notice that the

wildcards and the regular expressions used in the library are different, so you will have

to convert from wildcards to regular expressions.

2. Once your wildcarding implementation works for the current directory, make it work for any

absolute path.

IMPORTANT: Do not use the glob() call. You must use the functions discussed above.

Reminder: you do not need to handle wildcard expansion between quotation marks!

3.3: Supporting if/while/for

The file shell.y already includes rules for matching if/while/for expressions. You will complete the

implementation of these script constructions in your shell.

3.3.1 Implementing if statement

When the shell receives an input such as:

myshell> if [ -f Shell.o ]; then echo File Exists; fi

File Exists

Also, it can be used in the following way

myshell>if [ -f Shell.o ]; then

echo File Exists

fi

File Exists

Or in a shell script

vim testif.sh

#!./shell

if [ -f Shell.o ]; then

echo File Exists

fi

:x

chmod +x testif.sh

./testif.sh

File Exists

The arguments inside the brackets [ -f Shell.o ] will be executed by your shell in a child process using

the UNIX command "test -f Shell.o" and if the exit value is 0 (success) then the list of commands

inside the if statement (echo File Exists) will be executed.

You can run the UNIX "test" command as follows.

bash> test -f Shell.o

echo $?

0

Type "man test" to see other arguments for the test command.

3.3.2 Implementing while statement

When the shell receives an input such as:

myshell> setenv count 5; while[ $count -ne 0 ]; do echo $count; setenv

count `expr count - 1`; done

5

4

3

2

1

Also, it can be used in the following way

myshell>setenv count 5; while[ $count -ne 0 ]; do

echo $count; setenv count `expr count - 1`;

done

5

4

3

2

1

Or in a shell script

vim testwhile.sh

#!./shell

setenv count 5;

while[ $count -ne 0 ]; do

echo $count;

setenv count `expr count - 1`;

done

:x

chmod +x testwhile.sh

./testwhile.sh

5

4

3

2

1

The arguments inside the brackets [ -f Shell.o ] will be executed by your shell in a child process using

the UNIX command "test -f Shell.o" and if the exit value is 0 (success) then the list of commands

inside the while statement will be executed. After executing the list of commands, it will reevaluate the

expression in brackets.

3.3.3 Implementing for statement

When the shell receives an input such as:

myshell> for t in a b c d; do echo $t $t.org; done

a a.org

b b.org

c c.org

d d.org

Also, it can be used in the following way

myshell>for t in a b c d; do

echo $t $t.org;

done

a a.org

b b.org

c c.org

d d.org

Or in a shell script

vim testfor.sh

#!./shell

for t in a b c d; do

echo $t $t.org;

done

chmod +x testfor.sh

./testwhile.sh

5

4

3

2

1

The arguments inside the brackets [ -f Shell.o ] will be executed by your shell in a child process using

the UNIX command "test -f Shell.o" and if the exit value is 0 (success) then the list of commands

inside the while statement will be executed. After executing the list of commands, it will reevaluate the

expression in brackets.

3.3.4 Implementing Argument Environment Variables

To be able top interact with the shell script arguments, you will Add the following environment

variables:

${#} Number of arguments

${0} The shell script name

${1},

${2},...

${n}

Argument 1 to n of the script

${*} Expands to all the arguments passed to the script.

3.4: Edit mode (Extra only after finishing required parts)

tty-raw-mode.c and read-line.c contains the sample code that you will need to change your

terminal’s input from canonical to raw mode. In raw mode you will have more control over the terminal,

passing the characters to the shell as they are typed.

There are two example programs to look at: keyboard-example and read-line-example.

Run keyboard-example and type letters from your keyboard. You will see the corresponding

ascii code immediately printed on the screen.

The other program, read-line-example, is a simple line editor. Run this program and type

cread-line.ctrl-? to see the options of this program. The up-arrow causes the program to

print the previous command in its history.

The file tty-raw-mode.c contains sample code which switches the terminal from canonical

to raw mode. The file read-line.c contains sample code which implements the simple line

editor. Study the source code in these files.

To connect the line editor to your shell, add the following code to shell.l after the #include

lines:

%{

#include <string.h

#include "y.tab.h"

//////////// Start added code ///////////

extern “C” char * read_line();

int mygetc(FILE * f) {

static char *p;

char ch;

if (!isatty(0)) {

// stdin is not a tty. Call real getc

return getc(f);

}

// stdin is a tty. Call our read_line.

if (p==NULL || *p == 0) {

char * s = read_line();

p = s;

}

ch = *p;

p++;

return ch;

}

#undef getc

#define getc(f) mygetc(f)

/////////// End added code ///////////

%}

%%

Now modify your Makefile to compile your shell with the line editor. To do this just

defineEDIT_MODE_ON variable in the Makefile to be something for example “yes”.

EDIT_MODE_ON=yes

Now modify read-line.c to add the following editor commands:

● Left arrow key: Move the cursor to the left and allow insertion at that position. If the

cursor is at the beginning of the line it does nothing.

● Right arrow key: Move the cursor to the right and allow insertion at that position. If the

cursor is at the end of the line it does nothing.

● Delete key (ctrl-D): Removes the character at the cursor. The characters in the right side

are shifted to the left.

● Backspace key (ctrl-H): Removes the character at the position before the cursor. The

characters in the right side are shifted to the left.

● Home key (ctrl-A): The cursor moves to the beginning of the line

● End key (ctrl-E): The cursor moves to the end of the line

IMPORTANT: Do not use the readline library. You must implement your own line editor.

3.5: History (Extra only after finishing required parts)

In addition to the line editor above, also implement a history list. Currently the provided history is

static. You need to update the history by creating your own history table. Every time the user

runs a new command, a row will be added to the table. Implement the following editor

commands:

● Up arrow key: Shows the previous command in the history list.

● Down arrow key: Shows the next command in the history list.

3.6: Path completion (Extra only after finishing required

parts)

Implement path completion. When the <tab> key is typed, the editor will try to expand the

current word to the matching files similar to what csh and bash do.

bash$ ls

cart.txt card.txt

bash$ c<tab>

When tab is pressed, the line above becomes:

bash$ car

With the line indicator after c.

3.7: Variable prompt (Extra only after finishing required

parts)

The shell has a default prompt indicator: myprompt>. If there is an environment variable called

PROMPT, your shell should print the value of that variable as the prompt instead. Additionally, if

there is an environment variable called ON_ERROR, the shell should print its value whenever the

last simple command in a command exits with a nonzero code.

myshell> setenv PROMPT --cs252--

--cs252-- gcc

gcc: fatal error: no input files

compilation terminated

--cs252-- setenv ON_ERROR oops

--cs252-- gcc

gcc: fatal error: no input files

compilation terminated

oops

--cs252--

IMPORTANT: There are no automatic tests for the line editor so it will be

tested manually by the TAs. Make sure that you update the ctrl-? output

correctly with the commands you have added. Manual testing will count for

10% of the total grade of the shell.

Submission

Add a README file to the lab3-src/ directory with the following:

1. Features specified in the handout that work.

2. Features specified in the handout that do not work.

3. Extra features you have implemented.

To turn in Part 3:

1. Login to a CS department machine

2. Navigate to your lab3-src directory

3. Run make clean

4. Run make to check that your shell builds correctly

5. Run git tag -f part3

6. Run git push -f origin part3

7. Run git show part3

8. The show command should show the diff from the most recent commit

Grading

10% Milestone 1 (./testall p1 in lab)

10% Milestone 2 (./testall p2 in lab)

70% Final Testall

10% Manual Grading of readline and Ctrl+C

-5% For Memory Leaks

-5% For File Descriptor Leaks

Resources

Lex and Yacc Primer

Lab3 part1 slides (parsing)

Lab3 part1 slides (executing)

Lab3 part2 slides

Lab3 part3 slides