Beefy Boxes and Bandwidth Generously Provided by pair Networks
The stupid question is the question not asked

Re: Perl Cannot Be Parsed: A Formal Proof

by Errto (Vicar)
on Jan 22, 2008 at 18:20 UTC ( #663651=note: print w/replies, xml ) Need Help??

in reply to Perl Cannot Be Parsed: A Formal Proof

Just wondering: does this same idea apply to any language that allows constructs within the code itself to affect the syntactic structure of that code? Take, for example, the following theoretical Haskell expression:

foo =+= bar //|/ baz =+= qux
The parsing of this expression depends on the relative precedence of the two operators and possibily, but not necessarily, on the associativity of =+= It may also result in an error, if //|/ has higher precedence and =+= is declared as non-associative.

However, the parsing of this does not depend on executing any code in the sense that the OP means, I think. That is, there must be a static declaration somewhere else in the code that says what the properties of these two operators should be. It need not lexically precede the usage, but it has to appear somewhere in the relevant scope, and it cannot be dynamically generated in any way. How would that fit in?

Replies are listed 'Best First'.
Re^2: Perl Cannot Be Parsed: A Formal Proof
by BrowserUk (Pope) on Jan 22, 2008 at 19:09 UTC

    As with Perl, you cannot make sense of an individual source file without having already seen its dependancies.

    And, if you are correct about Haskell allowing use before definition (which I didn't think it did but...), then multiple passes may be required.

    Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.
    "Science is about questioning the status quo. Questioning authority".
    In the absence of evidence, opinion is indistinguishable from prejudice.
Re^2: Perl Cannot Be Parsed: A Formal Proof
by Anonymous Monk on Aug 25, 2009 at 04:28 UTC

    Correctly parsing a Haskell file requires parsing its dependencies, but it doesn't require running any Haskell code, since infix declarations are quite static.

    What it does mean is that to parse Haskell, you need to figure out the imports and infix declarations before actually parsing expressions. That's not very hard to do. You could, for example, initially parse expressions just into either lists of identifiers or rose trees regardless of precedence. Once you have the AST for a source file, it's easy to see the declarations that you need, and then use the information to fix up the expressions based on precedence.

Log In?

What's my password?
Create A New User
Node Status?
node history
Node Type: note [id://663651]
and all is quiet...

How do I use this? | Other CB clients
Other Users?
Others musing on the Monastery: (4)
As of 2017-02-27 03:31 GMT
Find Nodes?
    Voting Booth?
    Before electricity was invented, what was the Electric Eel called?

    Results (376 votes). Check out past polls.