i don't know lalr's c2ompute_FOLLOWS() in bison1.24

[山东]

c2ompute_FOLLOWS()
{
  register int i;

  digraph(includes);

  for (i = 0; i < ngotos; i++)
    {
      if (includes[i]) FREE(includes[i]);
    }

  FREE(includes);
}

digraph(relation)
short **relation;
{
  register int i;

  infinity = ngotos + 2;
  INDEX = NEW2(ngotos + 1, short);
  VERTICES = NEW2(ngotos + 1, short);
  top = 0;

  R = relation;

  for (i = 0; i < ngotos; i++)
    INDEX[i] = 0;

  for (i = 0; i < ngotos; i++)
    {
      if (INDEX[i] == 0 && R[i])
    traverse(i);
    }

  FREE(INDEX);
  FREE(VERTICES);
}



traverse(i)
register int i;
{
  register unsigned *fp1;
  register unsigned *fp2;
  register unsigned *fp3;
  register int j;
  register short *rp;

  int height;
  unsigned *base;

  VERTICES[++top] = i;
  INDEX[i] = height = top;

  base = F + i * tokensetsize;
  fp3 = base + tokensetsize;

  rp = R[i];
  if (rp)
    {
      while ((j = *rp++) >= 0)
    {
      if (INDEX[j] == 0)
        traverse(j);

      if (INDEX[i] > INDEX[j])
        INDEX[i] = INDEX[j];

      fp1 = base;
      fp2 = F + j * tokensetsize;

      while (fp1 < fp3)
        *fp1++ |= *fp2++;
    }
    }

  if (INDEX[i] == height)
    {
      for (;;)
    {
      j = VERTICES[top--];
      INDEX[j] = infinity;

      if (i == j)
        break;

      fp1 = base;
      fp2 = F + j * tokensetsize;

      while (fp1 < fp3)
        *fp2++ = *fp1++;
    }
    }
}


traverse(209)=???
base = F + 209 * tokensetsize=???

parse.y from bash1.05



%{
#include <stdio.h>
#include <signal.h>
#include "shell.h"
#include "flags.h"

#ifdef READLINE
#include <readline/readline.h>
#include <readline/history.h>
#endif

#define YYDEBUG 1
#define DEBUG 1
extern int eof_encountered;
extern int no_line_editing;
extern int interactive;
%}

%union {
  WORD_DESC *word;        /* the word that we read. */
  int number;            /* the number that we read. */
  WORD_LIST *word_list;
  COMMAND *command;
  REDIRECT *redirect;
  ELEMENT element;
  PATTERN_LIST *pattern;
}

/* Reserved words.  Members of the first group are only recognized
   in the case that they are preceded by a list_terminator.  Members
   of the second group are recognized only under special circumstances. */
%token IF THEN ELSE ELIF FI CASE ESAC FOR WHILE UNTIL DO DONE FUNCTION
%token IN

/* More general tokens. yylex () knows how to make these. */
%token <word> WORD
%token <number> NUMBER
%token AND_AND OR_OR GREATER_GREATER LESS_LESS LESS_AND
%token GREATER_AND SEMI_SEMI LESS_LESS_MINUS AND_GREATER
%token DOUBLE_OPEN DOUBLE_CLOSE

/* The types that the various syntactical units return. */

%type <command> inputunit command list list0 list1 simple_list simple_list1
simple_command shell_command group_command
%type <command> elif_clause
%type <redirect> redirection redirections
%type <element> simple_command_element
%type <word_list> words pattern
%type <pattern> pattern_list case_clause_sequence case_clause_1
pattern_list_1

%start inputunit

%left '&' ';' '\n' yacc_EOF
%left AND_AND OR_OR
%left '|'
%%

inputunit:    simple_list '\n'
            {
              /* Case of regular command.  Discard the error
                 safety net,and return the command just parsed. */
              global_command = $1;
              eof_encountered = 0;
              discard_parser_constructs (0);
              YYACCEPT;
            }
    |    '\n'
            {
              /* Case of regular command, but not a very
                 interesting one.  Return a NULL command. */
              global_command = (COMMAND *)NULL;
              YYACCEPT;
            }
    |
        error '\n'
            {
              /* Error during parsing.  Return NULL command. */
              global_command = (COMMAND *)NULL;
              eof_encountered = 0;
              discard_parser_constructs (1);
              if (interactive)
                YYACCEPT;
              else
                YYABORT;
            }
    |
        yacc_EOF
            {
              /* Case of EOF seen by itself.  Do ignoreeof or
                 not. */
              global_command = (COMMAND *)NULL;
              handle_eof_input_unit ();
              YYACCEPT;
            }
    ;

words:
            { $$ = NULL; }
    |    words WORD
            { $$ = make_word_list ($2, $1); }
    ;

redirection:    '>' WORD
            { $$ = make_redirection ( 1, r_output_direction, $2); }
    |    '<' WORD
            { $$ = make_redirection ( 0, r_input_direction, $2); }
    |    NUMBER '>' WORD
            { $$ = make_redirection ($1, r_output_direction, $3); }
    |    NUMBER '<' WORD
            { $$ = make_redirection ($1, r_input_direction, $3); }
    |    GREATER_GREATER WORD
            { $$ = make_redirection ( 1, r_appending_to, $2); }
    |    NUMBER GREATER_GREATER WORD
            { $$ = make_redirection ($1, r_appending_to, $3); }
    |    LESS_LESS WORD
            { $$ = make_redirection ( 0, r_reading_until, $2); }
    |    NUMBER LESS_LESS WORD
            { $$ = make_redirection ($1, r_reading_until, $3); }
    |    LESS_AND NUMBER
            { $$ = make_redirection ( 0, r_duplicating, $2); }
    |    NUMBER LESS_AND NUMBER
            { $$ = make_redirection ($1, r_duplicating, $3); }
    |    GREATER_AND NUMBER
            { $$ = make_redirection ( 1, r_duplicating, $2); }
    |    NUMBER GREATER_AND NUMBER
            { $$ = make_redirection ($1, r_duplicating, $3); }
    |    LESS_LESS_MINUS WORD
            { $$ = make_redirection ( 0, r_deblank_reading_until, $2); }
    |    NUMBER LESS_LESS_MINUS WORD
            { $$ = make_redirection ($1, r_deblank_reading_until, $3); }
    |    GREATER_AND '-'
            { $$ = make_redirection ( 1, r_close_this, 0); }

    |    NUMBER GREATER_AND '-'
            { $$ = make_redirection ($1, r_close_this, 0); }
    |    LESS_AND '-'
            { $$ = make_redirection ( 0, r_close_this, 0); }
    |    NUMBER LESS_AND '-'
            { $$ = make_redirection ($1, r_close_this, 0); }
    |    AND_GREATER WORD
            { $$ = make_redirection ( 1, r_err_and_out, $2); }
    |    GREATER_AND WORD
            { $$ = make_redirection ( 1, r_err_and_out, $2); }
    ;

simple_command_element: WORD
             { $$.word = $1; $$.redirect = 0; }
    |    redirection
            { $$.redirect = $1; $$.word = 0; }
    ;

redirections:    redirection
    |    redirections redirection
            { $1->next = $2; $$ = $1; }
    ;

simple_command:    simple_command_element
            { $$ = make_simple_command ($1, NULL); }
    |    simple_command simple_command_element
            { $$ = make_simple_command ($2, $1); }
    ;

command:    simple_command
            { $$ = clean_simple_command ($1); }
    |    shell_command
            { $$ = $1; }

    |    shell_command redirections
            { $$->redirects = $2; $$ = $1; }
    ;

shell_command:    FOR WORD newlines DO list DONE
            { $$ = make_for_command ($2, (WORD_LIST *)add_string_to_list
("$@", NULL), $5); }
    |    FOR WORD ';' newlines DO list DONE
            { $$ = make_for_command ($2, (WORD_LIST *)add_string_to_list
("$@", NULL), $6); }
    |    FOR WORD ';' newlines '{' list '}'
            { $$ = make_for_command ($2, (WORD_LIST *)add_string_to_list
("$@", NULL), $6); }
    |    FOR WORD newlines IN words list_terminator newlines DO list DONE
            { $$ = make_for_command ($2, (WORD_LIST *)reverse_list ($5),
$9); }
    |    FOR WORD newlines IN words list_terminator newlines '{' list '}'
            { $$ = make_for_command ($2, (WORD_LIST *)reverse_list ($5),
$9); }

    |    CASE WORD newlines IN newlines ESAC
            { $$ = make_case_command ($2, NULL); }
    |    CASE WORD newlines IN case_clause_sequence newlines ESAC
            { $$ = make_case_command ($2, $5); }
    |    CASE WORD newlines IN case_clause_1 ESAC
            { report_syntax_error ("Inserted `;;'");
              $$ = make_case_command ($2, $5); }

    |    IF list THEN list FI
              { $$ = make_if_command ($2, $4, NULL); }
    |    IF list THEN list ELSE list FI
            { $$ = make_if_command ($2, $4, $6); }
    |    IF list THEN list elif_clause FI
            { $$ = make_if_command ($2, $4, $5); }

    |    WHILE list DO list DONE
            { $$ = make_while_command ($2, $4); }
    |    UNTIL list DO list DONE
            { $$ = make_until_command ($2, $4); }

    |    '(' list ')'
            { $2->subshell = 1; $$ = $2; }

    |    group_command
            { $$ = $1; }

    |    WORD '(' ')' newlines group_command
            { $$ = make_function_def ($1, $5); }

    |    FUNCTION WORD '(' ')' newlines group_command
            { $$ = make_function_def ($2, $6); }

    |    FUNCTION WORD '\n' newlines group_command
            { $$ = make_function_def ($2, $5); }

    |    FUNCTION WORD group_command
            { $$ = make_function_def ($2, $3); }
    ;

group_command:    '{' list '}'
            { $$ = make_group_command ($2); }
    ;

elif_clause:    ELIF list THEN list
            { $$ = make_if_command ($2, $4, NULL); }
    |    ELIF list THEN list ELSE list
            { $$ = make_if_command ($2, $4, $6); }
    |    ELIF list THEN list elif_clause
            { $$ = make_if_command ($2, $4, $5); }
    ;


case_clause_1:    pattern_list_1
    |    case_clause_sequence pattern_list_1
              { $2->next = $1; $$ = $2; }
    ;

pattern_list_1:    newlines pattern ')' list
            { $$ = make_pattern_list ($2, $4); }
    |    newlines pattern ')' newlines
            { $$ = make_pattern_list ($2, NULL); }
    ;

case_clause_sequence:  pattern_list

      |    case_clause_sequence pattern_list
            { $2->next = $1; $$ = $2; }
    ;

pattern_list:    newlines pattern ')' list SEMI_SEMI
            { $$ = make_pattern_list ($2, $4); }
    |    newlines pattern ')' newlines SEMI_SEMI
            { $$ = make_pattern_list ($2, NULL); }
    ;

pattern:    WORD
            { $$ = make_word_list ($1, NULL); }
    |    pattern '|' WORD
            { $$ = make_word_list ($3, $1); }
    ;

/* A list allows leading or trailing newlines and
   newlines as operators (equivalent to semicolons).
   It must end with a newline or semicolon.
   Lists are used within commands such as if, for, while.  */

list:        newlines list0
            { $$ = $2; }
    ;

list0:        list1
    |    list1 '\n' newlines
    |    list1 '&' newlines
            { $$ = command_connect ($1, 0, '&'); }
    |    list1 ';' newlines

    ;

list1:        list1 AND_AND newlines list1
            { $$ = command_connect ($1, $4, AND_AND); }
    |    list1 OR_OR newlines list1
            { $$ = command_connect ($1, $4, OR_OR); }
    |    list1 '&' newlines list1
            { $$ = command_connect ($1, $4, '&'); }
    |    list1 ';' newlines list1
            { $$ = command_connect ($1, $4, ';'); }
    |    list1 '\n' newlines list1
            { $$ = command_connect ($1, $4, ';'); }
    |    list1 '|' newlines list1
            { $$ = command_connect ($1, $4, '|'); }
    |    command
    ;


list_terminator:'\n'
    |    ';'
    |    yacc_EOF
    ;

newlines:
    |    newlines '\n'
    ;

/* A simple_list is a list that contains no significant newlines
   and no leading or trailing newlines.  Newlines are allowed
   only following operators, where they are not significant.

   This is what an inputunit consists of.  */

simple_list:    simple_list1
    |    simple_list1 '&'
            { $$ = command_connect ($1, (COMMAND *)NULL, '&'); }
    |    simple_list1 ';'
    ;

simple_list1:    simple_list1 AND_AND newlines simple_list1
            { $$ = command_connect ($1, $4, AND_AND); }
    |    simple_list1 OR_OR newlines simple_list1
            { $$ = command_connect ($1, $4, OR_OR); }
    |    simple_list1 '&' simple_list1
            { $$ = command_connect ($1, $3, '&'); }
    |    simple_list1 ';' simple_list1
            { $$ = command_connect ($1, $3, ';'); }
    |    simple_list1 '|' newlines simple_list1
            { $$ = command_connect ($1, $4, '|'); }
    |    command
    ;
%%