<p>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.</p>

[{'answer_id': 68285, 'author': 'Ryan', 'author_id': 8819, 'author_profile': 'https://Stackoverflow.com/users/8819', 'pm_score': 2, 'selected': False, 'text': '<p>I don\'t know of any tutorials/guides, but you could try looking at the source for <a href="http://www.tinypy.org/" rel="nofollow noreferrer">tinypy</a>, it\'s a very small implementation of a python like language.</p>\n'}, {'answer_id': 68295, 'author': 'Jason Dagit', 'author_id': 5113, 'author_profile': 'https://Stackoverflow.com/users/5113', 'pm_score': 3, 'selected': False, 'text': '<p>You might want to read this rather well written essay on parsing Python, <a href="http://www.secnetix.de/olli/Python/block_indentation.hawk" rel="nofollow noreferrer">Python: Myths about Indentation</a>.</p>\n\n<p>While I haven\'t tried to write a context free parser using something like yacc, I think it may be possible using a conditional lexer to return the indentation change tokens as described in the url.</p>\n\n<p>By the way, here is the official python grammar from python.org: <a href="http://www.python.org/doc/current/ref/grammar.txt" rel="nofollow noreferrer">http://www.python.org/doc/current/ref/grammar.txt</a></p>\n'}, {'answer_id': 68311, 'author': 'Michael Barker', 'author_id': 6365, 'author_profile': 'https://Stackoverflow.com/users/6365', 'pm_score': 2, 'selected': False, 'text': '<p>Using indentation in a language doesn\'t necessarily mean that the language\'s grammar can not be context free.  I.e. the indentation will determine in which scope a statement exists.  A statement will still be a statement no matter which scope it is defined within (scope can often be handled by a different part of the compiler/interpreter, generally during a semantic parse).</p>\n\n<p>That said a good resource is the antlr tool (<a href="http://www.antlr.org" rel="nofollow noreferrer">http://www.antlr.org</a>).  The author of the tool has also produced a book on creating parsers for languages using antlr (<a href="http://www.antlr.org" rel="nofollow noreferrer">http://www.pragprog.com/titles/tpantlr/the-definitive-antlr-reference</a>).  There is pretty good documentation and lots of example grammars.</p>\n'}, {'answer_id': 68362, 'author': 'Daniel Spiewak', 'author_id': 9815, 'author_profile': 'https://Stackoverflow.com/users/9815', 'pm_score': 0, 'selected': False, 'text': '<p>Just because a language uses significant indentation doesn\'t mean that it is inherently context-sensitive.  As an example, Haskell makes use of significant indentation, and (to my knowledge) its grammar is context-free.</p>\n\n<p>An example of source requiring a context-sensitive grammar could be this snippet from Ruby:</p>\n\n<pre><code>my_essay = &lt;&lt; END_STR\nThis is within the string\nEND_STR\n\n&lt;&lt; self\n  def other_method\n    ...\n  end\nend\n</code></pre>\n\n<p>Another example would be Scala\'s XML mode:</p>\n\n<pre><code>def doSomething() = {\n  val xml = &lt;code&gt;def val &lt;tag/&gt; class&lt;/code&gt;\n  xml\n}\n</code></pre>\n\n<p>As a general rule, context-sensitive languages are slightly harder to imagine in any precise sense and thus far less common.  Even Ruby and Scala don\'t <em>really</em> count since their context sensitive features encompass only a minor sub-set of the language.  If I were you, I would formulate my grammar as inspiration dictates and then worry about parsing methodologies at a later date.  I think you\'ll find that whatever you come up with will be naturally context-free, or very close to it.</p>\n\n<p>As a final note, if you <em>really</em> need context-sensitive parsing tools, you might try some of the less rigidly formal techniques.  Parser combinators are used in Scala\'s parsing.  They have some annoying limitations (no lexing), but they aren\'t a bad tool.  LL(*) tools like ANTLR also seem to be more adept at expressing such "ad hoc" parsing escapes.  Don\'t try to use Yacc or Bison with a context-sensitive grammar, they are far to strict to express such concepts easily.</p>\n'}, {'answer_id': 68575, 'author': 'Scott Wisniewski', 'author_id': 1737192, 'author_profile': 'https://Stackoverflow.com/users/1737192', 'pm_score': 1, 'selected': False, 'text': '<p>I would recommend that you write your parser by hand, in which case having significant whitespace should not present any real problems.</p>\n\n<p>The main problem with using a parser generator is that it is difficult to get good error recovery in the parser. If you plan on implementing an IDE for your language, then having good error recovery is important for getting things like Intellisence to work. Intellisence always works on incomplete syntactic constructs, and the better the parser is at figuring out what construct the user is trying to type, the better an intellisence experience you can deliver.</p>\n\n<p>If you write a hand-written top-down parser, you can pretty much implement what ever rules you want, where ever you want to. This is what makes it easy to provide error recovery. It will also make it trivial for you to implement significant whitespace. You can simply store what the current indentation level is in a variable inside your parser class, and can stop parsing blocks when you encounter a token on a new line that has a column position that is less than the current indentation level. Also, chances are that you are going to run into ambiguities in your grammar. Most “production” languages in wide use have syntactic ambiguities. A good example is generics in C# (there are ambiguities around "&lt;" in an expression context, it can be either a "less-than" operator, or the start of a "generic argument list"). In a hand-written parser solving ambiguities like that are trivial. You can just add a little bit of non-determinism where you need it with relatively little impact on the rest of the parser, </p>\n\n<p>Furthermore, because you are designing the language yourself, you should assume it\'s design is going to evolve rapidly (for some languages with standards committees, like C++ this is not the case). Making changes to automatically generated parsers to either handle ambiguities, or evolve the language, may require you to do significant refactoring of the grammar, which can be both irritating and time consuming. Changes to hand written parsers, particularly for top-down parsers, are usually pretty localized.</p>\n\n<p>I would say that parser generators are only a good choice if:</p>\n\n<ol>\n<li>You never plan on writing an IDE ever,</li>\n<li>The language has <strong><em>really</em></strong> simple syntax, or</li>\n<li>You need a parser extremely quickly, and are ok with a bad user experience</li>\n</ol>\n'}, {'answer_id': 69185, 'author': 'Allan Wind', 'author_id': 9706, 'author_profile': 'https://Stackoverflow.com/users/9706', 'pm_score': 1, 'selected': False, 'text': '<p>Have you read Aho, Sethi, Ullman: "Compilers: Principles, Techniques, and Tools"?  It is a classical language reference book.</p>\n\n<p>/Allan</p>\n'}, {'answer_id': 69482, 'author': 'Kent Quirk', 'author_id': 11072, 'author_profile': 'https://Stackoverflow.com/users/11072', 'pm_score': 1, 'selected': False, 'text': '<p>If you\'ve never written a parser before, start with something simple. Parsers are surprisingly subtle, and you can get into all sorts of trouble writing them if you\'ve never studied the structure of programming languages.</p>\n\n<p>Reading Aho, Sethi, and Ullman (it\'s known as "The Dragon Book") is a good plan. Contrary to other contributors, I say you should play with simpler parser generators like Yacc and Bison first, and only when you get burned because you can\'t do something with that tool should you go on to try to build something with an LL(*) parser like Antlr.</p>\n'}, {'answer_id': 69527, 'author': 'bugmagnet', 'author_id': 426, 'author_profile': 'https://Stackoverflow.com/users/426', 'pm_score': 0, 'selected': False, 'text': '<p>A context-sensitive language? This one\'s non-indented: Protium (<a href="http://www.protiumble.com" rel="nofollow noreferrer">http://www.protiumble.com</a>)</p>\n'}, {'answer_id': 70783, 'author': 'λ Jonas Gorauskas', 'author_id': 11507, 'author_profile': 'https://Stackoverflow.com/users/11507', 'pm_score': 3, 'selected': False, 'text': '<p>I would familiarize myself with the problem first by reading up on some of the literature that\'s available on the subject. The classic <em>Compilers</em> book by Aho et. al. may be heavy on the math and comp sci, but a much more aproachable text is the <a href="http://compilers.iecc.com/crenshaw/" rel="noreferrer"><em>Let\'s Build a Compiler</em></a> articles by Jack Crenshaw. This is a series of articles that Mr. Crenshaw wrote back in the late 80\'s and it\'s the most under-appreciated text on compilers ever written. The approach is simple and to the point: Mr. Crenshaw shows "<strong>A</strong>" approach that works. You can easily go through the content in the span of a few evenings and have a much better understanding of what a compiler is all about. A couple of caveats are that the examples in the text are written in Turbo Pascal and the compilers emit 68K assembler. The examples are easy enough to port to a more current programming language and I recomment Python for that. But if you want to follow along as the examples are presented you will at least need <a href="http://dn.codegear.com/article/20803" rel="noreferrer">Turbo Pascal 5.5</a> and <a href="http://www.easy68k.com/" rel="noreferrer">a 68K assembler and emulator</a>. The text is still relevant today and using these old technologies is really fun. I highly recommend it as anyone\'s first text on compilers. The great news is that languages like Python and Ruby are open sourced and you can download and study the C source code in order to better understand how it\'s done. </p>\n'}, {'answer_id': 261520, 'author': 'Walter Bright', 'author_id': 33949, 'author_profile': 'https://Stackoverflow.com/users/33949', 'pm_score': 4, 'selected': False, 'text': "<p>A context-free grammar is, simply, one that doesn't require a symbol table in order to correctly parse the code. A context-sensitive grammar does.</p>\n\n<p>The D programming language is an example of a context free grammar. C++ is a context sensitive one. (For example, is T*x declaring x to be pointer to T, or is it multiplying T by x ? We can only tell by looking up T in the symbol table to see if it is a type or a variable.)</p>\n\n<p>Whitespace has nothing to do with it.</p>\n\n<p>D uses a context free grammar in order to greatly simplify parsing it, and so that simple tools can parse it (such as syntax highlighting editors).</p>\n"}, {'answer_id': 315462, 'author': 'Larry OBrien', 'author_id': 10116, 'author_profile': 'https://Stackoverflow.com/users/10116', 'pm_score': 2, 'selected': False, 'text': '<p>If you\'re really going to take a whack at language design and implementation, you might want to add the following to your bookshelf:</p>\n\n<ul>\n<li>Programming Language Pragmatics, Scott et al.</li>\n<li>Design Concepts in Programming Languages, Turbak et al.</li>\n<li>Modern Compiler Design, Grune et al. (I sacrilegiously prefer this to "The Dragon Book" by Aho et al.)</li>\n</ul>\n\n<p>Gentler introductions such as:</p>\n\n<ul>\n<li>Crenshaw\'s tutorial (as suggested by @\'Jonas Gorauskas\' here)</li>\n<li>The Definitive ANTLR Reference by Parr</li>\n<li>Martin Fowler\'s recent work on DSLs</li>\n</ul>\n\n<p>You should also consider your implementation language. This is one of those areas where different languages <em>vastly</em> differ in what they facilitate. You should consider languages such as LISP, F# / OCaml, and Gilad Bracha\'s new language Newspeak. </p>\n'}, {'answer_id': 1473209, 'author': 'Imagist', 'author_id': 130640, 'author_profile': 'https://Stackoverflow.com/users/130640', 'pm_score': 2, 'selected': False, 'text': '<p>"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:</p>\n\n<pre><code>int main()\n{\n    int i;\n    i = 1;\n    return 0;\n}\n\nint main()\n{\n    int i;\n    i = "Hello, world";\n    return 0;\n}\n</code></pre>\n\n<p>Free of context, <code>i = "Hello, world";</code> is a perfectly valid assignment, but in context you can see that the types are all wrong.  If the context were <code>char* i;</code> 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.</p>\n\n<p>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.</p>\n\n<p>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.</p>\n'}]
['https://Stackoverflow.com/questions/68243', 'https://Stackoverflow.com', 'https://Stackoverflow.com/users/-1/']