编译原理-有穷自动机-实践

前言

• 真的喜欢代码的人,有谁不期望有一天自己创造一门语音或者编译器呢,哪怕只是学习下程序是怎么跑起来的.
• 入门老师 HowdyAI 和 他的视频

实现 & | ( ) 表达式运算的程序, 有穷自动机, 人生第一段语法分析代码, 这种开心花钱真的只能通过学习获得

运行结果
输入: true |(false &true )
输出: 1

<?php


$s = [
    function () {
        return true;
    },
    '|',
    '(',
    function () {
        return false;
    },
    '&',
    function () {
        return true;
    },
    ')'
];

$echo = "";
foreach ($s as $item) {
    if(is_callable($item)){
        $echo .= $item() ? "true " : "false ";
    }else{
        $echo .= $item;
    }
}
echo $echo . PHP_EOL;

$index = 0;

// 终结符为 A1
class StateA
{
    const A0 = 0; // 初始
    const A1 = 1; // 计算了计算式
    const A2 = 2; // 匹配了符号
}

function A($word, $isReset)
{
    static $state = StateA::A0;
    static $expr = null;
    static $and = null;

    if ($isReset) {
        $state = StateA::A0;
        $expr = null;
        $and = null;
        return [];
    }

    switch ($state) {
        case StateA::A0:
            switch ($word) {
                case is_callable($word):
                    $tmp = $word();
                    $expr = function () use ($tmp) {
                        return $tmp;
                    };
                    $state = StateA::A1;
                    break;
                default:
                    print_r($word);
                    throw new Exception($word);
            }
            break;
        case StateA::A1:
            switch ($word) {
                case "&":
                    $and = true;
                    $state = StateA::A2;
                    break;
                case "|":
                    $or = true;
                    $state = StateA::A2;
                    break;
                default:
                    throw new Exception();
            }
            break;
        case StateA::A2:
            switch ($word) {
                case is_callable($word):
                    if ($and) {
                        $tmp = $expr() && $word();
                    } else {
                        $tmp = $expr() || $word();
                    }
                    $and = null;
                    $expr = function () use ($tmp) {
                        return $tmp;
                    };
                    $state = StateA::A1;
                    break;
                default:
                    throw new Exception();
            }
            break;
        default:
            throw new Exception();
    }
    return [$state, $expr];
}


function B($word, $isEnd)
{
    static $exprList = [
        []
    ];
    if ($isEnd) {
        if(count($exprList) !== 1){
            print_r($exprList);
            throw new Exception();
        }
        $tmp = reset($exprList);
        A(null, true);
        foreach ($tmp as $item) {
            [$tmpState, $tmpR] = A($item, false);
        }
        if (!isset($tmpState) || !isset($tmpR)) {
            throw new Exception();
        }
        return $tmpR();
    }

    switch ($word) {
        case "(";
            $exprList[] = [];
            break;
        case ")":
            $tmp = array_pop($exprList);
            $tmpState = null;
            A(null, true);
            foreach ($tmp as $item) {
                [$tmpState, $tmpR] = A($item, false);
            }
            if (!isset($tmpState) || !isset($tmpR)) {
                throw new Exception();
            }
            $exprList[count($exprList) - 1][] = $tmpR;
            break;
        default:
            $exprList[count($exprList) - 1][] = $word;
    }
    return null;
}

foreach ($s as $word) {
    B($word, false);
}

$r = B(null, true);

print_r($r);

有穷自动机 第二弹 2022年8月5号

• 可以解析array() 的数据结构,例如 array(1,1,2) 能解析为数组变量

  <?php
  $valueRaw = "array(1,1,2)";
  $tokens = token_get_all("<?php $valueRaw");
  array_shift($tokens);
  $array = getArray($tokens);
  
  var_dump($array);
  
  function getArray($tokens)
  {
      $res = null;
      $arrays = [
  
      ];
  
      $k = null;
      $v = null;
      $minus = false;
  
      foreach ($tokens as $token) {
          if (!is_array($token)) {
              switch ($token) {
                  case ")":
                      if (!is_null($v)) {
                          if (count($arrays)) {
                              if (is_null($k)) {
                                  $arrays[count($arrays) - 1][] = $v;
                              } else {
                                  $arrays[count($arrays) - 1][$k] = $v;
                              }
                          } else {
                              throw new Exception();
                          }
                          $k = null;
                          $v = null;
                      }
                      $tmp = array_pop($arrays);
                      if (count($arrays)) {
                          $v = $tmp;
                      } else {
                          if (is_null($res)) {
                              $res = $tmp;
                          } else {
                              throw new Exception();
                          }
                      }
                      break;
                  case ",":
                      if (!is_null($v)) {
                          if (count($arrays)) {
                              if (is_null($k)) {
                                  $arrays[count($arrays) - 1][] = $v;
                              } else {
                                  $arrays[count($arrays) - 1][$k] = $v;
                              }
                          } else {
                              throw new Exception();
                          }
                          $k = null;
                          $v = null;
                      }
                      break;
                  case "-":
                      $minus = true;
                      break;
              }
          } else {
              switch ($token[0]) {
                  case T_ARRAY:
                      $arrays[] = [];
                      break;
                  case T_LNUMBER:
                      $v = intval($token[1]);
                      if($minus){
                          $minus = false;
                          $v = -$v;
                      }
                      break;
                  case T_STRING:
                  case T_CONSTANT_ENCAPSED_STRING:
                      $v = substr($token[1], 1, (strlen($token[1]) - 2));
                      break;
                  case T_DNUMBER:
                      $v = floatval($token[1]);
                      if($minus){
                          $minus = false;
                          $v = -$v;
                      }
                      break;
                  case T_WHITESPACE:
                      break;
                  case T_DOUBLE_ARROW:
                      $k = $v;
                      $v = null;
                      break;
                  default:
                      throw new Exception();
              }
          }
      }
      return $res;
  }