3 ms·

How relevant are Context Free grammars for modern programming languages? It seems that most modern languages want things like “raw strings” where you can deal w

How relevant are Context Free grammars for modern programming languages? It seems that most modern languages want things like “raw strings” where you can deal with arbitrary strings by using syntax like (Rust) `r###` (however many `#` you need). It is my understanding that syntax like that makes these grammars fall outside of Context Free, no?

Rusky 3y ago
Features like that technically make the language context-sensitive, but in practice that context sensitivity is entirely contained within the lexer, and you can still describe the rest of the language with a context free grammar of tokens.
- keybored 3y ago
  Okay, thanks. I think that’s good.
chowells 3y ago
That sort of thing is typically handled during lexing. By the time the parser deals with it, it's a string literal. This is one of the advantages of splitting those into separate phases. There are other hacks in use as well. Haskell's syntax is context-sensitive because operator precedence and associativity can be declared in the same context as the operator is used. But GHC ignores that during the phase where it actually parses the input. It just ignores precedence and associativity when parsing operators. After it finishes parsing the translation unit, another phase goes back, finds nested operator applications in the parse tree, and fixes them up based on the precedence and associativity information it has found. It turns out that when your language is only just barely context-sensitive, you can find a way to use context-free tools to handle it, with a couple extra passes to fix things up.
o11c 3y ago
The actual place where CFGs fail tend to be if types and expressions aren't parsed the same. This especially causes problems if your language's generics use `<>`, but even C has the `T * v` problem.
- adrian_b 3y ago
  In traditional programming languages the origin of such problems is the straightjacket of the ASCII character set. When a programming language is designed now, the right way is to use distinct Unicode characters wherever necessary, easily avoiding all ambiguities.
  - layer8 3y ago
    I would like to agree, but since keyboards are still mostly ASCII (in particular with regard to punctuation characters), most people don’t have a Compose key configured, and also don’t want to be constrained to editors with an input method tailored to that programming language, it would be an uphill battle for adoption.
    - keybored 3y ago
      Interestingly though even C had the “not on my keyboard” problem, hence the trigraphs. And still they ended up having to use “lexer hacks”. Modern languages could use a more legible (unlike C trigraphs) solution as write-only alternatives (a canonical formatter could normalize). Since modern language can now use the whole (woah) printable ASCII range. :)
      - layer8 3y ago
        The trigraphs feature was a committee invention for something that had already largely stopped being a problem at the time it was decided. Nobody really used them, other than by mistake, which is why they were now removed in C23 (and already earlier in C++). A write-only solution is virtually the same as an input method, or you have to support different representations in source code after all. It also doesn’t fix all syntax ambiguities. For example you may want to allow “<<“ as an ASCII version of “«”, but then you still have possible ambiguities with consecutive “<“s (does “<<< … >>>” mean “<« … »>” or “«< … >»”?). And it has the drawback that you have to learn how to type the symbols that look differently from their ASCII sequence counterpart in the canonical version.

Rusky 3y ago

Features like that technically make the language context-sensitive, but in practice that context sensitivity is entirely contained within the lexer, and you can still describe the rest of the language with a context free grammar of tokens.

keybored 3y ago
Okay, thanks. I think that’s good.

chowells 3y ago

That sort of thing is typically handled during lexing. By the time the parser deals with it, it's a string literal. This is one of the advantages of splitting those into separate phases. There are other hacks in use as well. Haskell's syntax is context-sensitive because operator precedence and associativity can be declared in the same context as the operator is used. But GHC ignores that during the phase where it actually parses the input. It just ignores precedence and associativity when parsing operators. After it finishes parsing the translation unit, another phase goes back, finds nested operator applications in the parse tree, and fixes them up based on the precedence and associativity information it has found. It turns out that when your language is only just barely context-sensitive, you can find a way to use context-free tools to handle it, with a couple extra passes to fix things up.

o11c 3y ago

The actual place where CFGs fail tend to be if types and expressions aren't parsed the same. This especially causes problems if your language's generics use `<>`, but even C has the `T * v` problem.

adrian_b 3y ago
In traditional programming languages the origin of such problems is the straightjacket of the ASCII character set. When a programming language is designed now, the right way is to use distinct Unicode characters wherever necessary, easily avoiding all ambiguities.
- layer8 3y ago
  I would like to agree, but since keyboards are still mostly ASCII (in particular with regard to punctuation characters), most people don’t have a Compose key configured, and also don’t want to be constrained to editors with an input method tailored to that programming language, it would be an uphill battle for adoption.
  - keybored 3y ago
    Interestingly though even C had the “not on my keyboard” problem, hence the trigraphs. And still they ended up having to use “lexer hacks”. Modern languages could use a more legible (unlike C trigraphs) solution as write-only alternatives (a canonical formatter could normalize). Since modern language can now use the whole (woah) printable ASCII range. :)
    - layer8 3y ago
      The trigraphs feature was a committee invention for something that had already largely stopped being a problem at the time it was decided. Nobody really used them, other than by mistake, which is why they were now removed in C23 (and already earlier in C++). A write-only solution is virtually the same as an input method, or you have to support different representations in source code after all. It also doesn’t fix all syntax ambiguities. For example you may want to allow “<<“ as an ASCII version of “«”, but then you still have possible ambiguities with consecutive “<“s (does “<<< … >>>” mean “<« … »>” or “«< … >»”?). And it has the drawback that you have to learn how to type the symbols that look differently from their ASCII sequence counterpart in the canonical version.