3 ms·
> Lisp is the easiest language to parse that I've ever seen, managed to write a parser by hand. I've written a dozen or so parsers for different languages by h
by lolinder 3y ago
> Lisp is the easiest language to parse that I've ever seen, managed to write a parser by hand.
I've written a dozen or so parsers for different languages by hand: the parser is easy regardless of the syntax you choose. The complicated bit is always compilation/interpretation.
The biggest value I see to using S-expressions isn't the time saved in writing a parser, it's reducing the amount of bikeshedding you'll be tempted to do fiddling with syntax.
- matheusmoreira 3y agoAren't languages like C notoriously difficult to parse? I've read that they're actually context sensitive. IIRC much of Go's syntax was designed to avoid parsing complexity.
- shaftoe444 3y agoSee the clockwise/spiral rule!
- jstimpfle 3y agoType syntax started pretty easy to parse, basically just parse a C expression. It became more complex and inconsistent later (when for example types for function parameters were added), but IIRC the clockwise/spiral rule is nothing like the idea behind the syntax. I think it is too complicated / not getting the gist of it.
- kazinator 3y agoI suspect that the interpretation of C cannot be specified in a brief page of C code. For one thing, the language doesn't supply the data structures for representing any aspec of itself; the code will have to invent those: declarations, definitions, statements, types. Then handle a ton of cases. It will not be obvious that what the C code is doing is C interpretation, because all those data structures don't resemble the C syntax. The Lisp meta-circular interpreter side-steps that; the issue is settled elsewhere. It exists against a backdrop where the easy correspondence between the printed syntax and the data structure being handled by the interpreter is taken for granted. The C would need the same kind of backdrop; and that would be a lot of documentation.
- lifthrasiir 3y ago> Aren't languages like C notoriously difficult to parse? I've read that they're actually context sensitive. All programming languages with identifiers are context-sensitive if you put well-formedness into the grammar. C is not exactly difficult to parse, rather it just needs some specific approach compared to most other languages. The biggest (and technically the only [1]) ambiguity is a confusion between type-specifier and primary-expression, which is a roundabout way to say that `(A) * B` is either a multiplication or a dereference-then-cast expression depending on what `A` is in the current scope. But it also has a typical solution that works for most parsers: parser keeps a stack of scopes with contained identifiers, and lexer will distinguish type identifiers from other identifiers with that information. This approach is so popular that even has a name "semantic feedback". [1] As an example, the notorious pointer and array declaration syntax is actually an unambiguous context-free grammar. It is notorious only because we humans can't easily read one. > IIRC much of Go's syntax was designed to avoid parsing complexity. Go's semantics (in particular, name resolution and module system) was designed to avoid complexity. Its syntax is quite normal, modulo personal and subjective bits which all languages have. I can't see any particular mention of syntax decision to performance in the initial spec document [2]. [2] https://github.com/golang/go/blob/18c5b488a3b2e218c0e0cf2a7d4820d9da93a554/doc/go_spec https://github.com/golang/go/blob/18c5b488a3b2e218c0e0cf2a7d...
- jstimpfle 3y agoFor the context sensitive part, all you need is a symbol table to check which names are for types. I haven't actually done it but I don't think it is hard. The real problem is the preprocessor, it's very hard to implement, and implement in a standards-compliant way. (haven't finished one either, but everybody says so). And without preprocessor and proper include processing, you simply can't parse correctly because you lack the context of which types are defined (besides missing preprocessor symbols). Another problem that comes with that is that you always have to parse everything from beginning to end -- including the include files, which can easily be 10s or 100s of thousands of lines of code. I haven't seen a real performant and always correct parser for C IDEs, not sure if one exists.
- kazinator 3y agoThat rings untrue in the face of how John MacCarthy specified Lisp interpretation, on paper, in Lisp itself, quite briefly, and didn't even suspect it would be executable. Then Steve Russel comes along, and bootstraps it by hand-translating it to code.