twocoders.de
 

programme/php/bisektion/parser.php


1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
37:
38:
39:
40:
41:
42:
43:
44:
45:
46:
47:
48:
49:
50:
51:
52:
53:
54:
55:
56:
57:
58:
59:
60:
61:
62:
63:
64:
65:
66:
67:
68:
69:
70:
71:
72:
73:
74:
75:
76:
77:
78:
79:
80:
81:
82:
83:
84:
85:
86:
87:
88:
89:
90:
91:
92:
93:
94:
95:
96:
97:
98:
99:
100:
101:
102:
103:
104:
105:
106:
107:
108:
109:
110:
111:
112:
113:
114:
115:
116:
117:
118:
119:
120:
121:
122:
123:
124:
125:
126:
127:
128:
129:
130:
131:
132:
133:
134:
135:
136:
137:
138:
139:
140:
141:
142:
143:
144:
145:
146:
147:
148:
149:
150:
151:
152:
153:
154:
155:
156:
157:
158:
159:
160:
161:
162:
163:
164:
165:
166:
167:
168:
169:
170:
171:
172:
173:
174:
175:
176:
177:
178:
179:
180:
181:
182:
183:
184:
185:
186:
187:
188:
189:
190:
191:
192:
193:
194:
195:
196:
197:
198:
199:
200:
201:
202:
203:
204:
205:
206:
207:
208:
209:
210:
211:
212:
213:
214:
215:
216:
217:
218:
219:
220:
221:
222:
223:
224:
225:
226:
227:
228:
229:
230:
231:
232:
233:
234:
235:
236:
237:
238:
239:
240:
241:
242:
243:
244:
245:
246:
247:
248:
249:
250:
251:
252:
253:
254:
255:
256:
257:
258:
259:
260:
261:
262:
263:
264:
265:
266:
267:
268:
269:
270:
271:
272:
273:
274:
275:
276:
277:
278:
279:
280:
281:
282:
283:
284:
285:
286:
287:
288:
289:
290:
291:
292:
293:
294:
295:
296:
297:
298:
299:
300:
301:
302:
303:
304:
305:
306:
307:
308:
309:
310:
311:
312:
313:
314:
315:
316:
317:
318:
319:
320:
321:
322:
323:
324:
325:
326:
327:
328:
329:
330:
331:
332:
333:
334:
335:
336:
337:
338:
339:
340:
341:
342:
343:
344:
345:
346:
347:
348:
349:
350:
351:
352:
353:
354:
355:
356:
357:
358:
359:
360:
361:
362:
363:
364:
365:
366:
367:
368:
369:
370:
371:
372:
373:
374:
375:
376:
377:
378:
379:
380:
381:
382:
383:
384:
385:
386:
387:
388:
389:
390:
391:
392:
393:
394:
395:
396:
397:
398:
399:
400:
401:
402:
403:
404:
405:
406:
407:
408:
409:
410:
411:
412:
413:
414:
415:
416:
417:
418:
419:
420:
421:
422:
423:
424:
425:
426:
427:
428:
429:
430:
431:
432:
433:
434:
435:
436:
437:
438:
439:
440:
441:
442:
443:
444:
445:
446:
447:
448:
449:
450:
451:
452:
453:
454:
455:
456:
457:
458:
459:
460:
461:
462:
463:
464:
465:
466:
467:
468:
469:
470:
471:
472:
473:
474:
475:
476:
477:
478:
479:
480:
481:
482:
483:
484:
485:
486:
487:
488:
489:
490:
491:
492:
493:
494:
495:
496:
497:
498:
499:
500:
501:
502:
503:
504:
505:
506:
507:
508:
509:
510:
511:
512:
513:
514:
515:
516:
517:
518:
519:
520:
521:
522:
523:
524:
525:
<?php
class Evaluator
{
    private 
$stack = array();
    private 
$stackLevel;
    
    public function 
__construct()
    {
        
$this -> stackLevel 0;
    }
    
    public function 
Enter($value)
    {
        
$this->stack[$this->stackLevel] = $value;
        
$this->stackLevel ++;
    }

    public function 
Dump()
    {
        echo 
"StackLevel = ".$this -> stackLevel."<br>";
        
print_r($this -> stack);
        echo 
"<br>";
    }

    public function 
OperatorDyadic($operatorName)
    {
         if (
$this -> stackLevel <= 1)
             return;
             
        switch(
$operatorName)
        {
        case 
"NIL":
        break;
        case 
"PLUS":
            
$this -> stack[$this->stackLevel 2] += $this -> stack[$this->stackLevel 1];
            
$this -> stackLevel --;
        break;
        case 
"MINUS":
            
$this -> stack[$this->stackLevel 2] -= $this -> stack[$this->stackLevel 1];
            
$this -> stackLevel --;
        break;
        case 
"OR":
            
$this -> stack[$this->stackLevel 2] |= $this -> stack[$this->stackLevel 1];
            
$this -> stackLevel --;
        break;
        
        case 
"MULTIPLY":
            
$this -> stack[$this->stackLevel 2] *= $this -> stack[$this->stackLevel 1];
            
$this -> stackLevel --;
        break;        
        case 
"DIVIDE":
            
$this -> stack[$this->stackLevel 2] /= $this -> stack[$this->stackLevel 1];
            
$this -> stackLevel --;
        break;
        case 
"MODULO":
            
$this -> stack[$this->stackLevel 2] %= $this -> stack[$this->stackLevel 1];
            
$this -> stackLevel --;
        break;
        case 
"AND":
            
$this -> stack[$this->stackLevel 2] &= $this -> stack[$this->stackLevel 1];
            
$this -> stackLevel --;
        break;
        case 
"POWER":
            
$this -> stack[$this->stackLevel 2] =
                
pow($this -> stack[$this->stackLevel 2],
                
$this -> stack[$this->stackLevel 1]);
            
$this -> stackLevel --;
        break;
        }
    }


    public function 
OperatorMonadic($operatorName)
    {
         if (
$this -> stackLevel == 0)
             return;
             
        switch(
$operatorName)
        {
        case 
"NIL":
        break;
        case 
"NOT":
            
$this -> stack[$this->stackLevel 1] = ~$this -> stack[$this->stackLevel 1];
        break;
        case 
"NEGATIVE":
            
$this -> stack[$this->stackLevel 1] *= -1;
        break;
        case 
"POSITIVE":
            ;
        break;
        }
    }

    public function 
GetResult()
    {
        return     
$this->stack[$this->stackLevel 1];
    }
    
}

class 
Parser
{
     
/*
    
    Expression:
    
         +------------+    +--------+
    O----+ ExprIntern +----+  End   +----O
         +------------+    +--------+
    
    
    
    ExpressionInternal:
    
                               +--------+
    O----+-----------+----+----+  Term  +----+----+----+----O
         |           ^    ^    +--------+    |    |    |
         +----{~}----+    |                  |    |    |
         |           ^    |                 {+}  {-}  {|}
         +----(+)----*    |                  |    |    |
         |           ^    |                  |    |    |
         +----(-)----+    +------------------+<---+<---+
    
    
    Term:
    
              +--------+
    O----+----+  Power +----+----+----+----+----+----+----O
         ^    +--------+    |    |    |    |    |    |
         |                  |    |    |    |    |    |
         |                 {*}  {/}  {%}  {&} {<<}  {>>}
         |                  |    |    |    |    |    |
         |                  |    |    |    |    |    |
         +------------------+<---+<---+<---+<---+<---+
    
    
    Power:
        
              +--------+
    O----+----+ Factor +----+----O
         ^    +--------+    |    
         |                  |    
         |                 {^} 
         |                  |  
         |                  | 
         +------------------+
    
    Factor:
    
                     +------------+
    O----+-----------+   Const    +------------------------------------+----O
         |           +------------+                                    ^
         |                                                             |
         |           +------------+           +------------+           |
         +-----------+  FuncName  +----{(}----+ Expression +----{)}----+
         |           +------------+           +------------+           ^
         |                                                             |
         |           +------------+                                    |
         +----{(}----+ Expression +----{)}-----------------------------+
                     +------------+
    
    */
    
    
private $scanner;
    private 
$operatorTypeTerm;
    private 
$operatorTypeFactor;
    
    public function 
__construct(Scanner $input)
    {
        
$this->scanner $input;
        
        
$this->operatorTypeTerm "NIL";
        
$this->operatorTypePower "NIL";
        
$this->operatorTypeFactor "NIL";
        
$this->operatorTypeMonadic "NIL";
        
$this->evaluator = new Evaluator;
    }


    public function 
Expression()
    {
        
$ThisEvaluator = new Evaluator();
        if (
$this -> scanner -> Char('~'))
            
$this->operatorTypeMonadic "NOT";
            
        if (
$this -> scanner -> Char('+'))
            ;
            
        if (
$this -> scanner -> Char('-'))
            
$this->operatorTypeMonadic "NEGATIVE";
        
        for (;;)
        {
            if (!
$this -> Term())
                break;
        
            
$this -> evaluator -> OperatorMonadic($this -> operatorTypeMonadic);
            
$this -> evaluator -> OperatorDyadic($this -> operatorTypeTerm);
            
$this -> operatorTypeMonadic "NIL";
            
$this -> operatorTypeTerm "NIL";
            
            if (
$this -> scanner -> Char('+'))
            {
                 
$this -> operatorTypeTerm "PLUS";
                continue;                
            }
            if (
$this -> scanner -> Char('-'))
            {
                 
$this -> operatorTypeTerm "MINUS";
                continue;                
            }
            if (
$this -> scanner -> Char('|'))
            {
                 
$this -> operatorTypeTerm "OR";
                continue;                
            }
            
$Result[0] = true;
            
$Result[1] = $this -> evaluator -> GetResult();
            return 
$Result;                
        }
        
$Result[0] = false;
        return 
$Result;
    }
    
    public function 
Term()
    {
        for (;;)
        {
             if (!
$this -> Power())
                 break;
             
             
$this -> evaluator -> OperatorMonadic($this -> operatorTypeMonadic);
            
$this -> evaluator -> OperatorDyadic($this -> operatorTypePower);
            
$this -> operatorTypeMonadic "NIL";
            
$this -> operatorTypePower "NIL";

            if (
$this -> scanner -> Char('*'))
            {
                 
$this -> operatorTypePower "MULTIPLY";
                continue;                
            }
            if (
$this -> scanner -> Char('/'))
            {
                 
$this -> operatorTypePower "DIVIDE";
                continue;                
            }
            if (
$this -> scanner -> Char('%'))
            {
                
$this -> operatorTypePower "MODULO";
                continue;                
            }
            if (
$this -> scanner -> Char('&'))
            {
                
$this -> operatorTypePower "AND";
                continue;                
            }
            return 
true;                
        }
        return 
false;
    }    
    
    public function 
Power()
    {
        for (;;)
        {
             if (!
$this -> Factor())
                 break;
             
            
$this -> evaluator -> OperatorMonadic($this -> operatorTypeMonadic);
            
$this -> evaluator -> OperatorDyadic($this -> operatorTypeFactor);
            
$this -> operatorTypeMonadic "NIL";
            
$this -> operatorTypeFactor "NIL";
             
            if (
$this -> scanner -> Char('^'))
            {
                 
$this -> operatorTypeFactor "POWER";
                continue;                
            }
            return 
true;                
        }
        return 
false;
    }        
    
    public function 
Factor()
    {
        
$Result $this -> scanner -> Constant();
        if (
$Result[0])
        {
            
$this -> evaluator -> Enter($Result[1]);
            return 
true;
        }
        
$Result $this -> scanner -> Name();
        if (
$Result[0])
        {
            if (!
$this -> scanner -> Char('('))
                return 
false;

            if (!
$this -> ExpressionInternal())
                return 
false;

            if (!
$this -> scanner -> Char(')'))
                return 
false;
    
            return 
true;
        }
        
        if (!
$this -> scanner -> Char('('))
            return 
false;
        
        
$innerParser = new Parser ($this -> scanner);
        
$Result $innerParser -> Expression();    
        if(!
$Result[0])
            return 
false;
        
        
$this -> evaluator -> Enter($Result[1]);
                
        if (!
$this -> scanner -> Char(')'))
            return 
false;

        return 
true;
    }    
        
}

class 
Stream
{
    private 
$String;
    private 
$Pos;
    private 
$Length;
    
    public function 
__construct($Input)
    {
        
$this->Source $Input;
        
$this->Length strlen($this->Source);
        
$this->Pos 0;    
    }
    
    public function 
Get()
    {
        if (
$this->Pos  >= $this->Length)
            return 
'\0';
        
        
$Char substr($this->Source$this->Pos1);
        
$this->Pos ++;
        return 
$Char;
    }

    public function 
Unget()
    {
        if (
$this->Pos 0)
            
$this->Pos --;        
    }
    public function 
Dump()
    {
        echo 
"<hr>".$this->Source."<br>";
        echo 
$this->Length."<br>";
        echo 
$this->Pos."<br><hr>";
    }
    
}

class 
Scanner
{
     private 
$stream;

    public function 
__construct(Stream $stream)
    {
        
$this->stream $stream;
    }     

    public function 
Char($matchChar)
    {
        
$this->SkipSpace();
        
$Char $this->stream->Get();
        if (
$Char == $matchChar)
        {
            return 
true;
        }
        else
        {
            
$this->stream->Unget();
            return 
false;
        }
    }

    public function 
Name()
    {
        
$Name "";
         
$this->SkipSpace();
        
        
$Char $this->stream->Get();
        
        if (!
$this->IsLetter($Char))
        {
            
$this->stream->Unget();
            
$Result[0] = false;
            return 
$Result;
        } 
        do
        {
            
$Name $Name.$Char;
            
$Char $this->stream->Get();
        }
        while (
$this->IsLetter($Char));
        
        
$this->stream->Unget();
        
$Result $this -> SymbolSearch($Name);
        return 
$Result;
    }
    
    public function 
Constant()
    {
        
$IntValue 0;
        
$this->SkipSpace();
        
$ConstantResult = array();
     
        
$Char $this->stream->Get();
         
$Sign 1;
        if (
$Char == "-")
             
$Sign = -1;
        else    
             
$this->stream->Unget();
         
        
$Char $this->stream->Get();
    
        if (!
$this->IsDigit($Char))
        {
            
$this->stream->Unget();
            
$ConstantResult[0] = false;
            
$ConstantResult[1] = 0;    
            return 
$ConstantResult;
        }
        do
        {
            
$IntValue *= 10;
            
$IntValue += intval($Char);
            
$Char $this->stream->Get();
        }
        while (
$this->IsDigit($Char));
    
        if (
$Char != ".")
        {
            
$this->stream->Unget();
            
$ConstantResult[0] = true;
            
$ConstantResult[1] = $IntValue $Sign;    
            return 
$ConstantResult;
        }
    
        
$Divider 10;
        
$BrokenValue 0;
        for (;;)
        {
            
$Char $this->stream->Get();
            if (!
$this->IsDigit($Char))
            {
                
$this->stream->Unget();
                
$ConstantResult[0] = true;
                
$ConstantResult[1] = ($IntValue $BrokenValue) * $Sign;    
                return 
$ConstantResult;
            }
            
            
$BrokenValue += intval($Char)/$Divider;
            
$Divider *= 10;
        }

    }        
    public function 
End()
    {
        
$this->SkipSpace();
        
$Char $this->stream->Get();
        return 
$Char == '\0';
    }
    
    public function 
Dump()
    {
         
$this->stream->Dump();
    }
    
    private function 
IsLetter($Char)
    {
        return (
$Char >= 'a' && $Char <= 'z') || ($Char >= 'A' && $Char <= 'Z');
    }
    
    private function 
IsDigit($Char)
    {
        return 
$Char >= '0' && $Char <= '9';
    }
    
    private function 
SymbolSearch($Name)
    {
        
$SymbolTable = array
        (
            
"arccos",        //0
            
"arcsin",        //1
            
"arctan",        //2
            
"cotan",        //3
            
"exp",            //4
            
"pi",            //5
            
"sin",            //6
            
"tan",            //7
            
"cos",            //8
        
);
        if (
in_array($Name$SymbolTable)) 
        {
            
$ResultArray[0] = true;
            
$ResultArray[1] = array_search($Name,$SymbolTable);
        }
        else
            
$ResultArray[0] = false;
            
        return 
$ResultArray;
    }
    
    private function 
SkipSpace()
    {
         do
         {
            
$Char $this->stream->Get();
        }
        while (
$Char == ' ' || $Char == '\t');        
        
$this->stream->Unget();
    }
    
}
?>