4 ms·
let's say I wanted to learn the grammar of/how to parse a context-sensitive grammar from a 100 or thousands of valid examples -- what's the best approach?
by pyvpx 10y ago
let's say I wanted to learn the grammar of/how to parse a context-sensitive grammar from a 100 or thousands of valid examples -- what's the best approach?
- daveguy 10y agoFirst I would suggest you do your own homework assignments. ;) Currently recurrent neural networks are the best language processing ML algorithms. Here is a relatively new paper on recurrent neural network grammars and it references many of the recent papers: http://www.aclweb.org/anthology/N16-1024 http://www.aclweb.org/anthology/N16-1024
- pyvpx 10y agoit's not a homework assignment :) thanks for the link. I'm looking to parse a simple but unknown configuration file format deduced only from known good examples.
- daveguy 10y agoI'm not certain, but to do that optimally I think is an np-complete problem. If you put some restrictions on it: all files are the same format or only N fixed formats or context free grammars then it's manageable. Otherwise it boils down to natural language processing and imperfect, but useful algorithms in that domain will probably help. Are you sure it's context sensitive grammar rather than a collection of N context free grammars? Many file format standards can be expressed as context free grammars. If you are trying to figure out something like "what is the unknown XML structure" based on an example file or files then you are firmly inside natural language processing.