Strange problem with context free grammar

Question

I begin with an otherwise well formed (and well working) grammar for a language. Variables, binary operators, function calls, lists, loops, conditionals, etc. To this grammar I'd like to add what I'm calling the object construct:

object
  : object_name ARROW more_objects
  ;

more_objects
  : object_name
  | object_name ARROW more_objects
  ;

object_name
  : IDENTIFIER
  ;

The point is to be able to access scalars nested in objects. For example:

car->color
monster->weapon->damage
pc->tower->motherboard->socket_type

I'm adding object as a primary_expression:

primary_expression
  : id_lookup
  | constant_value
  | '(' expression ')'
  | list_initialization
  | function_call
  | object
  ;

---

Now here's a sample script:

const list = [ 1, 2, 3, 4 ];
for var x in list {
  send "foo " + x + "!";
}
send "Done!";

Prior to adding the nonterminal object as a primary_expression everything is sunshine and puppies. Even after I add it, Bison doesn't complain. No shift and/or reduce conflicts reported. And the generated code compiles without a sound. But when I try to run the sample script above, I get told error on line 2: Attempting to use undefined symbol '{' on line 2.

If I change the script to:

var list = 0;
for var x in [ 1, 2, 3, 4 ] {
  send "foo " + x + "!";
}
send "Done!";

Then I get error on line 3: Attempting to use undefined symbol '+' on line 3.

Clearly the presence of object in the grammar is messing up how the parser behaves [SOMEhow], and I feel like I'm ignoring a rather simple principle of language theory that would fix this in a jiff, but the fact that there aren't any shift/reduce conflicts has left me bewildered.

Is there a better way (grammatically) to write these rules? What am I missing? Why aren't there any conflicts?

(And here's the full grammar file in case it helps)

---

UPDATE: To clarify, this language, which compiles into code being run by a virtual machine, is embedded into another system - a game, specifically. It has scalars and lists, and there are no complex data types. When I say I want to add objects to the language, that's actually a misnomer. I am not adding support for user-defined types to my language.

The objects being accessed with the object construct are actually objects from the game which I'm allowing the language processor to access through an intermediate layer which connects the VM to the game engine. This layer is designed to decouple as much as possible the language definition and the virtual machine mechanics from the implementation and details of the game engine.

So when, in my language I write:

player->name

That only gets codified by the compiler. "player" and "name" are not traditional identifiers because they are not added to the symbol table, and nothing is done with them at compile time except to translate the request for the name of the player into 3-address code.

Answer 1

So I spent a reasonable amount of time picking over the grammar (and the bison output) and can't see what is obviously wrong here. Without having the means to execute it, I can't easily figure out what is going on by experimentation. Therefore, here are some concrete steps I usually go through when debugging grammars. Hopefully you can do any of these you haven't already done and then perhaps post follow-ups (or edit your question) with any results that might be revealing:

1. Contrive the smallest (in terms of number of tokens) possible working input, and the smallest possible non-working inputs based on the rules you expect to be applied.
2. Create a copy of the grammar file including only the troublesome rules and as few other supporting rules as you can get away with (i.e. you want a language that only allows construction of sequences consisting of the object and more_object rules, joined by ARROW. Does this work as you expect?
3. Does the rule in which it is nested work as you expect? Try replacing object with some other very simple rule (using some tokens not occuring elsewhere) and seeing if you can include those tokens without it breaking everything else.
4. Run bison with --report=all. Inspect the output to try to trace the rules you've added and the states that they affect. Try removing those rules and repeat the process - what has changed? This is extremely time consuming often, and is a giant pain, but it's a good last resort. I recommend a pencil and some paper.

Looking at the structure of your error output - '+' is being recognised as an identifier token, and is therefore being looked up as a symbol. It might be worth checker your lexer to see how it is processing identifier tokens. You might just accidentally be grabbing too much. As a further debugging technique, you might consider turning some of those token literals (e.g. '+', '{', etc) into real tokens so that bison's error reporting can help you out a little more.

EDIT: OK, the more I've dug into it, the more I'm convinced that the lexer is not necessarily working as it should be. I would double-check that the stream of tokens you are getting from yylex() matches your expectations before proceeding any further. In particular, it looks like a bunch of symbols that you consider special (e.g. '+' and '{') are being captured by some of your regular expressions, or at least are being allowed to pass for identifiers.

Answer 2

It seems you are doing a classical error when using direct strings in the yacc source file. Since you are using a lexer, you can only use token names in yacc source files. More on this here

Answer 3

I think your principal problem is that you failed to define a subtree constructor in your object subgrammar. (EDIT: OP says he left the semantic actions for object out of his example text. That doesn't change the following answer).

You probably have to lookup up the objects in the order encountered, too. Maybe you intended:

primary_expression 
   : constant_value                                        { $$ = $1; } 
   | '(' expression ')'                                    { $$ = $2; } 
   | list_initialization                                   { $$ = $1; } 
   | function_call                                         { $$ = $1; } 
   | object                                                { $$ = $1; } 
   ; 



object
   : IDENTIFIER    { $$ = LookupVariableOrObject( yytext ); } 
   |  object ARROW IDENTIFIER  { $$ = LookupSubobject( $1, yytext ); } 
   ; 

I assume that if one encounters an identifier X by itself, your default interpretation is that it is a variable name. But, if you encounter X -> Y, then even if X is a variable name, you want the object X with subobject Y.

What LookupVarOrObject does is to lookup the leftmost identifier encountered to see if it is variable (and return essentially the same value as idlookup which must produce an AST node of type AST_VAR), or see if it is valid object name, and return an AST node marked as an AST_OBJ, or complain if the identifier isn't one of these.

What LookupSuboject does, is to check its left operand to ensure it is an AST_OBJ (or an AST_VAR whose name happens to be the same as that of an object). and complain if it is not. If it is, then its looks up the yytext-child object of the named AST_OBJ.

EDIT: Based on discussion comments in another answer, right-recursion in the OP's original grammar might be problematic if the OP's semantic checks inspect global lexer state (yytext). This solution is left-recursive and won't run afoul of that particular trap.

Answer 4

You don't get shift/reduce conflicts because your rules using object_name and more_objects are right-recursive - rather than the left-recursive rules that Yacc (Bison) handles most naturally.

On classic Yacc, you would find that you can run out of stack space with deep enough nesting of the 'object->name->what->not' notation. Bison extends its stack at runtime, so you have to run out of memory, which is a lot harder these days than it was when machines had a few megabytes of memory (or less).

One result of the right-recursion is that no reductions occur until you read the last of the object names in the chain (or, more accurately, one symbol beyond that). I see that you've used right-recursion with your statement_list rule too - and in a number of other places too.

Answer 5

id_lookup : IDENTIFIER

is formally identical to

object_name : IDENTIFIER

and object_name would accept everything that id_lookup wouldn't, so assertLookup( yytext ); probably runs on everything that may look like IDENTIFIER and is not accepted by enother rule just to decide between the 2 and then object_name can't accept because single lookahead forbids that.

For the twilight zone, the two chars that you got errors for are not declared as tokens with opends the zone of undefinded behavior and could trip parser into trying to treat them as potential identifiers when the grammar gets loose.

Answer 6

I just tried running muscl in Ubuntu 10.04 using bison 2.4.1 and I was able to run both of your examples with no syntax errors. My guess is that you have a bug in your version of bison. Let me know if I'm somehow running your parser wrong. Below is the output from the first example you gave.

./muscle < ./test1.m (this was your first test)

\-statement list
  |-declaration (constant)
  | |-symbol reference
  | | \-list (constant)
  | \-list
  |   |-value
  |   | \-1
  |   |-value
  |   | \-2
  |   |-value
  |   | \-3
  |   \-value
  |     \-4
  |-loop (for-in)
  | |-symbol reference
  | | \-x (variable)
  | |-symbol reference
  | | \-list (constant)
  | \-statement list
  |   \-send statement
  |     \-binary op (addition)
  |       |-binary op (addition)
  |       | |-value
  |       | | \-foo 
  |       | \-symbol reference
  |       |   \-x (variable)
  |       \-value
  |         \-!
  \-send statement
    \-value
      \-Done!

 +-----+----------+-----------------------+-----------------------+
 |   1 | VALUE    | 1                     |                       |
 |   2 | ELMT     | @1                    |                       |
 |   3 | VALUE    | 2                     |                       |
 |   4 | ELMT     | @3                    |                       |
 |   5 | VALUE    | 3                     |                       |
 |   6 | ELMT     | @5                    |                       |
 |   7 | VALUE    | 4                     |                       |
 |   8 | ELMT     | @7                    |                       |
 |   9 | LIST     |                       |                       |
 |  10 | CONST    | @10                   | @9                    |
 |  11 | ITER_NEW | @11                   | @10                   |
 |  12 | BRA      | @14                   |                       |
 |  13 | ITER_INC | @11                   |                       |
 |  14 | ITER_END | @11                   |                       |
 |  15 | BRT      | @22                   |                       |
 |  16 | VALUE    | foo                   |                       |
 |  17 | ADD      | @16                   | @11                   |
 |  18 | VALUE    | !                     |                       |
 |  19 | ADD      | @17                   | @18                   |
 |  20 | SEND     | @19                   |                       |
 |  21 | BRA      | @13                   |                       |
 |  22 | VALUE    | Done!                 |                       |
 |  23 | SEND     | @22                   |                       |
 |  24 | HALT     |                       |                       |
 +-----+----------+-----------------------+-----------------------+
foo 1!
foo 2!
foo 3!
foo 4!
Done!