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.
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?
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.
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.