This forum is closed to new posts due to low activity and a deluge of spam. It is kept online as a static historical record. If you want to read about or discuss esoteric programming languages, the Esolang wiki is the place to go. An archive of the forum is available.

Is Befunge grammar context-free or context-sensitive? (2)

1 Name: Jake : 2009-08-14 02:48 ID:T+WsH8Nm

Hi, I had an idea a few days ago to create a textual, two-dimensional, declarative, domain-specific language for describing graphs and graph-like structures. While trying to work out how to formalize the grammar language, I discovered Befunge, which is also a textual, 2d language. I'm wondering, is Befunge's syntax context-free or context-sensitive? Would it be possible to describe it using EBNF notation? I've been searching for this on the interwebs, but have yet to find it. Any guidance would be appreciated.



2 Name: Ørjan : 2009-08-14 20:58 ID:dW+lWfZ0

Befunge is self-modifying, and a program part doesn't need to be syntactically correct until it is actually run. So I would assume its syntax is not even decidable.

Even without modification, I cannot imagine it being context-free, with program flow cutting across lines. Maybe context-sensitive though, that's equivalent to linear space computations and I think those can do a lot of soundness checking.

Name: Link:
Leave these fields empty (spam trap):
More options...