Designing a preliminary Earley parser using Mathematica
Author
Shrohan Mohapatra
Title
Designing a preliminary Earley parser using Mathematica
Description
Here I have showed the design and working of the Earley parser using some file-handling and string commands
Category
Working Material
Keywords
URL
http://www.notebookarchive.org/2021-02-4nj5nff/
DOI
https://notebookarchive.org/2021-02-4nj5nff
Date Added
2021-02-10
Date Last Modified
2021-02-10
File Size
115.41 kilobytes
Supplements
Rights
CC BY 4.0
Download
Open in Wolfram Cloud
EarleyParser[filename_,inputWord_]:=Block[{predictor,scanner,completer,stringText,listA,i,grammar1,words,S1,k,stateIndex,state,X,α,β,posDot,S3,finop},SetAttributes[predictor,{HoldFirst}];SetAttributes[scanner,{HoldFirst}];SetAttributes[completer,{HoldFirst}];predictor[S_,stateItem_,k_,grammar_]:=Block[{B1,i1,positionDot,S2=S,package},B1=Part[stateItem,1,2];positionDot=Part[StringPosition[B1,"."],1,1];If[positionDotStringLength[B1],Return[]];B1=StringTake[B1,{positionDot+1,positionDot+1}];If[Not[65≤Part[ToCharacterCode[B1]]≤90],Return[]];For[i1=1,i1≤Length[grammar],i1++,package={{Part[grammar,i1,1],"."<>Part[grammar,i1,2]},k};If[Part[grammar,i1,1]B1,If[MemberQ[Part[S2,k],package]False,AppendTo[Part[S2,k],package]]]];S=S2;];scanner[S_,stateItem_,k_,word_]:=Block[{A1,B1,j1,i1,positionDot,S2=S,alpha,beta,a,package},A1=Part[stateItem,1,1];B1=Part[stateItem,1,2];j1=Part[stateItem,2];positionDot=Part[StringPosition[B1,"."],1,1];If[positionDotStringLength[B1],Return[]];a=StringTake[B1,{positionDot+1,positionDot+1}];If[Not[97≤Part[ToCharacterCode[B1]]≤122],Return[]];alpha=StringTake[B1,{1,positionDot-1}];If[positionDot+2≤StringLength[B1],beta=StringTake[B1,{positionDot+2,StringLength[B1]}];,beta=""];If[k≤StringLength[word],If[StringTake[word,{k,k}]a,package={{A1,alpha<>a<>"."<>beta},j1};If[MemberQ[Part[S2,k+1],package]False,AppendTo[Part[S2,k+1],{{A1,alpha<>a<>"."<>beta},j1}]];]];S=S2;];completer[S_,stateItem_,k_]:=Block[{B,γ,S2=S,x,m,A,alpha,B1,beta,positionDot,j1,segment,package},B=Part[stateItem,1,1];γ=StringTake[Part[stateItem,1,2],{1,StringLength[Part[stateItem,1,2]]-1}];x=Part[stateItem,2];For[m=1,m≤Length[Part[S2,x]],m++,A=Part[S2,x,m,1,1];segment=Part[S2,x,m,1,2];positionDot=Part[StringPosition[segment,"."],1,1];j1=Part[S2,x,m,2];alpha=If[positionDot≥1,StringTake[segment,{1,positionDot-1}],""];beta=If[positionDot+2≤StringLength[segment],StringTake[segment,{positionDot+2,StringLength[segment]}],""];B1=If[positionDot+1≤StringLength[segment],StringTake[segment,{positionDot+1,positionDot+1}],""];If[B1B,package={{A,alpha<>B<>"."<>beta},j1};If[MemberQ[Part[S2,k],package]False,AppendTo[Part[S2,k],package]];]];S=S2;];stringText=Import[filename];listA=TextWords[stringText];grammar1=Table[None,{j,1,Length[listA]/2}];For[i=1,i≤Length[listA]/2,i++,grammar1[[i]]={listA[[2*i-1]],listA[[2*i]]};];words=inputWord;S1=Table[{},StringLength[words]+1];AppendTo[Part[S1,1],{{Part[grammar1,1,1],"."<>Part[grammar1,1,2]},1}];finop={{Part[grammar1,1,1],Part[grammar1,1,2]<>"."},1};For[k=1,k≤StringLength[words]+1,k++,For[stateIndex=1,stateIndex≤Length[Part[S1,k]],stateIndex++,state=Part[S1,k,stateIndex];X=Part[state,1,1];posDot=Part[StringPosition[Part[state,1,2],"."],1,1];α=If[posDot≥1,StringTake[Part[state,1,2],{1,posDot-1}],""];β=If[posDot+1≤StringLength[Part[state,1,2]],StringTake[Part[state,1,2],{posDot+1,StringLength[Part[state,1,2]]}],""];If[StringLength[β]≠0,If[65≤Part[ToCharacterCode[StringTake[β,{1,1}]],1]≤90,predictor[S1,state,k,grammar1],If[97≤Part[ToCharacterCode[StringTake[β,{1,1}]],1]≤122,scanner[S1,state,k,words]]],completer[S1,state,k]]]];Return[MemberQ[Part[S1,StringLength[words]+1],finop]];]
ReadString[NotebookDirectory[]<>"grammarText7.txt"]
G -> SS -> SpMS -> MM -> MsTM -> TT -> x
EarleyParser[NotebookDirectory[]<>"grammarText7.txt","xsxpxsx"]
True
EarleyParser[NotebookDirectory[]<>"grammarText7.txt","xsxpxx"]
False
ReadString[NotebookDirectory[]<>"grammarText1.txt"]
G -> SS -> aSbS -> ab
EarleyParser[NotebookDirectory[]<>"grammarText1.txt","ab"]
True
EarleyParser[NotebookDirectory[]<>"grammarText1.txt","abb"]
False
ReadString[NotebookDirectory[]<>"grammarText6.txt"]
G -> SS -> aSbS -> bSaS -> abS -> ba
EarleyParser[NotebookDirectory[]<>"grammarText6.txt","abba"]
False
EarleyParser[NotebookDirectory[]<>"grammarText6.txt","aabb"]
True
EarleyParser[NotebookDirectory[]<>"grammarText6.txt","aababb"]
True
ReadString[NotebookDirectory[]<>"grammarText4.txt"]
G -> SS -> SSS -> a
EarleyParser[NotebookDirectory[]<>"grammarText4.txt","aaa"]
True
ReadString[NotebookDirectory[]<>"grammarText8.txt"]
G -> SS -> aSbS -> SSS -> SpSS -> ScSS -> SsS -> x
EarleyParser[NotebookDirectory[]<>"grammarText8.txt","xcxs"]
True
EarleyParser[NotebookDirectory[]<>"grammarText8.txt","axpxbs"]
True
(*Toaccommodatetheothercharactersinanygivenlanguageorgrammar'salphabet....*)
EarleyParser[filename_,inputWord_]:=Block[{predictor,scanner,completer,charDetect,stringText,listA,i,grammar1,words,S1,k,stateIndex,state,X,α,β,posDot,S3,finop},SetAttributes[predictor,{HoldFirst}];SetAttributes[scanner,{HoldFirst}];SetAttributes[completer,{HoldFirst}];charDetect[x_]:=Or[32≤Part[ToCharacterCode[x],1]≤64,91≤Part[ToCharacterCode[x],1]≤126];predictor[S_,stateItem_,k_,grammar_]:=Block[{B1,i1,positionDot,S2=S,package},B1=Part[stateItem,1,2];positionDot=Part[StringPosition[B1,"."],1,1];If[positionDotStringLength[B1],Return[]];B1=StringTake[B1,{positionDot+1,positionDot+1}];If[Not[65≤Part[ToCharacterCode[B1]]≤90],Return[]];For[i1=1,i1≤Length[grammar],i1++,package={{Part[grammar,i1,1],"."<>Part[grammar,i1,2]},k};If[Part[grammar,i1,1]B1,If[MemberQ[Part[S2,k],package]False,AppendTo[Part[S2,k],package]]]];S=S2;];scanner[S_,stateItem_,k_,word_]:=Block[{A1,B1,j1,i1,positionDot,S2=S,alpha,beta,a,package},A1=Part[stateItem,1,1];B1=Part[stateItem,1,2];j1=Part[stateItem,2];positionDot=Part[StringPosition[B1,"."],1,1];If[positionDotStringLength[B1],Return[]];a=StringTake[B1,{positionDot+1,positionDot+1}];If[Not[charDetect[a]],Return[]];alpha=StringTake[B1,{1,positionDot-1}];If[positionDot+2≤StringLength[B1],beta=StringTake[B1,{positionDot+2,StringLength[B1]}];,beta=""];If[k≤StringLength[word],If[StringTake[word,{k,k}]a,package={{A1,alpha<>a<>"."<>beta},j1};If[MemberQ[Part[S2,k+1],package]False,AppendTo[Part[S2,k+1],{{A1,alpha<>a<>"."<>beta},j1}]];]];S=S2;];completer[S_,stateItem_,k_]:=Block[{B,γ,S2=S,x,m,A,alpha,B1,beta,positionDot,j1,segment,package},B=Part[stateItem,1,1];γ=StringTake[Part[stateItem,1,2],{1,StringLength[Part[stateItem,1,2]]-1}];x=Part[stateItem,2];For[m=1,m≤Length[Part[S2,x]],m++,A=Part[S2,x,m,1,1];segment=Part[S2,x,m,1,2];positionDot=Part[StringPosition[segment,"."],1,1];j1=Part[S2,x,m,2];alpha=If[positionDot≥1,StringTake[segment,{1,positionDot-1}],""];beta=If[positionDot+2≤StringLength[segment],StringTake[segment,{positionDot+2,StringLength[segment]}],""];B1=If[positionDot+1≤StringLength[segment],StringTake[segment,{positionDot+1,positionDot+1}],""];If[B1B,package={{A,alpha<>B<>"."<>beta},j1};If[MemberQ[Part[S2,k],package]False,AppendTo[Part[S2,k],package]];]];S=S2;];stringText=Import[filename];listA=TextWords[stringText];grammar1=Table[None,{j,1,Length[listA]/2}];For[i=1,i≤Length[listA]/2,i++,grammar1[[i]]={listA[[2*i-1]],listA[[2*i]]};];words=inputWord;Print[listA];S1=Table[{},StringLength[words]+1];AppendTo[Part[S1,1],{{Part[grammar1,1,1],"."<>Part[grammar1,1,2]},1}];finop={{Part[grammar1,1,1],Part[grammar1,1,2]<>"."},1};For[k=1,k≤StringLength[words]+1,k++,For[stateIndex=1,stateIndex≤Length[Part[S1,k]],stateIndex++,state=Part[S1,k,stateIndex];X=Part[state,1,1];posDot=Part[StringPosition[Part[state,1,2],"."],1,1];α=If[posDot≥1,StringTake[Part[state,1,2],{1,posDot-1}],""];β=If[posDot+1≤StringLength[Part[state,1,2]],StringTake[Part[state,1,2],{posDot+1,StringLength[Part[state,1,2]]}],""];If[StringLength[β]≠0,If[65≤Part[ToCharacterCode[StringTake[β,{1,1}]],1]≤90,predictor[S1,state,k,grammar1],If[charDetect[StringTake[β,{1,1}]],scanner[S1,state,k,words]]],completer[S1,state,k]]]];Return[MemberQ[Part[S1,StringLength[words]+1],finop]];]
Part[ToCharacterCode["-"],1]
45
EarleyParser[NotebookDirectory[]<>"grammarText9.txt","(a+b)*"]
{G,S,S,(S),S,SS,S,S,S,S,S.S,S,S,S,a,S,b}
False
Block[{debugPortion},debugPortion[filename_]:=Block[{stringText,listA,grammar1,i,listB,listC},stringText=Import[filename];listA=StringSplit[stringText,"\n"];grammar1=Table[StringSplit[Part[listA,k]," -> "],{k,1,Length[listA]}];Print[grammar1];];debugPortion[NotebookDirectory[]<>"grammarText9.txt"]]
{{G,S},{S,(S)},{S,SS},{S,S+S},{S,S.S},{S,S*},{S,a},{S,b}}
EarleyParser[filename_,inputWord_]:=Block[{predictor,scanner,completer,charDetect,stringText,listA,i,grammar1,words,S1,k,stateIndex,state,X,α,β,posDot,S3,finop},SetAttributes[predictor,{HoldFirst}];SetAttributes[scanner,{HoldFirst}];SetAttributes[completer,{HoldFirst}];charDetect[x_]:=Or[32≤Part[ToCharacterCode[x],1]≤64,91≤Part[ToCharacterCode[x],1]≤126];predictor[S_,stateItem_,k_,grammar_]:=Block[{B1,i1,positionDot,S2=S,package},B1=Part[stateItem,1,2];positionDot=Part[StringPosition[B1,"."],1,1];If[positionDotStringLength[B1],Return[]];B1=StringTake[B1,{positionDot+1,positionDot+1}];If[Not[65≤Part[ToCharacterCode[B1]]≤90],Return[]];For[i1=1,i1≤Length[grammar],i1++,package={{Part[grammar,i1,1],"."<>Part[grammar,i1,2]},k};If[Part[grammar,i1,1]B1,If[MemberQ[Part[S2,k],package]False,AppendTo[Part[S2,k],package]]]];S=S2;];scanner[S_,stateItem_,k_,word_]:=Block[{A1,B1,j1,i1,positionDot,S2=S,alpha,beta,a,package},A1=Part[stateItem,1,1];B1=Part[stateItem,1,2];j1=Part[stateItem,2];positionDot=Part[StringPosition[B1,"."],1,1];If[positionDotStringLength[B1],Return[]];a=StringTake[B1,{positionDot+1,positionDot+1}];If[Not[charDetect[a]],Return[]];alpha=StringTake[B1,{1,positionDot-1}];If[positionDot+2≤StringLength[B1],beta=StringTake[B1,{positionDot+2,StringLength[B1]}];,beta=""];If[k≤StringLength[word],If[StringTake[word,{k,k}]a,package={{A1,alpha<>a<>"."<>beta},j1};If[MemberQ[Part[S2,k+1],package]False,AppendTo[Part[S2,k+1],{{A1,alpha<>a<>"."<>beta},j1}]];]];S=S2;];completer[S_,stateItem_,k_]:=Block[{B,γ,S2=S,x,m,A,alpha,B1,beta,positionDot,j1,segment,package},B=Part[stateItem,1,1];γ=StringTake[Part[stateItem,1,2],{1,StringLength[Part[stateItem,1,2]]-1}];x=Part[stateItem,2];For[m=1,m≤Length[Part[S2,x]],m++,A=Part[S2,x,m,1,1];segment=Part[S2,x,m,1,2];positionDot=Part[StringPosition[segment,"."],1,1];j1=Part[S2,x,m,2];alpha=If[positionDot≥1,StringTake[segment,{1,positionDot-1}],""];beta=If[positionDot+2≤StringLength[segment],StringTake[segment,{positionDot+2,StringLength[segment]}],""];B1=If[positionDot+1≤StringLength[segment],StringTake[segment,{positionDot+1,positionDot+1}],""];If[B1B,package={{A,alpha<>B<>"."<>beta},j1};If[MemberQ[Part[S2,k],package]False,AppendTo[Part[S2,k],package]];]];S=S2;];stringText=Import[filename];listA=StringSplit[stringText,"\n"];grammar1=Table[StringSplit[Part[listA,k]," -> "],{k,1,Length[listA]}];words=inputWord;S1=Table[{},StringLength[words]+1];AppendTo[Part[S1,1],{{Part[grammar1,1,1],"."<>Part[grammar1,1,2]},1}];finop={{Part[grammar1,1,1],Part[grammar1,1,2]<>"."},1};For[k=1,k≤StringLength[words]+1,k++,For[stateIndex=1,stateIndex≤Length[Part[S1,k]],stateIndex++,state=Part[S1,k,stateIndex];X=Part[state,1,1];posDot=Part[StringPosition[Part[state,1,2],"."],1,1];α=If[posDot≥1,StringTake[Part[state,1,2],{1,posDot-1}],""];β=If[posDot+1≤StringLength[Part[state,1,2]],StringTake[Part[state,1,2],{posDot+1,StringLength[Part[state,1,2]]}],""];If[StringLength[β]≠0,If[65≤Part[ToCharacterCode[StringTake[β,{1,1}]],1]≤90,predictor[S1,state,k,grammar1],If[charDetect[StringTake[β,{1,1}]],scanner[S1,state,k,words]]],completer[S1,state,k]]]];Return[MemberQ[Part[S1,StringLength[words]+1],finop]];]
ReadString[NotebookDirectory[]<>"grammarText4.txt"]
G -> SS -> SSS -> a
EarleyParser[NotebookDirectory[]<>"grammarText4.txt","aaaa"]
True
ReadString[NotebookDirectory[]<>"grammarText10.txt"]
G -> SS -> S+MS -> S-MS -> MM -> M*TM -> M/TM -> TT -> TTT -> 0T -> 1T -> 2T -> 3T -> 4T -> 5T -> 6T -> 7T -> 8T -> 9
EarleyParser[NotebookDirectory[]<>"grammarText10.txt","45-90+70+6*8/2"]
True
ReadString[NotebookDirectory[]<>"grammarText4.txt"]
G -> SS -> SSS -> a
EarleyParser[NotebookDirectory[]<>"grammarText4.txt","a"]
True
Cite this as: Shrohan Mohapatra, "Designing a preliminary Earley parser using Mathematica" from the Notebook Archive (2021), https://notebookarchive.org/2021-02-4nj5nff
Download
