8 ms·

It's amazing that text parsing -- one of the first problems studied in CS -- is still such a difficult problem (conceptually). I look forward to the day when th

• 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 ago
    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?
    • FeepingCreature 10y ago
      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 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 ago
          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.
          • wolfgke 10y ago
            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.
            • SamReidHughes 10y ago
              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.
            • jblow 10y ago
              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.
    • joe_the_user 10y ago
      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.
      • ci5er 10y ago
        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).
  • ohyes 10y ago
    Which is funny because a recursive descent parser is actually very simple.
    • userbinator 10y ago
      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-parser-with-precedence http://stackoverflow.com/questions/28256/equation-expression...
    • joe_the_user 10y ago
      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.
• komaromy 10y ago
  With the vanishing of required compilers courses, I am unsure that this will ever be the case.
• userbinator 10y ago
  I look forward to the day when the average undergrad graduating with a computer science degree will be able to write a context-free-language parser from scratch in a few days. Does recursive-descent count? If so, I've come across material on the Internet suggesting that a simple arithmetic expression parser/evaluator is an assignment in some first and second-year CS courses, often covered at the same time as trees and tree-traversal. Of course, being taught and doing an assignment on something is not quite the same as really knowing, as according to some sources many of those graduates can barely manage FizzBuzz. On the other hand, recursive descent seems to be one of those techniques that everyone eventually manages to reinvent even if they've never been taught about it, as long as they're aware of recursion.
  • joe_the_user 10y ago
    I don't think it's true that a lot of people really reinvent recursive descent parsing. Or rather I think a lot more programmers who don't understand language concepts wind-up writing broken pieces of what could be a recursive descent parser. The programming piece of a recursive descent parser all easy - the tricky parts are having a language spec, operating on the language spec to get the appropriate normal forms (Chomsky and Greibach) and then turning the spec into a parser.
    • SamReidHughes 10y ago
      No, you don't need to know anything about normal forms to make a good parser.
      • mcguire 10y ago
        How do you handle those sorts of things?
        • SamReidHughes 10y ago
          Looking these things up, Chomsky normal form is clearly irrelevant, and Greibach normal form forces "progress" to be made. The equivalent of this is, let's say you hand-roll a parser and notice that it's recursing infinitely. Then you realize, "Durr, you bozo, you need to force it to consume something or it'll recurse forever without going anywhere!" And then you solve that problem by having it consume something first. For example, if you're parsing an expression a+b*c+d, and thanks to some naive thinking about left-associative operators, it recursively calls itself without consuming data. So you'll say, okay, first I need to chew off something that consumes data. Then -- what else can you do -- see if you've got an operator, and grow an expression from there. That's a well-contained situation that marches you straight into the right solution.
• jblow 10y ago
  Text parsing for programming languages is NOT a difficult problem. It is very easy actually, much easier than most academics would have you believe. What they are doing is trying to write theories and build conceptual systems about how to do things. That is their job. But when it comes to practical matters, the best route to take, as someone who wants to build a working compiler that gives good error messages and where the parser does not hamstring the rest of it, is to ignore almost all that stuff and just type the obvious code.
  • treeform 10y ago
    In jai, did you write the parser yourself or used a parser generator like yacc? In my toy languages I find writing my own parser more fun and not hard. I find it harder to make yacc do things such as indentation significance.
    • nulltype 10y ago
      I'm pretty sure he mentioned he wrote his own parser. https://twitter.com/jonathan_blow/status/734817293331357697 https://twitter.com/jonathan_blow/status/734817293331357697
      • jblow 10y ago
        Yes, it is hand-written. The parser is MUCH easier to build than the interesting/new parts of the compiler are. Lexing is the absolute easiest thing, then parsing is 2nd place.
  • zeroxfe 10y ago
    > Text parsing for programming languages is NOT a difficult problem. That depends entirely on 1) what grammar you're parsing, 2) what memory pressure you're in, 3) how fast you want to do it, and 4) how comprehensive you want the error handling. It's actually quite difficult to parse C++ on a low-memory embedded device without resorting to clever techniques.
    • 10y ago
• wyager 10y ago
  Can they not? I had at least two undergrad classes (Programming Languages and Automata Theory) that taught how to do efficient CFG parsing.
  • chubot 10y ago
    The problem is that the languages people actually use are NOT context free. C and C++ are known not to be context free, and (somewhat surprisingly to me) it's not clear that Java and Python are context-free either. I also bet that JavaScript's semicolon insertion rule makes it not context-free (perhaps among other things). http://trevorjim.com/parsing-not-solved/ http://trevorjim.com/parsing-not-solved/ Just because you use yacc doesn't mean it's context free. The entire design of yacc explicitly lets you break out of that paradigm -- i.e. with arbitrary semantic actions in a Turing-complete language (C). There is a fairly big gap between theory and practice. Even if parsing with derivatives were fast, or even it were LINEAR, it wouldn't really "solve" parsing in any meaningful sense. Because it's too weak to parse most real languages.
    • ThePhysicist 10y ago
      The Python grammar can be formulated in a context-free form (to my knowledge), except for the indentation rules that require access to a stack, albeit only in the preprocessor (which replaces the indentation with INDENT / DEDENT tokens). Another complication is that NEWLINE characters that occur inside parentheses are optional terminals, whereas outside they are relevant (this does not require a context to be parsed though, it just makes the tokenization step a bit more complex).
      • chubot 10y ago
        Yes, that is exactly what's mentioned here, on the same site that I linked: http://trevorjim.com/python-is-not-context-free/ http://trevorjim.com/python-is-not-context-free/ (Are you the author? :) ) Why does this matter? Because AFAICT the current best practice for implementing languages is to 1) prototype the language with a tool, then 2) throw that out and write the parser by hand. If you skip step 1, then it will be unclear what language you've defined (and it's not always obvious how to break up the procedures). If you skip step 2 and auto-generate your code instead, you typically don't have enough expressive power, and you have to hack around it (communication with globals, etc.) Tools and theory are focused excessively on CFGs (i.e. in this thread parsing with derivatives). Whereas real language always have non-context-free parts. Granted, Python is probably one of the most friendly and well-designed, and writing the lexer by hand and generating the parser works well there. I don't think that, in the case of Python, writing the parser by hand would have been a good idea.
• pavpanchekha 10y ago
  I've taught undergrads CKY in a half-hour, but only when limited to Chomsky-form grammars. This is still a general parsing algorithm, but the restriction is very annoying in practice. Turning a grammar into Chomsky form is quite annoying, too.
  • wolfgke 10y ago
    > Turning a grammar into Chomsky form is quite annoying, too. This can be done automatically.
    • pavpanchekha 10y ago
      Sure, but you haven't exactly taught undergrads how to parse arbitrary grammars until you teach them that automatic algorithm, too, and that algorithm is harder to teach than simple CKY.
• skybrian 10y ago
  Writing a parser by hand can be a bit repetitive, but it's actually not that bad with a bit of experience. Many production parsers are written by hand. Here's a good article about parsing expressions: http://journal.stuffwithstuff.com/2011/03/19/pratt-parsers-expression-parsing-made-easy/ http://journal.stuffwithstuff.com/2011/03/19/pratt-parsers-e... And my half-baked explanation which may not make sense unless you've already tried it: https://plus.google.com/+BrianSlesinsky/posts/hMr5NEnQcxC https://plus.google.com/+BrianSlesinsky/posts/hMr5NEnQcxC
• sklogic 10y ago
  Parsing is a solved problem. Any other research in this area is done out of curiosity, not necessity.