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

81–85 of 85 posts

Re: Just Write the Parser

#81

Post by chrisseaton »

wrs wrote: post #80
chrisseaton wrote: post #74

Earlier quoted context omitted.

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.

But there are no ambiguities in recursive descent! They won't discover them because... they don't exist! It's literally impossible.

> As an example too well-known to actually occur, suppose you parse...

Great example - and the good thing about recursive descent means it's impossible to write this ambiguously - you must prefer one or the other.

> It’s not ambiguous

Correct. So why are you telling me the problems of ambiguity?

> but your users won’t be happy when they find out the unambiguous rule

Why won't they be happy? You can tell them exactly how their code is going to be parsed. I thought ambiguities was bad but now you're complaining about ambiguity as well?!

Re: Just Write the Parser

#82

Post by wrs »

chrisseaton wrote: post #81
wrs wrote: post #80

Earlier quoted context omitted.

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. But there are no ambiguities in recursive descent! They won't discover them because... they don't exist! It's literally impossible. > As an example too well-known to actually occur, suppose you parse... Great example - and the good thing about recursive descent means it's impossible to write this ambiguously…

We seem to be talking past each other. :) Of course there are no ambiguities in any parser (unless it returns multiple parses, which would hardly be practical). But that’s almost always because the designer had to resolve some ambiguities present in the grammar.

The question is, did the designer resolve them deliberately or accidentally? And were they resolved in an ergonomic way?

The grammar fragment “expr :: IF expr THEN expr ELSE expr” is ambiguous. If I write a statement like the example, I expect (from 60 years of language tradition and simple ergonomics) a language author to choose to resolve that ambiguity by associating an ELSE with the nearest IF. Telling your puzzled users “it’s not ambiguous, it always goes with the farthest IF!” isn’t going to make them happier. It also won’t work to say “well, + has higher precedence than /, but that’s OK, it always does that”. Those are just bugs in the language design caused by a bad resolution of ambiguity.

If you use a tool to flag the ambiguities in your grammar, then you can be sure all the resolutions in your parser are deliberate and not accidental.

Re: Just Write the Parser

#83

Post by samatman »

tomp wrote: post #75
samatman wrote: post #73

Earlier quoted context omitted.

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 PE…

It's okay that you aren't familiar with PEGs. I am familiar with PEGs, and so I know just by reading that, which way the ambiguity resolves. So for me, a human reader, there is no obvious ambiguity.

It's like saying there's an ambiguity in "not a and b". Sure, if you don't know the precedence assigned to 'not' and 'and' in your language. But you're supposed to learn those things.

Your not knowing how PEGs work is a weak argument against using them.

Re: Just Write the Parser

#84

Post by chrisseaton »

wrs wrote: post #82
chrisseaton wrote: post #81

Earlier quoted context omitted.

> The result is often that one of your users will discover the ambiguity instead, and then it may be too late. But there are no ambiguities in recursive descent! They won't discover them because... they don't exist! It's literally impossible. > As an example too well-known to actually occur, suppose you parse... Great example - and the good thing about recursive descent means it's impossible to write this ambiguously…

We seem to be talking past each other. :) Of course there are no ambiguities in any parser (unless it returns multiple parses, which would hardly be practical). But that’s almost always because the designer had to resolve some ambiguities present in the grammar . The question is, did the designer resolve them deliberately or accidentally? And were they resolved in an ergonomic way? The grammar fragment “expr :: IF ex…

> But that’s almost always because the designer had to resolve some ambiguities present in the grammar.

Not if they started with a grammar that didn't have any ambiguity in the first place.

I think you're coming from the angle that you always start with a CFG, resolve ambiguity, then write a parser.

Imagine that I never write a CFG for my language. No CFG exists! Instead - I start by writing a PEG, and then I write a recursive descent parser from that. At no point in this process have I had to resolve ambiguity. I didn't start with an ambiguous CFG and then write a PEG from it. I started with a PEG. It's never been ambiguous, and never will be ambiguous. There's no ambiguity.

> The grammar fragment “expr :: IF expr THEN expr ELSE expr” is ambiguous.

Right.... but I wouldn't write that because I'm not starting with a CFG I'm starting with a PEG.

> Telling your puzzled users “it’s not ambiguous, it always goes with the farthest IF!” isn’t going to make them happier.

I can't understand this - if I give them a simple well-defined rule that tells them what the code means they'll be happy. What do you think they'd want instead? No rule? A badly defined rule?

Re: Just Write the Parser

#85

Post by yencabulator »

wrs wrote: post #80
chrisseaton wrote: post #74

Earlier quoted context omitted.

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 language your parser parses may not be the language you had in mind.

This can happen even if you write a formal specification.

Post reply on HN