/** Ċ Ġ* ĠCopyright Ġ( C ) Ġ 2 0 1 8 ĠDr . ĠDavid ĠH . ĠA keh ur st Ġ( http :// dr . david . h . ake hur st . net ) Ċ Ġ* Ċ Ġ* ĠLicensed Ġunder Ġthe ĠApache ĠLicense , ĠVersion Ġ 2 . 0 Ġ( the Ġ" License "); Ċ Ġ* Ġyou Ġmay Ġnot Ġuse Ġthis Ġfile Ġexcept Ġin Ġcompliance Ġwith Ġthe ĠLicense . Ċ Ġ* ĠYou Ġmay Ġobtain Ġa Ġcopy Ġof Ġthe ĠLicense Ġat Ċ Ġ* Ċ Ġ* ĠĠĠĠĠĠĠĠ Ġhttp :// www . apache . org / licenses / LICENSE - 2 . 0 Ċ Ġ* Ċ Ġ* ĠUnless Ġrequired Ġby Ġapplicable Ġlaw Ġor Ġagreed Ġto Ġin Ġwriting , Ġsoftware Ċ Ġ* Ġdistributed Ġunder Ġthe ĠLicense Ġis Ġdistributed Ġon Ġan Ġ" AS ĠIS " ĠBASIS , Ċ Ġ* ĠWITHOUT ĠWARRANTIES ĠOR ĠCONDITIONS ĠOF ĠANY ĠKIND , Ġeither Ġexpress Ġor Ġimplied . Ċ Ġ* ĠSee Ġthe ĠLicense Ġfor Ġthe Ġspecific Ġlanguage Ġgoverning Ġpermissions Ġand Ċ Ġ* Ġlimitations Ġunder Ġthe ĠLicense . Ċ Ġ*/ Ċ Ċ package Ġnet . ake hur st . language . ag l . parser Ċ Ċ import Ġnet . ake hur st . language . ag l . autom aton . Transition Ċ import Ġnet . ake hur st . language . ag l . runtime . graph . Grow ing Node Ċ import Ġnet . ake hur st . language . ag l . runtime . graph . Parse Graph Ċ import Ġnet . ake hur st . language . ag l . runtime . graph . Previous Info Ċ import Ġnet . ake hur st . language . ag l . runtime . structure . Look ahead Set Ċ import Ġnet . ake hur st . language . ag l . runtime . structure . Runtime Rule Ċ import Ġnet . ake hur st . language . ag l . runtime . structure . Runtime Rule Kind Ċ import Ġnet . ake hur st . language . ag l . runtime . structure . Runtime Rule Set Ċ import Ġnet . ake hur st . language . ag l . sp pt . SP PT Leaf From Input Ċ import Ġnet . ake hur st . language . ag l . sp pt . Shared Packed ParseTree Default Ċ import Ġnet . ake hur st . language . api . parser . Input Location Ċ import Ġnet . ake hur st . language . api . parser . Parse FailedException Ċ import Ġnet . ake hur st . language . api . processor . Automaton Kind Ċ import Ġnet . ake hur st . language . api . sp pt . SP PT Leaf Ċ import Ġnet . ake hur st . language . api . sp pt . Shared Packed ParseTree Ċ import Ġkotlin . math . max Ċ Ċ internal Ġclass ĠScan On Demand Parser ( ĊĠĠĠ Ġinternal Ġval Ġruntime Rule Set : ĠRuntime Rule Set Ċ ) Ġ: ĠParser Ġ{ ĊĊĠĠĠ Ġprivate Ġvar Ġruntime Parser : ĠRuntime Parser ? Ġ= Ġnull ĊĊĠĠĠ Ġoverride Ġfun Ġinterrupt ( message : ĠString ) Ġ{ ĊĠĠĠĠĠĠĠ Ġthis . runtime Parser ?. interrupt ( message ) ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġoverride Ġfun Ġbuild For ( goal Rule Name : ĠString , Ġautom aton Kind : ĠAutom aton Kind ) Ġ{ ĊĠĠĠĠĠĠĠ Ġthis . runtime Rule Set . build For ( goal Rule Name , Ġautom aton Kind ) ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġoverride Ġfun Ġparse For Goal ( goal Rule Name : ĠString , Ġinput Text : ĠString , Ġautom aton Kind : ĠAutom aton Kind ): ĠShared Packed ParseTree Ġ{ ĊĠĠĠĠĠĠĠ Ġval Ġgoal Rule Ġ= Ġthis . runtime Rule Set . find Runtime Rule ( goal Rule Name ) ĊĠĠĠĠĠĠĠ Ġval Ġinput Ġ= ĠInput FromString ( this . runtime Rule Set . terminal Rules . size , Ġinput Text ) ĊĠĠĠĠĠĠĠ Ġval Ġs 0 Ġ= Ġruntime Rule Set . fetch State Set For ( goal Rule , autom aton Kind ). start State ĊĠĠĠĠĠĠĠ Ġval Ġskip State Set Ġ= Ġruntime Rule Set . skip Parser State Set ĊĠĠĠĠĠĠĠ Ġval Ġrp Ġ= ĠRuntime Parser ( s 0 . state Set , Ġskip State Set , Ġgoal Rule , Ġinput ) ĊĠĠĠĠĠĠĠ Ġthis . runtime Parser Ġ= Ġrp ĊĊĠĠĠĠĠĠĠ Ġrp . start ( 0 , ĠLook ahead Set . EOT ) ĊĠĠĠĠĠĠĠ Ġvar Ġse asons Ġ= Ġ 1 ĊĠĠĠĠĠĠĠ Ġvar Ġmax Num Head s Ġ= Ġrp . graph . grow ing Head . size ĊĠĠĠĠĠĠĠ Ġvar Ġtotal Work Ġ= Ġmax Num Head s ĊĊĠĠĠĠĠĠĠ Ġdo Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġrp . grow ( false ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġse asons ++ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġmax Num Head s Ġ= Ġmax ( max Num Head s , Ġrp . graph . grow ing Head . size ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġtotal Work Ġ+= Ġrp . graph . grow ing Head . size ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ// Ġ} Ġwhile Ġ( rp . graph . can Grow ) ĊĠĠĠĠĠĠĠ Ġ} Ġwhile Ġ( rp . graph . can Grow Ġ&& Ġ( rp . graph . goals . isEmpty () Ġ|| Ġrp . graph . goal Matched All . not ())) ĊĠĠĠĠĠĠĠ Ġ// TODO : Ġwhen Ġparsing Ġan Ġambiguous Ġgrammar , ĊĠĠĠĠĠĠĠ Ġ// Ġhow Ġto Ġknow Ġwe Ġhave Ġfound Ġall Ġgoals ? Ġ- Ġkeep Ġgoing Ġuntil Ġc ang row Ġis Ġfalse ĊĠĠĠĠĠĠĠ Ġ// Ġbut Ġ- Ġhow Ġto Ġstop Ġ.. Ġsome Ġgrammar s Ġdon 't Ġstop Ġif Ġwe Ġdon 't Ġdo Ġtest Ġfor Ġa Ġgoal ! ĊĠĠĠĠĠĠĠ Ġ// Ġe . g . Ġleft Recursive . test _ aa ĊĠĠĠĠĠĠĠ Ġ// Ġe . g . Ġtest _ a 1 b O a 2 . amb iguous _ a ĊĊĠĠĠĠĠĠĠ Ġval Ġmatch Ġ= Ġrp . graph . longest Match ( se asons , Ġmax Num Head s , Ġfalse ) ĊĠĠĠĠĠĠĠ Ġreturn Ġif Ġ( match Ġ!= Ġnull ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ ĠShared Packed ParseTree Default ( match , Ġse asons , Ġmax Num Head s ) ĊĠĠĠĠĠĠĠ Ġ} Ġelse Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġnext Expected Ġ= Ġthis . find Next Expected After Error ( rp , Ġrp . graph , Ġinput ) Ġ// this Ġpossibly Ġmod ifies Ġrp Ġand Ġhence Ġmay Ġchange Ġthe Ġlongest Last G rown ĊĠĠĠĠĠĠĠĠĠĠĠ Ġthrow Error ( input , Ġrp , Ġnext Expected , Ġse asons , Ġmax Num Head s ) ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġprivate Ġfun Ġthrow Error ( ĊĠĠĠĠĠĠĠ Ġinput : ĠInput FromString , ĊĠĠĠĠĠĠĠ Ġrp : ĠRuntime Parser , ĊĠĠĠĠĠĠĠ Ġnext Expected : ĠPair < Input Location , ĠSet < Runtime Rule >>, ĊĠĠĠĠĠĠĠ Ġse asons : ĠInt , ĊĠĠĠĠĠĠĠ Ġmax Num Head s : ĠInt ĊĠĠĠ Ġ): ĠShared Packed ParseTree Default Ġ{ ĊĠĠĠĠĠĠĠ Ġval Ġl lg Ġ= Ġrp . longest Last G rown ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ?: Ġthrow ĠParse FailedException (" Nothing Ġparsed ", Ġnull , ĠInput Location ( 0 , Ġ 0 , Ġ 1 , Ġ 0 ), Ġempty Set (), " ") ĊĊĠĠĠĠĠĠĠ Ġval Ġlast Location Ġ= Ġnext Expected . first ĊĠĠĠĠĠĠĠ Ġval Ġexp Ġ= Ġnext Expected . second ĊĠĠĠĠĠĠĠ Ġ// val Ġexpected Ġ= Ġexp ĊĠĠĠĠĠĠĠ Ġ// ĠĠĠĠĠĠĠ Ġ. filter Ġ{ Ġit . number Ġ>= Ġ 0 Ġ&& Ġit . isEmpty Rule . not () Ġ} ĊĠĠĠĠĠĠĠ Ġ// ĠĠĠĠĠĠĠ Ġ. map Ġ{ Ġthis . runtime Rule Set . first Terminal s [ it . number ] Ġ} ĊĠĠĠĠĠĠĠ Ġ// ĠĠĠĠĠĠĠ Ġ. flatMap Ġ{ Ġit . map Ġ{ Ġit . value Ġ} Ġ} ĊĠĠĠĠĠĠĠ Ġ// ĠĠĠĠĠĠĠ Ġ. toSet () ĊĠĠĠĠĠĠĠ Ġval Ġexpected Ġ= Ġexp . map Ġ{ Ġit . tag Ġ}. toSet () ĊĠĠĠĠĠĠĠ Ġval Ġerror Pos Ġ= Ġlast Location . position Ġ+ Ġlast Location . length ĊĠĠĠĠĠĠĠ Ġval Ġerror Length Ġ= Ġ 1 Ġ// TODO : Ġdetermine Ġa Ġbetter Ġlength ĊĠĠĠĠĠĠĠ Ġval Ġlocation Ġ= Ġinput . location For ( error Pos , error Length )// Input Location ( error Pos , Ġerror Column , Ġerror Line , Ġerror Length ) ĊĊĠĠĠĠĠĠĠ Ġ// val Ġexpected Ġ= Ġempty Set < String >() ĊĠĠĠĠĠĠĠ Ġ// Ġval Ġlocation Ġ= Ġnext Expected . first // Input Location ( 0 , 0 , 0 , 0 ) ĊĠĠĠĠĠĠĠ Ġthrow ĠParse FailedException (" Could Ġnot Ġmatch Ġgoal ", ĠShared Packed ParseTree Default ( ll g , Ġse asons , Ġmax Num Head s ), Ġlocation , Ġexpected , Ġrp . graph . input . context In Text ( location . position )) ĊĊĠĠĠ Ġ} ĊĊĠĠĠ Ġprivate Ġfun Ġfind Next Expected After Error ( rp : ĠRuntime Parser , Ġgraph : ĠParse Graph , Ġinput : ĠInput FromString ): ĠPair < Input Location , ĠSet < Runtime Rule >> Ġ{ ĊĠĠĠĠĠĠĠ Ġ// If Ġthere Ġis Ġan Ġerror , Ġit Ġis Ġbecause Ġparsing Ġhas Ġstopped Ġbefore Ġfinding Ġa Ġgoal . ĊĠĠĠĠĠĠĠ Ġ// Ġparsing Ġcould Ġhave Ġstopped Ġbecause ĊĠĠĠĠĠĠĠ Ġ// Ġ Ġ- Ġno Ġmore Ġinput Ġand Ġwe Ġhave Ġnot Ġreached Ġa Ġgoal ĊĠĠĠĠĠĠĠ Ġ// Ġ Ġ- Ġno Ġnew Ġgrowing - head Ġbecause Ġno Ġaction / transition Ġtaken , Ġbecause ĊĠĠĠĠĠĠĠ Ġ// Ġ Ġ-- Ġlook ahead Ġis Ġwrong Ġwhen Ġdoing Ġan Ġaction ĊĠĠĠĠĠĠĠ Ġ// Ġ Ġ-- Ġother Ġgu ards Ġeliminate Ġthe Ġtransition ĊĠĠĠĠĠĠĠ Ġ// Ġ Ġ- Ġaction Ġcauses Ġno Ġchange Ġ( I Ġthink Ġthis Ġshould Ġnever Ġhappen ) ĊĠĠĠĠĠĠĠ Ġ// Ġif Ġit Ġstopped Ġbecause Ġof Ġlook ahead ... it Ġmaybe Ġthat Ġwe Ġcan Ġparse Ġone Ġmore Ġleaf , ĊĠĠĠĠĠĠĠ Ġ// ĊĊĠĠĠĠĠĠĠ Ġrp . reset Graph To Last G rown () ĊĠĠĠĠĠĠĠ Ġrp . try Grow Width Once () ĊĠĠĠĠĠĠĠ Ġval Ġposs Ġ= Ġif Ġ( graph . can Grow ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġrp . try Grow Height Or G raft () ĊĠĠĠĠĠĠĠ Ġ} Ġelse Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġrp . reset Graph To Last G rown () ĊĠĠĠĠĠĠĠĠĠĠĠ Ġrp . try Grow Height Or G raft () ĊĠĠĠĠĠĠĠ Ġ} ĊĊĠĠĠĠĠĠĠ Ġval Ġr Ġ= Ġposs . map Ġ{ Ġlg Ġ-> ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ// Ġcompute Ġnext Ġexpected Ġitem / Runtime Rule ĊĠĠĠĠĠĠĠĠĠĠĠ Ġwhen Ġ( lg . runtime Rules . first (). kind ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ ĠRuntime Rule Kind . GO AL Ġ-> Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġtr s Ġ= Ġlg . currentState . transitions ( null ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġexp Ġ= Ġtr s . flatMap Ġ{ Ġtr Ġ-> ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġwhen Ġ( tr . action ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ ĠTransition . Parse Action . GO AL Ġ-> Ġempty Set < Runtime Rule >() ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ ĠTransition . Parse Action . WIDTH Ġ-> Ġlg . currentState . first Of ( lg . look ahead ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ ĠTransition . Parse Action . EMB ED Ġ-> ĠTODO () ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ ĠTransition . Parse Action . HEIGHT Ġ-> Ġrp . state Set . create With Parent ( tr . look ahead Guard , Ġlg . look ahead ). content ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ ĠTransition . Parse Action . GR AFT Ġ-> Ġlg . previous . values . map Ġ{ Ġit . node . look ahead Ġ}. flatMap Ġ{ Ġrp . state Set . create With Parent ( tr . look ahead Guard , Ġit ). content Ġ} ĊĠĠĠ Ġ// ĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ ĠTransition . Parse Action . GR AFT _ OR _ HEIGHT Ġ-> ĠTODO () ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ ĠPair ( lg , Ġexp ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġelse Ġ-> Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġx Ġ= Ġlg . previous . values . flatMap Ġ{ Ġit Ġ-> ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġprev Ġ= Ġit . node ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġtr s Ġ= Ġlg . currentState . transitions ( prev . currentState ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ. filter Ġ{ Ġit . runtime Guard ( it , Ġprev , Ġprev . currentState . rule Positions ) Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġexp Ġ= Ġtr s . flatMap Ġ{ Ġtr Ġ-> ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġwhen Ġ( tr . action ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ ĠTransition . Parse Action . GO AL Ġ-> Ġempty Set < Runtime Rule >() ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ ĠTransition . Parse Action . WIDTH Ġ-> Ġlg . currentState . first Of ( lg . look ahead ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ ĠTransition . Parse Action . EMB ED Ġ-> Ġlg . currentState . first Of ( lg . look ahead ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ ĠTransition . Parse Action . HEIGHT Ġ-> Ġrp . state Set . create With Parent ( tr . look ahead Guard , Ġlg . look ahead ). content ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ ĠTransition . Parse Action . GR AFT Ġ-> Ġrp . state Set . create With Parent ( tr . look ahead Guard , Ġprev . look ahead ). content ĊĠĠĠĠĠĠ Ġ// ĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ ĠTransition . Parse Action . GR AFT _ OR _ HEIGHT Ġ-> ĠTODO () ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġexp ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ ĠPair ( lg , Ġx ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġval Ġmax Last Location : ĠInput Location Ġ= Ġr . map Ġ{ Ġinput . location For ( it . first . start Position , Ġit . first . next Input Position - it . first . start Position ) Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ. max By OrNull Ġ{ Ġit . end Position Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ?: Ġerror (" Internal Ġerror ") ĊĠĠĠĠĠĠĠ Ġval Ġfr Ġ= Ġr . filter Ġ{ Ġit . first . next Input Position Ġ== Ġmax Last Location . end Position Ġ} ĊĠĠĠĠĠĠĠ Ġval Ġres Ġ= Ġfr . flatMap Ġ{ Ġit . second Ġ}. toSet () ĊĠĠĠĠĠĠĠ Ġreturn ĠPair ( max Last Location , Ġres ) ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġprivate Ġfun Ġfind Next Expected ( rp : ĠRuntime Parser , Ġgraph : ĠParse Graph , Ġinput : ĠInput FromString , Ġg ns : ĠList < Pair < Grow ing Node , ĠCollection < Previous Info >? >> ): ĠSet < Runtime Rule > Ġ{ ĊĠĠĠĠĠĠĠ Ġ// ĠTODO : Ġwhen Ġthe Ġlast Ġleaf Ġis Ġfollowed Ġby Ġthe Ġnext Ġexpected Ġleaf , Ġif Ġthe Ġresult Ġcould Ġbe Ġthe Ġlast Ġleaf ĊĊĠĠĠĠĠĠĠ Ġval Ġmatches Ġ= Ġg ns . to Mutable List () ĊĠĠĠĠĠĠĠ Ġ// Ġtry Ġgrow Ġlast Ġleaf Ġwith Ġno Ġlook ahead ĊĠĠĠĠĠĠĠ Ġfor Ġ( gn Ġin Ġrp . last G rown Linked ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġgn index Ġ= ĠGrow ing Node . index From Grow ing Children ( gn . currentState , Ġgn . look ahead , Ġgn . children ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġgraph . grow ing Head [ gn index ] Ġ= Ġgn ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġdo Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġrp . grow ( true ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġfor Ġ( gn Ġin Ġrp . last G rown ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ// Ġmay Ġneed Ġto Ġchange Ġthis Ġto Ġfinal Input Pos ! ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( input . is End ( gn . next Input Position )) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ// Ġlast G rown Ġis Ġcombination Ġof Ġgrowing Ġand Ġto Grow ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ// Ġ Ġthe Ġprevious Ġof Ġgro ow ing Ġis Ġon Ġthe Ġnode , Ġof Ġto Grow Ġis Ġin Ġthe ĠMap ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġprev Ġ= Ġrp . to Grow Previous [ gn ] Ġ?: Ġgn . previous . values ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġmatches . add ( Pair ( gn , Ġprev )) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġ} Ġwhile Ġ( rp . can Grow Ġ&& Ġgraph . goals . isEmpty ()) ĊĊĠĠĠĠĠĠĠ Ġ// val Ġnext Expected Ġ= Ġmatches ĊĠĠĠĠĠĠĠ Ġ// ĠĠĠ Ġ. filter Ġ{ Ġit . can Grow Width Ġ} ĊĠĠĠĠĠĠĠ Ġ// ĠĠĠ Ġ. flatMap Ġ{ Ġit . next Expected Items Ġ} ĊĠĠĠĠĠĠĠ Ġ// ĠĠĠ Ġ. toSet () ĊĠĠĠĠĠĠĠ Ġ// return Ġnext Expected ĊĊĠĠĠĠĠĠĠ Ġval Ġtrans _ lh _ pairs Ġ= Ġmatches . flatMap Ġ{ Ġgn _ prev Ġ-> ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġgn Ġ= Ġgn _ prev . first ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġprev Ġ= Ġgn _ prev . second ?. map Ġ{ Ġit . node . currentState Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġtrans Ġ= Ġrp . transitions Ending In Non Empty From ( gn . currentState , Ġprev ?. toSet ()) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġtrans . map Ġ{ Ġtr Ġ-> ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġlh Ġ= Ġtr . look ahead Guard . resolve ( gn . look ahead ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ ĠPair ( tr , Ġlh ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġ}. toSet () ĊĊĠĠĠĠĠĠĠ Ġval Ġresult Ġ= Ġtrans _ lh _ pairs . flatMap Ġ{ Ġtr _ lh Ġ-> ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġtr Ġ= Ġtr _ lh . first ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġlh Ġ= Ġtr _ lh . second ĊĠĠĠĠĠĠĠĠĠĠĠ Ġwhen ( tr . action ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ ĠTransition . Parse Action . GO AL Ġ-> Ġlh ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ ĠTransition . Parse Action . WIDTH Ġ-> Ġtr . to . runtime Rules ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ ĠTransition . Parse Action . GR AFT Ġ-> Ġlh ĊĠĠĠĠĠĠ Ġ// ĠĠĠĠĠĠĠĠ ĠTransition . Parse Action . GR AFT _ OR _ HEIGHT Ġ-> Ġlh ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ ĠTransition . Parse Action . HEIGHT Ġ-> Ġlh ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ ĠTransition . Parse Action . EMB ED Ġ-> ĠTODO () ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġ}. toSet () ĊĠĠĠĠĠĠĠ Ġreturn Ġresult ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġoverride Ġfun Ġexpected At ( goal Rule Name : ĠString , Ġinput Text : ĠString , Ġposition : ĠInt , Ġautom aton Kind : ĠAutom aton Kind ): ĠSet < Runtime Rule > Ġ{ ĊĠĠĠĠĠĠĠ Ġval Ġgoal Rule Ġ= Ġthis . runtime Rule Set . find Runtime Rule ( goal Rule Name ) ĊĠĠĠĠĠĠĠ Ġval Ġused Text Ġ= Ġinput Text . substring ( 0 , Ġposition ) ĊĠĠĠĠĠĠĠ Ġval Ġinput Ġ= ĠInput FromString ( this . runtime Rule Set . terminal Rules . size , Ġused Text ) ĊĠĠĠĠĠĠĠ Ġval Ġss Ġ= Ġruntime Rule Set . fetch State Set For ( goal Rule , autom aton Kind ) ĊĠĠĠĠĠĠĠ Ġval Ġskip State Set Ġ= Ġruntime Rule Set . skip Parser State Set ĊĠĠĠĠĠĠĠ Ġval Ġrp Ġ= ĠRuntime Parser ( ss , Ġskip State Set , Ġgoal Rule , Ġinput ) ĊĠĠĠĠĠĠĠ Ġthis . runtime Parser Ġ= Ġrp ĊĊĠĠĠĠĠĠĠ Ġrp . start ( 0 , ĠLook ahead Set . EOT ) ĊĠĠĠĠĠĠĠ Ġvar Ġse asons Ġ= Ġ 1 ĊĊĠĠĠĠĠĠĠ Ġval Ġmatches Ġ= Ġmutable ListOf < Pair < Grow ing Node , ĠCollection < Previous Info >? >>() ĊĠĠĠĠĠĠĠ Ġdo Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġrp . grow ( false ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġfor Ġ( gn Ġin Ġrp . last G rown ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( input . is End ( gn . next Input Position )) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġprev Ġ= Ġrp . to Grow Previous [ gn ] ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( prev == null Ġ&& Ġgn . currentState . is Goal . not ()) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ// don 't Ġinclude Ġit ĠTODO : Ġwhy Ġdoes Ġthis Ġhappen ? ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} Ġelse Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġmatches . add ( Pair ( gn , Ġprev )) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠ Ġse asons ++ ĊĠĠĠĠĠĠĠ Ġ} Ġwhile Ġ( rp . can Grow Ġ&& Ġrp . graph . goals . isEmpty ()) ĊĠĠĠĠĠĠĠ Ġval Ġnext Expected Ġ= Ġthis . find Next Expected ( rp , Ġrp . graph , Ġinput , Ġmatches ) ĊĠĠĠĠĠĠĠ Ġreturn Ġnext Expected ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġoverride Ġfun Ġexpected Terminal s At ( goal Rule Name : ĠString , Ġinput Text : ĠString , Ġposition : ĠInt , Ġautom aton Kind : ĠAutom aton Kind ): ĠSet < Runtime Rule > Ġ{ ĊĠĠĠĠĠĠĠ Ġreturn Ġthis . expected At ( goal Rule Name , Ġinput Text , Ġposition , autom aton Kind ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ. flatMap Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġwhen Ġ( it . kind ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ ĠRuntime Rule Kind . TERMIN AL Ġ-> ĠlistOf ( it ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ ĠRuntime Rule Kind . NON _ TERMIN AL Ġ-> Ġthis . runtime Rule Set . first Terminal s [ it . number ] ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġelse Ġ-> ĠTODO () ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ. toSet () ĊĠĠĠ Ġ} Ċ }