Page 1 of 2
Programming help
Posted: Mon Dec 08, 2008 1:31 am
by XMEN Ashaman DTM
Okay. I've been working on a problem for a while now. I think I need some professional help (no really!)
What I am trying to do is parse a c++ sourcefile. Yes, it has to be c++ due to certain keywords (the different casts for one). Now, I am trying to do it as compactly as possible, but still readable.
Here's what I have so far:
a class that breaks a source file up into keyword tokens. I've identified all of my relevant keywords, focusing on identifying and classifying functions within the sourcecode as my next objective.
I plan on writing these codified sourcefiles to another file so that I can use them to work in a different program. I'm basically building a tool to perform some algorithm design and testing, and making my tool aware of the contents of a sourcefile helps out tremendously.
No, I'm not building an abstract symbols table, but it's along the same kind of idea I think. At least as I understand it, an AST is what a compiler uses to organize code and then optimize it.
Anyways, can anyone think of another way to implement this? It's taking forever to write out all of the keywords that I want to look for, and coming up with identifyers for each one. Is there a chart that shows all of the keywords used in c++ that is organized in some fashion? Say the keywords for program flow/control, the keywords for datatypes, and so on?
Here's the header for my class:
Code: Select all
class keywords
{
public:
keywords();
~keywords();
int isakeyword(string checkthisword); //Returns 1 if true, 0 if false
int getkeywordid(string keyword); //Returns keyword ID, 0 if an error
private:
int keywordid;
int keywordindex;
}
To me, c++ is still a different way of thinking from when I was in the embedded systems world with c. And the scientific stuff is easier for some reason, regardless of whether it's c or fortran or matlab.
isakeyword just verifies that the string read in has a keyword. getkeywordid does just what it's name says. I think if I implement it this way, it will read the string to look for keywords, and start writing a string that is basically a keyword (but as a code like f1i1ixxxx for a function with one input and one output - both integers). I don't know if that's going to be very fast though. Any thoughts on this part?
[/code]
Posted: Mon Dec 08, 2008 7:23 pm
by XMEN Iceman
Gambit is the man for this. Not me...I am just a simple Server Admin.
Posted: Mon Dec 08, 2008 10:10 pm
by XMEN Ashaman DTM
It's cool, Ice. I just wanted some advice from someone that has more experience than I do. You know?
Oh and as far as the class internals:
The functions are self explanatory, but the one that returns a keywordID uses a lookup table implemented in a struct. Right now, the table is indexed into with an enum type of the major keywords I'm looking for. Then, I search through the table until I find what I am looking for. And then the function returns, from the table, an ID code. It just seems so cumbersome this way, and I want to know if my thinking is correct (since I'm just a rocket scientist that has done quite a bit of scientific computing and not much with strings...)
Posted: Mon Dec 08, 2008 10:50 pm
by XMEN Gambit
Well, I've actually never written a compiler which would be the best background for this. However, you should probably take a look at the source for an open-source C++ compiler (such as gcc) to see how they did it. gcc might be a bit much, though, so if you can, find a different one. I found a couple resources that might help out, too. I've listed them below. But off the top of my head, backed up by what I've found, C++ is one of the more difficult languages to parse. It does sound like you're building an AST.
http://www.nobugs.org/developer/parsingcpp/
http://codeworker.free.fr/
http://portal.acm.org/citation.cfm?id=858245
----------------------
Having said that, here's some things to keep in mind:
1) C++ is case sensitive. Yes, I know this is on the level of "is it plugged in," I just didn't want you doing cross-case comparisons.
2) You've just listed the header rather than an implementation, but you should be able to find a hashmap class or something similar that will automatically return the index of a stored string ("keyword") when given the string. You can then eliminate isakeyword and your getkeywordid method will be fast. Really fast. There are implementations with very fast algorithms that will work a heck of a lot faster than something you'll code yourself. You can preload the data in your initialization phase (preferably from a config file) and then go parsing all you like.
Posted: Tue Dec 09, 2008 1:04 am
by XMEN Ashaman DTM
/me slaps head!
I totally forgot about hashes!
Posted: Tue Dec 09, 2008 3:35 am
by XMEN Ashaman DTM
Here's another question after reading through some material that I found via google (hash tables) and the links you posted:
I think I can define my own hashes, right? If that's the case, how can I dynamically define them? Actually, I think I have an idea for that. I guess my bigger question is, would I want to manipulate the hashes in my output file? Let me reword that: I'm thinking of building the hash table dynamically, say filling in values from a pre-defined table. So I would manipulate the hash table that I build dynamically, right? I'm not doing file writing until I need to (overhead, blech).
So I think I need a couple of things for my data:
-a pre-defined hash table with my keywords that I am searching for
-a dynamically-built hash table which is constructed to represent the sourcefile from keywords in the pre-defined hash table
-an input file to load my pre-defined hash table values (that way, I can change the keywords via the file)
-an output file that should be sort of readable, but compresses the information from the sourcefile
I think I've found several classes that work. I'll play around with them.
I got another question though: I see that the hash tables use a one-to-one mapping. Are hash tables the kind of thing to use for a mapping that is one-to-two? Actually, I think a tree of some kind would work better. Thoughts? (This one is just a curiosity question.)
Let me see what I come up with...
Posted: Tue Dec 09, 2008 10:01 pm
by XMEN Gambit
Your brain is bent funny. Must be the rocket scientist thing.
You just need one hashmap, for your keywords. Your sourcefile analysis should probably not be stored in a (separate) hashmap, however you can store an index into an array, or a pointer to a data structure, or something like that as the value in your hash. If you only need a count then that _could_ be stored. Some implementations would let you have an entire class as the value, but that's just doing this other stuff behind the scenes (MS has a bunch of different types, but I'm assuming you aren't using MS). Be careful about memory leaks.
If I was doing it, non-MS, I'd have a simple array of serializable classes or data structures for my analysis data and use a hash just to quickly find the index I wanted during parsing. When you dump out to a file, then you just have to iterate the array and dump each element. Obviously I don't know the whole picture and you might have a need to do it differently. I can elaborate if you like.
File I/O doesn't have to be hard. Here's an example that looks more like C:
http://www.arachnoid.com/cpptutor/student2.html
But you should be able to find a library that will make it super-easy if you don't mind the extra size. As much string processing as you're doing, I'd say you need strong libraries for string and *file* processing. Read those APIs and a world of possibilities open before you...
Posted: Tue Dec 09, 2008 11:12 pm
by XMEN Ashaman DTM
Maybe.
Seriously though, when you do a computational "whatever" simulation, you load your geometry, your boundary conditions, and/or your initial values from files. You can do the BCs and IVs as console inputs or from a lookup table, or from special functions, but it's just as easy to put them into files. Then you load the files, read in your data into your containers, generate a computational mesh from the geometry (the points where the equations are being solved), and start crunching.
The parallel stuff just comes into play when you want to break up different parts of your geometry or your equations so that different processors run just those parts. Then you have to pass messages or globals so that everyone is on the same page.
That ^^^^ seems straightforward to me. All this sting stuff is harder, because I haven't really messed around with strings, and I'm trying to really lock my thinking into object-oriented methods at the same time. I think I've got the OO stuff, I just need to practice more. The string stuff will come with time and use, I think. But it's things like hashmaps/hashtables that I just didn't think of. Even though one of my projects deals with hash functions and encoding/compressing info. Heh.
The idea is that I want to take any source file, parse it and encode/compress the info (into symbols, I guess), and use that info to start looking at interactions between files. Being able to have separate files that are the hashed original source, and being able to utilize those files in a different way is what I am after. I'm trying to speed up my ability to investigate algorithms, and the tools I'm building are exactly what I need. It's a learning process for me in that I want to be able to use my code to encode the sourcefiles of my program; since I already know what the code should be doing, I should be able to see the interactions more clearly.
Posted: Wed Dec 10, 2008 12:42 am
by XMEN Gambit
(Was making a satirical comment about different analysis patterns with the bent thing.)
I understand your first paragraph. (I'm not counting the "maybe.") And the second. And the third. You lose me at #4, 'cause we're bent differently. A high-bandwidth discussion is needed to get us both on the same page, but that's not necessary to just provide tips.
In your analysis portion for the source files, you'll need more information than just a count in order to do anything useful with it. Hence you'd need to collect and store more data than a count, which means a hash table is only going to be useful to store an index or a pointer to the deeper structure. I've not seen anything that would convince me to do it differently than I suggested, but that's not your job, and if you need something different then be different.
Analysis of source algorithms is a fairly complex task. I bet software patent lawyers (and comp sci grad assistants?) have tools that do things like this; perhaps you can find some useful info there. OTOH, if you can't, perhaps you can publish your solution when you find one, or something.
Posted: Fri Dec 12, 2008 2:34 am
by XMEN Ashaman DTM
Well, I'm pretty much having to start from scratch. The laptop that I bought last year, it died. It's got that same chipset from nvidia that's giving everyone problems. The manufacturer has replaced the motherboards for free (except shipping) even for laptops that are out of warranty. I'm just waiting for the company to tell me where to send it and how.
I think I can pull the data off of my harddisk, since it's a 2.5 inch SATA drive, but I haven't checked the connections yet.
It's probably good to start from scratch anyways.
As for what I've done already, I can do it again. And it's likely that a fresh start, without any of my recent notes, will do some good.
Posted: Fri Dec 12, 2008 10:30 pm
by XMEN Gambit
Yup, you can usually write code better the second time around.
Posted: Sat Jul 04, 2009 2:36 am
by XMEN Ashaman DTM
Well, been writing better code. Especially since the laptop was fixed, and I can work pretty much anywhere around the house and at pretty much anytime.
I have been running into a couple of issues though.
First, I've noticed I get writer's block. I usually just move onto another task that's got to be done, but there are days where I just can't think of how to approach a problem. Lately it's been defining the lookup tables for my sourcefile analysis. It gets boring. Heh.
But I've got my branches figured out, and I decided to put everything into vectors of strings. I found it was easier to process the strings using indices of the vectors. So I'm just at the point where I'm filling in the blanks of my design.
Now, here's the second part, and since I'm not a software engineer, I don't know where or when to start this transition. Here's the deal: I plan on integrating all this processing stuff into a graphical interface. It's not MDA or code generation or anything like that. However, there are some aspects of my project that could be compared to those things. I want to be able to take a sourcefile and "see" how it fits together with other files in a program. Kind of like a combination state diagram / flow chart for a program. And be able to use this information to assist in debugging by looking at how a program state changes as the execution moves through the flow of the program. If you think of it in terms of the diagrams found on this wikipedia article on
control theory, then I think you can see what I'm looking to do. I have some ideas for tools that would build on this, so I didn't find anything that could do what I wanted when I initially searched. And I decided it would be better for me to build it myself. Besides, I like to look at the big picture, but still have the ability to dive into the details.
I guess for the second one, I'm just not sure if I should start integrating into a gui or not. I've done some preliminary research and it looks like wxwidgets is what I'll use. It seems easy enough to use from what I've read, and I think some other tools like gtk are a bit on the overkill side. But I just don't know. Some guidance on this would be appreciated, since I'm pretty clueless on this part.
Posted: Sat Jul 04, 2009 8:41 am
by XMEN Gambit
You want to see how a file fits into the program? Not sure I've seen anything like that. There are numerous tools (Rational Rose comes to mind) for analyzing source code visually but that's usually by class or procedure rather than source file.
As for the monitoring change of state, you need a good debugger/profiler, but again not sure if I've seen exactly what you're looking for.
I'd not heard of wxwidgets before. Looks interesting.
Posted: Thu Jan 07, 2010 11:30 pm
by XMEN Ashaman DTM
FYI... dropped wxwidgets on my project. Moved to Qt. It was mostly because once I looked at Qt a bit more in depth, I realized that it was closer to my way of thinking than wxwidgets. There's also the fact that in Qt it just felt like the interfaces were cleaner, and there was a definite separation of concerns in the various components.
My only problem with Qt so far has been tracking down linking errors in linux. In Windows, everything compiles and links fine. It's kind of weird.
As for some stuff to show off, it's not ready yet. I've still got some major components to work out.
Here is something worth sharing
Posted: Fri Sep 03, 2010 3:19 am
by XMEN Ashaman DTM
Haven't tested it yet, but was pretty excited to finally put it all down into source. It's a table that maps whether two independent signals have a relationship. In my case I am using it to map inputs to outputs, in the same vein as
classical control theory.
The table below is for the relationship mapping only, a single function checks for type matching.
I'm working on a project that involves data flow programming concepts, and needed a way to represent the mapping of inputs to outputs. Again, haven't tested it yet, but it looks like it captures the mapping I wanted. Likely any errors are syntax errors; and yes, I know some of the operations performed in the functions are expensive.
Header:
Code: Select all
#ifndef SIGNALSTABLE_H_INCLUDED
#define SIGNALSTABLE_H_INCLUDED
#include <string>
#include <vector>
using namespace std;
/*Type Definitions: */
typedef vector<vector<bool>> table_t; //Array of bools for mapping according to the linear algebra convention: y=Ax,
//where the table is equivalent to "A" and represents the directed map from column to row
//Define iterators for above type (if needed):
vector<vector<bool>>::iterator table_outer_it;
vector<bool>::iterator table_inner_it;
class SignalTable {
private:
//Define a Table:
//a map of inputs to outputs using a map to associate a name to a vector
// the vector describes whether the input maps to the output using the
// linear algebra convention y=Ax
//vector<string> inputs, outputs "index" into the array defined as signal map
table_t signalmap; //2D array of BOOL elements. Element values assigned to indicate mapping from row to column:
// in1 in2 in3 in4 in5 in6
//in1 0 0 0 0 0 1
//in2 1 0 1 0 1 0
//in3 0 0 0 0 0 0
//in4 0 0 0 0 0 0
//in5 1 1 1 1 1 1
//in6 0 1 0 1 1 0
//
// Note that the convention comes from linear algebra (y=Ax), where matrix multiplication is
// observed
//
// Note that the index into x1, y1 is (input1, output1)
//
// Note that the mapping is one-way: each row (y) has a BOOL value for whether a relationship
// exists where a column (an x) is mapped to a row (y)
vector<string> inputs; //Array equivalent to col_name
vector<string> outputs; //Array equivalent to row_name
public:
SignalTable(); //Creates and initializes the SignalTable mapping with "0"s (no inputs mapped to any outputs)
~SignalTable(); //Destroyes the SignalTable mapping
void setInputs(string& in); //Add a single input to the inputs vector, checks for redundant entries
void setInputs(vector<string> ins); //Add all ins in the vector to inputs vector, checks for redundant ins
int removeInput(string& in); //removes the string from the inputs vector, returns 0 if successful
vector<string> getInputs(void); //Returns the array of inputs
void setOutputs(string& out); //Add a single output to the outputs vector, checks for redundant entries
void setOutputs(vector<string> outs); //Add all outs in the vector to the outputs vector, checks for redundant outs
int removeOutput(string& out); //removes the string from the outputs vector, returns 0 if successful
vector<string> getOutputs(void); //Returns the array of outputs
void createSignalTable(void); //Generates default Signal Table with no mappings (Initial memory allocation for table),
//uses inputs and outputs vectors to create the table
int createSignalTable(vector<string> ins, vector<string> outs, vector<vector<bool>> relation); //generates Signal Table with mappings
//found in "relation"
int setSignalTableElement(string& in, string& out, bool& relate); //Assigns relationship from in to out (by overwriting), returns -1 if failed
int toggleSignalTableElement(string& in, string& out); //Toggles relationship in the Signal Table, returns -1 if failed
int removeSignalTableElement(string& in, string& out); //Assigns FALSE to the relationship from in to out, returns -1 if failed
int getSignalTableElement(string& in, string& out); //Returns int 0 if false, int 1 if true, int -1 if error
};
#endif // SIGNALSTABLE_H_INCLUDED
CPP:
Code: Select all
#include <vector>
#include <string>
#include "SignalsTable.h"
/* INTERNAL VARIABLES:
vector<string> inputs; //An array of all inputs
vector<string> outputs; //An array of all outputs
table_t signalmap;
*/
//Start of function definitions:
SignalTable::SignalTable()
{
createSignalTable(void);
}
SignalTable::~SignalTable()
{
}
SignalTable::setInputs(string& in)
{
if(inputs.at(0) == "")
{
inputs.erase(0);
}
//First determine if this is a duplicate entry:
int found;
for(int ii=0; ii<inputs.size(); ++ii)
{
if(inputs.at(ii).compare(in) == 0)
{
found=ii;
}
}
//If no duplicates found:
if(size_t(found) <= inputs.size())
{
inputs.push_back(in);
}
}
SignalTable::setInputs(vector<string> ins)
{
vector<size_t> found;
ins_size = ins.size();
if(inputs.at(0) == "") //Check first inputs element for empty string (default in create function)
{
inputs.erase(0);
}
for(int ii=0; ii<inputs.size(); ++ii) //Take ii'th element in inputs to compare
{
for(int jj=0; jj<ins_size; ++jj) //Take jj'th element in ins to use for comparison
{
if(inputs.at(ii).compare(ins.at(jj)) == 0)
{
found.push_back(jj); //Store the ins indices that are duplicates
}
}
}
//If no duplicates are found, found vector should have no size:
if(found.size() < 1)
{
for(int jj=0; jj<ins_size; ++jj)
{
inputs.push_back(ins.at(jj));
}
}
else //size of found is > 0...
{
for(int jj=0; jj<ins_size; ++jj)
{
for(int kk=0; kk<found.size(); ++kk)
{
if(jj != found.at(kk))
{
inputs.push_back(ins.at(jj)); //Add those items to inputs that have no duplicates
}
}
}
}
}
SignalTable::getInputs(void)
{
return(inputs);
}
SignalTable::setOutputs(string& out)
{
if(outputs.at(0) == "")
{
outputs.erase(0);
}
//First determine if this is a duplicate entry:
int found;
for(int ii=0; ii<outputs.size(); ++ii)
{
if(outputs.at(ii).compare(out) == 0)
{
found == ii;
}
}
//If no duplicates found:
if(size_t(found) <= outputs.size())
{
outputs.push_back(out);
}
}
SignalTable::setOutputs(vector<string> outs)
{
vector<size_t> found;
outs_size = outs.size();
if(outputs.at(0) == "")
{
outputs.erase(0);
}
for(int ii=0; ii<outs_size; ++ii) //Take ii'th element in inputs to compare
{
for(int jj=0; jj<outs_size; ++jj) //Take jj'th element in ins to use for comparison
{
if(outputs.at(ii).compare(outs.at(jj)) == 0)
{
found.push_back(jj); //Store the ins indices that are duplicates
}
}
}
//If no duplicates are found, found vector should have no size:
if(found.size() < 1)
{
for(int jj=0; jj<outs_size; ++jj)
{
outputs.push_back(outs.at(jj));
}
}
else //size of found is > 0...
{
for(int jj=0; jj<outs_size; ++jj)
{
for(int kk=0; kk<found.size(); ++kk)
{
if(jj != found.at(kk))
{
outputs.push_back(outs.at(jj)); //Add those items to inputs that have no duplicates
}
}
}
}
}
SignalTable::getOutputs(void)
{
return(outputs);
}
SignalTable::createSignalTable(void)
{
signalmap.at(0).at(0)=false;
inputs.at(0)="";
outputs.at(0)="";
}
SignalTable::createSignalTable(vector<string> ins, vector<string> outs, vector<vector<bool>> relation)
{
ins_size =ins.size();
outs_size =outs.size();
rel_size =relation.size();
//Ensure that "relation" is not smaller than either of the ins or outs that are being used:
if((rel_size < ins_size) || (rel_size < outs_size))
{
return(-1);
}
else
{
inputs=ins;
outputs=outs;
signalmap=relation;
return(0);
}
}
SignalTable::setSignalTableElement(string& in, string& out, bool relate)
{
in_size = inputs.size();
out_size = outputs.size();
unsigned int ii;
unsigned int in_pos = 0;
unsigned int out_pos = 0;
for(ii=0; ii<in_size; ++ii)
{
if(inputs.at(ii).compare(in) == 0)
{
in_pos=ii;
}
}
for(ii=0; ii<out_size; ++ii)
{
if(outputs.at(ii).compare(out) == 0)
{
out_pos=ii;
}
}
if((in_pos != 0) && (out_pos != 0))
{
signalmap.at(in_pos).at(out_pos) = relate;
return(0);
}
else
{
return(-1);
}
}
SignalTable::toggleSignalTableElement(string& in, string& out);
{
in_size = inputs.size();
out_size = outputs.size();
unsigned int ii;
unsigned int in_pos = 0;
unsigned int out_pos = 0;
bool value;
for(ii=0; ii<in_size; ++ii)
{
if(inputs.compare(in) == 0)
{
in_pos = ii;
}
}
for(ii=0; ii<out_size; ++ii)
{
if(outputs.compare(out) == 0)
{
out_pos = ii;
}
}
if((in_pos != 0) && (out_pos != 0))
{
value = signalmap.at(in_pos).at(out_pos);
if(value == true)
{
signalmap.at(in_pos).at(out_pos) = false;
return(0);
}
else if(value == false)
{
signalmap.at(in_pos).at(out_pos) == true;
return(0);
}
else
{
return(-1);
}
}
else
{
return(-2);
}
}
SignalTable::removeSignalTableElement(string& in, string& out)
{
in_size = inputs.size();
out_size = outputs.size();
unsigned int ii;
unsigned int in_pos = 0;
unsigned int out_pos = 0;
for(ii=0; ii<in_size; ++ii)
{
if(inputs.at(ii).compare(in) == 0)
{
in_pos = ii;
}
}
for(ii=0; ii<out_size; ++ii)
{
if(outputs.at(ii).compare(out) == 0)
{
out_pos = ii;
}
}
if((in_pos != 0) && (out_pos != 0))
{
for(ii=0; ii<out_size; ++ii)
{
signalmap.at(in_pos).erase(ii);
}
for(ii=0; ii<in_size)
{
signalmap.erase(ii).at(out_pos);
}
removeInput(in);
removeOutput(out);
return(0);
}
else
{
return(-1);
}
}
SignalTable::removeInput(string& in)
{
in_size = inputs.size();
for(ii=0; ii<in_size; ++ii)
{
if(inputs.at(ii).compare(in) == 0)
{
inputs.erase(ii);
}
else
{
return(-1);
}
}
}
SignalTable::removeOutput(string& out)
{
out_size = outputs.size();
for(ii=0; ii<out_size; ++ii)
{
if(outputs.at(ii).compare(out) == 0)
{
outputs.erase(ii);
}
else
{
return(-1);
}
}
}
SignalTable::getSignalTableElement(string& in, string& out)
{
in_size = inputs.size();
out_size = outputs.size();
unsigned int ii;
unsigned int in_pos = 0;
unsigned int out_pos = 0;
for(ii=0; ii<in_size; ++ii)
{
if(inputs.at(ii).compare(in) == 0)
{
in_pos=ii;
}
}
for(ii=0; ii<out_size; ++ii)
{
if(outputs.at(ii).compare(out) == 0)
{
out_pos=ii;
}
}
if((in_pos != 0) && (out_pos != 0))
{
return(int(signalmap.at(in_pos).at(out_pos)));
}
else
{
return(-1);
}
}
As for my other project, it's still in work. I'm working the intensive back-end stuff now. The big component is something that reads a source file, and maps functions, objects, and data to generate elements for flow charts (for example). Something beyond a call-graph, flow chart, or AST; yet encompassess ideas from all three things. Something that basically is helping me to use a library by telling me of available functions, how the data is manipulated, and so on. Basically, something that is "programming smart" for me since I'm not a programmer.