I'm trying to do lexical scanning and parsing in a toy language. One with just functions (of the form $f(a,\,b,\,c,\,...)$, ended with semicolons) and special tokens (such as for, if, etc.). An example that would utilize everything neccecary is the following snippet:

f(1);
for i 1 10 {
  print('test');
  f(62);
  if(i==2) { 
    print('test');
  } 
} 

Whitespace does not matter; it's purely for show. All I want to do at this point is separate into nested tokens, such that the above would become:

{"f(1)", {"for i 1 10", {"print('test')", "f(62)", {"if(i==2)", {"print('test')"}}}}}

I tried simple pattern matching to get the "special tokens" out

StringCases[exampleProg, Characters["\n;"] ~~ __ ~~ "{" ~~ ___ ~~ "}"]

And while this (combined with some string drops) does separate out the special tokens, it does not work with the nested if. I could probably work out a nesting solution with FixedPoint, but I feel like there must be a more elegant way to do it, but I can't immediately see how to then seperate out the functions.

What's an easier way to accomplish my task?

  • Can we assume a one-to-one mapping between your toy language and MMA functions/symbols? That is, is your language just a re-write of MMA, with different keywords ('for' instead of 'For',...) and different infix/prefix/postfix conventions? – berniethejet Oct 10 at 15:14
  • @berniethejet In the end, probably - but I'm not sure how that would help here. I don't want to convert any of these tokens to actual MMA functions, but just put it in the table format described above. We don't need to know how many arguments the "special functions" take either, because in the format I described the arguments aren't seperated - it's just everything up to the {. – TreFox Oct 10 at 16:26

This can be done using functional parsers.

Does the solution below look like something you would be interested in? (If you are I will elaborate on the current answer...)

Grammar

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

ebnfToy = "
  <program> = ( [ <wgap> ] &> <statement> ) , { [ <wgap> ] &> <statement> } <@ Program@*Flatten ;
  <statement> = <function-call> | <if-statement> | <for-statement> ;
  <function-call> = <function-id> , '(' , [ <arg-list> ] , ')' <& ( [ <wgap> ] , ';' ) <@ FunctionCall@*StringJoin@*Flatten ;
  <for-statement> = ( <for-spec> <&[ <wgap> ] ) , ( '{' <& [ <wgap> ] ) &> ( <program> <& [ <wgap> ] &> '}' ) <@ ForStatement@*Flatten ;
  <for-spec> = <for> , <wgap> , <var-id> , <wgap> , <integer> , <wgap> , <integer> <@ ForSpec@*StringJoin ; 
  <for> = 'f' , 'o' , 'r'  <@ StringJoin ;
  <if-statement> = ( <if-spec> <& [ <wgap> ] ) , ( '{' , [ <wgap> ] ) &> ( <program> <& ( [ <wgap> ] , '}' ) ) <@ IfStatement@*Flatten ;
  <if-spec> = <if> , '(' , <logical-statement> , ')' <@ IfSpec@*StringJoin ;
  <if> = 'i' , 'f' <@ StringJoin ;
  <logical-statement> = { '_String' } <@ StringJoin@*Flatten@*List ;
  <function-id> = { '_WordString' } <@ StringJoin@*Flatten@*List ;
  <var-id> = { '_LetterString' } <@ StringJoin@*Flatten@*List ;
  <arg-list> = { '_String' } <@ StringJoin@*Flatten@*List ;
  <integer> = { '_?IntegerQ' } ;
  <wgap> = { ' ' } ;
  ";

res = GenerateParsersFromEBNF[ParseToEBNFTokens[ebnfToy]];
LeafCount[res]

(* 769 *)

pWGAP = ParseMany1[ParsePredicate[MemberQ[{" ", "\n", "\t"}, #] &]];

pARGLIST = 
  ParseApply[StringJoin, 
   ParseMany1[ParsePredicate[! MemberQ[{"(", ")", "{", "}"}, #] &]]];

pLOGICALSTATEMENT = 
  ParseApply[StringJoin, 
   ParseMany1[ParsePredicate[! MemberQ[{"(", ")", "{", "}"}, #] &]]];

pINTEGER = 
  ParseApply[StringJoin, 
   ParseMany1[ParsePredicate[StringMatchQ[#, DigitCharacter] &]]];

Parsing

code = "f(1);
  for i 1 10 {
    print('test');
    f(62);
    if(i==2) { 
      print('test');
    } 
  }";

pres = pPROGRAM[Characters[code]];
pres[[1, 2]]

(* 
Program[{FunctionCall["f(1)"], 
  ForStatement[{ForSpec["for i 1 10"], 
    Program[{FunctionCall["print('test')"], FunctionCall["f(62)"], 
      IfStatement[{IfSpec["if(i==2)"], 
        Program[{FunctionCall["print('test')"]}]}]}]}]}] *)

Block[{Program = Identity, FunctionCall = Identity, 
  ForSpec = Identity, ForStatement = Identity, IfSpec = Identity, 
  IfStatement = Identity},
 pres[[1, 2]]
]

(* {"f(1)", {"for i 1 10", {"print('test')", 
   "f(62)", {"if(i==2)", {"print('test')"}}}}} *)

TreeForm@%

enter image description here

  • That's incredibly interesting - I'll start researching, but I'd also love for you to expand on that. It looks like exactly what I want. – TreFox Oct 11 at 13:37

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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