Flex and Yacc Grammar Issue

Question

Edit #1: I think the problem is in my .l file. I don't think the rules are being treated as rules, and I'm not sure how to treat the terminals of the rules as strings.

My last project for a compilers class is to write a .l and a .y file for a simple SQL grammar. I have no experience with Flex or Yacc, so everything I have written I have pieced together. I only have a basic understanding of how these files work, so if you spot my problem can you also explain what that section of the file is supposed to do? I'm not even sure what the '%' symbols do.

Basically some rules just do not work when I try to parse something. Some rules hang and others reject when they should accept. I need to implement the following grammar:

start 
    ::= expression

expression
    ::= one-relation-expression | two-relation-expression

one-relation-expression
    ::= renaming | restriction | projection

renaming 
    ::= term RENAME attribute AS attribute

term 
    ::= relation | ( expression )

restriction
    ::= term WHERE comparison

projection 
    ::= term | term [ attribute-commalist ]

attribute-commalist
    ::= attribute | attribute , attribute-commalist

two-relation-expression
    ::= projection binary-operation expression

binary-operation
    ::= UNION | INTERSECT | MINUS | TIMES | JOIN | DIVIDEBY

comparison
    ::= attribute compare number

compare
    ::= < | > | <= | >= | = | <>

number
    ::= val | val number

val 
    ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

attribute 
    ::= CNO | CITY | CNAME | SNO | PNO | TQTY | 
          SNAME | QUOTA | PNAME | COST | AVQTY |
          S# | STATUS | P# | COLOR | WEIGHT | QTY

relation 
    ::= S | P | SP | PRDCT | CUST | ORDERS

Here is my .l file:

%{
#include <stdio.h>
#include "p5.tab.h"
%}
binaryOperation     UINION|INTERSECT|MINUS|TIMES|JOIN|DIVIDEBY
compare         <|>|<=|>=|=|<>
attribute       CNO|CITY|CNAME|SNO|PNO|TQTY|SNAME|QUOTA|PNAME|COST|AVQTY|S#|STATUS|P#|COLOR|WEIGHT|QTY
relation        S|P|SP|PRDCT|CUST|ORDERS
%%
[ \t\n]+        ;
{binaryOperation}   return binaryOperation;
{compare}       return compare;
[0-9]+          return val;
{attribute}     return attribute;
{relation}      return relation;
"RENAME"        return RENAME;
"AS"            return AS;
"WHERE"         return WHERE;
"("         return '(';
")"         return ')';
"["         return '[';
"]"         return ']';
","         return ',';
.           {printf("REJECT\n");
                exit(0);}
%%

Here is my .y file:

%{
#include <stdio.h>
#include <stdlib.h>
%}
%token RENAME attribute AS relation WHERE binaryOperation compare val
%%

start:
    expression          {printf("ACCEPT\n");}
    ;

expression:
    oneRelationExpression
    | twoRelationExpression
    ;

oneRelationExpression:
    renaming
    | restriction
    | projection
    ;

renaming:
    term RENAME attribute AS attribute
    ;

term:
    relation
    | '(' expression ')'
    ;

restriction:
    term WHERE comparison
    ;

projection:
    term
    | term '[' attributeCommalist ']'
    ;

attributeCommalist:
    attribute
    | attribute ',' attributeCommalist
    ;

twoRelationExpression:
    projection binaryOperation expression
    ;

comparison:
    attribute compare number
    ;

number:
    val
    | val number
    ;

%%

yyerror() {
    printf("REJECT\n");
    exit(0);
}

main() {
    yyparse();
}

yywrap() {}

Here is my makefile:

p5: p5.tab.c lex.yy.c
    cc -o p5 p5.tab.c lex.yy.c

p5.tab.c: p5.y
    bison -d p5.y

lex.yy.c: p5.l
    flex p5.l

This works:

S RENAME CNO AS CITY

These do not:

S

S WHERE CNO = 5

I have not tested everything, but I think there is a common problem for these issues.

Answer 1

Your grammar is correct, the problem is that you are running interactively. When you call yyparse() it will attempt to read all input. Because the input

S

could be followed by either RENAME or WHERE it won't accept. Similarly,

S WHERE CNO = 5

could be followed by one or more numbers, so yyparse won't accept until it gets an EOF or an unexpected token.

What you want to do is follow the advice here and change p5.l to have these lines:

[ \t]+        ;
\n            if (yyin==stdin) return 0;

That way when you are running interactively it will take the ENTER key to be the end of input.

Also, you want to use left recursion for number:

number:
    val
    | number val
    ;