String parsing: how to isolate parameters when a parameter can be a nested function

Question

In java, I'm trying to process functions of the from FUNC{parameter,parameter} using regular expressions. I've isolated the string containing the parameters, and now I have to extract them from the string. My idea was to split the parameters using the string.split method and the , symbol. I.e. expression.split(",").

The problem is that the parameters can themselves be functions, i.e. something like

FUNC1{FUNC2{1,2},7}

So splitting just by , doesn't work. What I'm trying now is the follow regex:

[^\\{]+,[^\\}]+

Which I think means, split the parameters by a , that is preceded by something that isn't a { and followed by something that isn't a }. But this isn't working either...what could be the problem?

Is this the highest level of nesting you will encounter? Or can you have FUNC1{FUNC2{FUNC3{FUNC4{...}}}} arbitrarily deep? — Oliver Charlesworth
– Oliver Charlesworth, Commented Apr 6, 2011 at 20:09
The language of balanced nested brackets (or any other symbol, for that matter) of an arbitrary depth is not regular. — eldarerathis
– eldarerathis, Commented Apr 6, 2011 at 20:09

schizodactyl · Accepted Answer · 2011-04-06 20:20:06Z

4

Regular expressions are not able to parse infinitely recursive structures, why not just read in the string and parse out your parameters?

Read the input one character at a time, find the first opening brace, continue to read until you hit a comma that is not inside another set of braces (count opening and closing braces until they are equal), and set the string between these positions to the value of the first parameter. Then continue to read the input until you hit a closing brace that is not inside another set of braces, and set this value to the second parameter. With some smart programming (not quite the algorithm I described) you can parse your entire input in one pass, including every function referenced inside an argument and that function's arguments.

answered Apr 6, 2011 at 20:20

schizodactyl

1,4551 gold badge10 silver badges11 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

DwB · Accepted Answer · 2011-04-06 20:08:52Z

1

Here is a link to a Java Regular Expression Test Tool

answered Apr 6, 2011 at 20:08

DwB

38.6k11 gold badges62 silver badges86 bronze badges

Comments

ŁukaszBachman · Accepted Answer · 2011-04-06 20:16:21Z

1

I believe the better way to achieve this would be to use Scanner. Scanner will let you to skip certain parts of input (String, in this case), group (i.e. retrieve) some of it's parts by matching regular expressions, and so on. It is very useful tool with powerful API.

Hope that helps to know where to look for.

answered Apr 6, 2011 at 20:16

ŁukaszBachman

33.8k11 gold badges68 silver badges74 bronze badges

Comments

Tim Bender · Accepted Answer · 2011-04-06 20:19:28Z

0

As mentioned in the comments, the language you are parsing doesn't appear to be regular, so it can't be parsed by a regular expression.

As for your current approach, calling String.split() will consume/destroy the portion of the String which matches the expression (not just the comma!) and i don't think that is what you want.

answered Apr 6, 2011 at 20:19

Tim Bender

20.5k2 gold badges52 silver badges59 bronze badges

1 Comment

user557597 Over a year ago

doesn't appear to be regular What does this mean, and is there a hi-test?

Collectives™ on Stack Overflow

String parsing: how to isolate parameters when a parameter can be a nested function

4 Answers 4

Comments

Comments

Comments

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

4 Answers 4

Comments

Comments

Comments

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related