diff options
| -rw-r--r-- | elymas/lib/parser.ey | 480 | ||||
| -rw-r--r-- | elymas/lib/sort.ey | 14 | ||||
| -rw-r--r-- | examples/working-loaded/parser.test | 8 |
3 files changed, 257 insertions, 245 deletions
diff --git a/elymas/lib/parser.ey b/elymas/lib/parser.ey index 90456bf..da562e3 100644 --- a/elymas/lib/parser.ey +++ b/elymas/lib/parser.ey @@ -10,8 +10,9 @@ { 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 + { =*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 @@ -36,253 +37,264 @@ > -- /children deffd 0 10 range { _ { { 0 -01* } rep 2 -01* }_ -01 txt .produce .u deffd }' each - { - [ ] ==rules 0 ==nextNonTerminalName - { ==nt ==t --e sys .typed .type 1 eq t nt ? * } ":?" deffd - { nextNonTerminalName _ 1 add =nextNonTerminalName txt .produce .u ==name scope } /nt deffst - { ==name scope } /nonterminal 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 --rules - { [ 0 ] cat _ itemId itemset =[] } each - itemset - } /addRuleStartToItemSet deffst - { _ ==e { "t" e } { "n" e .name } :? cat } /tId deffst - { ==r - [ - 0 r * .name " " - 1 r * |tId each " " - 3 r * txt .produce .u " " - ] |cat fold - } τitemId /itemId deffst - { --itemset dom { sort } τsort * |cat fold } τitemsestId /itemsetId deffst - { --itemset _ itemsetId itemsets =[] } τaddItemSet /addItemSet 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 + < + 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 - { =*r 3 r 1 r len eq } /ruleAtEnd deffst - { ==rulesToExpand - map ==expanded + { + [ ] ==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 - [ - { rulesToExpand # into the result array + { ==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 [ - 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 - } τnonterminalExpansion /nonterminalExpansions deffst - { ==itemset - itemset itemsetId ==fromId - itemset { ruleAtEnd not }' grep ==steppingRules - - steppingRules nonterminalExpansions =steppingRules - - map ==rulesByStep # tId -> [ rule ... ] - steppingRules { ==r - 3 r * 1 r * * tId ==eId - eId rulesByStep .has { eId rulesByStep * } { [ ] } ? * - [ r ] cat eId rulesByStep =[] - } each - - rulesByStep dom { ==eId - map ==nextItemSet + 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 + }' ? * - eId rulesByStep * { =r - [ r 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 ==itemset - 0 ==can [ ] ==rule - itemset |ruleAtEnd grep { ==r - lookahead 0 r * .name followSets .has { - can { /reduce_reduce_conflict die } rep - 1 =can r =rule + # states len 0 gt { # DEBUG + # 1 states * theItemSets * dumpItemSet + # } rep + } rep + states 1 # lookahead not consumed, repeat loop + } id reduceActions =[] } rep - } each - can { rule } rep can - } /canReduce 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 + + 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 - } each - } redoing - - # "" findRules map addRuleStartToItemSet closeItemSet _ addItemSet - "" findRules map addRuleStartToItemSet _ addItemSet ==initialItemSet - initialItemSet { stepItemSet } τstepItemSet * - "=====" dump itemsets |dumpItemSet each perfstats # DEBUG - - { - map ==itemsetIndices - 0 ==i - [ - itemsets { _ itemsetId i _ 1 add =i -01 itemsetIndices =[] } each - ] ==theItemSets + } 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 - { "unexpected nonterminal" die } /unexpectedNonterminal deffst - { "unexpected terminal" die } /unexpectedTerminal deffst + "" 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 - [ - itemsets { ==itemset - map _ ==actions # left in array - itemset itemsetId ==isId - isId transitions .has { - allNonTerminals dom { ==nt - isId transitions * ==outgoing - "n" nt cat ==label - label outgoing .has { - label outgoing * itemsetIndices * ==target - { [ target -1302 ] } - } { |unexpectedNonterminal } ? * nt actions =[] - } each - } rep - } each - ] ==nonterminalActions # stateIndex -> nonterminal .name -> { ... } + { "unexpected nonterminal" die }' /unexpectedNonterminal deffst + { "unexpected terminal" die }' /unexpectedTerminal deffst - [ - itemsets { ==itemset - map _ ==actions # left in array + [ + 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 - itemset itemsetId ==isId - isId transitions .has { isId transitions * } { map } ? * ==outgoing + itemsetId transitions .has { itemsetId transitions * } { map } ? * ==outgoing + itemset |ruleAtEnd grep ==rulesAtEnd - allTerminals dom { ==t - [ - { "t" t cat outgoing .has } { - "t" t cat outgoing * itemsetIndices * ==target - { [ target -1302 ] 0 } t actions =[] - # 0 => lookahead consumed, quit statemachine loop - } - { itemset t canReduce } { ==rule - 0 rule * .name ==nt - 1 rule * len ==tokill - 2 rule * =*reduceAction - { -- ==states # value dropped - states reduceAction ==value - tokill { 0 states * =states }' rep - states len 0 gt { - nt 1 states * nonterminalActions * * =*action - states value action =states - - # states len 0 gt { # DEBUG - # 1 states * theItemSets * dumpItemSet - # } rep - } rep - states 1 # lookahead not consumed, repeat loop - } t actions =[] - } - { 1 } { |unexpectedTerminal t actions =[] } - ] conds + "" ==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 - } each - ] ==terminalActions # stateIndex -> lookahead -> { ... } - }' τfinalization * - - < - { - [ [ ] 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 - > - } /automaton deffst - scope } /lalr1 deffd + ] ==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 diff --git a/elymas/lib/sort.ey b/elymas/lib/sort.ey index 6692cf2..60e1b9b 100644 --- a/elymas/lib/sort.ey +++ b/elymas/lib/sort.ey @@ -1,17 +1,17 @@ { /cmp deff _ /a deff dom /d deff { ==e ==s - s e eq { [ s d ] } { + s e eq { [ s d ] }' { s e add 2 div ==m s m mergeSort =*x 0 ==i m 1 add e mergeSort =*y 0 ==j - { i _ x -01 1 add =i } ==l - { j _ y -01 1 add =j } ==r + { i _ x -01 1 add =i }' ==l + { j _ y -01 1 add =j }' ==r [ - { i |x len lt j |y len lt and } { + { i |x len lt j |y len lt and }' { i x a j y a cmp l r ? * - } loop - { i |x len lt } l loop - { j |y len lt } r loop + }' loop + { i |x len lt }' l loop + { j |y len lt }' r loop ] } ? * } /mergeSort deffst diff --git a/examples/working-loaded/parser.test b/examples/working-loaded/parser.test index 8af1003..0398c08 100644 --- a/examples/working-loaded/parser.test +++ b/examples/working-loaded/parser.test @@ -14,13 +14,13 @@ num [ /0 ] { -- 0 } :rule num [ /1 ] { -- 1 } :rule num [ /2 ] { -- 2 } :rule -S :automaton ==Sparser +[ S :automaton ==Sparser ] len 0 gt { "stack garbage" die } rep "generation done" dump -100000 { +# 100000 { Sparser .run =*consume - [ "(" /2 "+" /1 "-" /1 ")" "+" /1 "" ] { _ consume } each -} rep + [ "(" "(" /2 "+" /1 "-" /1 ")" ")" "+" /1 "" ] { _ consume } each +# } rep result dump |