Help with yacc/compiler design/seg fault

I am taking a compiler design course and we are using yacc and lex for the parser and scanner. I keep getting a seg fault in an unexpected place and I was wondering if anyone here could help me track down the problem.

I will just post the .y file and the tree.c files for now because they are long, but I can post more if need be.

When I use gdb to track down the seg fault, it tells me that the problem is with my .y file, in line 74, which is the { $1->next = $3; $$ = $1; } section of the state_decls production. I cannot figure out why there is a problem here, and I could use some advice, even if that advice is just a better way to find the source of my problem.

The .y file:

Code:

---

%{
#include "tree.h"

extern tree root;
tree BuildTree(int, tree, tree, tree);
tree BuildIntTree(int, int);
tree BuildFloatTree(int, float);
%}

%token <i>        Ident 1 IntConst 2
%token <f>        RealConst 3
%token                Var 11 Int 12 Real 13 Boolean 14 Record 15
%token                End 16 Bind 17 To 18 Assert 19 Begin 20
%token                Loop 21 Exit 22 When 23 If 24 Then 25
%token                Elsif 26 Else 27 Put 28 Or 29 And 30
%token                Not 31 NotEq 32 Div 33 Mod 34
%token                SemiColon 40 Colon 41 Assign 42 Gt 43 Lt 44
%token                Eq 45 Lte 46 Gte 47 Plus 48 Minus 49
%token                Star 50 Slash 51 Dot 52 Comma 53 LParen 54 RParen 55

%start program

%union { tree t; int i; float f; }

%type <t>        program pStateDeclSeq id_list type field_list state_decls
%type <t>        declaration statement ref end_if expr and_expr not_expr
%type <t>        rel_expr sum prod factor basic

%%

program
        : pStateDeclSeq
                { root = $1; }
        ;

pStateDeclSeq
        : /* nullable */
                { $$ = NULL; }
        | statement SemiColon pStateDeclSeq
                { $1->next = $3; $$ = $1; }
        | Var id_list Colon type SemiColon pStateDeclSeq
                { $$ = BuildTree(Var, $2, $4, $6); }
        ;

id_list
        : Ident
                { $$ = BuildIntTree(Ident, $1); }
        | Ident Comma id_list
                { $$ = BuildTree(Comma, BuildIntTree(Ident, $1), $3, NULL); }
        ;

type
        : Int
                { $$ = BuildIntTree(Int, $<i>1); }
        | Real
                { $$ = BuildFloatTree(Real, $<f>1); }
        | Boolean
                { $$ = BuildIntTree(Boolean, $<i>1); }
        | Record field_list End Record
                { $$ = BuildTree(Record, $2, BuildTree(End, NULL, NULL, NULL), BuildTree(Record, NULL, NULL, NULL)); }
        ;

field_list
        : id_list Colon type
                { $$ = BuildTree(Colon, $1, $3, NULL); }
        | id_list Colon type SemiColon field_list
                { $$ = BuildTree(Colon, $1, $3, $5); }
        ;

state_decls
        : /* nullable */
                { $$ = NULL; }
        | statement SemiColon pStateDeclSeq
                { $1->next = $3; $$ = $1; }
        | declaration SemiColon pStateDeclSeq
                { $1->next = $3; $$ = $1; }
        ;

declaration
        : Var id_list Colon type
                { $$ = BuildTree(Var, $2, $4, NULL); }
        | Bind Ident To ref
                { $$ = BuildTree(Bind, BuildIntTree(Ident, $2), BuildTree(To, $4, NULL, NULL), NULL); }
        | Bind Var Ident To ref
                { $$ = BuildTree(Bind, BuildTree(Var, BuildIntTree(Ident, $3), NULL, NULL), BuildTree(To, $5, NULL,
NULL), NULL); }
        ;

statement
        : ref Assign expr
                { $$ = BuildTree(Assign, $1, $3, NULL); }
        | Assert expr
                { $$ = BuildTree(Assert, $2, NULL, NULL); }
        | Begin state_decls End
                { $$ = BuildTree(Begin, $2, BuildTree(End, NULL, NULL, NULL), NULL); }
        | Loop state_decls End Loop
                { $$ = BuildTree(Loop, $2, BuildTree(End, NULL, NULL, NULL), BuildTree(Loop, NULL, NULL, NULL)); }
        | Exit
                { $$ = NULL; }
        | Exit When expr
                { $$ = BuildTree(Exit, BuildTree(When, $3, NULL, NULL), NULL, NULL); }
        | If expr Then state_decls end_if
                { $$ = BuildTree(If, $2, BuildTree(Then, $4, $5, NULL), NULL); }
        ;

ref
        : Ident
                { $$ = BuildIntTree(Ident, $1); }
        | Ident Dot Ident
                { $$ = BuildTree(Dot, BuildIntTree(Ident, $1), BuildIntTree(Ident, $3), NULL); }
        ;

end_if
        : End If
                { $$ = NULL; }
        | Else state_decls End If
                { $$ = BuildTree(Else, $2, NULL, NULL); }
        | Elsif expr Then state_decls end_if
                { $$ = BuildTree(Elsif, $2, $4, $5); }
        ;

expr
        : expr Or and_expr
                { $$ = BuildTree(Or, $1, $3, NULL); }
        | and_expr
                { $$ = $1; }
        ;

and_expr
        : and_expr And not_expr
                { $$ = BuildTree(And, $1, $3, NULL); }
        | not_expr
                { $$ = $1; }
        ;

not_expr
        : Not not_expr
                { $$ = BuildTree(Not, $2, NULL, NULL); }
        | rel_expr
                { $$ = $1; }
        ;

rel_expr
        : sum
                { $$ = $1; }
        | rel_expr Eq sum
                { $$ = BuildTree(Eq, $1, $3, NULL); }
        | rel_expr NotEq sum
                { $$ = BuildTree(NotEq, $1, $3, NULL); }
        | rel_expr Lt sum
                { $$ = BuildTree(Lt, $1, $3, NULL); }
        | rel_expr Lte sum
                { $$ = BuildTree(Lte, $1, $3, NULL); }
        | rel_expr Gt sum
                { $$ = BuildTree(Gt, $1, $3, NULL); }
        | rel_expr Gte sum
                { $$ = BuildTree(Gte, $1, $3, NULL); }
        ;

sum
        : prod
                { $$ = $1; }
        | sum Plus prod
                { $$ = BuildTree(Plus, $1, $3, NULL); }
        | sum Minus prod
                { $$ = BuildTree(Minus, $1, $3, NULL); }
        ;

prod
        : factor
                { $$ = $1; }
        | prod Star factor
                { $$ = BuildTree(Star, $1, $3, NULL); }
        | prod Slash factor
                { $$ = BuildTree(Slash, $1, $3, NULL); }
        | prod Div factor
                { $$ = BuildTree(Div, $1, $3, NULL); }
        | prod Mod factor
                { $$ = BuildTree(Mod, $1, $3, NULL); }
        ;

factor
        : Plus basic
                { $$ = BuildTree(Plus, $2, NULL, NULL); }
        | Minus basic
                { $$ = BuildTree(Minus, $2, NULL, NULL); }
        | basic
                { $$ = $1; }
        ;

basic
        : ref
                { $$ = $1; }
        | LParen expr RParen
                { $$ = $2; }
        | IntConst
                { $$ = BuildIntTree(IntConst, $1); }
        | RealConst
                { $$ = BuildFloatTree(RealConst, $1); }
        ;

%%

---

The tree.c file:

Code:

---

#include <stdlib.h>
#include "tree.h"

tree BuildTree(int k, tree f1, tree s2, tree t3)
{
        tree t;
        t = (tree)malloc(sizeof(node));

        t->kind = k;
        t->first = f1;
        t->second = s2;
        t->third = t3;
        t->next = NULL;

        return t;
}

tree BuildIntTree(int k, int v)
{
        tree t;
        t = (tree)malloc(sizeof(node));
       
        t->kind = k;
        t->value = v;
        t->first = NULL;
        t->second = NULL;
        t->third = NULL;
        t->next = NULL;

        return t;
}

tree BuildFloatTree(int k, float v)
{
        tree t;
        t = (tree)malloc(sizeof(node));

        t->kind = k;
        t->value = v;
        t->first = NULL;
        t->second = NULL;
        t->third = NULL;
        t->next = NULL;

        return t;
}

void PrintTree(tree t, int indent)
{
        int i;
        char str[]="--|";

        if(t != NULL)
        {
                printf("%d\n", t->value);
                PrintTree(t->first, indent+1);
                PrintTree(t->second, indent+1);
                PrintTree(t->third, indent+1);
        }
}

---

Code:

---

{ $1->next = $3; $$ = $1; }

---

if i had to bet, i would say you're trying to access memory that's not there
and that $1->next == NULL