monodimensional or bidimensional context-free grammar?

[napier]

Hi,
I would like to understand a theoretical foundation about the software. Are the context-free grammars implemented in the software bidimensional? Are they an extension of the 1D context-free grammars?

[raimondious]

Could you clarify the difference between 1-D and 2-D CFGs? ContextFree implements the same kind of CFG as does yacc, bison:
Ones like:

S -> A|B|aSb
A -> c|B
B -> d|S

where capitals are rules that can expand to other rules, terminal symbols (the lowercases, which are shapes in CF's case), or a combination of the two.

[MtnViewJohn]

I think that Chris can answer this question best, but here goes...

Context Free interprets a CFDG grammar to produce a 'sentence'. The sentence is an ordered list of simple shapes (squares, circles, and triangles). Each shape has a 2-D affine transform associated with it that falls out of the grammar along with the shape. This sentence is then translated into a 2-D image, but the sentence itself is a 1-D string of shape symbols. If we created a 3-D version of Context Free then the sentence would be translated into a 3-D output but it would still be 1-D.

[napier]

Ok, now I've understood, it's the 1D case.
Raimondious, in the 2D case CFGs produce "pictures" instead of words/strings. If you want to know something more about you could search for "bidimensional grammar" on Google.

Bye bye!