# Lexical scanning and parsing in a toy language

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

• 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 '18 at 13:37