I'm dealing with a corpus of text that is written informally, but generally conforms to a very standard format by convention (think something like Froyo Frozen Yogurt, Smucker's Peanut Butter) and occasionally requires recursion (Froyo Frozen Yogurt with Smucker's Peanut Butter).

With regexes, the complexity quickly grows out of hand (Frozen Yogurt by Froyo, Froyo Frozen Yogurt with Peanut Butter by Smucker's, etc).

I'm having trouble finding resources to help me write an EBNF for this, and NLP method are too complex (plus my "parts of speech" don't really correspond to normal english). Is there an intermediate approach, aimed at semi-formalized text?

(repost from stackoverflow on Otavio Macedo's advice)

  • Some reasonable templates: [Manufacturer] [Flavor] [Food Type], [Flavor] [Food Type] (made|prepared|sold) by [Manufacturer] -- we have a complete(ish) lexicon of Food Type and possibly Manufacturer. Contrived example: Edy's Chocolate Chip Ice Cream with Praline made by Nestle and Nabisco (parse tree is something like this: asciiflow.com/#6223280195879178536) Commented Jun 13, 2012 at 17:37
  • Invalid: Smucker's Racecar (unknown Food Type), Yogurt imported by Froyo ('imported by' not a known relationship), Reebok Ice Cream (Reebok known not to be a food manufacturer). These could appear in freeform sentences (I like Smucker's Peanut Butter) but it's more important to solve the standalone case Commented Jun 13, 2012 at 17:37
  • have you looked at a unification-based approach?
    – user483
    Commented Jun 13, 2012 at 20:28
  • 1
    Did you consider Named-entity recognition? Commented Jun 15, 2012 at 5:06
  • @hippietrail NER seems promising, though it looks like this approach does not preserve structure information (e.g. Praline being a component of Ice Cream in above comment). This might be Good Enough. Commented Jun 16, 2012 at 22:25

1 Answer 1


It might be constrained, but NLP parsers work well, just the same. A few popular ones you could play with:

You could go the BNF way too, if you prefer. (The NLP community prefers to call it CFG (Context Free Grammar)). You can find some online demos of these too. NLTK comes with an implementation you could play with.

ADDENDUM http://www.diotavelli.net/people/void/demos/cky.html has a nice online demo that draws parse charts given a CFG grammar. The website has some limitations, so I recommend that you:

  1. write the CFG rules in your own text editor, and paste them into the text window. The online demo 'loses' rules as soon as it runs them.
  2. remember that the grammar must be in Chomsky Normal Form, i.e. each non-terminal expands to at most two other symbols (in each rule). If you want more, you'll have to compose it yourself.

While this is a good way to get started, you would eventually have to move to a more usable parser, such as the ones bundled with NLTK.

  • Thanks for these resources, the online demos are very helpful. My biggest problem with either of these approaches is that most docs I could find focus on grammars dealing with natural speech (nouns, verbs, etc) and code structures (blocks, expressions, loops, etc) respectively, and my grammar doesn't map neatly onto those. Commented Jun 16, 2012 at 22:34
  • @ArkadiyKukarkin: added more info.
    – prash
    Commented Jun 16, 2012 at 23:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.