61–70 of 71 posts
Jeffrey Kegler's work on Marpa is pretty exciting, but hasn't got much traction (maybe due to the implementation languages: Perl and Knuth's Literate Programming). https://metacpan.org/pod/Marpa::R2#A-simple-calculator
"Marpa is available as a open-source library. It is written in C, and the C library can be used directly or via a Perl interface."
http://jeffreykegler.github.io/Ocean-of-Awareness-blog/indiv...
The XL programming language ( http://xlr.sf.net ) has a rather unique approach to parsing. There is a short article about it here: http://grenouille-bouillie.blogspot.fr/2010/06/xl-axioms-rec... . XL features 8 simple node types, 4 leafs (integer, real, text, name/symbol) and 4 inner nodes (infix, prefix, postfix and block). With that, you can use a rather standard looking syntax, yet have an inner parse tree structu…
Judging from the article, if you parsed "if 3", you'd get back out (prefix if 3) instead of an error, since `if` is just a regular prefix operator. So, presumably there's some sort of well-formedness checking that goes on after parsing? Does anyone know more? The website says very little.
Underneath, there is a rewrite operator, ->, that means to transform the shape on the left into the shape on the right.
The precise semantics are a tiny bit more complicated than that, but it iterates until there is no more transformation that applies. Some specific rewrites will be transformed into "opcodes" of the underlying machine model. So A+B with integers on each side will execute an addition (the inner representation of the transform is something like A+B -> opcode Add).
For more details, you can read http://xlr.sourceforge.net/sites/default/files/XLRef.pdf. I badly need to update it, it's out of date, I have a more recent version, but I need to learn the new way to connect to SourceForge.
Earlier quoted context omitted.
Yeah that puzzles me a bit too. Multifix operators are not more complicated than prefix/postfix/infix (well, only marginally). For instance, you can give each operator a left priority and a right priority and merge them when they meet with the same priority. Then `if x then y else z` would become (if/then/else x y z) or something like that. I think that's saner and easier to handle than what he does.
Yeah, that's what I was expecting too. And then XL could claim to have only five node types: integer, real, text, name, and multifix :-)
Something like [A,B,C,D] writes as:
Block with [] containing Infix , containing Symbol A Infix , containing Symbol B Infix , containing Symbol C Symbol D
So this allows me to represent multifix along with their expected syntax. I could also represent for example:
[A, B; C, D]
if A then B else C unless D
for A in B..C loop D
The last one is actually one of the for loop forms in XL
Earlier quoted context omitted.
Yeah, that's what I was expecting too. And then XL could claim to have only five node types: integer, real, text, name, and multifix :-)
In XL, a multifix is a combination of infix, prefix or postfix. Note that the various nodes exist only for the programmer's convenience, i.e. they represent a user-visible syntax. Internally, I could do with only a node with two children. Something like [A,B,C,D] writes as: Block with [] containing Infix , containing Symbol A Infix , containing Symbol B Infix , containing Symbol C Symbol D So this allows me to repres…
The advantage of supporting multifix directly is that you get a more convenient and less confusing representation. For instance, given "if A then B else C" why should I expect (else (then (if A) B) C) and not (if (then A (else B C))? It's not obvious, and both are unwieldy compared to a ternary operator like (if/then/else A B C).
It is nice to see someone summarizing this kind of information. However, really this is a continuation of the academic attitude toward parsers making them MUCH harder than they have to be. If you want to study grammars in an abstract sense, then think of them this way, and that's fine. If you want to build a parser for a programming language, don't use any of this stuff. Just write code to parse the language in a str…
ADDENDUM: In particular, the article mentions PEGs. Not in an unambiguously positive light, but nonetheless: do you count PEGs as being a useless overly academic tool?
The LANGSEC project has done (in my opinion) a pretty good job arguing that this behavior causes many security issues in software. Perhaps only to some extent for programming languages in general, but in particular for data format languages and network protocols. The issue is slightly mitigated for programming languages because they typically don't have many wildly varying parsers; but (programming) languages without clearly specified grammars certainly have had problems with this in the past.
Are you familiar with their work? Do you just disagree with their conclusions?
[LANGSEC]: http://langsec.org
Earlier quoted context omitted.
In XL, a multifix is a combination of infix, prefix or postfix. Note that the various nodes exist only for the programmer's convenience, i.e. they represent a user-visible syntax. Internally, I could do with only a node with two children. Something like [A,B,C,D] writes as: Block with [] containing Infix , containing Symbol A Infix , containing Symbol B Infix , containing Symbol C Symbol D So this allows me to repres…
Multifix is more general than a combination of infix, prefix and postfix, though. For instance, a [] block is a multifix operator, but you can't implement it as a combination. The advantage of supporting multifix directly is that you get a more convenient and less confusing representation. For instance, given "if A then B else C" why should I expect (else (then (if A) B) C) and not (if (then A (else B C))? It's not o…
It's not simpler. XL started with a multifix representation, see http://mozart-dev.sourceforge.net/notes.html. Switching to the current representation was a MAJOR simplification.
The current representation captures the way humans parse the code. Infix captures "A+B" or "A and B". Prefix captures "+3" or "sin x". Postfix captures "3!" or "3km". Block captures "[A]", "(A)", "{A}" or indentation. Since humans perceive a difference, you need to record that difference somewhere. XL records that structure in the parse tree itself, not on side data structures such as grammar tables.
This approach also enables multiple tree shapes that overlap. Consider the following XL program (I replaced asterisks with slashes because the asterisk means "italics" for HN):
A/B+C -> multiply_and_add A, B, C
A+B/C -> multiply_and_add B, C, A
A+B -> add A, B
A*B -> mul A, B
In that case, I can match a multifix operator like multiply_and_add without needing a representation that would exclude matching A+B or A/B in other scenarios. This is especially important if you have type constraints on the arguments, e.g.:
A:matrix/B:matrix+C:matrix -> ...
A:matrix/B:real+C:real -> ...
Those would be checked against X/Y+Z in the code, but if X, Y and Z are real numbers, they would not match.
If you want to try it by yourself, you can download Tao from http://www.taodyne.com/shop/dev/en/content/10-compare-versio.... Tao uses XL as the basis of its dynamic document description. There's a tutorial here: http://www.taodyne.com/presentation/tutorial-2.0.html. Please note that the XL implementation used in Tao has several limitations, notably with local functions and closures.
Earlier quoted context omitted.
Parsing Techniques by Dick Grune is THE bible for parsing.
It is a nice reference but you won't learn anything from that if you're a beginner. It's super heavy on theory and very light on implementation.
I learned a lot and PTAPG introduction specifically says that it avoids heavy theory. It has all algorithms required in very understandable presentation. It also says what this or that algorithm does to exploit that or this feature from grammar structure.
Earlier quoted context omitted.
Both are based in Bryan Ford's packrat (PEG is Ford's too). OMeta is more like PEGTL in that it's a set of facilities/library at a highish level, more than a particular grammar system (they're all packrat parsers). http://bford.info/packrat/ It's all about descent parsing and memoisation (thus the name).
pegtl is not actually a packrat parser. Not all PEGs and absolutely not all recursive descent parsers are packrats. And actually, my experience with packrat parsers (mostly in ruby) in other languages has been that they actually slow things down on moderately or more complex grammars by massively exploding memory use and thus allocation pressures. Turning it off can make it faster , especially on complex grammars. It…
Earlier quoted context omitted.
One issue with PEG's (and other parsers) is that it doesn't address (unbounded) count fields (or bounded count fields in an elegant manner) or offsets. This means a pure PEG can't express e.g. PDF or ZIP files. To address this, we built a PEG-based parser generator with a few new features, Nail (paper at OSDI 14, github.com/jbangert/nail)
Another issue is that it uses at least the same memory as the the input. Not that I'm a PEG expert, but it also basically feels like a formalised recursive decent parser. Nothing wrong with that, but changing the grammar afterwards can have a rippling effect and require much more work than with a traditional LALR parser.
Earlier quoted context omitted.
Multifix is more general than a combination of infix, prefix and postfix, though. For instance, a [] block is a multifix operator, but you can't implement it as a combination. The advantage of supporting multifix directly is that you get a more convenient and less confusing representation. For instance, given "if A then B else C" why should I expect (else (then (if A) B) C) and not (if (then A (else B C))? It's not o…
Multifix is not more general than combinations of the 8 node types in XL, only more powerful than a combination of some subset. It's not simpler. XL started with a multifix representation, see http://mozart-dev.sourceforge.net/notes.html . Switching to the current representation was a MAJOR simplification. The current representation captures the way humans parse the code. Infix captures "A+B" or "A and B". Prefix cap…
Now, I'm not sure how you implemented multifix, but a good general implementation for it is not immediately obvious, so I suspect you simply used an algorithm that's more convoluted than necessary and made you overestimate the scheme's actual complexity. Implemented properly, though, it's ridiculously simple. To demonstrate, I have hacked together a JavaScript version here (sorry, I didn't get around to commenting the code yet):
http://jsfiddle.net/ed37wy5k/2/
The core of the parser is the oparse function, which clocks in at 32 lines of code. Along with a basic tokenizer, order function, evaluator and some fancy display code, the whole thing is barely over 200 LOC. I dug around for XL's source and from what I can tell, what you have is not simpler than this.
I also never suggested making multifix operators like multiply_and_add. Multifix is for operators which are inherently ternary, quaternary and so forth. For instance, when I see "a ? b : c" I don't parse it as prefix, postfix or binary infix, I parse it as ternary.