The Parser

Write a context-free grammar for SFL. You will need, at a minimum, a nonterminal for Program, one for Definition, and one for each level of precedence for expressions. You will also need some others to help out. Keep the grammar small where you can.

Write the grammar in Bison and put it into a file, src/parser.y. See the Bison manual. Do not include actions, just write the grammar. Put the rules for Program first, so that Program will be the start nonterminal.

Before the grammar, list all of the tokens that have names. Your Bison file might look something like this, where … indicates more of similar things.

%{
#define YYDEBUG
#include "token.h"
%}

%token <str>    TOK_ID
%token          TOK_ARROW
…

%%
Program	        : Definition
	        | Program  Definition
                ;

Definition      : TOK_DEF  TOK_ID  '='  Expression  TOK_END
                ;
…
%%
int main(int argc, char** argv)
{
  if(argc == 2) {
    yyin = fopen(argv[1], "r");
    if(yyin == NULL) {
      return 1;
    }
    yydebug = 1;
    return yyparse();
  }
  else {
    return 1;
  }
}

Make a copy of token.h. Now remove the token definitions from token.h (but keep the definition of YYSTYPE). Bison will create a file, y.tab.h, that defines the tokens.

Remove the declaration of yylval from lexer.lex. (But keep it in lexer.h.) Variable yylval is also created automatically by Bison.

To compile your Bison program, use the following command.

  bison -y -v -d parser.y

Test the parser. The way it is shown above (with YYDEBUG defined and yydebug set to 1) it will show a trace of the parsing process. To turn off the trace, just set yydebug to 0.

Error reporting

When there is a syntax error, Bison calls function yyerror(s), where s is a string (probably "syntax error"). The default definition just prints s, which is not very pleasant. Write your own definition of yyerror so that it at least shows the current line number. Also make it set a variable, error_occurred, to true, so that you know an error has occurred.

Submitting your work

When you have the parser working, submit it using the following command (presuming given file names).

  ~abrahamsonk/5220/bin/submit parser parser.y lexer.lex lexer.h token.h stringtable.c stringtable.h allocate.h