aima.core.nlp.parsing.grammars

Class ProbCNFGrammar

java.lang.Object

aima.core.nlp.parsing.grammars.ProbUnrestrictedGrammar

aima.core.nlp.parsing.grammars.ProbContextSensitiveGrammar

aima.core.nlp.parsing.grammars.ProbContextFreeGrammar

aima.core.nlp.parsing.grammars.ProbCNFGrammar

All Implemented Interfaces:

ProbabilisticGrammar

public class ProbCNFGrammar
extends ProbContextFreeGrammar

The CYK algorithm exploits the structure of grammars in Chomsky Normal Form in order to parse efficiently. A context-free grammar is in Chomsky Normal Form (CNF) if each rule has one of the following forms: 1. A -> BC, 2. A -> a, 3. S -> null, where B,C are non-start variables (V - {S}), and a is a terminal.

Author:

Jonathon

Field Summary

Fields inherited from class aima.core.nlp.parsing.grammars.ProbUnrestrictedGrammar

CNFGRAMMAR, CONTEXT_FREE, CONTEXT_SENSITIVE, PROB_CONTEXT_FREE, REGULAR, rules, terminals, type, UNRESTRICTED, vars

Constructor Summary

Constructors

Constructor and Description
ProbCNFGrammar()
ProbCNFGrammar(ProbCNFGrammar grammar)

Method Summary

Modifier and Type	Method and Description
boolean	addRule(Rule r) Add a rule to the grammar's rule list if it passes both the restrictions of the Context-free grammar, and the rule is in Chomsky Normal Form.
boolean	addRules(java.util.List<Rule> ruleList) Add a ruleList as the grammar's rule list if all rules in it pass both the restrictions of the Context-free grammar, and all rules or in Chomsky-Normal-Form
boolean	validRule(Rule r) For a grammar rule to be valid in a context-free grammar, all the restrictions of the context-free grammar must hold, and the rule must be in one of three forms.

Methods inherited from class aima.core.nlp.parsing.grammars.ProbContextFreeGrammar

leftDerivesRight

Methods inherited from class aima.core.nlp.parsing.grammars.ProbContextSensitiveGrammar

addRules

Methods inherited from class aima.core.nlp.parsing.grammars.ProbUnrestrictedGrammar

isTerminal, isVariable, toString, updateVarsAndTerminals, updateVarsAndTerminals, validateRuleProbabilities

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait

Methods inherited from interface aima.core.nlp.parsing.grammars.ProbabilisticGrammar

updateVarsAndTerminals, updateVarsAndTerminals, validateRuleProbabilities

Constructor Detail

ProbCNFGrammar

public ProbCNFGrammar()

ProbCNFGrammar

public ProbCNFGrammar(ProbCNFGrammar grammar)

Method Detail

addRules

public boolean addRules(java.util.List<Rule> ruleList)

Add a ruleList as the grammar's rule list if all rules in it pass both the restrictions of the Context-free grammar, and all rules or in Chomsky-Normal-Form

Specified by:

addRules in interface ProbabilisticGrammar

Overrides:

addRules in class ProbContextFreeGrammar

Returns:

true if rules are valid and incorporated into the grammar. false, otherwise

addRule

public boolean addRule(Rule r)

Add a rule to the grammar's rule list if it passes both the restrictions of the Context-free grammar, and the rule is in Chomsky Normal Form.

Specified by:

addRule in interface ProbabilisticGrammar

Overrides:

addRule in class ProbContextFreeGrammar

Returns:

true if rule is incorporated. false, otherwise

validRule

public boolean validRule(Rule r)

For a grammar rule to be valid in a context-free grammar, all the restrictions of the context-free grammar must hold, and the rule must be in one of three forms. 1. A -> BC, 2. A -> a, 3. S -> null, where B,C are non-start variables (V - {S}), and a is a terminal.

Specified by:

validRule in interface ProbabilisticGrammar

Overrides:

validRule in class ProbContextFreeGrammar

Parameters:

r, - a rule

Returns:

true, if rule is in CNF. false, otherwise