Return to lecture notes index
Assignment #3 - Shell Grammar

A Parser for a Shell
Due Thursday, September 18, 2007 (Next class)

The Assignment

Below is a rudimentary grammer that approximates the grammar of a shell. it has a shift-reduce conflict that derives from the way midCommand is defined. Your task is to prepare the grammar for use on your next project -- the UNIX shell.

To do this, you should fix the shift-reduce conflict. In order to demonstrate that what you have works, you should also construct a functioning parser. Please use yacc/bison and lex/flex. Do not roll your own.

In order to demonstrate that it works, your parser should output the production rule number each time a reduction is made. Simple, but readable, output of numbers is sufficient.

If you'd like, you can enhance the language to make it more flexible. For example, you can allow input and output redirects to occur in any order, or add support for conditionals.

The Provided (not LALR(1), Not in yacc-Form) Grammar

   CommandLine    :=  	NULL
                        FgCommandLine
                        FgCommandLine &

   FgCommandLine  :=  	SimpleCommand
               		FirstCommand MidCommand LastCommand

   SimpleCommand  :=  	ProgInvocation InputRedirect OutputRedirect

   FirstCommand   :=  	ProgInvocation InputRedirect

   MidCommand     :=	NULL
       			| ProgInvocation MidCommand

   LastCommand    :=  	| ProgInvocation OutputRedirect
          
   ProgInvocation :=  	ExecFile Args

   InputRedirect  := 	NULL
                   	< STRING

   OutputRedirect :=  	NULL
			> STRING

   ExecFile       :=  	STRING

   Args           :=  	NULL
			STRING Args
  

We're Here To Help!

As always -- remember, we're here to help!