import { Rule as EbnfRule , InputType , Grouping , Optionals } from './ebnfParser' ; export interface IProduction { /** nameof ? extends typeof Symbols.Symbol */ result : string ; /** nameof (? extends typeof Symbols.Symbol)[] */ inputs : string [ ] ; } function toProductionInputs ( inputs , prodInputs = [ [ ] ] ) { for ( const input of inputs ) { let nextInput = [ ] ; if ( typeof input === 'string' ) { nextInput = [ [ input ] ] ; } else if ( input instanceof Grouping ) { for ( const groupingProd of input . inputs ) { nextInput . push ( ... toProductionInputs ( groupingProd ) ) ; } } else if ( input instanceof Optionals ) { for ( const optionProd of input . inputs ) { nextInput . push ( ... toProductionInputs ( optionProd ) ) ; } nextInput . push ( [ ] ) ; } const newProdInputs = [ ] ; for ( const prevInputs of prodInputs ) { for ( const nextInputs of nextInput ) { const inputs = [ ... prevInputs , ... nextInputs ] ; newProdInputs . push ( inputs ) ; } } prodInputs = newProdInputs ; } return prodInputs ; } function toProductions ( rule ) { const productions = [ ] ; for ( const ruleInputs of rule . inputs ) { const prodInputs = [ ] ; for ( const prodInputs of toProductionInputs ( ruleInputs ) ) { productions . push ( { result : rule . result , inputs : prodInputs } ) ; } } return productions ; } export class Productions { private readonly rules : { [ name ] : IProduction [ ] ; } ; public readonly startSymbols : string [ ] ; constructor ( rules ) { this . rules = { } ; for ( const rule of rules ) { this . rules [ rule . result ] = toProductions ( rule ) ; } this . startSymbols = [ ] ; for ( const rule of rules ) { if ( this . startSymbols . indexOf ( rule . result ) < 0 && this . getProductionsUsing ( rule . result ) . length === 0 ) { this . startSymbols . push ( rule . result ) ; } } } public isTokenClass ( symbol ) { return ! ( symbol in this . rules ) ; } public getProductionsFor ( symbolClass ) { return this . rules [ symbolClass ] || [ ] ; } private getProductionsUsing ( symbolClass ) { const productionsUsing = [ ] ; for ( let result in this . rules ) { const prods = this . rules [ result ] ; for ( const prod of prods ) { if ( prod . inputs . indexOf ( symbolClass ) >= 0 ) { productionsUsing . push ( prod ) ; } } } return productionsUsing ; } private firstImpl ( result , visited ) { if ( this . isTokenClass ( result ) ) { return [ result ] ; } const firsts = [ ] ; visited . push ( result ) ; for ( const prod of this . getProductionsFor ( result ) ) { const first = prod . inputs [ 0 ] ; if ( this . isTokenClass ( first ) ) { if ( firsts . indexOf ( first ) < 0 ) { firsts . push ( first ) ; } } else if ( visited . indexOf ( first ) < 0 ) { for ( const symbol of this . firstImpl ( first , visited ) ) { if ( firsts . indexOf ( symbol ) < 0 ) { firsts . push ( symbol ) ; } } } } return firsts ; } public first ( result ) { return this . firstImpl ( result , [ ] ) ; } private followsImpl ( resultSymbol , visited ) { const follows = [ "EOF" ] ; visited . push ( resultSymbol ) ; for ( const prod of this . getProductionsUsing ( resultSymbol ) ) { const idx = prod . inputs . indexOf ( resultSymbol ) ; let recFollows = [ ] ; if ( idx === prod . inputs . length - 1 ) { if ( visited . indexOf ( prod . result ) < 0 ) { recFollows = this . followsImpl ( prod . result , visited ) ; } } else { recFollows = this . first ( prod . inputs [ idx + 1 ] ) ; } for ( const sym of recFollows ) { if ( follows . indexOf ( sym ) < 0 ) { follows . push ( sym ) ; } } } return follows ; } public follows ( resultSymbol ) { return this . followsImpl ( resultSymbol , [ ] ) ; } }