@@ -42,48 +42,63 @@ export class ContextFreeGrammar {
4242}
4343}
4444
45+ //#region Computations
4546public parse ( string :string ) :ParseTree | null {
46- if ( this . start != null ) {
47- const queue = new Array < [ Array < Token > , Array < Token > , string ] > ( [ new Array < Token > ( ) , [ Token . nonTerminal ( this . start ) ] , string ] ) ;
48- while ( queue . length > 0 ) {
49- const [ tree , [ token , ...rest ] , string ] = queue . shift ( ) ;
50- if ( token . kind === TokenKind . NonTerminal ) {
51- for ( const sequence of this . productions . get ( token . identifier ) ) {
52- queue . push ( [
53- [ ...tree , token ] ,
54- [ ...sequence , ...rest ] ,
55- string
56- ] ) ;
57- }
58- }
59- else if ( token . kind === TokenKind . Terminal ) {
60- if ( string . startsWith ( token . identifier ) ) {
61- if ( string . length === token . identifier . length && rest . length === 0 ) {
62- return this . constructTree ( [ ...tree , token ] ) ;
63- }
64- else if ( rest . length > 0 ) {
65- queue . push ( [
66- [ ...tree , token ] ,
67- rest ,
68- string . substring ( token . identifier . length )
69- ] ) ;
70- }
71- }
47+ if ( this . start == null ) {
48+ return null ;
49+ }
50+ if ( string . length > 0 ) {
51+ const cyk = this . cyk ( string ) ;
52+ if ( cyk == null || ! cyk . has ( string ) || ! cyk . get ( string ) . has ( this . start ) ) {
53+ return null ;
54+ }
55+ }
56+ else {
57+ if ( ! this . nullableNonTerminals ( ) . some ( t => t === this . start ) ) {
58+ return null ;
59+ }
60+ }
61+
62+ const queue = new Array < [ Array < Token > , Array < Token > , string ] > ( [ new Array < Token > ( ) , [ Token . nonTerminal ( this . start ) ] , string ] ) ;
63+ while ( queue . length > 0 ) {
64+ const [ tree , [ token , ...rest ] , string ] = queue . shift ( ) ;
65+ if ( token . kind === TokenKind . NonTerminal ) {
66+ for ( const sequence of this . productions . get ( token . identifier ) ) {
67+ queue . push ( [
68+ [ ...tree , token ] ,
69+ [ ...sequence , ...rest ] ,
70+ string
71+ ] ) ;
7272}
73- else if ( token . kind === TokenKind . Empty ) {
74- if ( string . length === 0 && rest . length === 0 ) {
73+ }
74+ else if ( token . kind === TokenKind . Terminal ) {
75+ if ( string . startsWith ( token . identifier ) ) {
76+ if ( string . length === token . identifier . length && rest . length === 0 ) {
7577return this . constructTree ( [ ...tree , token ] ) ;
7678}
7779else if ( rest . length > 0 ) {
7880queue . push ( [
7981[ ...tree , token ] ,
8082rest ,
81- string
83+ string . substring ( token . identifier . length )
8284] ) ;
8385}
8486}
8587}
88+ else if ( token . kind === TokenKind . Empty ) {
89+ if ( string . length === 0 && rest . length === 0 ) {
90+ return this . constructTree ( [ ...tree , token ] ) ;
91+ }
92+ else if ( rest . length > 0 ) {
93+ queue . push ( [
94+ [ ...tree , token ] ,
95+ rest ,
96+ string
97+ ] ) ;
98+ }
99+ }
86100}
101+
87102return null ;
88103}
89104private constructTree ( tokens :ReadonlyArray < Token > ) :ParseTree ;
@@ -122,7 +137,6 @@ export class ContextFreeGrammar {
122137throw new Error ( "Failed to construct the parse tree." ) ;
123138}
124139
125- //#region Computations
126140public generatingSymbols ( ) :Array < Token > ;
127141public generatingSymbols ( step :( symbols :Array < Token > ) => void ) :Array < Token > ;
128142public generatingSymbols ( step ?:( symbols :Array < Token > ) => void ) :Array < Token > {