Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Strange problem with context free grammar

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.

like image 268
Chris Tonkinson Avatar asked Aug 05 '10 22:08

Chris Tonkinson


People also ask

How do I remove useless symbols in CFG?

To remove useless productions , we first find all the variables which will never lead to a terminal string such as variable 'B'. We then remove all the productions in which variable 'B' occurs. We then try to identify all the variables that can never be reached from the starting variable such as variable 'C'.

Is context-free grammar ambiguous?

Ambiguous Context Free Languages : A context free language is called ambiguous if there is no unambiguous grammar to define that language and it is also called inherently ambiguous Context Free Languages.

What is ambiguity in context-free grammar with examples?

If a context free grammar G has more than one derivation tree for some string w ∈ L(G), it is called an ambiguous grammar. There exist multiple right-most or left-most derivations for some string generated from that grammar.


1 Answers

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

like image 126
jpalecek Avatar answered Oct 08 '22 20:10

jpalecek