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 { ==i
    { i { 0 -01* }" rep 2 -01* }' i txt .produce .u }
    { deffd }' ; each

  # 0 -> index of child ( from the right )
  # 1 -> state stack
  # 0 <- value of n-th child
  { { 0 -01* }" rep 2 -01* }" /child deffd

  <
    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
    { "unexpected nonterminal" die }' /unexpectedNonterminal 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 "" ] { /never_executed die } ] ] 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
        } /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

        [
          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 }' rep
                rulesAtEnd t canReduce { makeReduceAction }' each
              ] t actions =[]
            }' each
          } each
        ] ==terminalActions # stateIndex -> lookahead -> { ... }

        <
          {
            [
              [ [ ] 0 0 ] # (currently empty) stack of states
            ] ==states # all states of the GLR

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

              [ ] ==waitingStates
              states ==executingStates

              {
                [ executingStates { ==state
                  [
                    1 state * terminalActions * ==actionMap
                    lookahead actionMap .has {
                      lookahead actionMap * { # --action
                        state value -102 *
                      }' each
                    }' rep
                  ] _ ==results len ==i

                  { i }' {
                    i 2 sub =i
                    i 1 add results * {
                      i results * # collected outside the loop
                    }' {
                      [ waitingStates i results * ] =waitingStates
                    }' ? *
                  }' loop
                } each ] _ =executingStates len

                # ">>>---" dump
                # executingStates { ==state # DEBUG
                #   1 state * theItemSets * dumpItemSet
                # } each
                # "<<<---" dump
              }' { }" loop

              [
                { waitingStates len }" {
                  1 waitingStates *
                  0 waitingStates * =waitingStates
                }" loop
              ] _ =states
            }' > --
          } /run deffst
        >

        # perfstats # DEBUG
      } /automaton deffst

      { ==states
        [ states { 0 -01* 2 -01* }" each ]
      } /result deffst
    scope }
  > -- /glr deffd
> /parser defvd

# vim: syn=elymas