CSC 271
Homework 9

Assigned Nov 29, due Dec 13

There are a lot of problems here: a couple of exercises to get familiar with the lex/flex and yacc/bison languages, and then a long list of possible enhancements to your shell, which I recommend doing only after you've translated the shell to lex or yacc. You almost certainly won't finish all the enhancements in this list; pick some that you think will be interesting.

Exercises in flex

1. Write, in flex, a filter that eliminates vowels (a, e, i, o, u) and passes everything else through unchanged.

2. Write, in flex, a filter that counts how many occurrences there are of each vowel and prints out the results. It shouldn't actually print anything from the input itself.

3. Rewrite your shell from homework 6 in flex, and make sure it still works. (It will presumably have a rule for "cd", and a rule for "exit", and rules for any other built-in commands you put into homework 6, and a rule for "anything else". You'll probably also want a rule that skips whitespace.)

Exercises in bison

4. Write, in bison, a filter that reads an HTML or XML file and tells whether the tags are correctly nested. For example,

   <em>This is emphasized <font size="big">big</font> text</em>

   is correctly nested, but

   <em>This is emphasized <font size="big">big</em> text</font>

   is not. It would be neat if you could handle any HTML or XML tag, but if you can handle two or three kinds (say, <font size="...">, <em>, and <a href="...">), that's enough.

5. Rewrite your shell from above in bison, and make sure it still works. (At this point it won't take much advantage of bison's capabilities, but just wait....)

   Making your shell honest

6. Right now your shell is probably sorta "cheating" to run programs, by passing the whole command line off to "system". But how does "system" do it?

   First, you'll need to pick apart the command itself from its arguments (separated by spaces). You can do this in C/C++, but it's easier in flex.

   Then you need to run the program. Unix programs are normally run in a subprocess, which you'll create using fork ("man fork"), after which the subprocess should run the program using exec. The command "man 3 exec" will tell you about several versions of the exec built-in function; in particular, I recommend using execvp, because it takes care of searching through the PATH for the program. If you want, you can do that yourself, then call execv once you've found the right program.

Enhancements to your shell

You're not required to do all of the following; choose as many as you wish, but the more you do successfully, the more impressed I'll be. They're roughly in order from easiest to hardest.

7. If you haven't done so already, add a built-in command to show the value of an environment variable. (I recommend adding this to the flex or bison version, not the C/C++ version.)

8. If you haven't done so already, add a built-in command to change the value of an environment variable. (I recommend adding this to the flex or bison version.)

9. Allow the user to give several commands on one line, separated by semicolons (;). The shell should run the first one, with its arguments, in a subprocess until it finishes, then run the second one, and so on. (You can do this in flex, but it's probably easier in bison.)

10. Allow the user to give several commands on one line, separated by ampersands (&). The shell should start the first one with its arguments, not wait for it to finish, but immediately start the second one and so on. Note that the last command on the line can be nothing, so the line might look like

    find / -type d &

    Again, this will be easier in bison. Consider the interaction between ; and &: what does

    cmd1 & cmd2 ; cmd3

    do? Should it be thought of as (cmd1 & cmd2) ; cmd3 or as cmd1 & (cmd2 ; cmd3) ? This is really an operator-precedence question, like the difference between (3 + 4) * 5 and 3 + (4 * 5).

11. Allow the user to give several commands on one line, separated by double-ampersands (&&). The shell should start the first command, wait for it to finish, and if it succeeded (i.e. returned 0), start the second command.

12. Allow the user to give several commands on one line, separated by double-bars (||). The shell should start the first command, wait for it to finish, and if it failed (i.e. returned nonzero), start the second command.

13. Allow the user to override whatever operator precedence you chose for the ;, &, &&, and || operators by grouping commands with parentheses.

14. Allow the user to redirect I/O to named files, using < and > as usual in bash. When you see something like foo >bar, you should run the foo command with stdout connected to the bar file.

15. Allow the user to give several commands on one line, separated by bars (|). The shell should create a pipe (look it up with "man 2 pipe"), start the first command with its output connected to the input side of the pipe, and start the second command with its input connected to the output side of the pipe.

16. Allow the user to expand environment variables in the middle of a command line, using "$variablename" syntax as in bash

17. Make your shell run shell scripts nicely: it should treat any line starting with "#" as a comment, it should not print prompts if its input is coming from a file, etc.. Once this is done, you can run scripts in your shell in either of two ways:

    • type myshell <script

    • make the first line of the script "#!" followed by the complete pathname of your shell, e.g.

      #!/users/bloch/bin/myshell

      and just execute the script.

18. A simple history mechanism, allowing the user to repeat the previous command, using "!!" as in bash.

19. Expand filename wildcards * and ? as in bash: when you see something like foo *.c++, look in the current directory for all the files whose names end in ".c++", and use all their names as arguments to the foo command.