PCFGs are about the first thing that I learned about in my Stastical Machine Translation course. It's like a regular context-free grammar (see Wikipedia if you're not familiar with these), but each production is assigned a probability, such that all productions from the same non-terminal sum up to probability 1. Then you can assign a probability to a parse tree by multiplying the probabilities of all productions that were used (the model assumes that all productions are mutually statistically independent).
After a proper training run, you have your ambiguous grammar which, given an input sentence, will produce a set of parse trees, and assign a probability to each of them. You will typically choose the most probable one.
The Wikipedia article on PCFG is surprisingly biased on RNA/protein analysis and does not go into much detail on how to train these PCFGs. But it's basically just an EM algorithm using inside-outside weights. See for example https://link.springer.com/chapter/10.1007/978-3-540-78291-9_...
This requires defining matching patterns, like a word-based regex though, right? Houndify uses that approach because it is easier to integrate with speech recognition, but it is very cumbersome to use and maintain and doesn't allow learning new utterances.
I don't think Wit.ai works as simply as you believe - it isn't merely matching keywords. Unfortunately I haven't been able to find out exactly how it does work. Alexa, and Nuance Mix work the same way as Wit.ai. In my experience it is the superior approach.
Viv is also one to watch but they haven't really said the NLU works yet.
After a proper training run, you have your ambiguous grammar which, given an input sentence, will produce a set of parse trees, and assign a probability to each of them. You will typically choose the most probable one.
The Wikipedia article on PCFG is surprisingly biased on RNA/protein analysis and does not go into much detail on how to train these PCFGs. But it's basically just an EM algorithm using inside-outside weights. See for example https://link.springer.com/chapter/10.1007/978-3-540-78291-9_...