Understanding grammar for Parse trees

Viewed 106

I am just trying to understand a natural language interface for relational databases proposed by Fei Li (2014) (available as github project). Specifically I don't understand the grammar they define for a ParseTree of a natural language query to a database. This question is somewhat like this one but with a more complex grammar.

Background: A natural language sentence can be parsed as ParseTree (common library for this is the Stanford Parser) which describes the grammatical relations of words in a sentence.

The grammar for a valid ParseTree is:

  1. Q -> (SClause)(ComplexCondition)*

  2. SClause -> SELECT + GNP

  3. ComplexCondition -> ON + (leftSubtree*rightSubtree)

  4. leftSubtree -> GNP

  5. rightSubtree -> GNP | VN | MIN | MAX

  6. GNP -> (FN + GNP) | NP

  7. NP -> NN + (NN)*(condition)*

  8. condition -> VN | (ON + VN)

where

  • Q represents an entire query tree
  • + a parent-child relationship
  • * a sibling relationship
  • SN is a SELECT node
  • ON is an OPERATOR node (e.g. =, <=)
  • FN is a FUNCTION node (e.g. AVG)
  • NN is a NAME node (e.g. a column in a db table)
  • VN is a VALUE node (i.e. a value in a column in a db table)
  • ComplexCondition must have one ON with a leftSubtree and rightSubtree
  • NP is one NN whose children are multiple NNs and conditions.

My questions:

  1. why is condition defined as VN or (ON+VN)? This would mean that something like the digit 5 by itself can be a condition. Would make more sense of only the latter, i.e. (ON+VN) is a condition (e.g. >5)

  2. How can a rightSubtree just be a function (e.g. MIN). Btw I am understanding the pipe | as logical or.

  3. I understand that GNP is recursively defined but at a terminal node the GNP node must be just a NP node right? But a NP is defined as something that has children... HOW?!?!?!

  4. The authors of the github project quoted above state: "Take a Value Node (VN) for example, according to the grammar, it is invalid if and only if it has children. I don't know how to infer this from the grammar

Thanks for the help

0 Answers
Related