17
$\begingroup$

Clojure is a lisp-like language that runs on JVM and in Javascript. I just started learning it and I'm building a simple parser with Mathematica to understand and visualize it.

Like other lisps every Clojure expression is really a tree in polish notation, and so has a simple normal form that looks like this: (head expr expr ...) where expr is a symbol, string, or other atomic type.

Ok, so here's an example of my function parseTree at work:

s = "(defn double-int [i] (* i 2))";
c = parseTree[s]
TreeForm@c

enter image description here

Unfortunately, my function uses string patterns in a way that seems very brittle to me - I couldn't think of a better way to do it, but I was hoping you all might.

parseTree[s_String] := Module[{lst=Characters@s,rules={},srules={},p,a,n,l,ph,res},
    p=Cases[Thread[{lst,Range@Length@lst}],{"("|")",_}]//.{h___,{"(",i_},{")",j_},t___}:>{h,t,{i,j}};
    a=StringTake[s,#]&/@p;
    n=a[[1]];
    Do[
        l=parseLeaf[n];
        ph="$"<>ToString@Hash[l];
        AppendTo[rules,ph->l];
        AppendTo[srules,a[[i]]->ph];
        n=StringReplace[a[[i+1]],srules];
        ,{i,1,Length[a]-1}];
    res=parseLeaf[n]//.rules;
    res
]

parseLeaf["()"]:=clj[]
parseLeaf[expr_]:=Module[{head,rest,strc,sr},
    strc=StringCases[expr,{("("~~Shortest["hd["~~h__~~"]"]~~Whitespace~~r___~~")"):>{h,r},("("~~Shortest[h__]~~Whitespace~~r___~~")"):>{h,r}}];
    If[strc=={},
        sr=StringCases[expr,"("~~h__~~")":>h];
        Return[clj[sr[[1]]]]];
    {head,rest}=strc[[1]];
    rest=StringCases[rest,
            {n:("$"~~NumberString):>n,
            Shortest["\""~~s___~~"\""]:>str[ToString[s]],
            Shortest["clj[",s___,"]"]:>clj[s],
            Shortest["hd[",s___,"]"]:>hd[s],
            Shortest["[",s___,"]"]:>vec[s],
            Shortest["{",s___,"}"]:>dict[s],
            n:NumberString:>num[n],
            (n:(WordCharacter|"-"|"*"|"."|"#"|"/")..):>var[n]}
    ];
    clj[hd[head],rest]
]

References:

Improve this question
$\endgroup$
1

2 Answers 2

Reset to default
17
$\begingroup$

This answer is based on the Mathematica functional parsers package FunctionalParsers.m used and described in these blog posts.

This command loads that package:

Import["https://raw.githubusercontent.com/antononcube/MathematicaForPrediction/master/FunctionalParsers.m"]

Using direct parser definitions (first answer)

Consider the EBNF:

<space> = { 'WhitespaceCharacter' } ;
<var> = { 'WordCharacter' } ;
<number> = { 'DigitCharacter' } ;
<atom> =  <var> | <number> ;
<vector> = '[' , <atom> , { <space> , <atom> } , ']' ;
<arg> =  <atom> | <vec> | <tree> ;  
<args-list> = <arg> , { <space> , <arg> } ; 
<head> = <var> ;
<tree> = '(' , <head> , [ <space> , <args-list> ] , ')' ;

Define the corresponding parsers:

pSPACE = ParsePredicate[StringMatchQ[#, WhitespaceCharacter ..] &];

pVAR = var[StringJoin[#]] &\[CircleDot]ParseMany1[
    ParsePredicate[
     StringMatchQ[#, 
       Except[{"(", ")", "[", "]", WhitespaceCharacter}] ..] &]];

pNUMBER = 
  num[ToExpression[StringJoin[#]]] &\[CircleDot]ParseMany1[
    ParsePredicate[StringMatchQ[#, DigitCharacter ..] &]];

pATOM = ParseSpaces[pNUMBER\[CirclePlus]pVAR];

pVECTOR = 
  vec @@ # &\[CircleDot]ParseShortest[
    ParseBracketed[ParseListOf[pATOM, pSPACE]]];

pARGSLIST = 
  ParseShortest[
   ParseListOf[
    ParseSpaces[pATOM\[CirclePlus]pVECTOR\[CirclePlus]pTREE], pSPACE]];

pHEAD = hd @@ # &\[CircleDot]pVAR;

ParseRecursiveDefinition[pTREE, 
  clj @@ Join[{#[[1]]}, #[[2]]] &\[CircleDot]ParseParenthesized[
    pHEAD\[CircleTimes]ParseOption[
      pSPACE \[RightTriangle] pARGSLIST]]];

Note that pVAR is defined for a larger set of strings than <var> in the EBNF. Here is a prettier view on that code:

enter image description here

\[CirclePlus], \[CircleTimes], and \[CircleDot] correspond to the parsers ParseAlternativeComposition, ParseSequentialComposition, and ParseApply respectively. A triangle points to the parser the output of which is picked up in a sequential composition.

Parse the example in the question:

res = pTREE[Characters["(defn double-int [i] (* i 2))"]]

(* {{{}, clj[hd["defn"], {var["double-int"], vec[var["i"]], 
    clj[hd["*"], {var["i"], num[2]}]}]}} *)

and plot the result:

TreeForm[res[[1, 2]]]

enter image description here Here are other parsing examples:

In[164]:= pTREE[Characters["(defn myfun [i j k] (list (* i 2) (+ j 5) (sq k)))"]]

Out[164]= {{{}, clj[hd["defn"], {var["myfun"], vec[var["i"], var["j"], var["k"]], 
    clj[hd["list"], {clj[hd["*"], {var["i"], num[2]}], 
      clj[hd["+"], {var["j"], num[5]}], clj[hd["sq"], {var["k"]}]}]}]}}

In[165]:= pTREE[Characters["(defn myfun [i j k] (list))"]]

Out[165]= {{{}, clj[hd["defn"], {var["myfun"], vec[var["i"], var["j"], var["k"]], 
    clj[hd["list"]]}]}}

Using parser generation from EBNF (update)

Instead of defining the parsers for each of rule of the EBNF grammar we can use the FunctionalParsers.m package to generate the parsers from the EBNF grammar.

ebnfCode = "
  <tree> = '(' &> <head>, [ <args-list> ] <& ')' <@ clj@@#& ;
  <head> = <var> <@ hd@@#& ;
  <args-list> = { <arg> } ; 
  <arg> = <atom> | <vector> | <tree>; 
  <atom> = <var>|<number>; 
  <var> = '_WordString' <@ var ;
  <number> = '_?NumberQ' <@ num ;
  <vector> = '[' &> { <atom> } <& ']' <@ vec@@#& ;
  ";

The strings "&>" and "<&" stand for "parse sequentially and pick right" and "parse sequentially and pick left" respectively. The string "<@" stands for "apply to the parsing result of #1 the modifier function #2".

This command generates the parsers:

GenerateParsersFromEBNF[ParseToEBNFTokens[ebnfCode]];

For each EBNF rule a separate parser is made. E.g. for <vector> = ... the parser pVECTOR is made.

The generated definition of the parser pVAR has to be extended in order to allow the symbols "-", "_", etc. to be in the variable names.

pVAR = var\[CircleDot]ParsePredicate[
    StringMatchQ[#, Except[{"(", ")", "[", "]"}] ..] &];

Let us define a dedicated tokenizer for the considered Clojure expressions:

ToClojureTokens = ParseToTokens[#, {"(", ")", "[", "]"}, {" ", "\n"}] &;

With the tokenizer we can make the following table of parsing results:

statements = {"[7  34  5 72]", "(ar [7  34  5 72])", "(m 3 (p 4 6))", 
   "(defn doubleint [i] (* i 2))", "(list (* i 2) (+ j 5) (sq k))", 
   "(defn myfun [i j k] (list (* i 2) (+ j 5) (sq k)))"};
ParsingTestTable[pTREE, statements, 
 "TokenizerFunction" -> ToClojureTokens, "Layout" -> "Vertical"]

enter image description here

Here are the tree forms of the parsed expressions in the table:

Map[TreeForm@*First@*Reverse@*First@*pTREE@*ToClojureTokens, statements]

enter image description here

Other discussions

The functional parsers approach has been discussed also in answers of other MSE questions.

  1. "CSS Selectors for Symbolic XML" ;

  2. "General strategies to write big code in Mathematica?"

Improve this answer
$\endgroup$
4
  • $\begingroup$ This is impressive. +1, of course. $\endgroup$
    – Leonid Shifrin
    Mar 29, 2016 at 8:10
  • $\begingroup$ @LeonidShifrin Thanks! This question and my answer fit very well our recent discussion on DSLs. $\endgroup$
    – Anton Antonov
    Mar 29, 2016 at 11:29
  • $\begingroup$ @AntonAntonov how would you change your code to parse special clojure charaters like @, ~, `, and quote literals like '(1 2 3 4)? $\endgroup$
    – user5601
    Apr 13, 2016 at 20:54
  • $\begingroup$ @user5601 I think such a change is pretty easy. For example, we can add an EBNF rule <literal> = \"'\" , <tree> ;. Would you consider updating the question with the clojure expressions you have in mind? (Or make a new question...) $\endgroup$
    – Anton Antonov
    Apr 13, 2016 at 22:15
6
$\begingroup$

I have a solution which is brittle only in that the Clojure expressions "(", ")" could mess up bracket detection and that I rely on strings like "<4>" to keep track of things. It's not very brittle once string handling is properly treated. Don't know if it's any better than yours, but it was fun to write and I think it's rather slick, modulo aforementioned fixable brittleness. Special mention to the use of a closure varname to count the leafs.

  • parse just takes a depth-1 Clojure expression like (head arg1 arg2 arg3) and returns "head"["arg1", "arg2", "arg3"].
  • prepare replaces [contents] with (List contents) in the string.
  • splitTree breaks out the expression into {top-expression, {{label -> sub-expression, label -> sub-expression, …}}}; see example below.
parse[expr_String?(StringFreeQ[StringTake[#, 2 ;; -2], "("] &)] := 
 (#[[1]] @@ Rest[#]) &@
  StringSplit[StringTake[expr, 2 ;; -2], " "]

varname[start_: 0] := 
 Module[{p = start}, (p++; "<" <> ToString[p] <> ">") &]

prepare[str_] := 
 (
  newvars = varname[];
  StringReplace[str, 
   Shortest["[" ~~ x__ ~~ "]"] :> "(List " <> x <> ")"];
 )

splitTree[str_] := 
 Reap@FixedPoint[
  StringReplace[#, 
   x : r__ ~~ int : Shortest["(" ~~ __ ~~ ")"] ~~ s__ :>
    (With[{var = newvars[]}, Sow[var -> int]; 
    r <> var <> s])] &, str]

Example usage:

prepare["(defn double-int [i] (* i (+ 3 4)))"]

outputs

"(defn double-int (List i) (* i (+ 3 4)))"

then

output = MapAt[parse, splitTree[%], {2, 1, All, 2}]

outputs

{"(defn double-int <3> <2>)",
 {{"<1>" -> "+"["3", "4"], 
   "<2>" -> "*"["i", "<1>"],
   "<3>" -> "List"["i"]}}}

then

parse[output[[1]]] //. output[[2, 1]]

outputs

"defn"["double-int", "List"["i"], "*"["i", "+"["3", "4"]]]
Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.