import { NonTerminal , Category , isNonTerminal , Terminal } from "./category" ; import { Rule } from "./rule" ; import { getLeftCorners , getUnitStarCorners , getReflexiveTransitiveClosure , LeftCorners } from "./left-corner" ; import { Semiring , LogSemiring , makeDeferrable } from "semiring" ; import { Expression } from "semiring" ; function getOrCreateSet < X , Y > ( map , x ) { if ( map . has ( x ) ) { return map . get ( x ) ; } else { const yToP = new Set < Y > ( ) ; map . set ( x , yToP ) ; return yToP ; } } export interface ProbabilitySemiringMapping < Y > { semiring : Semiring < Y > ; fromProbability ( p ) : Y ; toProbability ( p ) : number ; ZERO : Y ; ONE : Y ; } export class Grammar < T , SemiringType > { readonly name : string ; readonly ruleMap : Map < NonTerminal , Set < Rule < T > > > ; readonly rules : Set < Rule < T > > = new Set < Rule < T > > ( ) ; readonly nonTerminals : Set < NonTerminal > = new Set < NonTerminal > ( ) ; readonly terminals : Terminal < T > [ ] ; private readonly leftCorners : LeftCorners < T > ; readonly leftStarCorners : LeftCorners < T > ; readonly unitStarScores : LeftCorners < T > ; readonly probabilityMapping : ProbabilitySemiringMapping < SemiringType > ; readonly deferrableSemiring : Semiring < Expression < SemiringType > > ; constructor ( name , ruleMap , probabilityMapping ) { this . name = name ; this . ruleMap = ruleMap ; this . probabilityMapping = probabilityMapping ; this . deferrableSemiring = makeDeferrable ( probabilityMapping . semiring ) ; const values = ruleMap . values ( ) ; let done = false ; const terminals = new Set < Terminal < T > > ( ) ; while ( ! done ) { const next = values . next ( ) ; done = next . done ; if ( ! done ) { const rulez = next . value ; rulez . forEach ( ( rule ) => { this . rules . add ( rule ) ; this . nonTerminals . add ( rule . left ) ; rule . right . forEach ( ( a ) => { if ( isNonTerminal ( a ) ) this . nonTerminals . add ( a ) ; else terminals . add ( a ) ; } ) ; } ) ; } } this . terminals = Array . from ( terminals ) ; const zero = 0.0 ; this . leftCorners = getLeftCorners ( this . rules , zero ) ; this . leftStarCorners = getReflexiveTransitiveClosure ( this . nonTerminals , this . leftCorners , zero ) ; this . unitStarScores = getUnitStarCorners ( this . rules , this . nonTerminals , zero ) ; } getLeftStarScore ( from , to ) { return this . leftStarCorners . get ( from , to ) ; } getLeftScore ( from , to ) { return this . leftCorners . get ( from , to ) ; } getUnitStarScore ( from , to ) { return this . unitStarScores . get ( from , to ) ; } static withSemiring < T , Y > ( semiringMapping , name ? ) { return new GrammarBuilder < T , Y > ( semiringMapping , name ) ; } static builder < T > ( name ? ) { return new GrammarBuilder < T , number > ( LOG_SEMIRING , name ) ; } } const LOG_SEMIRING = { semiring : LogSemiring , fromProbability : ( x ) => - Math . log ( x ) , toProbability : ( x ) => Math . exp ( - x ) , ZERO : LogSemiring . additiveIdentity , ONE : LogSemiring . multiplicativeIdentity } ; export class GrammarBuilder < T , SemiringType > { private readonly ruleMap : Map < NonTerminal , Set < Rule < T > > > ; private readonly name : string ; private semiringMapping : ProbabilitySemiringMapping < SemiringType > ; constructor ( semiringMapping , name ? ) { this . ruleMap = new Map < NonTerminal , Set < Rule < T > > > ( ) ; this . name = name ; this . semiringMapping = semiringMapping ; } setSemiringMapping ( semiringMapping ) { this . semiringMapping = semiringMapping ; return this ; } addNewRule ( probability , left , right ) { this . addRule ( { left , right , probability } ) ; return this ; } addRule ( rule ) { if ( ! rule . probability || typeof rule . probability !== "number" ) throw new Error ( "Probability not defined: " + rule . probability ) ; if ( ! rule . left ) throw new Error ( "Left hand side not defined: " + rule . left ) ; if ( ! rule . right || ! rule . right . length || typeof rule . right . length !== "number" ! || rule . right . length <= 0 ) throw new Error ( "Right hand side not defined: " + rule . right ) ; if ( this . ruleMap . has ( rule . left ) ) { this . ruleMap . get ( rule . left ) . forEach ( rle => { if ( rule . right . length === rle . right . length ) { for ( let i = 0 ; i < rule . right . length ; i ++ ) if ( rule . right [ i ] !== rle . right [ i ] ) return ; throw new Error ( "Already added rule " + rule . left + " -> " + rule . right . toString ( ) ) ; } } ) ; } getOrCreateSet ( this . ruleMap , rule . left ) . add ( rule ) ; return this ; } build ( ) { return new Grammar ( this . name , this . ruleMap , this . semiringMapping ) ; } }