Alex Rivera | Logout

What's a good resource for starting to write a programming language, that's not context free?

Asked 2008-09-16T00:28:16.567
14

I'm looking to write a programming language for fun, however most of the resource I have seen are for writing a context free language, however I wish to write a language that, like python, uses indentation, which to my understanding means it can't be context free.

Edit
Report

2 Answers

3

"Context-free" is a relative term. Most context-free parsers actually parse a superset of the language which is context-free and then check the resulting parse tree to see if it is valid. For example, the following two C programs are valid according to the context-free grammar of C, but one quickly fails during context-checking:

int main()
{
    int i;
    i = 1;
    return 0;
}

int main()
{
    int i;
    i = "Hello, world";
    return 0;
}

Free of context, i = "Hello, world"; is a perfectly valid assignment, but in context you can see that the types are all wrong. If the context were char* i; it would be okay. So the context-free parser will see nothing wrong with that assignment. It's not until the compiler starts checking types (which are context dependent) that it will catch the error.

Anything that can be produced with a keyboard can be parsed as context-free; at the very least you can check that all the characters used are valid (the set of all strings containing only displayable Unicode Characters is a context-free grammar). The only limitation is how useful your grammar is and how much context-sensitive checking you have to do on your resulting parse tree.

Whitespace-dependent languages like Python make your context-free grammar less useful and therefore require more context-sensitive checking later on (much of this is done at runtime in Python through dynamic typing). But there is still plenty that a context-free parser can do before context-sensitive checking is needed.

answered 2009-09-24T17:54:45.073
2

I don't know of any tutorials/guides, but you could try looking at the source for tinypy, it's a very small implementation of a python like language.

answered 2008-09-16T00:40:10.190

Your Answer