New compilers for OgreScript [UPDATED]

[Praetor]

I've started to collect a few features from the feature requests forum that pertain to scripts and material scripts in particular, and started to dabble in a new compiler for the scripts. A new compiler that takes advantage of a more complete compilation mechanism will enable much of these features. I've come up the with idea that formalizing the language that is used by ogre's scripts is the first step. It seems to me like the major elements of the language are the same for all scripts, or at least can be made to be, and that the differences are in the names and values used. So, here is the first step, a rough formalization of the script language:

Code: Select all

alpha ::= [A-Z][a-z]
num ::= [0-9]
keyword ::= alpha{alpha | num | '_'}
value ::= keyword | '"'{alpha|num|' '}'"'
block ::= keyword '{' {block_contents} '}'
block_contents ::= block | keyword value {value}

Any corrections, additions, or syntax problems, feel free!

The new compilers will be built as much as can be off of the current compilers. The next step would be quick tests for performance and memory consumption as that is one of the bottlenecks for the current development, and it wouldn't make sense for the new compilers to be worse than the current ones.

[haffax]

Are you aware of Ogre's Compiler2Pass? nfz started work on it some time ago and it is already in Ogre, but not used by default. It already more or less uses the idea to use and expand a BNF for Ogre's scripts.

But I am not sure of the status and outlook regarding it.

[Praetor]

That's what I've been toying with. The Compiler2Pass actually is in use right now, in both dagon and eihort. Maybe you are thinking of a new version? The current version works well. Newer requested features in the scripts are starting to strain it though, and I think that stems from the fact that it is a lexer, which then goes right into a token-by-token compiler. It works great and very quickly for the scripts as they were, but allowing for more flexible formats and newer features is getting pretty difficult.

The first thing I want to do is look into the lexer that is used now. If it is robust and works well I can just reuse that. I'd hate to code my own, or bring in another outside dependency. It just happens to be that (surprise surprise) it is not exactly trivial code to examine.

[Kencho]

Just a quick glance at it, but seems that you forgot our friend texture_unit

Code: Select all

keyword ::= alpha{alpha | num | '_'}

[Praetor]

@ kencho too true. Thanks, I made the change.

Looking deeper into Compiler2Pass, well, there is a lot there. It looks like it indeed does some sort of work with the BNF grammar itself. I'll have to look into that. I also know that making it accept things like newlines between certain tokens has strained it. What I want to know is whether that strain is on the lexer, or in some other part of it. I guess I'll keep looking.

The key to the new compiler will be that the grammar is very simple. Right now, everything is syntactic analysis. Semantic analysis has been very hard. Instead, like a heavier compiler, I want to build an abstract syntax tree from the input. This will let the grammar needed to parse any specific type of script be a lot simpler (as you can see above) and push quite a bit of work off to semantic analysis.

[Assaf Raman]

I don't like it.
I think that using XML will be better.
It will sure be much more easy to create scripts with external tools.

[Game_Ender]

But the point of Ogre Script format is to allow easy creation of scripts by hand, not by other tools. Where data interchange is expected Ogre uses XML (see skeleton and mesh formats). I personally don't have any problem writing XML by hand, but I can understand the aversion to it. It would probably wouldn't be that hard to create a XML based parser for whatever project you need based on the Ogre C++ API.

[Praetor]

All new features are going to be additions. The new compilers should be able to compile all current scripts.

[haffax]

XML/Not XML has been discussed to death already, and always has been rejected for the reasons Game_Ender named. Also creation/parsing it with script languages is very easy.

[Assaf Raman]

I guess you are right.
Script files are much easier to read then XML files.
Also - you can use the material class to serialize the script files for use with any automated tool that will be created.
I withdraw my request for an XML script.
Sorry for your time.

[Praetor]

I believe I've tracked down the confusion in Compiler2Pass.

Compiler2Pass is a very generic parser generator/lexer. It is designed so that the entire grammar of a specific script can be customized. Currently, materials, compositors, etc. each register their own EBNF grammars to be parsed. Look at OgreMaterialScriptCompiler.cpp and see the grammar, and then compare it to the one above.

I want to identify what is the same in all the scripts, and have a new, sleeker lexer tokenize that, and let the custom parts of the script end up in an AST for more rigorous operations. That's why my grammar is so simple in comparison, most of the stuff will just be nodes in a tree.

[Kencho]

The problem I see with this approach is that the syntax is too vague for certain things... The grammar you describe there is able to lexically identify tokens and create a token tree. However, once you've built the tree, you have to re-walk it in order to manually determine if it's correct or not. For instance,

Code: Select all

material my_material
{
    technique
    {
        pass
        {
            ...
        }
    }
}

will create this tree sturcture (by the way, I've realised it doesn't recognise "material my_material {...}"):

Code: Select all

block_contents
  block
    keyword 
    {
    block_contents
      block
        keyword
        {
        block_contents
          block
            keyword
            {
              block_contents [...]
            }
        }
    }

But the problem is that

Code: Select all

material my_material
{
    pass
    {
        technique
        {
            ...
        }
    }
}

generates the same tree.
So we would need some extra token attributes (for instance, its value, to differentiate, ie "technique" and "pass"). And then, perform the syntax correctness check ourselves by hand on the tree.

Yacc/Bison can perform LALR analysis easily, checking the syntax correctness as they build the syntactic tree, and also performing associated syntactic/semantic actions (useful to build the objects structure -a material and their techniques, passes...- as the script is parsed).

IMHO, it's better to use an existing parser generator, though it might require to define each grammar separately, forced to duplicate some code there...

[Praetor]

I was thinking of parser generators as well, and I also thought of use boost's spirit (the spirit people provide a nice distribution with minimal boost dependencies). I will work up a simple lexer prototype to see how it goes. The thing is, the tree only needs to be created, then traversed once. The traversal is the actual compilation (granted, some mini-traversals may need to happen during this process) and the semantic check.

I also noticed a few omissions with the above grammar. I'll make the changes in a bit.

A quick prototype should clear most of this business up.

[tau]

I vote for using YAcc for the old and new formats - easy to spot a problem and add new features.

Just my 2 cents.

[Praetor]

I'll look into generators. The nice thing about hand-coded (if it's easy enough, as this syntax seems to be) is I can infuse it with much better warnings. Granted, I could go in and hand-edit the generated code...

I'm on the quarter system at my uni so finals are coming up. In a week or 2 I'll be able to work up a small prototype to try a hand-coded lexer and AST generator. A little proof of concept. I'll focus on material scripts first.

[Praetor]

UPDATE!

Well, I didn't go with the generator after all. Turned out, as I suspected, the lexer was a really simple state machine to code up. I've now moved on to AST generation with a sample Material compiler. The same mechanism is used, where a base compiler is derived to form the material compiler. So, currently what happens is the material compiler gives hints to the base to help it tokenize and generate the AST. The AST is then stored in a protected variable and the overridden function compile is called. The interesting thing is I've already tested such input as

Code: Select all

material Test{technique{pass{
    diffuse 0 0 0
}}}

and the really awesome

Code: Select all

pass Template
{
    diffuse 1 1 1
}

material Test
{
    technique{pass : Template{}}
}

You'll notice the copying paradigm used for materials used here at the pass level. The compiler is still very much a prototype and I need to polish up how the copying (: "") works but so far it is going well. Once I work out a good standardized way to address members of other elements (like another material's technique) you would be able to copy from other materials. We'll call this addressing OgrePath for now.

So, how fast is it? Is it a memory hog? Unfortunately, I have absolutely no idea. Seems fast enough so far. Once I generate a full AST from material files I can really start testing it. Hmm... I wonder if this would fly as an SoC project...

[Praetor]

Another update. Close to a preview/prototype for materials. I have managed to generate a full AST for material files now. Here is the test material script.

Code: Select all

pass Template{}

material Examples/CelShading{lod_distances 0 100 1000
	technique{lod_index 0
	scheme test
		pass
		{
		    diffuse 0 0 0
		    ambient 1 1 1
			vertex_program_ref Ogre/CelShadingVP
			{
				// map shininess from custom renderable param 1
				param_named_auto shininess custom 1
			}
			fragment_program_ref Ogre/CelShadingFP
			{
				// map diffuse from custom renderable param 2
				param_named_auto diffuse custom 2
				// map specular from custom renderable param 2
				param_named_auto specular custom 3
			}
			texture_unit
			{
				texture cel_shading_diffuse.png 1d
				tex_address_mode clamp
				filtering none
			}
			texture_unit
			{
				texture cel_shading_edge.png 1d
				tex_address_mode clamp
				filtering none
				tex_coord_set 2
			}}}}

vertex_program Test cg{profiles arbvp1 ps_1_1}

Notice that I've mangled some of the lines in terms of newlines and such. The compiler must be able to handle that. Here is a representation of the AST generated.

Code: Select all

ID: 10 Line 1::pass
ID: 2 Line 1::Template
ID: 8 Line 3::material
ID: 2 Line 3::Examples/CelShading
	ID: 16 Line 3::lod_distances
		ID: 2 Line 3::0
		ID: 2 Line 3::100
		ID: 2 Line 3::1000
	ID: 9 Line 4::technique
		ID: 21 Line 4::lod_index
			ID: 2 Line 4::0
		ID: 20 Line 5::scheme
			ID: 2 Line 5::test
		ID: 10 Line 6::pass
			ID: 23 Line 8::diffuse
				ID: 2 Line 8::0
				ID: 2 Line 8::0
				ID: 2 Line 8::0
			ID: 22 Line 9::ambient
				ID: 2 Line 9::1
				ID: 2 Line 9::1
				ID: 2 Line 9::1
			ID: 14 Line 10::vertex_program_ref
			ID: 2 Line 10::Ogre/CelShadingVP
				ID: 86 Line 13::param_named_auto
					ID: 2 Line 13::shininess
					ID: 2 Line 13::custom
					ID: 2 Line 13::1
			ID: 15 Line 15::fragment_program_ref
			ID: 2 Line 15::Ogre/CelShadingFP
				ID: 86 Line 18::param_named_auto
					ID: 23 Line 18::diffuse
					ID: 2 Line 18::custom
					ID: 2 Line 18::2
				ID: 86 Line 20::param_named_auto
					ID: 24 Line 20::specular
					ID: 2 Line 20::custom
					ID: 2 Line 20::3
			ID: 11 Line 22::texture_unit
				ID: 48 Line 24::texture
					ID: 2 Line 24::cel_shading_diffuse.png
					ID: 2 Line 24::1d
				ID: 52 Line 25::tex_address_mode
					ID: 2 Line 25::clamp
				ID: 54 Line 26::filtering
					ID: 2 Line 26::none
			ID: 11 Line 28::texture_unit
				ID: 48 Line 30::texture
					ID: 2 Line 30::cel_shading_edge.png
					ID: 2 Line 30::1d
				ID: 52 Line 31::tex_address_mode
					ID: 2 Line 31::clamp
				ID: 54 Line 32::filtering
					ID: 2 Line 32::none
				ID: 51 Line 33::tex_coord_set
					ID: 2 Line 33::2
ID: 12 Line 36::vertex_program
ID: 2 Line 36::Test
ID: 2 Line 36::cg
	ID: 75 Line 36::profiles
		ID: 2 Line 36::arbvp1
		ID: 2 Line 36::ps_1_1

Note 1) I recently added storing line numbers with tokens. This is for the sole purpose of useful error messages.

Note 2) Notice the ID tags. Those are token IDs and each different token has its own ID. This should once the lexing process is done there are NO MORE STRING COMPARISONS. Probably won't offer an amazing speed boost, but it'll be something. And, I suppose it depends on the size and number of material scripts you are compiling. Could be significant.

Note 3) The top of the material script declare a global pass. This can then be "inherited" from later on. This is the main benefit of the AST. The tree lets me go back and forth along the input very quickly. The cost of backtracking for something like this is tiny in comparison to running over the input again. And, since it's so easy I don't need to store a lot of extra state to "remember" these kinds of features, so it keeps memory consumption low.

Next step is taking this AST and generating an actual usable material. I'm pretty sure this will be fairly trivial.

[CaseyB]

Cool! Good work, I think this is a great step as it will be more flexible!!

[jacmoe]

Not only that: it will mean leaner material scripts! Reusable material elements!

[Praetor]

I just thought of something else.

Say you wanted to create a whole library of materials, and had some base techniques you wanted to inherit from. Either you would need all materials in the same script, or you would need to re-declare the base techniques in each script file. This is because those high-level base techniques are scripting elements only, they don't affect the internal Ogre material system's state at all, so I wouldn't be able to go back and find them later. Instead, I was thinking you could define these base elements in a separate script and support an import feature. Like this:

In base.material

Code: Select all

technique BaseTechnique
{
    ...
}

In test.material

Code: Select all

import base.material

material Test
{
    technique : BaseTechnique
    {
        ...
    }
}

The import would be just like the one in C/C++, just a textual copy. This would probably increase compilation times, but for smaller base scripts it's probably negligible.

[spookyboo]

Interesting to see how this turns out.

I've done something similar in my particle scripts. Define an alias (which can be a technique, emitter, ...) in one script and use the alias where it is needed (in another script).
You don't need the import base.material in test.material if you ensure that BaseTechnique is compiled first (needs different extensions for base.material)

[Praetor]

Well, if the technique I'm referring to was actually part of another material, then it will be fine, I can simply go into the material system and pluck out that previous material. But in this case there is a global Pass that is part of no material. It does not make sense that a pass just floats around outside of a material, so I need some way to access it. Also, this can ensure a more explicit reference instead of hoping one material gets loaded before another.

Eventually if this compiler works out it will extend to more than materials. All scripts should be compiled with it. So, I suppose when I get to particle systems we should discuss what additions you've made so they are incorporated as well.

[Kencho]

Looking great. Nice job, Praetor! Hope this definitely becomes part of Ogre

[jacmoe]

@kencho:

Are you aware of Ogre's Compiler2Pass? nfz started work on it some time ago and it is already in Ogre, but not used by default. It already more or less uses the idea to use and expand a BNF for Ogre's scripts.

That's what I've been toying with.

... snip ...

The first thing I want to do is look into the lexer that is used now. If it is robust and works well I can just reuse that. I'd hate to code my own, or bring in another outside dependency. It just happens to be that (surprise surprise) it is not exactly trivial code to examine.

Looks like Praetor is continuing what nfz started.