News for hackers. Stuff that matters.
Re:On the Complexity and Performance of Parsing with Derivat... by joe_the_user on Saturday June 25, 2016 @12:46PM (#11976922)
Yes,

I'm scanning the original video introducing derivatives[1].

The need for parsing is ubiquitous yet, Never mind CS students, in my experiences a significant number of professional programmers cannot create a basic parser either from scratch or from a standard tool.

Edit: The video picks on hand-written c parser. Such a thing isn't necessarily bad IF it's in a formally derived recursive descent parser. But just ad-hoc parsing without being informed by a grammar is pretty much waiting for disaster.

[1] https://www.youtube.com/watch?v=ZzsK8Am6dKU

Re:On the Complexity and Performance of Parsing with Derivat... by ci5er on Saturday June 25, 2016 @12:50PM (#11976940)
It's a pain and not something you really keep touching again and again once you've got it baked.

I've done it a number of times and I've had to relearn ANTLR each time (or fall back to flex/yacc or perl if I'm feeling grungy or go commando with a hand-crafted FSM if I'm on an odd machine architecture)

Is this something that you'd expect people who code even daily to be able to whip out without looking at a man page?

Re:On the Complexity and Performance of Parsing with Derivat... by joe_the_user on Saturday June 25, 2016 @01:01PM (#11976985)
Sure,

All of the parser-generator tools are really opaque and not something that can be easily used for simple things. On the other hand, recursive descent parsers are something that can be whipped easily if you have a little project. And the problem is that a lot programmers both can't produce a recursive descent parser AND don't know when their problem domain is moving into a place where such a thing is needed.

Re:On the Complexity and Performance of Parsing with Derivat... by ci5er on Saturday June 25, 2016 @01:14PM (#11977046)
Fair enough. They're not rocket science conceptually - but I have to relearn the tools each time. Not a huge deal - a couple of hours - but I was thinking that you were claiming I needed to have it down as cold as when I got out of CS 202 (or whatever that thing was).
Re:On the Complexity and Performance of Parsing with Derivat... by FeepingCreature on Saturday June 25, 2016 @12:55PM (#11976958)
I don't understand why people use FSMs or parser tools.

I wrote the parser for my script language, jerboa ( https://github.com/FeepingCreature/jerboa ) over a few days; it's (I thought) entirely standard recursive descent single-pass. This is how I've always written parsers. Where would you even use FSMs for parsers?

Re:On the Complexity and Performance of Parsing with Derivat... by wolfgke on Saturday June 25, 2016 @01:01PM (#11976987)
> Where would you use FSMs for parsers?

For the lexing (lexical analysis) stage of the parser. I know that the alternative to using a lexer (for which the tokens are specified by regular languages, thus lexed by FSMs) is to use so-called scannerless parsing (this is possible since every regular-language is context-free, thus the tokens can also be specified by the original context-free grammar). But using this alternative is usually much more painful since you usually want the grammar to have a nice property that allows linear-time parsing and a unique parse tree. LR(k), LL(k) etc. are such properties. Such properties are much more difficult to ensure for scannerless parsing.

Re:On the Complexity and Performance of Parsing with Derivat... by jblow on Saturday June 25, 2016 @01:07PM (#11977023)
Except no, lexing is trivial; it is by far the easiest part of writing a compiler. You don't need anything fancy, you just type in the code.
Re:On the Complexity and Performance of Parsing with Derivat... by programLyrique on Saturday June 25, 2016 @01:45PM (#11977197)
When you add unicode, it can become more complicated (or rather, cumbersome)...
Re:On the Complexity and Performance of Parsing with Derivat... by jblow on Saturday June 25, 2016 @05:56PM (#11978184)
Well, you just need to call unicode_next_character all the time instead of saying s++, similarly for whitespace, similarly for asking whether a character can initiate or continue an identifier, etc. It does not change the basic nature of the task at all.
Re:On the Complexity and Performance of Parsing with Derivat... by programLyrique on Sunday June 26, 2016 @04:38AM (#11979908)
Sure, but if you are using a language without support for unicode, and you don't use a dedicated library (which would be already using a kind of lexer, wouldn't it?), you have also to parse these unicode characters yourself.
Re:On the Complexity and Performance of Parsing with Derivat... by yoklov on Sunday June 26, 2016 @06:09PM (#11983017)
A unicode_next_character function is very simple to write regardless of unicode support in your language.

I usually write it as a small (256 byte) lookup table where each entry tells you how many characters to skip next. If you don't use a lookup table, its 4 single-line `if` statements (and if you do it's a one liner, plus however many lines the table takes).

Re:On the Complexity and Performance of Parsing with Derivat... by jblow on Monday June 27, 2016 @02:41AM (#11984514)
There's free source code for basic Unicode operations all over the internet.
Re:On the Complexity and Performance of Parsing with Derivat... by nulltype on Sunday June 26, 2016 @12:45AM (#11979410)
Here's a video of Rob Pike, developer of Go, talking about a lexer he built for the Go text/template package:

https://www.youtube.com/watch?v=HxaD_trXwRE

It supports unicode.

Re:On the Complexity and Performance of Parsing with Derivat... by wolfgke on Saturday June 25, 2016 @01:13PM (#11977043)
If you want to write a lexer from scratch, this is IMHO not trivial. If you use a generator it is much easier, but so is also using a parser generator for the CFG parsing stage.
Re:On the Complexity and Performance of Parsing with Derivat... by jblow on Saturday June 25, 2016 @05:54PM (#11978173)
If you can't write a lexer by hand, just forget trying to write a compiler that does anything interesting, because the lexer is MUCH easier than any other part of the compiler.

There are a lot of reasons for this, but one of the basic ones is that the lexer does not need to interact in a complex way with the compiler's state. It is a relatively simple pipeline where characters go in one end and tokens come out the other.

Re:On the Complexity and Performance of Parsing with Derivat... by SamReidHughes on Saturday June 25, 2016 @01:38PM (#11977161)
Hand-rolling a lexer seems pretty trivial to me. The code writes itself. A generator is a tool whose limitations you have to work around, be it for a lexer or a parser.
Re:On the Complexity and Performance of Parsing with Derivat... by SamReidHughes on Saturday June 25, 2016 @02:26PM (#11977370)
The only actual increase in difficulty from scannerless parsing is having to janitor whether a function will always slurp up whitespace before it finishes. Linear-time is easy, questions of unique parse tree are irrelevant because the only ambiguity is who owns a piece of whitespace that gets discarded anyway.
Re:On the Complexity and Performance of Parsing with Derivat... by ci5er on Saturday June 25, 2016 @01:05PM (#11977009)
What wolfgke said. I (personally) use FSMs as my swiss-army chainsaw a lot. I realize that this isn't common practice, but I came from silicon, so what are ya gonna do?
Re:On the Complexity and Performance of Parsing with Derivat... by ohyes on Saturday June 25, 2016 @12:51PM (#11976942)
Which is funny because a recursive descent parser is actually very simple.
Re:On the Complexity and Performance of Parsing with Derivat... by userbinator on Saturday June 25, 2016 @01:18PM (#11977067)
I agree completely, but it seems a lot of others (unfortunately) don't, as this rather saddening link shows:

http://stackoverflow.com/questions/28256/equation-expression...

Re:On the Complexity and Performance of Parsing with Derivat... by joe_the_user on Saturday June 25, 2016 @01:18PM (#11977068)
Yes, the thing about the inability of a given programmer to produce a recursive descent parser is that it generally comes from an actual ignorance of a what an abstract language is rather than from a particular technical inability. Especially, coming from naive object orientation, a language seems like it should just be a thing, an "object" and so you should be able to define a "language object" and go from there. But actually an abstract language operates on a "whole other level" than the usual hierarchy of members and methods described in simple object-oriented design.

Anyway, hopefully the derivative idea is to have constructs kind-of like regular expressions but actually reflecting language-structure and able to general good and understandable parsers.