path: root/elymas/lib/parser.ey

<
  <
    { sys .linux .gettimeofday -- 1000000 mul add } /t deffd
    < { == }' > ==time =*setTime
    < { == }' > ==count =*setCount
    { ==l 0 l setTime 0 l setCount
      { =*f { t ==start f t start sub time l . add l setTime count l . 1 add l setCount } }
      quoted not { * } rep
    }
    { time keys { _ dump _ time -01 . txt .produce .u " μs" cat dump count -01 . txt .produce .u " calls" cat dump } each }
  > -- /perfstats deffd "τ" defq

  { =*body { 0 ==again { 1 =again }' body again } { }" loop } /redoing deffd
  { =*wasNew ==m ==k k m .has not { 1 k m =[] wasNew } rep } /enlarge deffd

#  { ==a a len 1 gt {
#      0 ==i 0 ==j
#      a dom { =i
#        i 1 add a len range { =j
#          i a * j a * -1010 gt {
#            i a =[] j a =[]
#          }" { -- -- }" ? *
#        }' each
#      }' each
#      a
#    }' rep
#  } /strsort deffd
#  
#  [ /a /h /b /c /f /d /g /i /e ] strsort dump /yolo die

  <
    0 10 range { ==i
      { .states i { 0 -01* } rep 2 -01* } i txt .produce .u }
      { defmd }' ; each

    { < ==states > }
  > -- /children deffd
  0 10 range { _ { { 0 -01* } rep 2 -01* }_ -01 txt .produce .u deffd }' each

  <
    sys .typed .|type =*:SYSTYPEDTYPE
    { ==nt ==t SYSTYPEDTYPE 1 eq t nt ? * } ":?" deffd
    { _ ==e { "t" e } { "n" e .name } :? cat } /tId deffd
    { ==r
      [
        0 r * .name " "
        1 r * |tId each " "
        3 r * txt .produce .u "  "
      ] |cat fold
    } /itemId deffd
    { ==itemset --rules
      { [ 0 ] cat _ itemId itemset =[] } each
      itemset
    } /addRuleStartToItemSet deffd
    { --itemset dom _ len 1 gt { sort |cat fold }" { 0 -01* }" ? * }' /itemsetId deffd
    { ==name scope } /nonterminal deffd
    [ ] ==shiftActions # target state index -> shift action function
    { ==target                 # lookahead consumed, quit statemachine loop --v
      { target shiftActions len ge } { shiftActions _ len ==i [ { [ i -1302 ] 0 }' ] cat =shiftActions } loop
      target shiftActions *
    } /makeShiftAction deffd
    { =*r 3 r 1 r len eq } /ruleAtEnd deffd

    {
      [ ] ==rules 0 ==nextNonTerminalName
      { nextNonTerminalName _ 1 add =nextNonTerminalName txt .produce .u ==name scope } /nt deffst
      { ==action ==expansion ==nonterminal
        rules [ [ nonterminal expansion action ] ] cat =rules
      } /rule deffst

      { ==start
        rules [ [ < "" ==name > [ start "" ] { } ] ] cat ==rules
        map ==itemsets
        map ==transitions # itemsetId -> label -> itemsetId

        { ==nt rules { ==r 0 r * .name nt eq } grep } /findRules deffst
        { ==itemset
          "------" dump
          itemset { ==r
            3 r * ==pos
            [
              0 r * .name " -> "
              1 r * dom { ==i
                i pos eq { " . " } rep
                i 1 r * * tId " "
              } each
              pos 1 r * len eq { " . " } rep
            ] |cat fold dump
          } each
        } /dumpItemSet deffst

        { ==rulesToExpand
          map ==expanded

          [
            { rulesToExpand # into the result array
              [
              rulesToExpand { ==r
                3 r * 1 r * * ==t
                t { } {
                  t .name expanded .has not {
                    1 t .name expanded =[]
                    t .name findRules { [ 0 ] cat } each
                  } rep
                } :?
              } each
            ] _ =rulesToExpand len } { } loop
          ] |cat fold ==steppingRules

          map ==rulesByStep # tId -> [ rule ... ]
          steppingRules { ==r
            3 r * 1 r * * tId ==eId
            eId rulesByStep .has { eId rulesByStep * } { [ ] } ? *
            [ r ] cat eId rulesByStep =[]
          } each

          rulesByStep
        } /nonterminalExpansions deffst
        { ==itemset
          itemset itemsetId ==fromId
          itemset { ruleAtEnd not }' grep ==steppingRules

          steppingRules nonterminalExpansions ==rulesByStep # tId -> [ rule ... ]

          rulesByStep dom { ==eId
            map ==nextItemSet

            eId rulesByStep * {
              [ -01 4 dearray 1 add ] _ itemId nextItemSet =[]
            }' each

            nextItemSet itemsetId ==toId
            toId itemsets .has not {
              nextItemSet toId itemsets =[] # add new itemset
              # nextItemSet dumpItemSet perfstats
              nextItemSet stepItemSet
            }' rep

            fromId transitions .has not { map fromId transitions =[] }' rep
            toId eId fromId transitions * =[]
          } each
        } /stepItemSet deffst
        { ==lookahead ==rulesAtEnd
          [ ] ==r
          rulesAtEnd { =r lookahead 0 r * .name followSets .has }' grep
          _ len _ ==l 1 gt { /reduce_reduce_conflict die }' rep
            l dearray l
        } /canReduce deffst
        map ==reduceActions # itemid -> reduce action function
        { _ ==item itemId ==id
          id reduceActions .has not {
            0 item * .name ==nt
            1 item * len ==tokill
            2 item * =*reduceAction
            { -- ==states # value dropped
              states reduceAction ==value
              tokill { 0 states * =states }' rep
              states len 0 gt {
                nt 1 states * nonterminalActions * * ==target
                target 0 lt |unexpectedNonterminal {
                  [ states target value ] =states
                }' ? *

                # states len 0 gt { # DEBUG
                #   1 states * theItemSets * dumpItemSet
                # } rep
              } rep
              states 1 # lookahead not consumed, repeat loop
            } id reduceActions =[]
          } rep

          id reduceActions *
        } /makeReduceAction deffst

        map ==allNonTerminals
        rules { 0 -01 * 1 -01 .name allNonTerminals =[] } each
        map ==allTerminals
        rules { 1 -01* { ==e e { 1 e allTerminals =[] } { } :? } each } each

        map ==nullableNonTerminals
        { [ -01 { _ ==e { 0 } { e .name nullableNonTerminals .has } :? }
          each ] all } /isNullable deffst
        { ==redo
          rules { 1 -01* isNullable } grep {
            0 -01* .name nullableNonTerminals |redo enlarge
          } each
        } redoing

        allNonTerminals { -- map } '*0.0 =*firstSets # nonterminal -> terminal -> 1
        { map ==result 0 ==finished { ==e
          finished not {
            e {
              1 e result =[] 1 =finished
            } {
              e .name _ firstSets dom { 1 -01 result =[] } each
                        nullableNonTerminals .has =finished
            } :?
          } rep
        } each result } /firstSet deffst
        { ==redo
          rules { ==r 0 r * .name firstSets ==lhsSet 1 r * ==rhs
            0 ==i
            { { i 1 add =i } ; ==lookAtNextElement
              i rhs len ge { 0 } {
                i rhs * _ {
                  lhsSet |redo enlarge
                } {
                  _ .name firstSets dom { lhsSet |redo enlarge } each
                    [ -01 ] isNullable lookAtNextElement rep
                } :?
              } ? *
            } redoing
          } each
        } redoing
        
        allNonTerminals { -- map } '*0.0 =*followSets # nonterminal -> terminal -> 1
        { ==redo
          rules { ==r 0 r * .name followSets ==lhsSet 1 r * ==rhs
            rhs dom { _ ==i rhs *
              _ { -- } {
                .name followSets { |redo enlarge }_ ==put
                i 1 add rhs len range rhs *
                _ firstSet dom put each
                  isNullable { lhsSet dom put each } rep
              } :?
            } each
          } each
        } redoing

        "" findRules map addRuleStartToItemSet _  ==initialItemSet _ itemsetId itemsets =[]
        initialItemSet stepItemSet
        # "=====" dump itemsets |dumpItemSet each perfstats # DEBUG
        
        map ==itemsetIndices
        0 ==i
        itemsets dom ==itemsetsDom
        [
          itemsetsDom { ==id id itemsets * id i _ 1 add =i -01 itemsetIndices =[] }' each
        ] ==theItemSets

        { "unexpected nonterminal" die }' /unexpectedNonterminal deffst
        { "unexpected terminal" die }' /unexpectedTerminal deffst

        [
          itemsetsDom { ==itemsetId
            map _ ==actions # left in array
            itemsetId transitions .has {
              allNonTerminals dom { ==nt
                itemsetId transitions * ==outgoing
                "n" nt cat ==label
                label outgoing .has {
                  label outgoing * itemsetIndices *
                }" { 1 neg }" ? * nt actions =[]
              } each
            } rep
          } each
        ] ==nonterminalActions # stateIndex -> nonterminal .name -> { ... }

        allTerminals dom ==allTerminalsDom
        [
          itemsetsDom { _ ==itemsetId itemsets * ==itemset
            map _ ==actions # left in array

            itemsetId transitions .has { itemsetId transitions * } { map } ? * ==outgoing
            itemset |ruleAtEnd grep ==rulesAtEnd

            "" ==t allTerminalsDom { =t
              "t" t cat outgoing .has {
                "t" t cat outgoing * itemsetIndices * makeShiftAction t actions =[] }' {
              rulesAtEnd t canReduce {
                makeReduceAction t actions =[] }'
              # else
                { |unexpectedTerminal t actions =[]
              }' ? * }' ? *
            }' each
          } each
        ] ==terminalActions # stateIndex -> lookahead -> { ... }

        <
          {
            [ [ ] 0 0 ] ==states
            { ==lookahead ==value
              1 states * theItemSets * dumpItemSet # DEBUG
              [ "received: " lookahead ] |cat fold dump # DEBUG

              { states value
                lookahead 1 states * terminalActions * * *
                -01 =states states len and
              } { } loop
            }
          } /run deffst
        >

        perfstats
      } /automaton deffst
    scope }
  > -- /lalr1 deffd
> /parser defvd

# vim: syn=elymas