Logical expression parser in lazarus ?

[Tommi]

I was looking for something to port code from C to lazarus, but everything I found was just a string replacer. So I did my C parser that write lazarus code.
It does a good job because the result is almost immediately compilable.

For example with this input (take from rosettacode):

Code: [Select]

double factorial(int n) {
double f = 1;
int i;
for (i = 1; i <= n; i++) f *= i;
return f;
}
 
double expected(int n) {
double sum = 0;
int i;
for (i = 1; i <= n; i++)
sum += factorial(n) / pow(n, i) / factorial(n - i);
return sum;
}
 
int randint(int n) {
int r, rmax = RAND_MAX / n * n;
while ((r = rand()) >= rmax);
return r / (RAND_MAX / n);
}
 
int test(int n, int times) {
int i, count = 0;
for (i = 0; i < times; i++) {
int x = 1, bits = 0;
while (!(bits & x)) {
count++;
bits |= x;
x = 1 << randint(n);
}
}
return count;
}
 
int main(void) {
srand(time(0));
puts(" n\tavg\texp.\tdiff\n-------------------------------");
 
int n;
for (n = 1; n <= MAX_N; n++) {
int cnt = test(n, TIMES);
double avg = (double)cnt / TIMES;
double theory = expected(n);
double diff = (avg / theory - 1) * 100;
printf("%2d %8.4f %8.4f %6.3f%%\n", n, avg, theory, diff);
}
return 0;
}

the output is:

Code: [Select]


function factorial (
n:integer
):double;
var
f:double;
i:integer;
Aa54b07b013:boolean;
begin
f := 1;
i := 1;
Aa54b07b013 := false;
while ( true ) do
begin
if (Aa54b07b013=true ) then
begin
inc(i);
end;
if not (i <= n ) then break;
Aa54b07b013 := true;
f *= i;
end;
result:=f;
exit;
end;

function expected (
n:integer
):double;
var
sum:double;
i:integer;
Aa54b07b0117:boolean;
begin
sum := 0;
i := 1;
Aa54b07b0117 := false;
while ( true ) do
begin
if (Aa54b07b0117=true ) then
begin
inc(i);
end;
if not (i <= n ) then break;
Aa54b07b0117 := true;
sum += factorial (n) / pow (n, i) / factorial (n - i);
end;
result:=sum;
exit;
end;

function randint (
n:integer
):integer;
var
r:integer;
rmax:integer;
begin
rmax := RAND_MAX / n * n;
while ((r = rand ()) >= rmax) do
begin
result:=r / (RAND_MAX / n);
exit;
end;

function test (
n:integer;
times:integer
):integer;
var
i:integer;
count:integer;
x:integer;
bits:integer;
A795f48f5138:boolean;
begin
count := 0;
i := 0;
A795f48f5138 := false;
while ( true ) do
begin
if (A795f48f5138=true ) then
begin
inc(i);
end;
if not (i < times ) then break;
A795f48f5138 := true;
x := 1;
bits := 0;
while ( not((bits )& x)) do
begin
inc(count);
bits |= x;
x := 1 << randint (n);
end;
end;
result:=count;
exit;
end;

function main (
):integer;
var
n:integer;
cnt:integer;
avg:double;
theory:double;
diff:double;
A6bfdfe1e263:boolean;
begin
srand (time (0));
puts (' n\tavg\texp.\tdiff'+#13+'-------------------------------');
n := 1;
A6bfdfe1e263 := false;
while ( true ) do
begin
if (A6bfdfe1e263=true ) then
begin
inc(n);
end;
if not (n <= MAX_N ) then break;
A6bfdfe1e263 := true;
cnt := test (n, TIMES);
avg := (double) cnt / TIMES;
theory := expected (n);
diff := (avg / theory - 1) * 100;
printf ('%2d %8.4f %8.4f %6.3f%%'+#13+'', n, avg, theory, diff);
end;
result:=0;
exit;
end;

Not bad I think

My issue now is that I need to add an expression parser that consider precedence beetween operators,
so this:

Code: [Select]

while ( (--j*6+j*k)*j++<y && j>k++)
becomes:

Code: [Select]

while (true) do
    dec(j);
    tmp[0]:=j*6;
    tmp[1]:=j*k;
    if not (tmp[0]*tmp[1])*j<y) then break;
    inc(j);
   if not (j>k) then break;
   dec(k);

Is there a formalized algorithm to do things like this ? Some lib or similar ? This is the more difficult part of my software....

May be that some one is interested in helping me or in receiving my code ?I would release the source code as open source.
It manage brackets between ( && !! !) (but not bitwise operators at the moment)
It supports FOR,DO-WHILE,WHILE,IF-THEN-ELSE, arrays, pointers etc. but it needs some imporvement.

[marcov]

C parsing is well documented, though not trivial. Since pascal doesn't support pre and postfix operators, this will need a lot more work though.

[Tommi]

Infact I think to emulate pre and postfix operators in some manner. But I am interested in know if there is some standard way

[marcov]

Infact I think to emulate pre and postfix operators in some manner. But I am interested in know if there is some standard way

A standard way would be to introduce a temp for every intermediate value so that you get an expression with maximally one operator as rvalue.  Then model ++ -- etc as a load and a inc/dec.

[Tommi]

Thank you. I will do it so.

[circular]

Hi Tommi,

As marcov said, it is rather straightforward, simply apply the definition of the operators. However I think it may not be a obvious regarding the order in which operations are done. For example if you have (++n) + n + (++n) is it equal to (n+1)+n+(n+2) or is it equal to (n+1)+(n+1)+(n+2) or is it equal to (n+1)+(n+2)+(n+2).

I don't know if the order of the operations is necessarily form left to right.

[Edson]

I think you need to define functions like this:

Code: [Select]

function _pp(var x: integer): integer;
begin
  Result := x;
  Inc(x);
end;
function pp_(var x: integer): integer;
begin
  Inc(x);
  Result := x;
end;
function _ss(var x: integer): integer;
begin
  Result := x;
  Dec(x);
end;
function ss_(var x: integer): integer;
begin
  Dec(x);
  Result := x;
end;

in some general unit.

Then your expresion:

Code: [Select]

while ( (--j*6+j*k)*j++<y && j>k++)
should be easy translated to:

Code: [Select]

while ( (ss_(j)*6+j*k)*_pp(j)<y) AND  (j>_pp(k))
If these functions could be be INLINE, it would be better.

[Tommi]

I think that it is a very intelligent Idea. I don't know if fpc has inline option but at least it should compile ok.

In effect this option is necessary only in rare cases so I could do:

I say to the parser to check if it finds ++ or -- in the expression
-if not ----> it copies exactly the formula
or
-if yes it checks:
-is a simply formula like (--j<k) ---> it does:

Code: [Select]

dec(j)
if (j<k) then break;
[code]

-is a complicated formula ----> apply the metod that you suggest

[sarason]

I would be interested in having a look at your code and running some of my test code through it.
If I had time I would love to join your project!

sarason