Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Just Write the Parser

tiarkrompf.github.io

Post reply on HN
Print view View original

71–80 of 85 posts

Re: Just Write the Parser

#71

Post by sleavey »

lifthrasiir wrote: post #57
eyelidlessness wrote: post #30

Considering that something as simple and limited as JSON has been a source of security vulnerabilities from ambiguities in the spec, thanks but nope. Declarative definitions of a grammar help identify those ambiguities... and if the grammar is defined separately from its interpretation, it opens the door to invisible ambiguities that can become another vector for vulnerabilities. Unless you have provable implementati…

Spec ambiguities of JSON mostly come from the insufficient description of data model and well-formedness and not from the syntax itself. Say, to this day (including RFC 8259) duplicate keys from the JSON object are not explicitly forbidden, even though most applications require that. Probably the only issue arisen from the JSON syntax proper would be the treatment of line and paragraph separators.

And my number one gripe, that you can't add a trailing comma to the last list item. Very annoying when streaming JSON data.

Re: Just Write the Parser

#72

Post by wrs »

chrisseaton wrote: post #63
wrs wrote: post #16

One reason to use a parser generator for a new language is that it will tell you that your language is inherently ambiguous or otherwise broken in a way you didn’t realize. A hand-coded parser tends to just codify your bad assumptions. It can actually be a good idea to maintain a YACC (or other) grammar for your language just to run the tool as a kind of “grammar linter”, even if you’re going to write the parser by h…

If you define your language using a recursive descent parser then it can’t be ambiguous.

Yes, exactly — that means you’re resolving ambiguities whether or not you’re aware of them (“codify your bad assumptions”).

Re: Just Write the Parser

#73

Post by samatman »

tomp wrote: post #60
samatman wrote: post #42

Earlier quoted context omitted.

I firmly disagree about the value of PEGs (and hence combinators) as a formalism that's ambiguous or hard to reason about. PEGs are as well-specified as CFGs, they just work in a different way. One of the strengths of PEGs is that they're never ambiguous. That does mean that order of alternates is important, and sometimes you do have to fiddle with that order when translating something like ABNF. But what you get in…

"PEGs are never ambiguous" is equivalent to solving a problem by proclaiming the wrong solution to be correct. In that sense, LALR parser generators (e.g. yacc) are also never ambiguous, because even if your grammar is ambiguous in the formal sense, yacc will produce a working parser with well-defined resolution of conflicts... But the reality is, E = E `+` E is intrinsically ambiguous, no matter how you want to spin…

I don't agree, as I've said, because PEG is a declarative formalism, and LALR is a parsing strategy. GLL implemented with graph-structured stacks can and will produce a parse forest for an ambiguous grammar, LALR will manifest one of those parses for the same grammar.

To lean on that means you have hidden information: your grammar is BNF + LALR, or BNF + GLL, not just BNF. PEGs, by contrast, are always PEGs. What you see is what you get.

A grammar in PEG format will always give you one parse, and which parse is predictable. If you want a different parse, you have to rewrite it. Indeed, as I'm sure you know, your example grammar isn't valid in the original PEG formalism, which prohibits immediate left recursion. Automatic rewrites into an intermediate rule are the leading method of allowing it.

Ambiguity is a well-defined concept in grammars, and PEGs aren't.

I've noticed that a lot of CFG enthusiasts don't like this about PEGs. They consider it inelegant, unprincipled. Some of that is aesthetic, some is unfamiliarity, and some is sunk cost: none of it actually engages with the formal expressive power of PEGs, nor their ergonomics as a practical tool for development.

Re: Just Write the Parser

#74

Post by chrisseaton »

wrs wrote: post #72
chrisseaton wrote: post #63

Earlier quoted context omitted.

If you define your language using a recursive descent parser then it can’t be ambiguous.

Yes, exactly — that means you’re resolving ambiguities whether or not you’re aware of them (“codify your bad assumptions”).

You're not aware of them... because they never exist. A language specified by a recursive descent parser is never ambiguous in the first place. There's nothing to resolve.

I don't know where 'codify your bad assumptions' comes into it? What assumptions? How are they codified without you knowing?

Re: Just Write the Parser

#75

Post by tomp »

samatman wrote: post #73
tomp wrote: post #60

Earlier quoted context omitted.

"PEGs are never ambiguous" is equivalent to solving a problem by proclaiming the wrong solution to be correct. In that sense, LALR parser generators (e.g. yacc) are also never ambiguous, because even if your grammar is ambiguous in the formal sense, yacc will produce a working parser with well-defined resolution of conflicts... But the reality is, E = E `+` E is intrinsically ambiguous, no matter how you want to spin…

I don't agree, as I've said, because PEG is a declarative formalism, and LALR is a parsing strategy. GLL implemented with graph-structured stacks can and will produce a parse forest for an ambiguous grammar, LALR will manifest one of those parses for the same grammar . To lean on that means you have hidden information: your grammar is BNF + LALR, or BNF + GLL, not just BNF. PEGs, by contrast, are always PEGs. What yo…

Sure, I guess you're right, if you consider formal grammars as existing in their own abstract bubble removed from our reality.

I, on the other hand, am primarily interested in using grammars to parse programming languages, which are essentially a human form of communication (computers could use bitcode or lisp-style ASTs, no need for syntax).

I'm not an expert on PEGs, so this is copy-pasted from Wikipedia page on PEGs, I hope it's valid - the classical dangling else ambiguity.

     S ← 'if' C 'then' S 'else' S / 'if' C 'then' S
Now, there is an obvious ambiguity here, for a human reader (mediated, of course, by tabs). If you're using a formalism that wishes that ambiguity away, it just means that the formalism is a non-ideal one. What I like about LALR parser generators is, that they will explicitly alert you of this kind of human-level ambiguities.

Re: Just Write the Parser

#76

Post by leonliang »

As a previous student in Professor Rompf's compiler class, I had the best learning experience while writing the parser for a Scala-like language. The parser logic has since influenced not only how I code, also how I think.

Re: Just Write the Parser

#77

Post by WorldMaker »

UK-Al05 wrote: post #67
thequux wrote: post #38

Earlier quoted context omitted.

Most parser combinator DSLs use PEGs to parse, which don't actually prevent ambiguity, but instead hide it. I strongly recommend using something that compiles your declarative grammar into LL(k) or LALR(k)

Do they hide or do they just apply order to choices. Making it impossible to be ambiguous compared to the CFG definition? It's only sweeping under the rug, if you look at PEG under CFG rules. PEG is not CFG. I think practice of writing industrial software that is better.

I do sometimes wonder if a lot of these arguments themselves would be less ambiguous if PEGs (or some other name of them) were formally added to Chomsky's Hierarchy of Languages between Regular Languages and the languages expressed by CFGs. Though I think it would take someone with a much more rigorous math background than myself to make the case formal enough to get it accepted.

(If it helps, and it may be a red herring, the dualism between PEGs and Parser Combinators has me thinking it's a Category Theory related "step" in the hierarchy. "Deterministic Monadic Compositions" in a reflection of DFA/NFA duals to Regular Languages might imply "Monadic Languages" as a possible name? Again, my math background is definitely not formal enough here to make actual suggestions, but maybe it sparks an idea for someone else.)

Re: Just Write the Parser

#78

Post by tiarkrompf »

musicale wrote: post #51
musicale wrote: post #35

Earlier quoted context omitted.

What's the best way to handle unary "-" and other unary operators? I'd like to be able to write expressions like "-2^-(2+2)" or "a cos b + a sin b". For "-2^-(2+2)" note that exponentiation has higher precedence than negation.

Thanks for the other replies, but I was asking the original author for a suggestion using the presented framework, rather than an alternate algorithm or approach from someone else. As presented, the approach didn't seem to handle unary operators. I probably should have noted that I am already familiar with Pratt parsing, which seems like something that isn't actually brain-dead simple and obvious in the same way (whi…

Great question! Unary operators are really simple to add: you just look for the operator symbol first thing at the right level of precedence. Same idea as "if (peek == '(') ..." for parentheses, but outside the code that deals with '*' and '^' (if you want those to bind more strongly).

Re: Just Write the Parser

#79

Post by swyx »

newlikeice wrote: post #70
swyx wrote: post #66

Earlier quoted context omitted.

what is "recursive decent"?

man can dig hole. while digging one hole he finds two holes. he Diggs the one hole till he finds the bottom. climbs up to where he found the two the proceeds down the other hole. till he finds two more holes and then digs to the bottom of the first hole he finds until he hits bottom there. he descends until he hits bottom or digs through the earth. one hole at a time. the digging is just the way your language constru…

ah. i was thrown off by the typo. i thought you were complimenting their decency.

Re: Just Write the Parser

#80

Post by wrs »

chrisseaton wrote: post #74
wrs wrote: post #72

Earlier quoted context omitted.

Yes, exactly — that means you’re resolving ambiguities whether or not you’re aware of them (“codify your bad assumptions”).

You're not aware of them... because they never exist. A language specified by a recursive descent parser is never ambiguous in the first place. There's nothing to resolve. I don't know where 'codify your bad assumptions' comes into it? What assumptions? How are they codified without you knowing?

The language your parser parses may not be the language you had in mind. Indeed, the language you had in mind may not actually exist. It’s easy to operate based only on examples, and think you know what your language is, when in fact there are cases you didn’t consider. Your parser will resolve the ambiguity (because it has to), but if the tool had told you about the ambiguity, you might have redesigned the language. The result is often that one of your users will discover the ambiguity instead, and then it may be too late.

As an example too well-known to actually occur, suppose you parse “if x then if y then x else z” with the else clause associated to the first if statement, because that’s just how you happened to write the parser. It’s not ambiguous, but your users won’t be happy when they find out the unambiguous rule.

Post reply on HN