5 ms·

Hmm, I wrote a VHDL (a superset of ADA used for hardware design) front end using bison and flex. That's a serious language. Regarding error messages, if one i

by hasbot 7y ago

Hmm, I wrote a VHDL (a superset of ADA used for hardware design) front end using bison and flex. That's a serious language. Regarding error messages, if one implements the grammar as specified by the language spec, yes, confusing and useless error messages will result. That's because the language spec grammar includes restrictions based on semantics. To get good error messages, one has to remove/relax the spec grammar and then use semantic checking. Parsing is an art; not a science.

chrisseaton 7y ago
Right - no 'serious language' is hyperbole, and another counter example is Ruby. But... if I was asked to implement a language tomorrow I wouldn't even consider using Bison and Flex. Why? Because they're context-free tools, and almost every industrial language is context-sensitive. Square pegs and round holes. These tools are a great example of over-complicating and over-theorising programming languages. We invented a theory that doesn't even apply to the problem we have, and then created crazy tools to solve the wrong problem, and gloss over the fact that they don't apply with terrible hacks and side-effects. We made a mistake with that phase in programming language history...
- judofyr 7y ago
  Interesting. I've always thought that there's no real reason why e.g. Ruby has to be context-sensitive. Yes, I am aware of the fact that local variables are resolved statically, but do they have to be resolved during parsing? Couldn't they just be parsed as a method_call_or_var_lookup, and then later resolved? The main "feature" that Ruby's context-sensitive parser has is the ability to parse differently depending on what precedes it is a local variable or not, and I'm not sure if that's a good feature or not. Are there other parts of Ruby's grammars that are also context-sensitive? I'd say that Bison's biggest issue is that it's limited to LALR; if it actually supported full context-free grammars it would be far more useful.
  - chrisseaton 7y ago
    > Yes, I am aware of the fact that local variables are resolved statically That's the one that comes to my mind yes. I'd bet that there are others, but couldn't list them to you now. > do they have to be resolved during parsing? I guess not in practice? But why are we doing this to ourselves, right? These parsing tools work great! (As long as you only do half do the job you were trying to do and then sort of hack it back together afterward.)
    - judofyr 7y ago
      > But why are we doing this to ourselves, right? These parsing tools work great! (As long as you only do half do the job you were trying to do and then sort of hack it back together afterward.) I agree with you in practice: The current parser generators are not as good as I'd like them to be. They are too restrictive and too locked into a "let's parse this subset of grammars mathematically optimally" instead of "let's make it easy for programmers to declare grammars". (Disclaimer: I started working on a completely new parser compiler https://www.sanity.io/blog/why-we-wrote-yet-another-parser-compiler https://www.sanity.io/blog/why-we-wrote-yet-another-parser-c... which is capable of parsing full context-free grammars. I personally believe this is part of the puzzle of making them more usable.) However, since we're talking about Ruby's syntax: I don't think Ruby's parser would be any nicer if it was handwritten. The problem here is that they discovered the power of "lexer tweaks parser state" and let it drive the design of the language. This has caused the language itself to be complicated (both for humans and for computers!) Unfortunately I don't have time for it, but I'd love to dive into the changes required in Ruby's syntax to make it context-free (e.g. pushing the local variable lookup into the bytecode generator).
      - chrisseaton 7y ago
        Thanks I'll read that article.
- hasbot 7y ago
  That's more hyperbole. You're putting a lot of responsibility on some simple tools. Programming language design complexity came first and not as a result of yacc or lex.
  - chrisseaton 7y ago
    > Programming language design complexity came first and not as a result of yacc or lex. I'm really not sure where you got the impression I was blaming Yacc or Lex for the complexity of the languages - I think you've imagined that. The situation we're in in practice is that our language grammars are complex and are context-sensitive. So why are we trying to use context-free tools? It's madness - we're trying to hammer a nail using a screwdriver.
    - hasbot 7y ago
      I got that impression from this sentence of yours: > These tools are a great example of over-complicating and over-theorising programming languages. If programming languages are over-complicated, it's not the fault of these tools. > So why are we trying to use context-free tools? I no longer keep up with compilers (or languages), but when I was, there was no other tools. Either go through the tedium and effort of hand-rolling a lexer/parser or munge the language grammar to fit.
      - chrisseaton 7y ago
        I see why you'd think that, but I meant over-complicating the implementation of languages, not their design. > there was no other tools I don't think you need tools. Just write your parser as a normal program directly in a general-purpose programming language. I'm not sure that parsing is so special as to require an external DSL.
        hasbot 7y ago
        No tool is ever necessary. But not using yacc is tedious, slow, error-prone, uninteresting, and utterly no fun.
- seanmcdirmid 7y ago
  What production languages are context sensitive? C++ surely, Java and C# only when dealing with angle brackets for generics, what else?
  - beagle3 7y ago
    Defining a variable before use makes a language context sensitive. So does e.g. typedef in C - is (a)*b multiplying a by b or typecasting what b points to? Depends on the types. We usually semantically patch that at the right stage through the lexer or the AST so things still work in a CF setting, but almost no modern language is CF.
    - seanmcdirmid 7y ago
      Use before declaration is resolved at the type checker level, not during parsing. C-style casting isn’t context sensitive if you don’t mind treating the casting type has an expression and then pulling a type out of it in the type checker (or evaluator if dynamic). Type checking is where all the complexity really is. Parsing and lexing are just easy things you do before the hard stuff.
      - beagle3 7y ago
        C has a lot of things which are context sensitive, and you can't treat the casting type as an expression: c*(a)-b parses under (double a, b, c;) as ((ca)-b) ; but under (typedef double a; double b, c) it parses as c-b, (with a type conversion applied after the negation) which is a different parse, and which can be more complicated than that to the point that fixing the AST is equivalent to reparsing the source. Use before declaration can only be resolved at the typechecker if you assume every name is a variable, but the introduction of typedefs makes that assumption wrong, so you can't wait for the type checker - every C parser I know patches that information back into the lexer so that it would parse correctly. Indeed, the "typename" keyword was added to C++ because you can't leave that to the typechecker if you want a unique parse before instantiation.
        7y ago
- beagle3 7y ago
  Is there any grammar for a modern language that is context sensitive and expresses the constraints better than a context free grammar? It’s true almost no usable language is really CF, but a CF grammar with a few semantic patches still seems to be the better way to describe them. It’s been a while since I needed to parse a grammar, but if I had to I’d probably use re2c+lemon, Ometa/ohm, or a hand-rolled Pratt parser. (Or an Earley parser if the grammar was ambiguous and it made sense)
MaxBarraclough 7y ago
I'm reminded of another comment from some time ago [0] that recommended 'permissive' parsers for a different reason: you can build a list of syntax errors for the user, which isn't possible if you explode immediately, and you may be able to generate better syntax errors than your parser would have. [0] https://news.ycombinator.com/item?id=17072670 https://news.ycombinator.com/item?id=17072670

by hasbot 7y ago

chrisseaton 7y ago

Right - no 'serious language' is hyperbole, and another counter example is Ruby. But... if I was asked to implement a language tomorrow I wouldn't even consider using Bison and Flex. Why? Because they're context-free tools, and almost every industrial language is context-sensitive. Square pegs and round holes. These tools are a great example of over-complicating and over-theorising programming languages. We invented a theory that doesn't even apply to the problem we have, and then created crazy tools to solve the wrong problem, and gloss over the fact that they don't apply with terrible hacks and side-effects. We made a mistake with that phase in programming language history...

judofyr 7y ago
Interesting. I've always thought that there's no real reason why e.g. Ruby has to be context-sensitive. Yes, I am aware of the fact that local variables are resolved statically, but do they have to be resolved during parsing? Couldn't they just be parsed as a method_call_or_var_lookup, and then later resolved? The main "feature" that Ruby's context-sensitive parser has is the ability to parse differently depending on what precedes it is a local variable or not, and I'm not sure if that's a good feature or not. Are there other parts of Ruby's grammars that are also context-sensitive? I'd say that Bison's biggest issue is that it's limited to LALR; if it actually supported full context-free grammars it would be far more useful.
- chrisseaton 7y ago
  > Yes, I am aware of the fact that local variables are resolved statically That's the one that comes to my mind yes. I'd bet that there are others, but couldn't list them to you now. > do they have to be resolved during parsing? I guess not in practice? But why are we doing this to ourselves, right? These parsing tools work great! (As long as you only do half do the job you were trying to do and then sort of hack it back together afterward.)
  - judofyr 7y ago
    > But why are we doing this to ourselves, right? These parsing tools work great! (As long as you only do half do the job you were trying to do and then sort of hack it back together afterward.) I agree with you in practice: The current parser generators are not as good as I'd like them to be. They are too restrictive and too locked into a "let's parse this subset of grammars mathematically optimally" instead of "let's make it easy for programmers to declare grammars". (Disclaimer: I started working on a completely new parser compiler https://www.sanity.io/blog/why-we-wrote-yet-another-parser-compiler https://www.sanity.io/blog/why-we-wrote-yet-another-parser-c... which is capable of parsing full context-free grammars. I personally believe this is part of the puzzle of making them more usable.) However, since we're talking about Ruby's syntax: I don't think Ruby's parser would be any nicer if it was handwritten. The problem here is that they discovered the power of "lexer tweaks parser state" and let it drive the design of the language. This has caused the language itself to be complicated (both for humans and for computers!) Unfortunately I don't have time for it, but I'd love to dive into the changes required in Ruby's syntax to make it context-free (e.g. pushing the local variable lookup into the bytecode generator).
    - chrisseaton 7y ago
      Thanks I'll read that article.
hasbot 7y ago
That's more hyperbole. You're putting a lot of responsibility on some simple tools. Programming language design complexity came first and not as a result of yacc or lex.
- chrisseaton 7y ago
  > Programming language design complexity came first and not as a result of yacc or lex. I'm really not sure where you got the impression I was blaming Yacc or Lex for the complexity of the languages - I think you've imagined that. The situation we're in in practice is that our language grammars are complex and are context-sensitive. So why are we trying to use context-free tools? It's madness - we're trying to hammer a nail using a screwdriver.
  - hasbot 7y ago
    I got that impression from this sentence of yours: > These tools are a great example of over-complicating and over-theorising programming languages. If programming languages are over-complicated, it's not the fault of these tools. > So why are we trying to use context-free tools? I no longer keep up with compilers (or languages), but when I was, there was no other tools. Either go through the tedium and effort of hand-rolling a lexer/parser or munge the language grammar to fit.
    - chrisseaton 7y ago
      I see why you'd think that, but I meant over-complicating the implementation of languages, not their design. > there was no other tools I don't think you need tools. Just write your parser as a normal program directly in a general-purpose programming language. I'm not sure that parsing is so special as to require an external DSL.
      - hasbot 7y ago
        No tool is ever necessary. But not using yacc is tedious, slow, error-prone, uninteresting, and utterly no fun.
seanmcdirmid 7y ago
What production languages are context sensitive? C++ surely, Java and C# only when dealing with angle brackets for generics, what else?
- beagle3 7y ago
  Defining a variable before use makes a language context sensitive. So does e.g. typedef in C - is (a)*b multiplying a by b or typecasting what b points to? Depends on the types. We usually semantically patch that at the right stage through the lexer or the AST so things still work in a CF setting, but almost no modern language is CF.
  - seanmcdirmid 7y ago
    Use before declaration is resolved at the type checker level, not during parsing. C-style casting isn’t context sensitive if you don’t mind treating the casting type has an expression and then pulling a type out of it in the type checker (or evaluator if dynamic). Type checking is where all the complexity really is. Parsing and lexing are just easy things you do before the hard stuff.
    - beagle3 7y ago
      C has a lot of things which are context sensitive, and you can't treat the casting type as an expression: c*(a)-b parses under (double a, b, c;) as ((ca)-b) ; but under (typedef double a; double b, c) it parses as c-b, (with a type conversion applied after the negation) which is a different parse, and which can be more complicated than that to the point that fixing the AST is equivalent to reparsing the source. Use before declaration can only be resolved at the typechecker if you assume every name is a variable, but the introduction of typedefs makes that assumption wrong, so you can't wait for the type checker - every C parser I know patches that information back into the lexer so that it would parse correctly. Indeed, the "typename" keyword was added to C++ because you can't leave that to the typechecker if you want a unique parse before instantiation.
      - 7y ago
beagle3 7y ago
Is there any grammar for a modern language that is context sensitive and expresses the constraints better than a context free grammar? It’s true almost no usable language is really CF, but a CF grammar with a few semantic patches still seems to be the better way to describe them. It’s been a while since I needed to parse a grammar, but if I had to I’d probably use re2c+lemon, Ometa/ohm, or a hand-rolled Pratt parser. (Or an Earley parser if the grammar was ambiguous and it made sense)

MaxBarraclough 7y ago

I'm reminded of another comment from some time ago [0] that recommended 'permissive' parsers for a different reason: you can build a list of syntax errors for the user, which isn't possible if you explode immediately, and you may be able to generate better syntax errors than your parser would have. [0] https://news.ycombinator.com/item?id=17072670 https://news.ycombinator.com/item?id=17072670