33 ms·

Parsing and all that

63 points by foresterre 2y ago

kazinator 2y ago
Combining a finite state machine for recognizing sentential patterns, with a stack, gives us LR parsing. But push-down automata are significant not only because they have practical uses in parsing, but because they represent a theoretical class. They are more powerful than finite automata, but are not Turing complete. If, say, we use a push-down automaton to make a Boolean decision: does this input string fall into the to-be-recognized set, or not? then there are some kinds of strings it won't be able to decide, that a full Turing machine could decide. The limitation of push down automata is a direct consequence of the stack discipline. There is only one stack, and when the stack is popped, information is thrown away. The tape machine that Turing described as part of developing his theory of computation doesn't have that limitation; when the tape head moves backwards, material it has written to the tape is not erased in a stack-like discipline.
- mcguire 2y ago
  Neat observation: finite automata, push-down automata, and Turing machines can be distinguished purely by the number of stacks they need. Finite automata: no stack. Pushdown automata: one stack. Turing machine: two stacks. (Use them like the tape: to move forward, pop the f-stack and push the symbol on the b-stack; to move backward pop the b-stack and push to the f-stack.)
  - mark_undoio 2y ago
    I think it's a shame this wasn't highlighted more explicitly in, at least, my computer science degree. We did finite state machines in quite a bit of detail, vaguely referred to pushdown automata but then concentrated on lambda calculus for quite a lot, with Turing machines less so. The Turing machine description, without showing it in this hierarchy, seems like a really weird abstraction. Fitting it in here (and combining it with the different Chomsky classes of grammar) makes it all feel more joined up.
    - mcguire 2y ago
      That was the way I learned it. I found the lambda calculus the odd one out. :-)
- eternityforest 2y ago
  What else can they do? Has anyone used them outside of parsing, as a way to satisfy the principle of least power?
  - 082349872349872 2y ago
    Michael Jackson's single-threaded "Jackson Structured Programming"?
norir 2y ago
There is a part of me that feels we should just forget that LR ever existed and insist on LL(k) for k <= 2 for all new languages. The supposed expressivity benefits are not worth the complexity cost in my not so humble opinion. For me, the best approach is to write the grammar in a dsl that checks that it is unambiguous and in LL(k) and then implement by hand with recursive descent.
- marcosdumay 2y ago
  Well, IMO, but you write a parser only a couple of times for each language, but you read code all the time. So, anything that makes code easier to read is a must. That includes the extra expressiveness of an LR grammar.
  - mhh__ 2y ago
    In 2012 yes, but these days having grammars that lots of tools can parse and output easily is a boon for tooling.
  - vidarh 2y ago
    I agree there are a few places like this, but they're usually solved when you want an LL parser for as much as possible of the language by either making them part of the tokenization or by "escaping" a small subset of the grammar. I wish that language designers (looking at you, Ruby - as much as I love using Ruby, the grammar is an abomination) would at least try to stick to LL as much as possible, and consciously, carefully and in a limited fashion "escape" into LR for as small subsets as possible. Break rules if it actually helps developers, sure, but it'd be nice if people tried to make the weird bits as tiny as possible... EDIT: Also, in practice this is often what we end up doing when we write recursive descent anyway, only in a less than formal way. It'd be nice if more tooling let us write grammars that default to LL w/checking, but let you insert clearly delineated exceptions.
    - marcosdumay 2y ago
      Oh, I do agree with that! A language should be LL as much as possible. And also depend on the parsed data as little as possible. Stuff like C's variable declaration must be avoided. But I don't think either of those rules can be made universal. Some language for expressing exceptions would be great.
keybored 2y ago
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 2y 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 2y ago
    Okay, thanks. I think that’s good.
- chowells 2y 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 2y 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.

63 points by foresterre 2y ago

Combining a finite state machine for recognizing sentential patterns, with a stack, gives us LR parsing. But push-down automata are significant not only because they have practical uses in parsing, but because they represent a theoretical class. They are more powerful than finite automata, but are not Turing complete. If, say, we use a push-down automaton to make a Boolean decision: does this input string fall into the to-be-recognized set, or not? then there are some kinds of strings it won't be able to decide, that a full Turing machine could decide. The limitation of push down automata is a direct consequence of the stack discipline. There is only one stack, and when the stack is popped, information is thrown away. The tape machine that Turing described as part of developing his theory of computation doesn't have that limitation; when the tape head moves backwards, material it has written to the tape is not erased in a stack-like discipline.

mcguire 2y ago
Neat observation: finite automata, push-down automata, and Turing machines can be distinguished purely by the number of stacks they need. Finite automata: no stack. Pushdown automata: one stack. Turing machine: two stacks. (Use them like the tape: to move forward, pop the f-stack and push the symbol on the b-stack; to move backward pop the b-stack and push to the f-stack.)
- mark_undoio 2y ago
  I think it's a shame this wasn't highlighted more explicitly in, at least, my computer science degree. We did finite state machines in quite a bit of detail, vaguely referred to pushdown automata but then concentrated on lambda calculus for quite a lot, with Turing machines less so. The Turing machine description, without showing it in this hierarchy, seems like a really weird abstraction. Fitting it in here (and combining it with the different Chomsky classes of grammar) makes it all feel more joined up.
  - mcguire 2y ago
    That was the way I learned it. I found the lambda calculus the odd one out. :-)
eternityforest 2y ago
What else can they do? Has anyone used them outside of parsing, as a way to satisfy the principle of least power?
- 082349872349872 2y ago
  Michael Jackson's single-threaded "Jackson Structured Programming"?

norir 2y ago

There is a part of me that feels we should just forget that LR ever existed and insist on LL(k) for k <= 2 for all new languages. The supposed expressivity benefits are not worth the complexity cost in my not so humble opinion. For me, the best approach is to write the grammar in a dsl that checks that it is unambiguous and in LL(k) and then implement by hand with recursive descent.

marcosdumay 2y ago
Well, IMO, but you write a parser only a couple of times for each language, but you read code all the time. So, anything that makes code easier to read is a must. That includes the extra expressiveness of an LR grammar.
- mhh__ 2y ago
  In 2012 yes, but these days having grammars that lots of tools can parse and output easily is a boon for tooling.
- vidarh 2y ago
  I agree there are a few places like this, but they're usually solved when you want an LL parser for as much as possible of the language by either making them part of the tokenization or by "escaping" a small subset of the grammar. I wish that language designers (looking at you, Ruby - as much as I love using Ruby, the grammar is an abomination) would at least try to stick to LL as much as possible, and consciously, carefully and in a limited fashion "escape" into LR for as small subsets as possible. Break rules if it actually helps developers, sure, but it'd be nice if people tried to make the weird bits as tiny as possible... EDIT: Also, in practice this is often what we end up doing when we write recursive descent anyway, only in a less than formal way. It'd be nice if more tooling let us write grammars that default to LL w/checking, but let you insert clearly delineated exceptions.
  - marcosdumay 2y ago
    Oh, I do agree with that! A language should be LL as much as possible. And also depend on the parsed data as little as possible. Stuff like C's variable declaration must be avoided. But I don't think either of those rules can be made universal. Some language for expressing exceptions would be great.

keybored 2y ago

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 2y 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 2y ago
  Okay, thanks. I think that’s good.
chowells 2y 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 2y 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.