Cenzic 232 Patent
Paid Advertising
sla.ckers.org is
ha.ckers sla.cking
Sla.ckers.org
Whether this is about ha.ckers.org, sla.ckers.org or some other project you are interested in or want to talk about, throw it in here to get feedback. 
Go to Topic: PreviousNext
Go to: Forum ListMessage ListNew TopicSearchLog In
Some CFG matched with replace module
Posted by: dasickis
Date: March 13, 2008 01:46PM

Is there anything wrong with the approach of trying to match Context Free Grammars (CFG) with the RegExp replace module in javascript.

For example, matching parens with the following:

function matchParen(str){
paren = 0;
pos = str.replace(/./g,function test(){
switch(arguments[0]){
case '(':paren++;break;
case ')':paren--;break;
}
if(paren==0){paren=Infinity; return arguments[1]+1;}
return "";
})
str.substr(0,pos);
}

It's not robust enough to match:
str = ")((adlkjd)&test)))";
starting with the first opening paren rather than the first paren.

For now, I've made another function to do the work (paste it later it's at home), but is there anything wrong with this method?

Options: ReplyQuote
Re: Some CFG matched with replace module
Posted by: dasickis
Date: March 19, 2008 01:06PM

Can anyone comment on this? Even if the comment is "You suck!"

Options: ReplyQuote
Re: Some CFG matched with replace module
Posted by: thornmaker
Date: March 19, 2008 03:45PM

I don't think anyone understands what you are asking. Are you wondering if your code has bugs? has security vulnerabilities? Is a practical solution for whatever problem you are trying to solve? Is an efficient solution for whatever problem you are trying to solve? And what exactly does your code have to do with context free grammars in the first place? Please try to explain what you expect the code to be doing, and what type of feedback you're looking for.

Options: ReplyQuote
Re: Some CFG matched with replace module
Posted by: kishord
Date: March 19, 2008 07:58PM

Does it have to do with greedy matching?

E.g. if you have string aaaaaa
then a* by default will match the whole string.

I am not talking about the regex in your code here. Just check if you have any greedy match in regex.

Web Application Security Journ(ey)al

Options: ReplyQuote
Re: Some CFG matched with replace module
Posted by: dasickis
Date: March 21, 2008 08:50AM

What are the limitations of trying to match certain CFG's using this method? For example, I'm trying to match 'matching parentheses' which is a CFG thus needs to be matched with at least a push-down automata.

Additionally, I'm trying to figure out where my example code for CFGs would break. Also, what are some other software design issues you see with accomplishing the parsing using the regexp replace function.

Please tell me if I'm still asking very vague questions.

Options: ReplyQuote
Re: Some CFG matched with replace module
Posted by: majak
Date: March 21, 2008 04:47PM

At first, i don't know why are you doing it so obscure. Tell me, what exactly do you want to do?
Then, why your example fails... After first ')', paren is -1. And then, after '(', paren is 0, so it is changed to Infinity. It won't increase or decrease anymore. I hope this helps.
(And btw, this function returns nothing, str.substr(0,pos) won't strip str, it only returns that stripped value (and even if it does, you change str only at local scope, not global))

Options: ReplyQuote
Re: Some CFG matched with replace module
Posted by: dasickis
Date: March 24, 2008 10:52AM

I just wanted to see if it was possible to match parentheses using the replace method. Now I see that it's somewhat possible I wanted to see any shortcoming of the function or if it can be extended. I know this is not a practical approach, but it was to expand my understanding of the replace method.

I have edited the function to return str.substr(0,pos).

Basically, what I do is I initially set the number of [unbalanced]parens to 0 and then I check the string to find parens. For every right paren add one and for every left paren subtract one. Once every right paren has been matched with a left paren (hence total of [unbalanced]parens = 0). I no longer want to keep searching the remainder of the string as I've found my matching paren and I set paren to Infinity to assure that it will never equal 0 regardless of the remainder parens.

Options: ReplyQuote


Sorry, only registered users may post in this forum.