Lex/YACC Question

MTK358 · 03-28-2010, 12:23 PM

So you have to define the types of non-terminals using %type, right?

MTK358 · 03-28-2010, 12:41 PM

That fixed it, but now I have another problem:

Code:

%union {
	char* string;
	Node* node;
}

%token <string> INTEGER
%token <string> IDENTIFIER

%type <node> expr

"Node" is a typedef'd struct that represents a node in the abstract syntax tree.

Code:

$ ./compile
Running YACC:
lang.y: conflicts: 4 shift/reduce
Running Lex:
Running GCC:
In file included from lang.l:2:
lang.y:12: error: expected specifier-qualifier-list before ‘Node’
GCC returned with exit code 1

theNbomr · 03-28-2010, 01:00 PM

I don't see anything wrong with the grammar part of the code, and it seems to be the compiler complaining, so how about showing the definition of the Node type. Is it in the code section of the yacc file, or is it in a header file? If the latter, is there a #include for it?

You seem to spend relatively little time tracking down problems on your own. It might be a helpful learning experience to dig into the problems a little more before posting for help. Just a friendly suggestion.

--- rod.

MTK358 · 03-28-2010, 01:04 PM

I don't know, the Node definition is in a separate .h file that is included in the .y file.

Anyway, this is it:

Code:

struct Node {
	int type;
	union {
		struct {
			int type;
			int numOps;
			struct Node** ops;
		} opValues;
		char* litValue;
		char* idValue;
	};
};
typedef struct Node Node;

MTK358 · 03-28-2010, 03:51 PM

OK, I got that fixed now, but here I really got stuck:

Code:

Node *mkOpNode(int type, int numOps, /*Node*/ ...) {
	Node* n = malloc(sizeof(Node));
	n->type = NODE_OP;
	n->opValues.type = type;
	n->opValues.numOps = numOps;
	n->opValues.ops = malloc(sizeof(Node*)*numOps);
	if(numOps > 0 && n->opValues.ops == NULL) {
		fprintf(stderr, "error: cannot allocate memory for node\n");
		exit(1);
	}
	va_list ap;
	int i;
	for(i=0; i<numOps; i++) {
		n->opValues.ops[i] = va_arg(ap, Node*); // Segfault here!
	}
	va_end(ap);
	return n;
}

When it reaches the line highlighted in bold, it segfaults.

I used gdb and found that this happens on the first iteration, so it couldn't be going out the array's bounds. I also found that n->opValues.ops (which is of Node** type) is not NULL, so that isn't the problem. I wonder what's wrong?

larryherman · 03-28-2010, 04:17 PM

You didn't call va_start() before calling va_arg(), so ap has no initial value; if you try examining it in gdb you should see it's either NULL (0) or has some random (garbage) value.

It's good that you used gdb but when you have an error examining the values of all of the variables in the section of code in question may be necessary to figure out what's going on.

MTK358 · 03-28-2010, 06:59 PM

That's fixed, but this is really strange now:

Code:

$ ./lang
8 + 3
+
    Literal: 8 + 3

    Identifier: 8 + 3

    Literal: 3

    Identifier: 3

WTF?!?!?

It's supposed to look exactly like this:

Code:

8 + 3
+
    Literal: 8
    Literal: 3

Sergei Steshenko · 03-28-2010, 07:11 PM

Quote:

Originally Posted by MTK358

That's fixed, but this is really strange now:

Code:

$ ./lang
8 + 3
+
    Literal: 8 + 3

    Identifier: 8 + 3

    Literal: 3

    Identifier: 3

WTF?!?!?

It's supposed to look exactly like this:

Code:

8 + 3
+
    Literal: 8
    Literal: 3

Well, I guess now it's the time:

Welcome to the wonderful world of LEX + YACC debugging

.

MTK358 · 03-28-2010, 07:26 PM

I fixed it!

The funny strings were because yylval was stored in the nodes, but it changes later during parsing. I solved that by making a simple function that allocates a duplicate string.

The Literal/Identifiers with the same value were because I for got the breaks in the switch statement that acted on different nodes.

Now the output is EXACTLY like my example.

Sergei Steshenko · 03-28-2010, 07:38 PM

Quote:

Originally Posted by MTK358

I fixed it!

The funny strings were because yylval was stored in the nodes, but it changes later during parsing. I solved that by making a simple function that allocates a duplicate string.

The Literal/Identifiers with the same value were because I for got the breaks in the switch statement that acted on different nodes.

Now the output is EXACTLY like my example.

So, now you probably have some feeling of (lack of) variables locality, encapsulation and at all relationship between language constructs recognized by parser and triggered by recognition callbacks.

MTK358 · 03-28-2010, 08:05 PM

Code:

stmt: This is line 44
	expr '\n' { $$ = $1; }
	IF expr '\n' stmts ';' '\n' { $$ = mkOpNode(IF, 2, $2, $4); }
;

Code:

$ ./compile 
Running YACC:
lang.y:45.21-22: $$ for the midrule at $3 of `stmt' has no declared type
lang.y:46.60-61: $2 of `stmt' has no declared type
lang.y:46.64-65: $4 of `stmt' has no declared type
YACC returned with exit code 1

What does this mean?

larryherman · 03-28-2010, 09:05 PM

Are you missing a vertical bar between the two lines of your stmt rule? (You want a stmt to be either an expr followed by a newline, or an if statement.)

MTK358 · 03-29-2010, 07:05 AM

Garbled literals/identifiers again:

(input is highlighted in bold)

Code:

$ ./lang
if a = 0
        b := c + (4 * x)
;
if
  EQ
    Identifier: a =
    Literal: 0
  :=
    Identifier: b := c + (4 * x)

    +
      Identifier: c +
      *
        Literal: 4
        Identifier: x)