1

While there are enormous resources to convert a CFG(Context Free Grammar) to language, there isn't any resource to create a CFG out of a given sentence. Basically, I am trying to use the grammar to do a CKY parsing and generate tree.

Currently, If I generate a grammar by hand, then it's not generating the correct tree. So, I was wondering if there is an online tool that generates a CFG from a given sentence, then it would be highly helpful.

Edit:

Sentence - I shot an elephant in my pajamas

Grammar 

S -> NP VP
PP -> P NP
NP -> Det N
NP -> Det N PP
NP -> 'I'
VP -> V NP
VP -> VP PP
Det -> 'an'
Det -> 'my'
N -> 'elephant'
N -> 'pajamas'
V -> 'shot'
P -> 'in'
YaArj
  • 11
  • 2
  • 1
    A single sentence is not enough to define a grammar. And even less enough to deduce the precise structure of the parse tree. There's lots of research on deducing grammars from examples, which you should be able to search for, but the bottom line is that it's not easy and not very reliable. And you need lots of carefully crafted samples for it to be even a little practical. – rici Apr 13 '19 at 21:36
  • I am not sure if you understand the context and the definition of several terms like grammar. Please see the edit to know what I is meant by a grammar given a sentence. – YaArj Apr 14 '19 at 00:24
  • I believe @rici is correct here. I suspect that you’re looking for a **parse tree** rather than a **CFG** here. – templatetypedef Apr 14 '19 at 02:16
  • @template: to me, that looks more like a **derivation** but there's little practical difference. – rici Apr 14 '19 at 02:35
  • If you are looking for an algorithm for extracting a parse tree from a CKY parse table, see https://stackoverflow.com/questions/33705923/steps-to-generate-parse-tree-from-cyk-algorithm-natural-language-processing. – rici Apr 14 '19 at 04:13
  • @rici I was under the impression that a derivation was a series of sentential forms where each step follows from the previous by the application of a production rule. The OP’s question seems to suggest that they’re looking to recover the structure of the sentence with the individual tokens annotated with types, which led me to think parse trees. But please do correct me if I’m mistaken here! – templatetypedef Apr 14 '19 at 04:41
  • @template: yes, that is what a derivation is. But you can also write it by listing the production rules applied. That's also a traverse of the parse tree, of course, which is why I said there is little practical difference. A closer examination of the list of rules in OP's edit shows that the order doesn't correspond with either a derivation or a plausible tree traverse, so the challenge is to unscramble the list. A depth-first tree traverse would be a plausible outcome, but left- or right-most derivations would have the same information... – rici Apr 14 '19 at 07:03
  • Anyway, I'm certain that you are correct that the goal is to recover the sentence structure using productions found during execution of the CKY algorithm. – rici Apr 14 '19 at 07:06

0 Answers0