didix16/php-grammar

一个用于构建语言的简单库，用于生成词法和解析器

维护者

详细信息

github.com/didix16/php-grammar

主页

源代码

问题

安装次数: 6,104

依赖者: 2

建议者: 0

安全: 0

星标: 1

关注者: 2

分支: 0

公开问题: 0

1.0.1 2021-08-09 12:39 UTC

Requires

  • php: >= 7.2

MIT 415280cedeca18c025ae78a846073d892330be12

parserbuildtokenizerSimpletokenlexergrammar

This package is auto-updated.

Last update: 2024-09-09 19:56:28 UTC

README

一个用于生成词法和解析器以构建语言的简单库。

内容

什么是标记

标记是您语言的最基本组成部分。它可以是特定字母表 A 中的一个单个字符，也可以是其中一些字符的组合。

什么是词法分析器

词法分析器负责解析原始文本并将其分词，以便解析器可以使用语法进行解释。

示例：假设我们有以下文本

$library = require('path/to/lib');

假设我们的语言有变量、函数等。

应用解析器后的结果将生成以下标记

  • T_VAR < library > 被称为 'library' 的变量标识符
  • T_ASIGN < = > 表示从右向左赋值的单个字符
  • T_FUNC < require > 函数名。语言应识别该函数并执行它。
  • T_FUNC_ARG < 'path/to/lib' > 传递给上一个函数的函数参数。
  • T_ENDLINE <;> 表示行结束的单个字符

有了这些标记后，解析器应在其语法中识别出您正在构建的语言的正确语法。

什么是解析器

解析器或语法负责解释由词法分析器生成的标记，并评估它们，以确定您正在构建的语言的正确语法。

我们还将语法称为上下文无关语法。更多信息请参阅上下文无关语法 - 维基百科

为了编程语法，我们将使用乔姆斯基正规形式，因为我们必须为我们的语法定义良好的规则，并且最重要的是，我们将使用BNF - 巴科斯-诺尔范式来定义每个规则。

安装

composer require didix16/php-grammar

用法

我将展示一个简单的示例，说明如何构建一个语言，该语言可以识别一个简单的脚本以执行某些操作，如GET URL并进行处理。

让我们称它为APIScript，并应使用APILexer和APIParser。

一个简单的脚本结构可能如下所示

GET https://some-awesome-api.com/endpoint?token=TOKEN
PIPETO $mySuperService
SAVEDB localhost:10000

我们可以识别行，其中每行都是一个操作。每个操作都有一个键名、一个空格和一个参数（它可以是参数列表）

所以，假设我们必须识别以下标记

T_ACTION, T_WHITESPACE, T_ARG 和 T_NEWLINE

<?php

// APILexer.php

use didix16\Grammar\Lexer;
use didix16\Grammar\Token;

class APILexer extends Lexer {

    /**
     * Token identifiers
     */
    const T_ACTION = 2;
    const T_WHITESPACE = 3;
    const T_ARG = 4;
    const T_NEWLINE = 5;

    /**
     * For the sake of tokenization, its necessary to make a general regular expression
     * to identify the tokens inside the raw text.
     */
    const REG_TOKEN = '/([A-Za-z_][A-Za-z0-9_\-]*)(?= )|( )|([^ \n\r]+)|(\n?)/';

    /**
     * These are the string representation of each token. It is using the token ID
     * to get the name so, the order matters and should be the same you specified
     * on Token identifiers.
     * 
     * Index 0 and 1 should be allways "n/a" for 0 and <EOF> for 1.
     */
    static $tokenNames = ["n/a", "<EOF>", "T_ACTION", "T_WHITESPACE", "T_ARG", "T_NEWLINE"];

    /**
     * These are the regular expressions that identifies each token.
     * They will be used to compare against the next word found by REG_TOKEN and must
     * check if is one of our language tokens.
     */
    const REG_T_ACTION = '/^[a-zA-Z_][a-zA-Z0-9_]*$/';
    const REG_T_WHITESPACE = '/^ $/';
    const REG_T_ARG = '/^([^ \n]+)$/';
    const REG_T_NEWLINE = '/^(\n)$/'
    


    /**
     * Returns the next word is ahead current lexer pointer
     * @return string
     */
    protected function lookahead(): string
    {
        $word = self::LAMBDA;
        if (0 != preg_match(self::REG_TOKEN, $this->input, $matches, PREG_OFFSET_CAPTURE, $this->p + strlen($this->word))){
            $word = $matches[0][0];
        }
        return $word;
    }

    /**
     * From input string, consume a word and advance the internal pointer to the next word
     */
    public function consume(): Lexer
    {
        if (0 != preg_match(self::REG_TOKEN, $this->input, $matches, PREG_OFFSET_CAPTURE, $this->p)){

            $this->word = $matches[0][0];
            $this->p = $matches[0][1] + strlen($this->word);
        } else {
            $this->word = self::LAMBDA;
        }

        return $this;
    }

    /**
     * Check if word $text is an action
     */
    protected function isAction($text){

        return 1 === preg_match(self::REG_T_ACTION, $text);
    }

    /**
     * Check if word $text is a whitespace character
     */
    protected function isWhitespace($text){
        
        return 1 === preg_match(self::REG_T_WHITESPACE, $text);
    }

    /**
     * Check if word $text is an argument
     */
    protected function isArg($text){
        
        return 1 === preg_match(self::REG_T_ARG, $text);
    }

    /**
     * Check if word $text is a new line character
     */
    protected function isNewLine($text){

        return 1 === preg_match(self::REG_T_NEWLINE, $text);
    }

    /**
     * Returns the next token identified by this lexer
     * @return Token
     * @throws \Exception
     */
    public function nextToken(): Token {

        // current word being processed
        $word = $this->word;
        if ($this->word != self::LAMBDA) {
            
            // action and arg are very similiar. We have to differentiate them
            if (
                $this->isAction($this->word) ||
                $this->isArg($this->word)
            ){
                
                $lastTokenType = $this->lastToken()->getType();

                $this->consume();

                // if last token was a whitspace then we are on an arg token
                $type = $lastTokenType !== self::T_WHITESPACE ? self::T_ACTION : self::T_ARG;

                return $this->returnToken($type, $word);

                
            } else 
            if ($this->isWhitespace($this->word)) {

                $this->consume();
                return $this->returnToken(self::T_WHITESPACE, $word);
            } else 
            if ($this->isNewLine($this->word)) {

                $this->consume();
                return $this->returnToken(self::T_NEWLINE, $word);
            }
            
            else {
                throw new \Exception("Invalid symbol [" . $word . "]");
            }


        }

        return $this->returnToken(self::EOF_TYPE, self::$tokenNames[1]);
    }

    /**
     * Given a token type, returns its token name representation
     * @return string
     */
    public function getTokenName($tokenType): string {

        return APILexer::$tokenNames[$tokenType];
    }
}

我们现在将定义我们的语法。看看如何将BNF应用于程序形式。

我假设APILexer和APIParser在同一个目录下。

<?php

// APIParser.php

use didix16\Grammar\Lexer;
use didix16\Grammar\Parser;

/**
 * Grammar: S (Syntax) is the entrypoint
 * ------------------------------------------------------
 * S            := LineList
 * Line         := Action Whitespace Argument
 * LineList     := Line [NewLine LineList]
 * Action       := /^[a-zA-Z_][a-zA-Z0-9_]*$/
 * Argument     := /^[^ \n]+/
 * Whitespace   := /^ $/
 * NewLine      := /^\n$/
 */
class APIParser extends Parser {

    /**
     * Line := Action Whitespace Argument
     */
    public function line(){

        $this->action();

        $this->whitespace();

        $this->argument();

    }

    /**
     * LineList := Line [NewLine LineList]
     */
    public function lineList(){

        $this->line();

        if ( $this->lookahead->getType() === APILexer::T_NEWLINE ){

            $this->newLine();
            $this->lineList();
        }

    }

    /**
     * Action := ^[a-zA-Z_][a-zA-Z0-9_]*$
     */
    public function action(){

        $this->match(APILexer::T_ACTION);
    }

    /**
     * Argument := /^[^ \n]+/
     */
    public function argument(){

        $this->match(APILexer::T_ARG);
    }

    /**
     * Whitespace := /^ $/
     */
    public function whitespace(){

        $this->match(APILexer::T_WHITESPACE);
    }

    /**
     * NewLine := ^\n$
     */
    public function newLine(){

        $this->match(APILexer::T_NEWLINE);
    }

    /**
     * S := LineList
     */
    public function parse(): array {

        $this->lineList();
        $this->match(Lexer::EOF_TYPE);

        return $this->getTokens();
    }
}

最后，让我们用一个简单的代码示例来演示

$script = "GET https://some-awesome-api.com/endpoint?token=TOKEN
PIPETO $mySuperService
SAVEDB localhost:10000";


$lexer = new APILexer($script);
$parser = new APIParser($lexer);

$tokens = $parser->parse();

// var_dump($tokens) should be:

array(12) {
  [0]=>
  object(Token)#4 (2) {
    ["value":protected]=>
    string(3) "GET"
    ["type":protected]=>
    int(2)
  }
  [1]=>
  object(Token)#2 (2) {
    ["value":protected]=>
    string(1) " "
    ["type":protected]=>
    int(3)
  }
  [2]=>
  object(Token)#5 (2) {
    ["value":protected]=>
    string(49) "https://some-awesome-api.com/endpoint?token=TOKEN"
    ["type":protected]=>
    int(4)
  }
  [3]=>
  object(Token)#6 (2) {
    ["value":protected]=>
    string(1) "
"
    ["type":protected]=>
    int(5)
  }
  [4]=>
  object(Token)#7 (2) {
    ["value":protected]=>
    string(6) "PIPETO"
    ["type":protected]=>
    int(2)
  }
  [5]=>
  object(Token)#8 (2) {
    ["value":protected]=>
    string(1) " "
    ["type":protected]=>
    int(3)
  }
  [6]=>
  object(Token)#9 (2) {
    ["value":protected]=>
    string(15) "$mySuperService"
    ["type":protected]=>
    int(4)
  }
  [7]=>
  object(Token)#10 (2) {
    ["value":protected]=>
    string(1) "
"
    ["type":protected]=>
    int(5)
  }
  [8]=>
  object(Token)#11 (2) {
    ["value":protected]=>
    string(6) "SAVEDB"
    ["type":protected]=>
    int(2)
  }
  [9]=>
  object(Token)#12 (2) {
    ["value":protected]=>
    string(1) " "
    ["type":protected]=>
    int(3)
  }
  [10]=>
  object(Token)#13 (2) {
    ["value":protected]=>
    string(15) "localhost:10000"
    ["type":protected]=>
    int(4)
  }
  [11]=>
  object(Token)#14 (2) {
    ["value":protected]=>
    string(5) "<EOF>"
    ["type":protected]=>
    int(1)
  }
}

现在，有了解析后的标记，您可以执行任何评估操作及其参数的操作。

例如，您可能有一个解释器，它会评估标记并执行相应的操作。

例如，GET可能使用某些库来执行HTTP GET请求；PIPETO可能将收集的数据传递给您的系统服务之一；SAVEDB可能将PIPETO $mySuperService的结果保存到指定的DDBB主机。

也请参阅

  • php-interpreter - 一个基于PHP的基解释器，用于解析您自己的标记。