Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Recursive Descent Parser for EBNF in PHP

I am attempting to write a recursive descent parser in PHP for the following EBNF:

EXP ::= < TERM > { ( + | - ) < TERM > }
TERM ::= < FACTOR > { ( * | / ) < FACTOR > }
FACTOR ::= ( < EXP > ) | < DIGIT >
DIGIT ::= 0 | 1 | 2 | 3

I followed this guide which I saw recommended on a similar question. (I searched before I posted)

For the most part, I get how it works and I understand the grammar. I think the problem is within my syntax. I am new to PHP, so I have been referencing W3Schools. I currently am getting the following error with my code:

Warning: Wrong parameter count for exp() .... on line 101

I have tried to look up this error and have not had much luck. I read some posts about people passing in the wrong parameter typed, but I do not have any parameters set for that function. Is there something about PHP I am missing here?

Below is my code, I think the logic is correct since I based it off of the parse tree for the grammar. The $input will be coming from a form box on an HTML page. I also picked up the str_split function from a different post when I discovered that PHP4 does not have it built in.

<html>
<body>
<?php 
if(!function_exists("exp")){
  function exp(){
    term();
    while($token == "+" | $token == "-"){
        if($token == "+"){
            match("+");
            term();
        }
        if($token == "-"){
            match("-");
            term();
        }
    }
  }//end exp
}

if(!function_exists("term")){
  function term(){
    factor();
    while($token == "*" | $token == "/"){
        if($token == "*"){
            match("*");
            factor();
        }
        if($token == "/"){
            match("/");
            factor();
        }
    }
  }//end term
}

if(!function_exists("factor")){
  function factor(){
    if($token == "("){
        match("(");
        exp();
        if($token == ")")
            match(")");
    }
    else if($token == 0|1|2|3){
         if($token == 0)
            match(0);
         if($token == 1)
            match(1);
         if($token == 2)
            match(2);
         if($token == 3)
            match(3);
    }
    else
        error();
  }//end factor
}

if(!function_exists("match")){
  function match($expected){
    if($token == $expected)
        nextToken();
    else
        error();
  }//end match
}

if(!function_exists("next_Token")){
  function nextToken(){
    $next++;
    $token = $tokenStr[$next];
    if($token == "$");
        legal();
  }
}

if(!function_exists("error")){
  function error(){
    echo "Illegal token stream, try again";
  }
}

if(!function_exists("legal")){
  function legal(){
    echo "Legal token stream, congrats!";
  }
}

if(!function_exists('str_split')) {
  function str_split($string, $split_length = 1) {
    $array = explode("\r\n", chunk_split($string, $split_length));
    array_pop($array);
    return $array;
  }
}

$tokenStr = str_split($input);
$next = 0;
$token = $tokenStr[0];
exp();
?>
</body>
</html>

So basically I want to know what causes that error and why and am I on the right track in terms of creating this parser.

I appreciate any comments, suggestions, criticisms, water baloons, and tomatoes. Thank you for taking the time to read my post. Have a great day/night.

like image 690
Seephor Avatar asked Mar 27 '11 23:03

Seephor


1 Answers

exp() is a builtin PHP function. You cannot define it under that name.

You should have no reason to use the if(!function_exists(' idiom in normal PHP applications. (It's often used more as a workaround when include scripts clash or identical functions are declared at different places.)


Another syntax problem that I noticed is your use of the bitwise OR. The logical OR should be || or just or.

while($token == "*" | $token == "/"){
like image 84
mario Avatar answered Oct 10 '22 09:10

mario