Edgar Hoo Blog

编写识别由下列文法所定义的表达式的递归下降语法分析器。

E -> E+T | E-T | T

T -> T*F | T/F |F

F -> (E) | i

输入：每行含一个表达式的文本文件。

输出：分析成功或不成功信息。

（来源：海南大学儋州校区计算机系）

采用PHP编码，代码如下：

• /*
• Item Name: Recursive of the Decline Grammar Analysis
• Description: Compilation Principle Experiment 2nd
• Version: 1.0
• Author: Edgar Hoo
• Author URI: http://EdgarHoo.com
• Last Updated: Dec. 1, 2008 @ SCUTA
• CopyRight 2008 BY-NC-SA
• */
• @ $fp = fopen("rdga.txt", 'rb');
• if (!$fp){
• echo '没有文件！</body></html>';
• exit;
• }
• $array = file("rdga.txt");
• $n = count($array);
• $err = 1;
• if ($array[0] == '') echo '文件没有内容！';
• for ($i=0;$i<$n;$i++){
•     $order = trim($array[$i]);
•     check($order,&$err);
• }
• function check($order,&$err){
•     $l = strlen($order);
•     for ($j=0;$j<$l;$j++){
•         $x = substr($order,$j,1);
•         if (!($x=='+' || $x=='-' || $x=='*' || $x=='/' || $x=='(' || $x==')' || $x=='i'))
•         $err=0;
•         if ($err==0) break;
•     }
•     if ($err==0) echo $order.'含有非法字符！<br />';
•     else{
•         $j=0;
•         $x = substr($order,$j,1);
•         recogE($order,&$x,&$j,&$err);
•         if ($err==1){
•             if ($j==$l) echo $order.'符合文法。<br />';
•             else echo $order.'不符合文法。<br />';
•         }
•     }
• }
• function recogE($order,&$x,&$j,&$err){
•     if ($err==1){
•         recogT($order,&$x,&$j,&$err);
•         recogE1($order,&$x,&$j,&$err);
•     }
• }
• function recogT($order,&$x,&$j,&$err){
•     if ($err==1){
•         recogF($order,&$x,&$j,&$err);
•         recogT1($order,&$x,&$j,&$err);
•     }
• }
• function recogE1($order,&$x,&$j,&$err){
•     if ($err==1){
•         if ($x=='+' || $x=='-'){
•             ++$j;
•             $x = substr($order,$j,1);
•             recogT($order,&$x,&$j,&$err);
•             recogE1($order,&$x,&$j,&$err);
•         }
•         else if ($x!='' && $x!=')'){
•             echo $order.'不符合文法。<br />';
•             $err=0;
•         }
•     }
• }
• function recogT1($order,&$x,&$j,&$err){
•     if ($err==1){
•         if ($x=='*' || $x=='/'){
•             ++$j;
•             $x = substr($order,$j,1);
•             recogF($order,&$x,&$j,&$err);
•             recogT1($order,&$x,&$j,&$err);
•         }
•         else if ($x!='' && $x!=')' && $x!='+' && $x!='-'){
•             echo $order.'不符合文法。<br />';
•             $err=0;
•         }
•     }
• }
• function recogF($order,&$x,&$j,&$err){
•     if ($err==1){
•         if ($x=='('){
•             ++$j;
•             $x = substr($order,$j,1);
•             recogE($order,&$x,&$j,&$err);
•             if ($x==')'){
•                 ++$j;
•                 $x = substr($order,$j,1);
•             }
•             else if ($x==''){
•                 echo $order.'不符合文法。<br />';
•                 $err=0;
•                 ++$j;
•                 $x = substr($order,$j,1);
•             }
•         }
•         else if ($x=='i') {
•             ++$j;
•             $x = substr($order,$j,1);
•         }
•         else {
•             echo $order.'不符合文法。<br />';
•             $err=0;
•         }
•     }
• }
• fclose($fp);

测试地址：循环下降语法分析器

@ Dec. 6, 2008 SCUTA