Lexical scanning and parsing in a toy language

Question

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?

Answer 1

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@%