18 ms·
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 significa
by joe_the_user 10y ago
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 https://www.youtube.com/watch?v=ZzsK8Am6dKU
- ci5er 10y agoIt'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?
- FeepingCreature 10y agoI don't understand why people use FSMs or parser tools. I wrote the parser for my script language, jerboa ( https://github.com/FeepingCreature/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?
- wolfgke 10y ago> 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.
- jblow 10y agoExcept 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.
- wolfgke 10y agoIf 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.
- SamReidHughes 10y agoHand-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.
- jblow 10y agoIf 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.
- programLyrique 10y agoWhen you add unicode, it can become more complicated (or rather, cumbersome)...
- jblow 10y agoWell, 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.
- ci5er 10y agoWhat 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?
- joe_the_user 10y agoSure, 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.
- ci5er 10y agoFair 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).
- ohyes 10y agoWhich is funny because a recursive descent parser is actually very simple.
- userbinator 10y agoI 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-parser-with-precedence http://stackoverflow.com/questions/28256/equation-expression...
- joe_the_user 10y agoYes, 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.