[Home] [Downloads] [Search] [Help/forum]

Register forum user name Search FAQ

Gammon Forum

[Folder]  Entire forum
-> [Folder]  Programming
. -> [Folder]  General
. . -> [Subject]  Expression parser
Expression parser

It is now over 60 days since the last post. This thread is closed.     [Refresh] Refresh page

Pages: 1  2  3  4 5  

Posted by Nick Gammon   Australia  (22,985 posts)  [Biography] bio   Forum Administrator
Date Reply #45 on Mon 15 Feb 2010 07:16 PM (UTC)
Message
You are certainly supposed to be able to call Evaluate multiple times. I found the problem, the new version has been pushed to GitHub:


http://github.com/nickgammon/parser

The changes are here:

http://github.com/nickgammon/parser/commit/994c67

Basically it was not resetting the pWord_ pointer back to the start of the expression when you called Evaluate again. I don't know why no-one noticed this earlier.
- Nick Gammon

www.gammon.com.au, www.mushclient.com
[Go to top] top
Posted by Nick Gammon   Australia  (22,985 posts)  [Biography] bio   Forum Administrator
Date Reply #46 on Mon 15 Feb 2010 08:46 PM (UTC)
Message
I have made a couple of other corrections, basically moving the resetting the pointer into a single place, and improving the Makefile for making the test program.

The complete source can be downloaded from:

http://github.com/nickgammon/parser/downloads
- Nick Gammon

www.gammon.com.au, www.mushclient.com
[Go to top] top
Posted by Bruno Jobard   (2 posts)  [Biography] bio
Date Reply #47 on Tue 16 Feb 2010 02:15 AM (UTC)
Message
Thank you Nick for the modifications. It works fine now.

But I am concern by performances because I have to fill a big 2D array with values evaluated for a single expression.

Is there any way, when the expression has been parsed once, to evaluate subsequent results with a kind of "compiled" expression? Meaning not having to start all the parsing again.

Ideally, I would like to reach performances close to hard coded expression. Is there any way of accelerating the evaluation?

Thanks,

Bruno.
[Go to top] top
Posted by Nick Gammon   Australia  (22,985 posts)  [Biography] bio   Forum Administrator
Date Reply #48 on Tue 16 Feb 2010 03:01 AM (UTC)
Message
Not really. The basic design is to evaluate on-the-fly.

According to page 1 of this thread the parser works reasonably fast (like 10,000 evaluations in under a second).

But if you really need to do millions of evaluations of a single expression this is probably the time to switch to using C++.

Or try using Lua. Lua is pretty fast, and does in fact precompile an expression.
- Nick Gammon

www.gammon.com.au, www.mushclient.com
[Go to top] top
Posted by Bernhard   (18 posts)  [Biography] bio
Date Reply #49 on Tue 27 Apr 2010 07:21 PM (UTC)
Message
I found your parser quite useful.
Yet, I've got a problem with the "if" function. It seems like both, the if and the else section are evaluated regardless of the condition:
"if(cond,a=1,b=2)" always sets, a to 1 and b to 2, for cond==0 as well as for cond!=0.
also "if(something,x=x+1,x)" does not behave like I expected.
[Go to top] top
Posted by David Haley   USA  (3,881 posts)  [Biography] bio
Date Reply #50 on Tue 27 Apr 2010 07:44 PM (UTC)
Message
'If' is a function here, not a control flow statement. So, all arguments are evaluated, as for any function, and then the function returns the expression (which, recall, has already been evaluated) matching the condition.

This is by design, this is meant to be an expression parser, not a full language.
David Haley aka Ksilyan
Head Programmer,
Legends of the Darkstone

http://david.the-haleys.org
[Go to top] top
Posted by Nick Gammon   Australia  (22,985 posts)  [Biography] bio   Forum Administrator
Date Reply #51 on Tue 27 Apr 2010 08:13 PM (UTC)
Message
Bernhard said:

"if(something,x=x+1,x)" does not behave like I expected.


David is right. To add 1 to x under a condition you want something more like:


x = if (something, x + 1, x)


The result of the if function will be either x + 1, or x, depending on the condition, and this result is then assigned to x.
- Nick Gammon

www.gammon.com.au, www.mushclient.com
[Go to top] top
Posted by Bernhard   (18 posts)  [Biography] bio
Date Reply #52 on Mon 03 May 2010 08:45 PM (UTC)
Message
The two examples in my last post were actually simplified, just to isolate the problem. My real intention (still simplified) was to implemente a sequence of statements like

if(0==eventAB, state17=1,
if(state11, state18=1,
if(state12, state19=1, ...)))
if(0==eventCD, state17=1, if(...))

Of course this can be reformulated to

state17 = if(0==eventAB, 1, state17)
state18 = if((0!=eventAB)&&(state11), 1, state18)
state19 = if((0!=eventAB)&&(0==state11)&&(state12), 1, state19)
...
state17 = if(0==eventCD, 1, state17)

unfortunately it makes the code less readable.

My other intention was to add an "exec(###)" function which calls a batch file (returning the ERRORLEVEL), so basically "return system(script###.bat)" in C. This would allow to get data from external scripts e.g., cond59=exec(11), and to trigger reactions, e.g., if(condition_for_reaction12, exec(12), 0)

[Go to top] top
Posted by Nick Gammon   Australia  (22,985 posts)  [Biography] bio   Forum Administrator
Date Reply #53 on Mon 03 May 2010 08:56 PM (UTC)
Message
Yes, well it is an expression parser, not a full statement parser. If you are going to run external scripts anyway, why not just use Lua? That has a small footprint, and can be imbedded into C or C++ with minimal effort. You can then write things in a more natural way. That would be much, much neater than trying to use this parser and shoe-horn in an external script via system calls. For example:

Template:post=6400 Please see the forum thread: http://gammon.com.au/forum/?id=6400.
- Nick Gammon

www.gammon.com.au, www.mushclient.com
[Go to top] top
Posted by David Haley   USA  (3,881 posts)  [Biography] bio
Date Reply #54 on Mon 03 May 2010 10:42 PM (UTC)
Message
Yes, I agree, if you want a real programming language why not just use one? What's the higher-level context here?
David Haley aka Ksilyan
Head Programmer,
Legends of the Darkstone

http://david.the-haleys.org
[Go to top] top
Posted by Bernhard   (18 posts)  [Biography] bio
Date Reply #55 on Wed 05 May 2010 08:18 PM (UTC)
Message

My intention was to add some advanced configuration capability to my C/C++ program. Those configurations should not be written by me but by the users – so, usually by people without good programming skills. The basic configuration, let’s call it level 1, would be simple parameters like "maxUsers = 20". I can read them with GetPrivateProfileString/Int or whatever. Level 2 would allow simple expressions, e.g., configurations like "logBufferSize = maxUserSessions * 100" or conditions like "acceptEntry = (userLevel > 5) * (currentUserCount < 20)" – basically the same kind of expressions you can use in Microsoft Excel & co. (which actually allows “if”). I think your parser is perfectly suitable to add this type of configuration features to a C/C++ program. Level 3 allows some simple conditional reactions, maybe similar to state machine descriptions. That's where I ran into troubles with the 'if'. Still I think I should not burden the users with learning a full programming language. It’s beyond debate that anything more than that (level 4) requires a scripting language (vbscript, lua, ..) or (level 5) even a component/plug-in architecture in the main program – that would certainly would overshoot the mark as a configuration/customization interface for someone without proper programming skills.

Level 3 should be sufficient. On the other hand, users tend to want more and more anyway. lua will certainly satisfy even ambitious users and if it encourages someone to learn a full programming language its fine with me. lua looks quite promising, the only thing I hate is that it considers 0 as true while most (all?) other languages do not - I can already her the users complaining. I also have to allow a syntax as simple as "maxUsers = 50" if you only need configuration level 1.

What do you think?
[Go to top] top
Posted by David Haley   USA  (3,881 posts)  [Biography] bio
Date Reply #56 on Wed 05 May 2010 08:34 PM (UTC)
Message
It turns out that Lua was originally designed precisely as a configuration language. You can easily extend C/C++ with Lua, as Nick said, and then have config files that look like this:


use_ui = false 


-- high level search settings
directional_increment = 0.05
probabilistic_roadmap_size = 250

probabilistic_focus_roadmap_points_per_point = 5
probabilistic_focus_roadmap_spread_x = 0.10
probabilistic_focus_roadmap_spread_y = 0.10
use_highlevel_smoothing = false

roadmap_predicate_thresholdz_init = 0.01
roadmap_predicate_thresholdz_inc  = 0.01
roadmap_predicate_thresholdz_max  = 0.05

roadmap_predicate_maxside_threshold_init =  0.030
roadmap_predicate_maxside_threshold_inc  =  0.005
roadmap_predicate_maxside_threshold_max  =  0.050

highlevel_goal_proximity = 0.05
highlevel_goal_proximity_factor = 0.3

highlevel_thresholdz_maxjump = 1.5

terrain_polling_num_samples = 50

goal_cost_bias = 0.95
goal_heur_bias = 0.95

highlevel_cost_function = "HighLevelCostFunction"
highlevel_heur_function = "HighLevelHeurFunction"
highlevel_pred_function = "RoadmapVisibilityPredicate"
highlevel_lua_func_file = "highlevel.lua"

-- debugger settings
debug_astar = true
debug_class = true
debug_sim = true
debug_train = true


Or as a more complicated example, like this:

TerrainTypes = {
        beach = { name = "beach", tileImage = "tiles/world/beach.png"},
        densewoods = { name = "densewoods", tileImage = "tiles/world/dense_woods.png" },
        densewoods_snow = { name = "densewoods_snow", tileImage = "tiles/world/dense_woods_snow.png" },
        desert = { name = "desert", tileImage = "tiles/world/desert.png" },
        farmland = { name = "farmland", tileImage = "tiles/world/farmland.png" },
        fields = { name = "fields", tileImage = "tiles/world/fields.png" },
        ice = { name = "ice", tileImage = "tiles/world/ice.png" },
        jungle = { name = "jungle", tileImage = "tiles/world/jungle.png" },
        lightwoods = { name = "lightwoods", tileImage = "tiles/world/light_woods.png" },
        lightwoods_snow = { name = "lightwoods_snow", tileImage = "tiles/world/light_woods_snow.png" },
        mountain = { name = "mountain", tileImage = "tiles/world/mountain.png" },
        ocean = { name = "ocean", tileImage = "tiles/world/ocean.png" },
        pass = { name = "pass", tileImage = "tiles/world/pass.png" },
        plains = { name = "plains", tileImage = "tiles/world/plains.png" },
        range = { name = "range", tileImage = "tiles/world/range.png" },
        river = { name = "river", tileImage = "tiles/world/river.png" },
        rocky = { name = "rocky", tileImage = "tiles/world/rocky.png" },
        savannah = { name = "savannah", tileImage = "tiles/world/savannah.png" },
        snow = { name = "snow", tileImage = "tiles/world/snow.png" },
        swamp = { name = "swamp", tileImage = "tiles/world/swamp.png" },
        tundra = { name = "tundra", tileImage = "tiles/world/tundra.png" },
        wasteland = { name = "wasteland", tileImage = "tiles/world/wasteland.png" },
}


The user doesn't have to even know that they're using Lua; I think that the above examples, especially the first one, show that you can have a config file that is Lua but looks very simple. They can even do variables and have if statements in there, if they want to.

Anyhow, you can have the simple syntax as shown above by loading the script and executing it in a special environment. Then, all assignments to "global" variables will be made into that environment table, and you can pick them out of it later.

It's true that you'll have to deal with 0 being 'true' in Lua, but, well, that's life.



You can do similar things in Python, like this:

name = "Building_Wall"
image = "gfx/Buildings/Wall.bmp"
transparency = (255, 0, 255)

# Cap naming convention: cap_<NESW>
#
# Joint naming convention: joint_<direction in which there is no cap>
#
# Base naming convenition: base_<WE>

tiles = {
    
    'cap_0110': (0, 0, 20, 20),
    'cap_0111': (40, 0, 20, 20),
    'cap_0011': (80, 0, 20, 20),

    'cap_1110': (0, 40, 20, 20),
    'cap_1111': (40, 40, 20, 20),
    'cap_1011': (80, 40, 20, 20),

    'cap_1100': (0, 80, 20, 20),
    'cap_1101': (40, 80, 20, 20),
    'cap_1001': (80, 80, 20, 20),

    'cap_1100_baseleft': (240, 0, 20, 20),
    'cap_1110_baseleft': (240, 40, 20, 20),

    'joint_northeast': (0, 140, 20, 20),
    'joint_northwest': (40, 140, 20, 20),
    'joint_southeast': (80, 140, 20, 20),
    'joint_southwest': (120, 140, 20, 20),

    'base_01': (0, 100, 20, 20),
    'base_11': (40, 100, 20, 20),
    'base_10': (80, 100, 20, 20),

    'dummy': (20, 0, 20, 20),
    
}


but Lua is easier to embed (and much more lightweight) than Python.
David Haley aka Ksilyan
Head Programmer,
Legends of the Darkstone

http://david.the-haleys.org
[Go to top] top
Posted by Nick Gammon   Australia  (22,985 posts)  [Biography] bio   Forum Administrator
Date Reply #57 on Wed 05 May 2010 09:03 PM (UTC)

Amended on Wed 05 May 2010 09:45 PM (UTC) by Nick Gammon

Message
Bernhard said:


lua looks quite promising, the only thing I hate is that it considers 0 as true while most (all?) other languages do not - I can already her the users complaining.


I don't think it is too bad personally. After all, having 0 be false and non-zero to be true is really a throwback to the way C does it (and remember VB used to use -1 for true which is kind of confusing too).

Just say, "for booleans use true and false". It makes sense really.

However if this completely throws people out you have a couple of options:


  • For variables that are supposed to be boolean (ie from your internal context) throw an error if they don't supply a boolean (in particular, the number 0 could be ambiguous - did they really mean "false"?)

  • Or, for booleans simply convert 0 to false as you process the variable.


You need range-checking anyway (eg. what happens if they make maxUsers to be -100?). So checking booleans have a valid value is just another check.
- Nick Gammon

www.gammon.com.au, www.mushclient.com
[Go to top] top
Posted by Nick Gammon   Australia  (22,985 posts)  [Biography] bio   Forum Administrator
Date Reply #58 on Wed 05 May 2010 09:57 PM (UTC)
Message
Bernhard said:


lua looks quite promising, the only thing I hate is that it considers 0 as true while most (all?) other languages do not - I can already her the users complaining.


The other thing is that I don't know about this being totally true. After all, 0 is a number and false is a boolean. They are different types for a start. Just as an example, in SQL, it uses NULL to represent "no data" in the same way Lua uses nil.

As an example, say on a database you wanted to know how many children someone has. The answer NULL could mean "that number is unknown (and could be anything)" whereas 0 means "we know the answer, and the answer is zero".

Thus trying to make NULL and zero have the same meaning would not be useful.

Similarly with Lua, variables themselves are untyped (the values are typed, not the variable). Thus numerically typed values have to be able to hold any number (including zero) without being mistaken for a boolean typed value.

There is an interesting discussion here:

http://en.wikipedia.org/wiki/Boolean_data_type

Amongst other things it says:

Wikipedia said:

In Ruby programming language, on the other hand, only the null object and a special false object are "false", everything else (including the integer 0) is "true".


So in Ruby, at least, it also does not treat 0 as false.
- Nick Gammon

www.gammon.com.au, www.mushclient.com
[Go to top] top
Posted by Bernhard   (18 posts)  [Biography] bio
Date Reply #59 on Thu 06 May 2010 09:18 PM (UTC)
Message
Thank you Nick and David. I will switch to lua then.

Nick Gammon said:

However if this (0 = true) completely throws people out you have a couple of options:

*For variables that are supposed to be boolean (ie from your internal context) throw an error if they don't supply a boolean (in particular, the number 0 could be ambiguous - did they really mean "false"?)

*Or, for booleans simply convert 0 to false as you process the variable.

You need range-checking anyway (eg. what happens if they make maxUsers to be -100?). So checking booleans have a valid value is just another check.


I'm not sure if I should do that, because it makes conditions internal to lua behave different than the conditions which are passed on to C/C++. If I consider 'return 0' as false when the caller was a C function, it is still true in case the caller was a lua function. 


lua_genpcall(L, "if (0) then print '0 is true' end", "");

will allways print '0 is true' unless I change lua itself and make my own dialect ... so I better instruct the users to keep this in mind and tell them something like:

David Haley said:

It's true that you'll have to deal with 0 being 'true' in Lua, but, well, that's life.


;-)

[Go to top] top

The dates and times for posts above are shown in Universal Co-ordinated Time (UTC).

To show them in your local time you can join the forum, and then set the 'time correction' field in your profile to the number of hours difference between your location and UTC time.

195,206 views.

This is page 4, subject is 5 pages long:  [Previous page]  1  2  3  4 5  [Next page]

It is now over 60 days since the last post. This thread is closed.     [Refresh] Refresh page

Go to topic:           Search the forum

[Go to top] top

Quick links: MUSHclient. MUSHclient help. Forum shortcuts. Posting templates. Lua modules. Lua documentation.

Information and images on this site are licensed under the Creative Commons Attribution 3.0 Australia License unless stated otherwise.

[Home]

Written by Nick Gammon - 5K   profile for Nick Gammon on Stack Exchange, a network of free, community-driven Q&A sites   Marriage equality

Comments to: Gammon Software support
[RH click to get RSS URL] Forum RSS feed ( https://gammon.com.au/rss/forum.xml )

[Best viewed with any browser - 2K]    [Hosted at HostDash]