Don't have an account? Register now to chat, post, use our tools, and much more.
Latest Headlines
Online Users
There are 140 users online: 4 members, 98 guests and 38 bots.
Members: cwipfli, seeseemelk.
Bots: VoilaBot (3), Spinn3r (3), Magpie Crawler (3), VoilaBot (12), Googlebot (17).
RSS & Social Media
SAX
You must log in to view the SAX chat widget
|
| Author |
Message |
|
AHelper
LONG LIVE COMICTECH
Joined: 30 Jan 2011
Posts: 1685
Location: Aufhelperstan, Utopian Republic
|
 Posted: 01 Apr 2012 11:56:18 pm Post subject: |
 |
|
I will be posting an explanation of a new way to parse strings into node trees. It will take me a while to type the post as I work out issues with the design. Stay tuned!
_________________
°ᴥ° Get Lucky
<BrandonW> "You don't even want to know what TI Connect does when it's just detecting your calculator...It ACTUALLY ERASES THE SWAP SECTOR on every communication attempt...EVERY SINGLE ATTEMPT...Yes, TI Connect will kill your calculator..What do I have to do to get your attention?!....Such a bloated protocol." |
|
| Back to top |
|
|
KermMartian
Site Admin
Joined: 14 Mar 2005
Posts: 55882
Location: Earth, Sol, Milky Way
|
| Posted: 02 Apr 2012 12:29:34 am Post subject: |
|
|
| AHelper wrote: | | I will be posting an explanation of a new way to parse strings into node trees. It will take me a while to type the post as I work out issues with the design. Stay tuned! |
Wait, you'll be parsing strings directly into trees instead of a list of nodes? I really need to get you my gcas2.c and gcas2.h; should I just dump them in your general direction?
_________________
 
 
 |
|
| Back to top |
|
|
AHelper
LONG LIVE COMICTECH
Joined: 30 Jan 2011
Posts: 1685
Location: Aufhelperstan, Utopian Republic
|
| Posted: 02 Apr 2012 12:41:46 am Post subject: |
|
|
emailing them is the easiest, or you could- pm them
- post them on sf.net/projects/glassos
- put a patch into the archives
- others
And yes, I will eliminate the cas_parse variable and combine gcas_parse_string and gcas_assemble_tree into one function. Fun, huh?
Also, I am very interested in how you added functions.
_________________
°ᴥ° Get Lucky
<BrandonW> "You don't even want to know what TI Connect does when it's just detecting your calculator...It ACTUALLY ERASES THE SWAP SECTOR on every communication attempt...EVERY SINGLE ATTEMPT...Yes, TI Connect will kill your calculator..What do I have to do to get your attention?!....Such a bloated protocol." |
|
| Back to top |
|
|
AHelper
LONG LIVE COMICTECH
Joined: 30 Jan 2011
Posts: 1685
Location: Aufhelperstan, Utopian Republic
|
| Posted: 03 Apr 2012 12:34:04 am Post subject: |
|
|
BE AWARE! YOUR EYES MAY BLEED WHILE READING THIS POST!
So, here is a prototype parser. Function:
Code:
cas_node* _proto_parse(char **s, cas_node* hold, cas_node* op);
The parser has two main variables, the hold and op variables. Both are cas_node*'s. The hold variable hold a complete tree, the op holds partial trees or references. A third variable, cas_node* last holds the last modified/created node.
So, here it goes, the string: "1+2*3^4+5"
So, hold: null, op: null, last: null;
parser enters a read loop. It reads the first character, identifies it as a number and calls parse_number. Parse number reads the string, gets the number, makes a node of that number, moves the string to after the number, and returns the node.
The hold variable gets the new node since it is null. The last variable is also set to it.
The loop is started again and a + is read. The parser calls a function that does the same thing as the last, but makes an addition node.
The op variable is set. op->n1 = hold; so the tree begins its assembly.
Hold: (1) op:(1)+(), last: (1)
Now, it reads the 2 and gets the node again. Since the op is !null, it completes the node. Last is the new node, so op->n2 = last; Also, hold=op; op=null;
Now:
Hold: (1)+(2) op: null last:(2)
So, here we get to a *. Op is set to the node. The parser checks the hold node to see if it is an op. It is, +. It does OoO and sees that * > +. The parser recurses.
Currently, hold: (1)+(2) op: (*) last: (2)
The new parser is called, all null values. We pass the (*) as the op and the (2) as the hold params. It starts out like
hold: (2) op: (*) last: (2);
If you followed the above, you can get to this point:
Hold: (2)*(3) op: null last: (3)
Now we read the ^ and get back to
Hold: (2)*(3) op: (^) last:(3)
Since ^ > *, we recurse yet again.
Starting #3 with
Hold: (3) op: (^) last: (3)
We can get to:
hold: (3)^(4) op: null last: (4)
Here's the fun part.
Read the op in, it is a +. This time, + < ^. Problems here!!! this function will return the hold variable. Somehow the (+) node needs to get passed back to the caller's op variable.
So, in parser #2, we have
hold:(2)*(3) op: (3)^(4) last: (3) somewhere: (+)
then... magic (not really, n2 would be replaced with op, that's all)
hold:(2)*((3)^(4)) op:(+) last: ???
Now, we do the same OoO checks. + < *, so we back out again.
in parser #1
hold: (1)+(2) op: (2)*((3)^(4)) last: (2) somewhere: (+)
then... magic hold->n2 = op;
hold: (1)+((2)*((3)^(4))) op: (+) last: ???
Now, we check OoO and see that + == +. Now, we complete the node (which is what we wanted to do in the first place). Now:
hold: (1)+((2)*((3)^(4))) op: ((1)+((2)*((3)^(4))))+() last: ???
Now, we continue as normal. We get the "5" and store to last. Since op !null, we finish the tree.
hold: ((1)+((2)*((3)^(4))))+(5) op: null last: (5)
Now, we hit a \0, so this function returns. Another example will be given later when I fix the return issue.
Things to do/make
cas_node* parse(char **s, cas_node* _hold, cas_node* _op);
cas_node* parse_number(char **s);
cas_node* parse_operation(char **s);
cas_node* parse_characters(char **s);
:: cas_node* parse_variable(char **s); // needs the variable array ptr
:: cas_node* parse_function(char **s); // for "[a-z]("
Please contribute any functions or feedback. This is crucial to improving gCAS2 and will remove the buggy functions in place and will allow syntax checking (if op !null and it wants to return for non-OoO reasons).
_________________
°ᴥ° Get Lucky
<BrandonW> "You don't even want to know what TI Connect does when it's just detecting your calculator...It ACTUALLY ERASES THE SWAP SECTOR on every communication attempt...EVERY SINGLE ATTEMPT...Yes, TI Connect will kill your calculator..What do I have to do to get your attention?!....Such a bloated protocol." |
|
| Back to top |
|
|
AHelper
LONG LIVE COMICTECH
Joined: 30 Jan 2011
Posts: 1685
Location: Aufhelperstan, Utopian Republic
|
| Posted: 06 Apr 2012 07:46:28 pm Post subject: |
|
|
Worked on the parser for a bit today, but was distracted (don't try to program at a ball park).
it is coming together slowly. i have error checking and reporting, so yay for that. More to come in this post.
_________________
°ᴥ° Get Lucky
<BrandonW> "You don't even want to know what TI Connect does when it's just detecting your calculator...It ACTUALLY ERASES THE SWAP SECTOR on every communication attempt...EVERY SINGLE ATTEMPT...Yes, TI Connect will kill your calculator..What do I have to do to get your attention?!....Such a bloated protocol." |
|
| Back to top |
|
|
KermMartian
Site Admin
Joined: 14 Mar 2005
Posts: 55882
Location: Earth, Sol, Milky Way
|
| Posted: 06 Apr 2012 07:52:07 pm Post subject: |
|
|
| AHelper wrote: | Worked on the parser for a bit today, but was distracted (don't try to program at a ball park).
it is coming together slowly. i have error checking and reporting, so yay for that. More to come in this post. |
Hurray! I hope I'll have the time to help out with testing, or at least writing, although my time commitments are not very amenable to that.
_________________
|
|
| Back to top |
|
|
AHelper
LONG LIVE COMICTECH
Joined: 30 Jan 2011
Posts: 1685
Location: Aufhelperstan, Utopian Republic
|
|
| Back to top |
|
|
KermMartian
Site Admin
Joined: 14 Mar 2005
Posts: 55882
Location: Earth, Sol, Milky Way
|
|
| Back to top |
|
|
AHelper
LONG LIVE COMICTECH
Joined: 30 Jan 2011
Posts: 1685
Location: Aufhelperstan, Utopian Republic
|
| Posted: 06 Apr 2012 10:12:31 pm Post subject: |
|
|
Firstly, yeah, I will change up the function naming, no problem.
Secondly, yes. Move the character pointer up. Here is my op parser function:
Code:
cas_node* parse_op(char**s)
{
char c = **s;
cas_node_type t;
cas_node *ret;
(*s)++;
switch(c)
{
case '+':
t = nADD;
break;
case '-':
t = nSUB;
break;
case '*':
t = nMULT;
break;
case '/':
t = nDIV;
break;
case '^':
t = nPOWER;
break;
default:
return (cas_node*)0;
break;
}
ret = parse_new_node();
ret->type = t;
return ret;
}
invoked like
Code:
char *str = "+34";
cas_node* plus = parse_op(&str);
str == "34";
Now, before anyone jumps into the function parsing, the storage method must be addressed now. I had planned to make non-binary node. Currently, you have n1 and n2, period. I have planned to add in the variable-sized node that would have cas_node *n[] and uint8_t count.
Each parameter will be treated as a node, so you can do things like log10(1+2,3+4). (This is also planned to be used with grouped addition, like a+b+a becoming (+)[a,b,a]. Currently gCAS2 cannot tell that (a+b)+a should be 2a+b, but a variable sized node will let me sort and group correctly.)
Now, remember that this isn't the same as {1,2,3} (lists), could use the same method, but isn't being thought about just yet.
KermM: if you make the function parser, you can watch gcas2.c in svn as I work on it. I will try to commit often. And now for some notes on functions:
Since C is nice, I can make the variable sized node as
Code:
typedef struct
{
cas_node_type;
uint8_t count;
cas_node *n[];
} cas_node_vl; (variable-length)
i reorder the cas_node to have node_type on top so you can cast properly. A type of nFUNCTION will mean that the node should be cast to a cas_node_vl. So, I intend that all functions use the vl node type, even short functions (sqrt() sin(), etc.). The binary nodes were intended only for binary operations (I eliminated factorial support since it doesn't fit in with the cas_node usage.
(Commit 61 is for you. Look for commits like "aimed at KermM", which should contain gcas stuffs)
_________________
°ᴥ° Get Lucky
<BrandonW> "You don't even want to know what TI Connect does when it's just detecting your calculator...It ACTUALLY ERASES THE SWAP SECTOR on every communication attempt...EVERY SINGLE ATTEMPT...Yes, TI Connect will kill your calculator..What do I have to do to get your attention?!....Such a bloated protocol." |
|
| Back to top |
|
|
KermMartian
Site Admin
Joined: 14 Mar 2005
Posts: 55882
Location: Earth, Sol, Milky Way
|
| Posted: 06 Apr 2012 10:26:28 pm Post subject: |
|
|
That seems very reasonable to me. I definitely see the cases where multiple-argument functions will be important, and I absolutely support anything that will provide more symbolic CAS support.
_________________
|
|
| Back to top |
|
|
AHelper
LONG LIVE COMICTECH
Joined: 30 Jan 2011
Posts: 1685
Location: Aufhelperstan, Utopian Republic
|
| Posted: 06 Apr 2012 10:59:29 pm Post subject: |
|
|
Another compilcation, if I branch out, I return if the op is less than the last op node. Now, if I do 1*2+3, the parser would want to return at +, even though it cannot return. Should it check the parameters if one isn't null? is there a case if no params are passed? iirc, left paren. passes no params., so I am a bit lost for the best way...
_________________
°ᴥ° Get Lucky
<BrandonW> "You don't even want to know what TI Connect does when it's just detecting your calculator...It ACTUALLY ERASES THE SWAP SECTOR on every communication attempt...EVERY SINGLE ATTEMPT...Yes, TI Connect will kill your calculator..What do I have to do to get your attention?!....Such a bloated protocol." |
|
| Back to top |
|
|
KermMartian
Site Admin
Joined: 14 Mar 2005
Posts: 55882
Location: Earth, Sol, Milky Way
|
| Posted: 07 Apr 2012 09:07:09 am Post subject: |
|
|
Hmm, that's tricky.  One thing that had been vaguely occurring to me even before you brought this up would be to build the tree in order, not worrying about order-of-operations, then swap operator nodes as necessary. I'm not sure if it would work, though.
_________________
|
|
| Back to top |
|
|
AHelper
LONG LIVE COMICTECH
Joined: 30 Jan 2011
Posts: 1685
Location: Aufhelperstan, Utopian Republic
|
| Posted: 07 Apr 2012 12:05:43 pm Post subject: |
|
|
That's what the old parser was doing. (I hope, i forgot a lot about it since I couldn't read what I typed )
Direct creation of the tree should be the fastest and not require too much extra parsing.
About my previous problem, I am thinking about using an error code to warn the function that it is the first. CASERR_FIRST_PARSE can be passed in to the last variable, shouldn't be hard to check and use in the routine.
_________________
°ᴥ° Get Lucky
<BrandonW> "You don't even want to know what TI Connect does when it's just detecting your calculator...It ACTUALLY ERASES THE SWAP SECTOR on every communication attempt...EVERY SINGLE ATTEMPT...Yes, TI Connect will kill your calculator..What do I have to do to get your attention?!....Such a bloated protocol." |
|
| Back to top |
|
|
AHelper
LONG LIVE COMICTECH
Joined: 30 Jan 2011
Posts: 1685
Location: Aufhelperstan, Utopian Republic
|
| Posted: 08 Apr 2012 01:42:02 am Post subject: |
|
|
So, this calls for a new post.
The new parser function, seen here: http://glassos.svn.sf.net/viewvc/glassos/trunk/src/gCAS2/gcas2.c?view=markup&pathrev=63 at line 916
is now starting to work in gCAS2. Currently, initial tests look very good. I have op parsing for +-*/^ (removed !), number parsing with leading - as a negative and decimal (also can be leading), and parenthesis. I will add to this post when more tests are completed:
Parsed: "12.3+4.56"
What happens: The parser starts up and runs through three loops, 2 for the numbers and 1 for the op. Showing off decimal support.
Parsed: "1+2+3"
What happens: The parser is running for more than just one op. Here, it parses left to right with the right-most nodes as the root of the tree (on top).
Parsed: "1+"
Returns: Error code 4 - Reason: An op is incomplete and is one-sided.
Parsed: "1+2*3"
What happens: The parse makes the 1+2 node as normal, but this time if sees that the next op is higher ranked than the held op (* > + in order of ops). The parser then branches out.
Parsed: "1+2*3+4"
What happens: The parser does the same thing as above, but takes it another step. When a new op is read in, if checks it to the held op. if new > held, then it branches. if new == held, it continues on. if new < held, then it will return if it branched out.
Parsed: "1+2*(3+4)-5"
What happens: When the parser hits the '(', it branches out as it it hit the start of a string. When it hits the *, it would pass on the hold and incomplete nodes in order to work with already parsed nodes. The '(' causes it to start fresh, returning on the next ')' or '\0'. (Bug is here, but the result is correct)
Parsed: "1+2-3*4/5^6/7*8-9+10"
What happens: So, the parser recurses every time the next op > the current op. Look at the top. You have 1+(...)+10. It is doing its job to do left-to-right order of ops while recursing, giving this awesome looking tree.
Parsed: "1+2^3*4"
What is happening: The parser returns from a branch started with the ^, then has to rebranch since the * > +.
(Bow down to graphviz for letting me make gCAS2 generate such lovely images)
Next, I need variable and function support added, then the CAS can have work done on functions and the new node type 
_________________
°ᴥ° Get Lucky
<BrandonW> "You don't even want to know what TI Connect does when it's just detecting your calculator...It ACTUALLY ERASES THE SWAP SECTOR on every communication attempt...EVERY SINGLE ATTEMPT...Yes, TI Connect will kill your calculator..What do I have to do to get your attention?!....Such a bloated protocol."
Last edited by AHelper on 10 Apr 2012 06:50:43 am; edited 3 times in total |
|
| Back to top |
|
|
AHelper
LONG LIVE COMICTECH
Joined: 30 Jan 2011
Posts: 1685
Location: Aufhelperstan, Utopian Republic
|
| Posted: 08 Apr 2012 09:49:37 pm Post subject: |
|
|
Now the problem: | Quote: | | Read the op in, it is a +. This time, + < ^. Problems here!!! this function will return the hold variable. Somehow the (+) node needs to get passed back to the caller's op variable. |
For the images before, I hacked and just returned the new node because the incomplete node in the parent would be modified. I forgot that when the hold node of the branch is modified, the parent's incomplete node is invalid.
1+2*3^3*2+1 - When it hits the * after ^3, it returns and changes the hold node. It never returns this change, so you end up with 1+2*3^3+1, not fun. Adding in a cas_node **next_incomplete var to the parameters for parse(...); to fix that. Return will now be the hold variable, as it should be.
Also, all of the above equations generated (prev. post) ran without any memory leaks, woo!
_________________
°ᴥ° Get Lucky
<BrandonW> "You don't even want to know what TI Connect does when it's just detecting your calculator...It ACTUALLY ERASES THE SWAP SECTOR on every communication attempt...EVERY SINGLE ATTEMPT...Yes, TI Connect will kill your calculator..What do I have to do to get your attention?!....Such a bloated protocol." |
|
| Back to top |
|
|
AHelper
LONG LIVE COMICTECH
Joined: 30 Jan 2011
Posts: 1685
Location: Aufhelperstan, Utopian Republic
|
| Posted: 10 Apr 2012 06:50:19 am Post subject: |
|
|
I fixed the return so that I pass a cas_node **next_incomplete as a parameter now. The latest image is showing that addition along with clearer logic in branching code.
_________________
°ᴥ° Get Lucky
<BrandonW> "You don't even want to know what TI Connect does when it's just detecting your calculator...It ACTUALLY ERASES THE SWAP SECTOR on every communication attempt...EVERY SINGLE ATTEMPT...Yes, TI Connect will kill your calculator..What do I have to do to get your attention?!....Such a bloated protocol." |
|
| Back to top |
|
|
KermMartian
Site Admin
Joined: 14 Mar 2005
Posts: 55882
Location: Earth, Sol, Milky Way
|
| Posted: 10 Apr 2012 07:58:18 am Post subject: |
|
|
Great! I'm very happy that you've been adding the error-detection. Do the codes for that identify where in the string the error occurred, by the way, or is it just a general error code?
_________________
|
|
| Back to top |
|
|
AHelper
LONG LIVE COMICTECH
Joined: 30 Jan 2011
Posts: 1685
Location: Aufhelperstan, Utopian Republic
|
| Posted: 10 Apr 2012 08:43:08 am Post subject: |
|
|
| KermMartian wrote: | | Great! I'm very happy that you've been adding the error-detection. Do the codes for that identify where in the string the error occurred, by the way, or is it just a general error code? |
Yes, the error location can be determined. Since the string pointer is modified, it will be left at the source of the error.
_________________
°ᴥ° Get Lucky
<BrandonW> "You don't even want to know what TI Connect does when it's just detecting your calculator...It ACTUALLY ERASES THE SWAP SECTOR on every communication attempt...EVERY SINGLE ATTEMPT...Yes, TI Connect will kill your calculator..What do I have to do to get your attention?!....Such a bloated protocol." |
|
| Back to top |
|
|
KermMartian
Site Admin
Joined: 14 Mar 2005
Posts: 55882
Location: Earth, Sol, Milky Way
|
| Posted: 10 Apr 2012 10:46:37 am Post subject: |
|
|
That's superb! That will come in very, very handy for the next beta of Graph3DP that will use the new parser.
_________________
|
|
| Back to top |
|
|
AHelper
LONG LIVE COMICTECH
Joined: 30 Jan 2011
Posts: 1685
Location: Aufhelperstan, Utopian Republic
|
| Posted: 10 Apr 2012 12:26:30 pm Post subject: |
|
|
Are you still interested in making the function parser? I will be getting onto the variable parser sometime...
I really need to get that new node created for functions and such... so little time
_________________
°ᴥ° Get Lucky
<BrandonW> "You don't even want to know what TI Connect does when it's just detecting your calculator...It ACTUALLY ERASES THE SWAP SECTOR on every communication attempt...EVERY SINGLE ATTEMPT...Yes, TI Connect will kill your calculator..What do I have to do to get your attention?!....Such a bloated protocol." |
|
| Back to top |
|
|
|
Register to Join the Conversation
Have your own thoughts to add to this or any other topic? Want to ask a question, offer a suggestion, share your own programs and projects, upload a file to the file archives, get help with calculator and computer programming, or simply chat with like-minded coders and tech and calculator enthusiasts via the site-wide AJAX SAX widget? Registration for a free Cemetech account only takes a minute.
» Go to Registration page
|
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum
|
© Copyright 2000-2013 Cemetech & Kerm Martian :: Page Execution Time: 0.047620 seconds.
|
![[t]](/forum/templates/Cemetech6/images/twitter.png)
![[t]](/forum/templates/Cemetech6/images/fb.png)
![[RSS]](/forum/templates/Cemetech6/images/rss.png)
