Confusion about a Bison/YACC Grammar

Question

With the following Grammar, I get a syntax error with this sort of input:

ls /home > foo #Runs and works okay, but raises error token
ls /home /foo /bar /etc #works okay

I think it may have something to do with how lookahead works, but this is my first grammar and I am a bit confused about why it doesn't work this way: external_cmd GT WORD is a redirect, redirect is a command, command is a commands, so input commands NEWLINE should work.

Top Rules of the Grammar:

input:
    error NEWLINE {
        printf("Error Triggered\n");
        yyclearin;
        yyerrok; 
        prompt(); 
    } |
    input NEWLINE {
        prompt();
    } | 
    input commands NEWLINE {
        prompt (); 
    } | 
    /* empty */
    ;   

commands: 
    command |   
    command SEMI | 
    command SEMI commands
    ;   

command:
    builtin_cmd |
    redirect |
    external_cmd { 
        execute_command($1, 0, NULL);
    }
    ;

redirect:
    external_cmd GT WORD  {
        printf("Redirecting stdout of %s to %s\n", $1->cmd, $3);
        //printf("DEBUG: GT\n");
        execute_command($1, STDOUT_FILENO, $3);
    }
    external_cmd LT WORD {
        printf("Redirecting stin of %s to %s\n", $1->cmd, $3);
        //printf("DEBUG: GT\n");
        execute_command($1, STDIN_FILENO, $3);
    }
    ;

The debug / verbose input of when the error token is raised:

Next token is token WORD ()
Shifting token WORD ()
Entering state 6
Reading a token: Next token is token WORD ()
Shifting token WORD ()
Entering state 24
Reading a token: Next token is token GT ()
Reducing stack by rule 22 (line 115):
   $1 = token WORD ()
-> $$ = nterm arg_list ()
Stack now 0 2 6
Entering state 26
Reducing stack by rule 19 (line 91):
   $1 = token WORD ()
   $2 = nterm arg_list ()
-> $$ = nterm external_cmd ()
Stack now 0 2
Entering state 16
Next token is token GT ()
Shifting token GT ()
Entering state 29
Reading a token: Next token is token WORD ()
Shifting token WORD ()
Entering state 33
Reducing stack by rule 11 (line 68):
Redirecting stdout of ls to foo
DEBUG: redirect mode is 1
DEBUG: Command to run is ls
DEBUG: Adding Argument /home
admin  kbrandt  tempuser
-> $$ = nterm @1 ()
Stack now 0 2 16 29 33
Entering state 34
Reading a token: Next token is token NEWLINE ()
syntax error
Error: popping nterm @1 ()
Stack now 0 2 16 29 33
Error: popping token WORD ()
Stack now 0 2 16 29
Error: popping token GT ()
Stack now 0 2 16
Error: popping nterm external_cmd ()
Stack now 0 2
Error: popping nterm input ()
Stack now 0
Shifting token error ()
Entering state 1
Next token is token NEWLINE ()
Shifting token NEWLINE ()
Entering state 3
Reducing stack by rule 1 (line 38):
   $1 = token error ()
   $2 = token NEWLINE ()
Error Triggered
-> $$ = nterm input ()
Stack now 0
Entering state 2

Update:
external_cmd is:

external_cmd:
    WORD arg_list {
        $$ = malloc( sizeof(struct ext_cmd) );
        if ( $$ == NULL)
            printf("Memory Allocation Error\n");
        $$->cmd = $1;
        $$->args_pp = $2;
    } |
    WORD    {
        $$ = malloc( sizeof(struct ext_cmd) );
        if ( $$ == NULL)
            printf("Memory Allocation Error\n");
        $$->cmd = $<string>1;
        $$->args_pp = NULL;
    }

Answer 1

1. You really really should use left recursion with LALR(1) parser generators. Right recursion requires that all elements be shifted onto the parser state stack before even a single reduction can occur. You can imagine what this does to error recovery.

2. What exactly is external_cmd? It kind of looks like it is being reduced early but it's hard to tell because you didn't include it.

3. Why is YYACCEPT invoked after any redirection? If you are intending to restart the parser on each line then you shouldn't have the recursive input collector. As long as you do have it, don't do a YYACCEPT.

Answer 2

The syntax error is coming from your SECOND call to yyparse. When you have the redirect, you grammar does a YYACCEPT, which causes the parser to return immediately without reading anything more. On the second call, the first token read is a NEWLINE, which cases the error (your grammar does not allow for blank lines.)

With no redirect, there's no YYACCEPT, so the grammar continue to run, reading the newline and returning on reaching the end of the input.

Answer 3

Found it, in my redirect rule there is a missing pipe, so instead of two components, there is one with a mid-rule action, which is not what I want.