How to Parse Ruby
programmingisterrible.com
programmingisterrible.com
I learned a ton about ruby when implementing that. Did you know that this totally works:
my_method <<-ONE, <<-TWO, <<-THREE
text of one
ONE
text of two
TWO
text of three
THREE
(also note that pygments chokes on my perfectly valid ruby file, at `%r(\\\\)`)
Pygments was actually better at lexing ruby at one point but the regular expressions were too complex and some other bug fixes broke other stuff. I think at the moment it's good enough.
But yeah, I was in the same boat. I learned Ruby for Pygments.
//EDIT: vim does considerably worse on that file btw.
:D I guess you're the author of all those frustrated "wtf ruby" comments I found in the pygments lexer, then :). I seriously doubt I could have done it at all without pygments as a reference.
My vim does fine on that file: http://imgur.com/VSYr4aa . Maybe I'm using a more recent version...? It misses some of the `end` keywords, but that's just a quirk that it has ;)
Another example that bit me - this took the longest, I think:
foo = 10
foo %(2) # call method foo with string "2"
foo % 2 # the value of foo modulo 2
% 2 # the string "2" <<-END
this is some text
END
It's particularly useful in metaprogramming, since you can maintain formatting, and you don't have to escape " or ' if they happen to show up in your code.
What's interesting in the OP's example is that you end up passing three strings " text of one\n", " text of two\n", " text of three\n". I had no idea that would happen, though I have seen things like
define_method <<-RUBY, __FILE__, __LINE__ + 1
some_code
RUBY
I had no idea it could be nested like that and I've been using ruby for 8 years. Crazy!
Some days I wish Matz would formalize the grammar so it is sane.
foo * bar;
(a) - (b)
- in JavaScript braces are used both as block delimiters and object literal delimiters - in CoffeeScript, which prevents that particular grammar ambiguity from JS, whitespace is used for many different things: scope/block delimiting, object literals, even function calls (optional parentheses) - Python uses parentheses both for expression grouping (precedence), function calls AND tuples - square brackets are used in many languages to both denote literal lists/arrays and element access ([] operator) - etc, etc, etc
There are very few languages that i know about don't do this kind of lexical-token overloading. Smalltalk is an example: square brackets are always blocks, parentheses are only used to group expressions, dots are always statement terminators, etc. I think Haskell is another example of a straightforward syntax, but don't quote me on that.
Is there any formal name for these kinds of non-overloaded/simple syntaxes? If there is a formalism for those, why is it that "overloaded" syntaxes are preferred most of the time, or why are they so prevalent?
I guess it's always a trade-off between simplicity at the grammar level and ease of use, but i'm not so sure about that either. Smalltalk has a very simple grammar, yet that doesn't make it harder to use than other languages with similar semantics; e.g. Ruby, which prefers to be "programmer friendly" by having multiple syntactic forms for denoting blocks, even a special syntax for calling function whose last parameter is a block, and much much more.
The problems is that there's only a limited number of symbols available in ASCII, especially "matching"/"paired" symbols where you've got all of three pairs to work with (`{}`, `[]` and `()`), with one pair having a lot of immutable baggage (`()`) and one being coopted by C's inheritance (`{}`). (I'm not counting `<`/`>` as they have even more historical baggage as comparison operators)
Now of course we could use non-paired symbols even for paired situations, but I guess these symbol pairs look... right? Especially for situations where we're defining a "section" or "grouping" rather than a coherent block (such as a string)
As for why tokens are overloaded--you just run out of good tokens if you don't reuse them. Consider the tokens '(' and '['. It's quite common to use '(' in the prefix context for grouping, and '(' in the infix context to mean a function call. How do you eliminate the overloading? You can make function calls use whitespace as an infix operator, but that creates a host of other problems. Also, overloading is useful for creating parallelism in the syntax. You might use '[' in the prefix context to signify literal arrays and '[' as an infix operator to signify array dereferencing. In that situation, overloading is synergestic.
Someone might be able to say with more certainty, but I believe this is covered by the formalism of "Context Free Grammars" versus "Context Sensitive Grammars"[1]. That is, a language is context free if you don't need information from elsewhere in the code to determine the meaning of a symbol.
There's a good discussion of what makes C context sensitive on Eli Bendersky's blog[2].
Edit:
Thinking about this some more, I'm realizing that this has little to do with the overloading of symbols like block delimiters, since these can be tokenized and parsed by a context free grammar fairly easily in an "overloaded" fashion.
Maybe what you're describing is related to the concept of "purely functional," or even some more vague notion of purity generally...
[1] http://en.wikipedia.org/wiki/Context-free_grammar
[2] http://eli.thegreenplace.net/2007/11/24/the-context-sensitiv...
Also ( means something different in a string, so in that sense evert programming language with strings are hard to parse locally.
Also note that ambiguity formally means that more than one parse trees can represent the same string.
Ruby has a stated design goal of making developers happy. As far as I'm aware, it hasn't been designed to be easily parsed.
I, as an end user (i.e. programmer), prefer it this way. If ease of parsing is important for you, maybe you should use something like LISP.
That does not mean they're opposite goals. Having parsing ambiguities means insufficient thought has been given to parsing, or the language has been defined as "as implemented" with an ad-hoc and organically grown parser (other examples of such case: Perl, PHP)
> I, as an end user (i.e. programmer), prefer it this way.
You prefer that languages have broken, inane or completely missing grammars? So you like PHP even more than Ruby?
Of course they're not opposite, but you have to choose what to focus on.
> You prefer that languages have broken, inane or completely missing grammars? So you like PHP even more than Ruby?
Sorry if it wasn't clear, I was comparing easy parsing to developer happiness. That is, I prefer a language tries to make me happy rather than be easy to parse. (this goes back to your point above)
This is the key problem with DWIM interfaces in general. When it does what you mean, it's so nice. But sometimes you're stuck with ambiguity and lack of a precise means of expression; then you have to jump through hoops to push the 'intuitive' thing out of your way. (Curiously, both MS Word and Perl, of all things, manifest this problem.)
Whether it often is the case isn't relevant. It may be possible, or even necessary, to make a language hard to parse in order to make it better for the programmer.
Otherwise, by your logic LISP is by definition the best programming language. That maybe be true, but I'm not sure if you would follow your own logic to it's logical conclusion.
Well, that's exactly right, it is the best! Not sure for the GP but I would follow this logic to this conclusion happily :)
Um, er... Sorry, I just recently wrote my first program in Lisp (in Racket exactly) that was something more than a few tens of lines of code and am very happy because of this and I couldn't resist posting this here :)
I like Ruby too, it's actually my favorite language because it's so easy to do metaprogramming, but sometimes I wish it were clearer what the execution will be even if that comes at the expense of some clarity elsewhere.
The problem is that this is a statement which does not make sense. You can have both. And as nine_k notes, a language which can also be harder to read: an ambiguous syntax is also ambiguous for a human reader.
Is that a better way of wording it?
It is possible (and often correlated) to maximize developer happiness with an easy to parse syntax.
Also C, Java, really just about every language in common usage.
That right there is why I disagree with your point. I'm far happier programming in ruby than java, even though there is more ambiguity to the syntax.
Also, you could have structured the "supreme readable ruby code" much more cleanly:
Admittedly I could have come up with a better code example :) I wanted to show code transforms a collect a couple of times.
While it takes longer to read the Java version, it is unambiguous what it does. With Ruby (as nice as the language is) that is not always the case, at least for me.
(Pardon the tabbing, I don't have that much time to waste on uneducated comments like the above)
btw, I've added a sort to mine, what would that look like for yours?
https://gist.github.com/jaydonnell/4735159
Edit: I see you don't have the courage to use your real account.
Since it seems like you're talking about visual activity now instead of visual clarity, I agree that Java will be more "hard to read" under your definition. But aside from the two lines for the class declaration & method declaration and the other two for the ending brackets, there really isn't much bloat.
All that you have to implement for a simple numerical sort is some logic if a > b return 1 else if a == b return 0 else return -1.
Iterable<String> s = Splitter.on(" ").split("Hello World");
Multiset<String> counts = HashMultiSet.create(s);
Multiset<String> sorted = Multisets.copyHightestCountFirst(counts);
TreeHashSet.create(Splitter.on(" ").split("Hello World"))
Show the java code that does the same thing and it will be clear that the ruby is more readable.
String[] sents = {"the quick", "the slow", "the blue"};
Iterable<String> s = Splitter.on(" ").split(Joiner.on(" ").join(sents));The parser is context free-- LL(1), actually.
The lexer maintains one extra stack to track indentations, meaning it's more of a PDA than a DFA, but the actual complication is mild.
That alone does not make it a nice language, of course.
I can only assume that it's lying its pants off, as I noted in an other subthread `(a) - (b)` can't be parsed (to an AST) without knowing the identity of `a` in the current scope: if it's a type the expression is a cast of `-(b)` to `a`, if it's a value it's a subtraction of `(b)` from `(a)`.
By "it can't be parsed to an AST" I meant "it can't be parsed to a useful AST used to run or generate code" on its own, it needs to be disambiguated through contextual information before anything can be done with the prospective subtree. Sorry for the lack of clarity.
> It's called an ambiguous grammar, which can still be context free.
The only way to disambiguate is to provide expression context (namely visible name bindings at this point), it's essentially the same problem Eli Bendersky described when talking about C grammar's context-sensitivity: http://eli.thegreenplace.net/2007/11/24/the-context-sensitiv...
http://www.rubyinside.com/using-ripper-to-see-how-ruby-is-pa...
-- Tom Duff, "Rc — A Shell for Plan 9 and UNIX Systems"[1]
[1] http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.41....
Language ambiguity due to context is pretty common. The way to deal with them is with nested scope symbol tables. And determine the semantic of a symbol usage based on previous declaration of the symbol, tracked in the symbol tables.
In the article's example, x + 3, it confuses the stages of the lexer and the parser. The lexer only knows x as a symbol. Its output is symbol('x') op('+') num(3). It doesn't know it's a function call or a variable reference. It is the parser's job to figure out the semantic of x based on context and to build the AST.
In this case if x has been declared as a variable before, its symbol and type info are recorded in the symbol table. When x + 3 is encountered, it's a simple lookup on the symbol table to see if it's a declared variable and generate the AST node with op('+', var('x'), num(3)).
If x has been declared as function in the symbol table, the lookup will generate the funcall AST node.
For special declaration rule like usage before declaration (as in Ruby), the lack of definition in the symbol table can be defaulted to a funcall.
If anyone's interested, this definition of Ruby 1.4 is pretty good: http://www.cse.buffalo.edu/~regan/cse305/RubyBNF.pdf
The question is whether what it defines corresponds to Ruby. It's easy enough to define an unambiguous subset of the language and declare you're done, but it's irrelevant if the grammar does not match what the language actually is.
That said, 1.8.7 still has these issues. You absolutely _can_ parse Ruby, that doesn't mean it's not incredibly difficult.