@@ -218,11 +218,11 @@ export class ContextFreeGrammar {
218218}
219219
220220public cyk ( string :string ) :CYKTable ;
221- public cyk ( string :string , step :( table : CYKTable ) => void ) :CYKTable ;
222- public cyk ( string :string , step ?:( table : CYKTable ) => void ) :CYKTable {
221+ public cyk ( string :string , step :StepCallback < [ number , CYKTable ] > ) :CYKTable ;
222+ public cyk ( string :string , step ?:StepCallback < [ number , CYKTable ] > ) :CYKTable {
223223const cfg = this . cnf ( ) ;
224224const table = new CYKTable ( string ) ;
225- const callStep = ( ) => step ?.( new CYKTable ( table ) ) ;
225+ const callStep = ( height : number , desc : string ) => step ?.( [ height , new CYKTable ( table ) ] , desc ) ;
226226
227227const getSequencesFor = ( part :string ) :Array < Array < string > > => {
228228const sequences = new Array < Array < string > > ( ) ;
@@ -238,44 +238,50 @@ export class ContextFreeGrammar {
238238
239239for ( const i of string ) {
240240if ( ! table . has ( i ) ) {
241- table . set (
242- i ,
243- new Set < string > (
244- [ ...cfg . productions ]
245- . filter ( ( [ _ , p ] ) => p . some ( s => s . length === 1 && s [ 0 ] . kind === TokenKind . Terminal && s [ 0 ] . identifier === i ) )
246- . map ( ( [ nt , _ ] ) => nt )
247- )
241+ const producers = new Set < string > (
242+ [ ...cfg . productions ]
243+ . filter ( ( [ _ , p ] ) => p . some ( s => s . length === 1 && s [ 0 ] . kind === TokenKind . Terminal && s [ 0 ] . identifier === i ) )
244+ . map ( ( [ nt , _ ] ) => nt )
248245) ;
246+ table . set ( i , producers ) ;
247+ if ( producers . size > 0 ) {
248+ callStep ( 1 , `Add non-terminals that directly can produce the string "${ i } ) ;
249+ }
250+ else {
251+ callStep ( 1 , `No non-terminals can directly produce the string "${ i } ) ;
252+ }
249253}
250254}
251- callStep ( ) ;
252255
253256for ( let l = 2 ; l <= string . length ; l ++ ) {
254257for ( let i = 0 ; i <= string . length - l ; i ++ ) {
255258const part = string . substr ( i , l ) ;
256259if ( ! table . has ( part ) ) {
257260const seqs = getSequencesFor ( part ) ;
258- table . set (
259- part ,
260- new Set < string > (
261- [ ...cfg . productions ]
262- . filter ( ( [ _ , p ] ) =>
263- p . some ( s =>
264- seqs . some ( seq =>
265- seq . every ( ( t , i ) =>
266- i < s . length &&
267- s [ i ] . kind === TokenKind . NonTerminal &&
268- s [ i ] . identifier === t
269- )
261+ const producers = new Set < string > (
262+ [ ...cfg . productions ]
263+ . filter ( ( [ _ , p ] ) =>
264+ p . some ( s =>
265+ seqs . some ( seq =>
266+ seq . every ( ( t , i ) =>
267+ i < s . length &&
268+ s [ i ] . kind === TokenKind . NonTerminal &&
269+ s [ i ] . identifier === t
270270)
271271)
272272)
273- . map ( ( [ nt , _ ] ) => nt )
274- )
273+ )
274+ . map ( ( [ nt , _ ] ) => nt )
275275) ;
276+ table . set ( part , producers ) ;
277+ if ( producers . size > 0 ) {
278+ callStep ( l , `Add productions that can produce the string "${ part } ) ;
279+ }
280+ else {
281+ callStep ( l , `No productions can produce the string "${ part } ) ;
282+ }
276283}
277284}
278- callStep ( ) ;
279285}
280286
281287return table ;