DEV Community: Anton Sukhachev

JSON parser with PHP and Bison

Anton Sukhachev — Mon, 03 Apr 2023 09:28:50 +0000

Read this post if you don't know what Bison is.

Today I'll try to parse JSON into AST and compare it with the native PHP function json_decode().
To test our parser I will use this JSON file:

test.json

{
    "fieldString": "string",
    "fieldNumber": 99,
    "fieldBoolTrue": true,
    "fieldBoolFalse": false,
    "fieldNull": null,
    "fieldEmptyArray": [],
    "fieldEmptyObject": {},
    "fieldArray": [
        "string",
        99,
        true,
        false,
        null,
        {},
        []
    ]
}

First, we need to install PHP dependencies.

composer require --dev mrsuh/php-bison-skeleton
composer require mrsuh/tree-printer
composer require doctrine/lexer

mrsuh/php-bison-skeleton - to build PHP parser with Bison
mrsuh/tree-printer - to print AST
doctrine/lexer - to parse text into tokens

We will store our files like this:

.
├── /ast-parser
    ├── /bin
    │   └── parse.php # entry point to parse JSON
    ├── /lib
    │   └── parser.php # generated file
    ├── /src
    │   ├── Lexer.php
    │   └── Node.php # AST node
    └── grammar.y

The Node class must implement Mrsuh\Tree\NodeInterface to print AST.

src/Node.php

<?php

namespace App;

use Mrsuh\Tree\NodeInterface;

class Node implements NodeInterface
{
    private string $name;
    private string $value;
    /** @var Node[] */
    private array $children;

    public function __construct(string $name, string $value, array $children = [])
    {
        $this->name     = $name;
        $this->value    = $value;
        $this->children = $children;
    }

    public function getChildren(): array
    {
        return $this->children;
    }

    public function __toString(): string
    {
        if (!empty($this->value)) {
            return sprintf("%s: '%s'", $this->name, $this->value);
        }

        return $this->name;
    }
}

I'll use the Doctrine lexer library. It helps to parse complex text.

src/Lexer.php

<?php

namespace App;

use Doctrine\Common\Lexer\AbstractLexer;

class Lexer extends AbstractLexer implements LexerInterface
{
...
    protected function getCatchablePatterns(): array
    {
        return [
            '\:',
            '\{',
            '\}',
            '\[',
            '\]',
            '\,',
            "\"[^\"]+\"",
            'true',
            'false',
            'null',
        ];
    }

    protected function getNonCatchablePatterns(): array
    {
        return [
            ' ',
            '\n'
        ];
    }

    protected function getType(&$value): int
    {
        if (in_array($value, [':', '{', '}', '[', ']', ','], true)) {
            return ord($value);
        }

        if (is_numeric($value)) {
            return LexerInterface::T_NUMBER;
        }

        switch (strtolower($value)) {
            case 'true':
            case 'false':
                return LexerInterface::T_BOOL;
            case 'null':
                return LexerInterface::T_NULL;
        }

        return LexerInterface::T_STRING;
    }
...
}

For example, Lexer will translate the JSON

{
    "array": [
        "string",
        99,
        true,
        false,
        null
    ]
}

into this:

word	token
{	ASCII (123)
"array"	LexerInterface::T_STRING (258)
:	ASCII (58)
[	ASCII (91)
"string"	LexerInterface::T_STRING (258)
,	ASCII (44)
99	LexerInterface::T_NUMBER (259)
,	ASCII (44)
true	LexerInterface::T_BOOL (260)
,	ASCII (44)
false	LexerInterface::T_BOOL (260)
,	ASCII (44)
null	LexerInterface::T_NULL (261)
,	ASCII (44)
]	ASCII (93)
}	ASCII (125)
	LexerInterface::YYEOF (0)

Time to create grammar.y file and build lib/parser.php

PHP already has the native function json_decode() and it uses Bison to generate a C parser.
I think we can get ready Bison grammar file from the php-src repository and modify it.
The grammar file is very small because JSON standard is very simple.

We will use block %code parser to define variables and methods to store AST into the Parser class.

grammar.y

%define api.parser.class {Parser}
%define api.namespace {App}
%code parser {
    private Node $ast;
    public function setAst(Node $ast): void { $this->ast = $ast; }
    public function getAst(): Node { return $this->ast; }
}

%token T_STRING
%token T_NUMBER
%token T_BOOL
%token T_NULL

%%
start:
  value  { self::setAst($1); }
;

object:
'{' members '}' { $$ = $2; }
;

members:
  %empty             { $$ = []; }
| member             { $$ = [$1]; }
| members ',' member { $$ = $1; $$[] = $3; }
;

member:
  T_STRING ':' value  { $$ = new Node('T_STRING', $1, [$3]); }
;

array:
'['  elements ']' { $$ = $2; }
;

elements:
  %empty             { $$ = []; }
| value              { $$ = [$1]; }
| elements ',' value { $$ = $1; $$[] = $3; }
;

value:
  object   { $$ = new Node('T_OBJECT', '', $1); }
| array    { $$ = new Node('T_ARRAY', '', $1); }
| T_STRING { $$ = new Node('T_STRING', $1); }
| T_NUMBER { $$ = new Node('T_NUMBER', $1); }
| T_BOOL   { $$ = new Node('T_BOOL', $1); }
| T_NULL   { $$ = new Node('T_NULL', $1); }
;

%%

bison -S vendor/mrsuh/php-bison-skeleton/src/php-skel.m4 -o lib/parser.php grammar.y

Command options:

-S vendor/mrsuh/php-bison-skeleton/src/php-skel.m4 - path to skeleton file
-o parser.php - output parser file
grammar.y - our grammar file

The final PHP file is the entry point for the parser.

bin/parse.php

<?php

require_once __DIR__ . '/../vendor/autoload.php';

use App\Parser;
use App\Lexer;
use Mrsuh\Tree\Printer;

$lexer  = new Lexer(fopen($argv[1], 'r'));
$parser = new Parser($lexer);
if (!$parser->parse()) {
    exit(1);
}

$printer = new Printer();
$printer->print($parser->getAst());

Autoload for generated lib/parser.php file.

composer.json

{
    "autoload": {
        "psr-4": {
            "App\\": "src/"
        },
        "files": ["lib/parser.php"]
    },
    ...
}

Finally, we can test our parser.

php bin/parse.php test.json 
.
├── T_OBJECT
    ├── T_STRING: 'fieldString'
    │   └── T_STRING: 'string'
    ├── T_STRING: 'fieldNumber'
    │   └── T_NUMBER: '99'
    ├── T_STRING: 'fieldBoolTrue'
    │   └── T_BOOL: 'true'
    ├── T_STRING: 'fieldBoolFalse'
    │   └── T_BOOL: 'false'
    ├── T_STRING: 'fieldNull'
    │   └── T_NULL: 'null'
    ├── T_STRING: 'fieldEmptyArray'
    │   └── T_ARRAY
    ├── T_STRING: 'fieldEmptyObject'
    │   └── T_OBJECT
    └── T_STRING: 'fieldArray'
        └── T_ARRAY
            ├── T_STRING: 'string'
            ├── T_NUMBER: '99'
            ├── T_BOOL: 'true'
            ├── T_BOOL: 'false'
            ├── T_NULL: 'null'
            ├── T_OBJECT
            └── T_ARRAY

It works!

I think it will be cool if we compare the native json_decode() function and our parser.
First, I need a JSON file for benchmarks. I can get JSON info about Bulbasaur pokemon from API https://pokeapi.co.

curl 'https://pokeapi.co/api/v2/pokemon/bulbasaur' > bench.json

The file weight is 215KB.

We need to modify our grammar.y file to avoid Node creating.

grammar-bench.y

...
value:
  object   { $$ = $1; }
| array    { $$ = $1; }
| T_STRING { $$ = $1; }
| T_NUMBER { $$ = $1; }
| T_BOOL   { $$ = $1; }
| T_NULL   { $$ = $1; }
...

bison -S ../../src/php-skel.m4 -o lib/parser.php grammar-bench.y

We are ready to start the comparison.

PHP 8.2

php vendor/bin/phpbench run tests --report=my-report
+-------------+----------+----------+--------+
| subject     | mem_peak | mode     | rstdev |
+-------------+----------+----------+--------+
| benchNative | 2.539mb  | 1.570ms  | ±0.89% |
| benchBison  | 12.443mb | 84.283ms | ±1.08% |
+-------------+----------+----------+--------+

PHP 8.1

php vendor/bin/phpbench run tests --report=my-report
+-------------+----------+----------+--------+
| subject     | mem_peak | mode     | rstdev |
+-------------+----------+----------+--------+
| benchNative | 2.593mb  | 1.595ms  | ±0.68% |
| benchBison  | 18.471mb | 87.471ms | ±0.68% |
+-------------+----------+----------+--------+

PHP 8.0

php vendor/bin/phpbench run tests --report=my-report
+-------------+----------+----------+--------+
| subject     | mem_peak | mode     | rstdev |
+-------------+----------+----------+--------+
| benchNative | 2.700mb  | 1.586ms  | ±0.90% |
| benchBison  | 18.578mb | 87.533ms | ±0.83% |
+-------------+----------+----------+--------+

PHP 7.4

php vendor/bin/phpbench run tests --report=my-report
+-------------+----------+-----------+--------+
| subject     | mem_peak | mode      | rstdev |
+-------------+----------+-----------+--------+
| benchNative | 2.857mb  | 1.725ms   | ±1.00% |
| benchBison  | 18.735mb | 105.099ms | ±0.91% |
+-------------+----------+-----------+--------+

PHP Bison parser shows the best result with PHP 8.2.
It is ~56 times slower than the native json_decode() function.

I hope it was interesting for you!

You can get the parser source code here and test it by yourself.

Some useful links:

Nginx parser with PHP and Bison

Anton Sukhachev — Mon, 27 Mar 2023 10:55:29 +0000

Read this post if you don't know what Bison is.

Today I'll try to parse Nginx config into AST.
I get the actual Nginx config from official Symfony documentation to test the parser.
nginx.conf

server {
    server_name domain.tld www.domain.tld;
    root /var/www/project/public;

    location / {
        # try to serve file directly, fallback to index.php
        try_files $uri /index.php$is_args$args;
    }

    location /bundles {
        try_files $uri =404;
    }

    location ~ ^/index\.php(/|$) {
        fastcgi_pass unix:/var/run/php/php-fpm.sock;
        fastcgi_split_path_info ^(.+\.php)(/.*)$;
        include fastcgi_params;

        # optionally set the value of the environment variables used in the application
        fastcgi_param APP_ENV prod;
        fastcgi_param APP_SECRET <app-secret-id>;
        fastcgi_param DATABASE_URL "mysql://db_user:db_pass@host:3306/db_name";
        fastcgi_param SCRIPT_FILENAME $realpath_root$fastcgi_script_name;
        fastcgi_param DOCUMENT_ROOT $realpath_root;       
        internal;
    }

    location ~ \.php$ {
        return 404;
    }

    error_log /var/log/nginx/project_error.log;
    access_log /var/log/nginx/project_access.log;
}

First, we need to install PHP dependencies.

composer require --dev mrsuh/php-bison-skeleton
composer require mrsuh/tree-printer
composer require doctrine/lexer

mrsuh/php-bison-skeleton - to build PHP parser with Bison
mrsuh/tree-printer - to print AST
doctrine/lexer - to parse text into tokens

We will store our files like this:

.
├── /ast-parser
    ├── /bin
    │   └── parse.php # entry point to parse nginx configs
    ├── /lib
    │   └── parser.php # generated file
    ├── /src
    │   ├── Lexer.php
    │   └── Node.php # AST node
    └── grammar.y

The Node class must implement Mrsuh\Tree\NodeInterface to print AST.
src/Node.php

<?php

namespace App;

use Mrsuh\Tree\NodeInterface;

class Node implements NodeInterface
{
    private string $name;
    /** @var array<string, mixed> */
    private array $attributes;
    /** @var Node[] */
    private array $children;

    public function __construct(string $name, array $attributes = [], array $children = [])
    {
        $this->name       = $name;
        $this->attributes = $attributes;
        $this->children   = $children;
    }

    public function getChildren(): array
    {
        return $this->children;
    }

    public function __toString(): string
    {
        $line = $this->name;
        if (!empty($this->attributes)) {
            $line .= ' {';
            foreach ($this->attributes as $key => $value) {
                $line .= sprintf(
                    " %s: '%s'",
                    $key,
                    is_array($value) ? implode(', ', $value) : $value
                );
            }
            $line .= ' }';
        }

        return $line;
    }
}

This time I'll use Doctrine lexer library. It can help to parse complex text.

src/Lexer.php

<?php

namespace App;

use Doctrine\Common\Lexer\AbstractLexer;

class Lexer extends AbstractLexer implements LexerInterface
{
    public function __construct($resource)
    {
        $this->setInput(stream_get_contents($resource));
        $this->moveNext();
    }

    protected function getCatchablePatterns(): array
    {
        return [';'];
    }

    protected function getNonCatchablePatterns(): array
    {
        return [' ','[\n]+','#[^\n]+']; // skip spaces, eol, and comments 
    }

    protected function getType(&$value): int
    {
        switch ($value) {
            case 'server':
                return LexerInterface::T_SERVER;
            case 'server_name':
                return LexerInterface::T_SERVER_NAME;

               ...
        }

        return ord($value);
    }

    public function yyerror(string $message): void
    {
        printf("%s\n", $message);
    }

    public function getLVal()
    {
        return $this->token->value;
    }

    public function yylex(): int
    {
        if (!$this->lookahead) {
            return LexerInterface::YYEOF;
        }

        $this->moveNext();

        return $this->token->type;
    }
}

For example, Lexer will translate the Nginx config below

server {
    server_name domain.tld www.domain.tld;
    root /var/www/project/public;

    location / {
        # try to serve file directly, fallback to index.php
        try_files $uri /index.php$is_args$args;
    }
}

into this:

word	token
server	LexerInterface::T_SERVER (258)
{	ASCII (123)
server_name	LexerInterface::T_SERVER_NAME (259)
domain.tld	LexerInterface::T_SERVER_NAME_VALUE (260)
www.domain.tld	LexerInterface::T_SERVER_NAME_VALUE (260)
;	ASCII (59)
root	LexerInterface::T_SERVER_ROOT (261)
/var/www/project/public	LexerInterface::T_SERVER_ROOT_PATH (262)
;	ASCII (59)
location	LexerInterface::T_LOCATION (263)
/	ASCII (264)
{	ASCII (123)
try_files	LexerInterface::T_TRY_FILES (283)
$uri	LexerInterface::T_TRY_FILES_PATH (284)
/index.php$is_args$args	LexerInterface::T_TRY_FILES_PATH (284)
;	ASCII (59)
}	ASCII (125)
}	ASCII (125)
	LexerInterface::YYEOF (0)

Time to create grammar.y file and build lib/parser.php

We will use block %code parser to define variables and methods to store AST into the Parser class.
You can find full grammar file here.
grammar.y

%define api.parser.class {Parser}
%define api.namespace {App}
%code parser {
    private Node $ast;
    public function setAst(Node $ast): void { $this->ast = $ast; }
    public function getAst(): Node { return $this->ast; }
}

%token T_SERVER
%token T_SERVER_NAME
%token T_SERVER_NAME_VALUE
%token T_SERVER_ROOT
%token T_SERVER_ROOT_PATH
...
%token T_TRY_FILES
%token T_TRY_FILES_PATH

%%
server:
  T_SERVER '{' server_body_list '}' { self::setAst(new Node('T_SERVER', [], $3)); }
;

server_name_values:
  T_SERVER_NAME_VALUE                     { $$ = [$1]; }
| server_name_values T_SERVER_NAME_VALUE  { $$ = $1; $$[] = $2; }
;

server_body:
  T_SERVER_NAME server_name_values ';'  { $$ = new Node('T_SERVER_NAME', ['names' => $2]); }
| T_SERVER_ROOT T_SERVER_ROOT_PATH ';'  { $$ = new Node('T_SERVER_ROOT', ['path' => $2]); }
| T_ERROR_LOG T_ERROR_LOG_PATH ';'      { $$ = new Node('T_ERROR_LOG', ['path' => $2]); }
| T_ACCESS_LOG T_ACCESS_LOG_PATH ';'    { $$ = new Node('T_ACCESS_LOG', ['path' => $2]); }
;
...

bison -S vendor/mrsuh/php-bison-skeleton/src/php-skel.m4 -o lib/parser.php grammar.y

Command options:

-S vendor/mrsuh/php-bison-skeleton/src/php-skel.m4 - path to skeleton file
-o parser.php - output parser file
grammar.y - our grammar file

The final PHP file is the entry point for the parser.
bin/parse.php

<?php

require_once __DIR__ . '/../vendor/autoload.php';

use App\Parser;
use App\Lexer;
use Mrsuh\Tree\Printer;

$lexer  = new Lexer(fopen($argv[1], 'r'));
$parser = new Parser($lexer);
if (!$parser->parse()) {
    exit(1);
}

$printer = new Printer();
$printer->print($parser->getAst());

Autoload for generated lib/parser.php file.
composer.json

{
    "autoload": {
        "psr-4": {
            "App\\": "src/"
        },
        "files": ["lib/parser.php"]
    },
    ...
}

Finally, we can test our parser.

php bin/parse.php nginx.conf
.
├── T_SERVER
    ├── T_SERVER_NAME { names: 'domain.tld, www.domain.tld' }
    ├── T_SERVER_ROOT { path: '/var/www/project/public' }
    ├── T_LOCATION { regexp: '' path: '/' }
    │   └── T_TRY_FILES { paths: '$uri, /index.php$is_args$args' }
    ├── T_LOCATION { regexp: '' path: '/bundles' }
    │   └── T_TRY_FILES { paths: '$uri, =404' }
    ├── T_LOCATION { regexp: '~' path: '^/index\.php(/|$)' }
    │   ├── T_FAST_CGI_PATH { path: 'unix:/var/run/php/php-fpm.sock' }
    │   ├── T_FAST_CGI_SPLIT_PATH_INFO { path: '^(.+\.php)(/.*)$' }
    │   ├── T_INCLUDE { path: 'fastcgi_params' }
    │   ├── T_FAST_CGI_PARAM { APP_ENV: 'prod' }
    │   ├── T_FAST_CGI_PARAM { APP_SECRET: '<app-secret-id>' }
    │   ├── T_FAST_CGI_PARAM { DATABASE_URL: '"mysql://db_user:db_pass@host:3306/db_name"' }
    │   ├── T_FAST_CGI_PARAM { SCRIPT_FILENAME: '$realpath_root$fastcgi_script_name' }
    │   ├── T_FAST_CGI_PARAM { DOCUMENT_ROOT: '$realpath_root' }
    │   └── T_INTERNAL
    ├── T_LOCATION { regexp: '~' path: '\.php$' }
    │   └── T_RETURN { code: '404' body: '' }
    ├── T_ERROR_LOG { path: '/var/log/nginx/project_error.log' }
    └── T_ACCESS_LOG { path: '/var/log/nginx/project_access.log' }

It works!

You can get the parser source code here and test it by yourself.

Some useful links:

AST parser with PHP and Bison

Anton Sukhachev — Sun, 19 Mar 2023 08:02:38 +0000

Read this post if you don't know what Bison is.

I already have the Bison AST parser, but this time I will do it without PHP FFI.

First, we need to install the PHP skeleton package to build the parser and tree printer package to print AST.

composer require --dev mrsuh/php-bison-skeleton
composer require mrsuh/tree-printer

It will more readable if we separate code from printer.php to individual files.

.
├── /ast-parser
    ├── /bin
    │   └── parse.php # entry point for parser
    ├── /lib
    │   └── parser.php # generated file
    ├── /src
    │   ├── Lexer.php
    │   └── Node.php # AST node
    └── grammar.y

To print AST with the tree printer package Node class must implement Mrsuh\Tree\NodeInterface.

src/Node.php

<?php

namespace App;

use Mrsuh\Tree\NodeInterface;

class Node implements NodeInterface
{
    private string $name;
    private string $value;
    /** @var Node[] */
    private array $children;

    public function __construct(string $name, string $value, array $children = [])
    {
        $this->name     = $name;
        $this->value    = $value;
        $this->children = $children;
    }

    public function getChildren(): array
    {
        return $this->children;
    }

    public function __toString(): string
    {
        $line = $this->name;
        if (!empty($this->value)) {
            $line .= sprintf(" '%s'", $this->value);
        }

        return $line;
    }
}

Lexer is not modified from previous post, but this time we will put it in a separate file src/Lexer.php.

src/Lexer.php

<?php

namespace App;

class Lexer implements LexerInterface {

    private array $words;
    private int   $index = 0;
    private int   $value = 0;

    public function __construct($resource)
    {
        $this->words = explode(' ', trim(fgets($resource)));
    }

    public function yyerror(string $message): void
    {
        printf("%s\n", $message);
    }

    public function getLVal()
    {
        return $this->value;
    }

    public function yylex(): int
    {
        if ($this->index >= count($this->words)) {
            return LexerInterface::YYEOF;
        }

        $word = $this->words[$this->index++];
        if (is_numeric($word)) {
            $this->value = (int)$word;

            return LexerInterface::T_NUMBER;
        }

        return ord($word);
    }
}

For example, Lexer will translate the expression 10 + 20 - 30 into this:

word	token	value
10	LexerInterface::T_NUMBER (258)	10
+	ASCII (43)
20	LexerInterface::T_NUMBER (258)	20
-	ASCII (45)
30	LexerInterface::T_NUMBER (258)	30
	LexerInterface::YYEOF (0)

It's time to create the grammar.y file and build lib/parser.php
You can define %code blocks, so Bison will render code as is in printer.php

grammar.y

%code imports { // code imports };
%code parser  { // code parser }; 
%code init    { // code init };

printer.php

<?php

// code imports

class Parser {
    // code parser
    public function __construct() {
        // code init
    }
}

We will use block %code parser to define variables and methods to store AST into the Parser class.
Bison has reserved the symbol $ in grammar actions.
It's very sad for PHP developers, but we can call the function setAst() with self::setAst() instead of $this->setAst().

grammar.y

%define api.parser.class {Parser}
%define api.namespace {App}
%code parser {
    private Node $ast;
    public function setAst(Node $ast): void { $this->ast = $ast; }
    public function getAst(): Node { return $this->ast; }
}

%token T_NUMBER

%left '-' '+'

%%
start:
  expression                 {  self::setAst($1); }
;

expression:
  T_NUMBER                   { $$ = new Node('NUMBER', $1); }
| expression '+' expression  { $$ = new Node('OPERATION_PLUS', '', [$1, $3]);  }
| expression '-' expression  { $$ = new Node('OPERATION_MINUS', '', [$1, $3]);  }
;

bison -S vendor/mrsuh/php-bison-skeleton/src/php-skel.m4 -o lib/parser.php grammar.y

Command options:

-S vendor/mrsuh/php-bison-skeleton/src/php-skel.m4 - path to skeleton file
-o parser.php - output parser file
grammar.y - our grammar file

And final PHP file is the entry point bin/parse.php.

bin/parse.php

<?php

require_once __DIR__ . '/../vendor/autoload.php';

use App\Lexer;
use App\Parser;
use Mrsuh\Tree\Printer;

$lexer  = new Lexer(STDIN);
$parser = new Parser($lexer);
if (!$parser->parse()) {
    exit(1);
}

$printer = new Printer(STDOUT);
$printer->print($parser->getAst());

We need to add a special autoload section to composer.json for generated lib/parser.php file.

composer.json

{
    "autoload": {
        "psr-4": {
            "App\\": "src/"
        },
        "files": ["lib/parser.php"]
    },
    ...
}

Ok. Our parser is ready and we can test it:

php bin/parse.php <<< "1 + 2 - 3"
.
├── OPERATION_MINUS
    ├── OPERATION_PLUS
    │   ├── NUMBER '1'
    │   └── NUMBER '2'
    └── NUMBER '3'

Try to parse big expression:

php bin/parse.php <<< "1 + 2 - 3 + 4 - 5 + 6 - 7 + 8 - 9 + 10"
.
├── OPERATION_PLUS
    ├── OPERATION_MINUS
    │   ├── OPERATION_PLUS
    │   │   ├── OPERATION_MINUS
    │   │   │   ├── OPERATION_PLUS
    │   │   │   │   ├── OPERATION_MINUS
    │   │   │   │   │   ├── OPERATION_PLUS
    │   │   │   │   │   │   ├── OPERATION_MINUS
    │   │   │   │   │   │   │   ├── OPERATION_PLUS
    │   │   │   │   │   │   │   │   ├── NUMBER '1'
    │   │   │   │   │   │   │   │   └── NUMBER '2'
    │   │   │   │   │   │   │   └── NUMBER '3'
    │   │   │   │   │   │   └── NUMBER '4'
    │   │   │   │   │   └── NUMBER '5'
    │   │   │   │   └── NUMBER '6'
    │   │   │   └── NUMBER '7'
    │   │   └── NUMBER '8'
    │   └── NUMBER '9'
    └── NUMBER '10'

Great!

You can get the parser source code here and test it by yourself.

Some useful links:

PHP Skeleton for Bison

Anton Sukhachev — Mon, 13 Mar 2023 11:13:21 +0000

What is Bison?

Bison is a parser generator.
For example, it can help you to build a parser to parse your code into AST:

<?php

namespace App;

class Test
{
    public function test($foo) {}
}

.
├── ZEND_AST_STMT_LIST
    ├── ZEND_AST_NAMESPACE
    │   └── ZEND_AST_ZVAL 'App'
    └── ZEND_AST_CLASS 'Test'
        └── ZEND_AST_STMT_LIST
            └── ZEND_AST_METHOD 'test'
                └── ZEND_AST_PARAM_LIST
                    └── ZEND_AST_PARAM
                        └── ZEND_AST_ZVAL 'foo'

There is software that uses Bison:

software	grammar.y
PHP	https://github.com/php/php-src/blob/master/Zend/zend_language_parser.y
Bash	https://git.savannah.gnu.org/cgit/bash.git/tree/parse.y
Ruby	https://github.com/ruby/ruby/blob/master/parse.y
MySQL	https://github.com/mysql/mysql-server/blob/8.0/sql/sql_yacc.yy
PostgreSQL	https://github.com/postgres/postgres/blob/master/src/backend/parser/gram.y
CMake	https://github.com/Kitware/CMake/blob/master/Source/LexerParser/cmExprParser.y

How Bison works?

Bison takes your grammar.y file, parses it, extracts all definitions, and then constructs a bunch of tables like this:

$yytable = [
    6, 3, 7, 20, 8, 51, 28, 1, 52, 4,
    9, 13, 10, 29, 15, 30, 18, 31, 16, 19,
    32, 22, 33, 34, 23, 24, 35, 11, 37, 25,
    21, 38, 39, 26, 45, 0, 40, 42, 0, 43,
    41, 0, 0, 49, 0, 0, 0, 0, 0, 47,
    48, 0, 50, 0, 53, 54
];

Then, this data is passed to a template that is called skeleton.
This skeleton is a special file written in M4 language that renders your parser.php file.
By default, Bison supports C/C++/D/Java languages, but you can extend it with your own skeleton file.

Simple calculator

Let's make a simple calculator with Bison and PHP. It will parse expression from stdin and print result.

First, we must install PHP skeleton package.

composer require --dev mrsuh/php-bison-skeleton

Then we define a simple grammar file.

grammar.y

%define api.parser.class {Parser}

%token T_NUMBER

%left '-' '+'

%%
start:
  exp                { printf("%f\n", $1); }
;

exp:
  T_NUMBER           { $$ = $1; }
| exp '+' exp        { $$ = $1 + $3;  }
| exp '-' exp        { $$ = $1 - $3;  }
;

%%

Let's build a parser from grammar.y:

bison -S vendor/mrsuh/php-bison-skeleton/src/php-skel.m4 -o parser.php grammar.y

Command options:

-S vendor/mrsuh/php-bison-skeleton/src/php-skel.m4 - path to skeleton file
-o parser.php - output parser file
grammar.y - our grammar file

For now, parser.php does nothing. But we can see the interface LexerInterface inside it:

parser.php

interface LexerInterface
{
    public const YYEOF = 0;    
    public const YYerror = 256;    
    public const YYUNDEF = 257;
    public const T_NUMBER = 258; /** %token T_NUMBER */
    ...
}
...

Interface contains constants with our tokens from grammar.y file and some special values for the end of file or errors.
With this interface, we can write our class Lexer to parse calculation expressions into tokens.

class Lexer implements LexerInterface {

    private array $words;
    private int   $index = 0;
    private int   $value = 0;

    public function __construct($resource)
    {
        $this->words = explode(' ', trim(fgets($resource)));
    }

    public function getLVal()
    {
        return $this->value;
    }

    public function yylex(): int
    {
         $this->value = 0;

        if ($this->index >= count($this->words)) {
            return LexerInterface::YYEOF;
        }

        $word = $this->words[$this->index++];

        if (is_numeric($word)) {
            $this->value = (int)$word;

            return LexerInterface::T_NUMBER;
        }

        return ord($word);
    }
}

Every time we call the function Lexer::yylex(), it will return the token's identifier and store the word into the value property.
For example, the expression 10 + 20 - 30 will translate into this:

word	token	value
10	LexerInterface::T_NUMBER (258)	10
+	ASCII (43)
20	LexerInterface::T_NUMBER (258)	20
-	ASCII (45)
30	LexerInterface::T_NUMBER (258)	30
	LexerInterface::YYEOF (0)

And the last part.
We must instantiate lexer, parser and bind them.

$lexer  = new Lexer(STDIN);
$parser = new Parser($lexer);
if (!$parser->parse()) {
    exit(1);
}

Let's assemble all parts above into a single grammar.y file.

grammar.y

%define api.parser.class {Parser}

%token T_NUMBER

%left '-' '+'

%%
start:
  exp                { printf("%f\n", $1); }
;

exp:
  T_NUMBER           { $$ = $1; }
| exp '+' exp        { $$ = $1 + $3;  }
| exp '-' exp        { $$ = $1 - $3;  }
;

%%

class Lexer implements LexerInterface {

    private array $words;
    private int   $index = 0;
    private int   $value = 0;

    public function __construct($resource)
    {
        $this->words = explode(' ', trim(fgets($resource)));
    }

    public function getLVal()
    {
        return $this->value;
    }

    public function yylex(): int
    {
         $this->value = 0;

        if ($this->index >= count($this->words)) {
            return LexerInterface::YYEOF;
        }

        $word = $this->words[$this->index++];

        if (is_numeric($word)) {
            $this->value = (int)$word;

            return LexerInterface::T_NUMBER;
        }

        return ord($word);
    }
}

$lexer  = new Lexer(STDIN);
$parser = new Parser($lexer);
if (!$parser->parse()) {
    exit(1);
}

Build it:

bison -S vendor/mrsuh/php-bison-skeleton/src/php-skel.m4 -o parser.php grammar.y

It's time to test our parser.

php parser.php <<< "1 + 2 - 3 + 4 - 5 + 6 - 7 + 8 - 9 + 10"
7

It works!

Some useful links:

Few steps to make your docker image smaller

Anton Sukhachev — Mon, 20 Feb 2023 15:59:21 +0000

I have some projects where I need bison. I decided to build my image when I didn't find official or fresh unofficial docker images.

To compile bison you need to install some apt dependencies and compile the last version of autoconf from the source code.
I decided to make it from debian:bullseye-slim image. It is the latest Debian light image which size is 80.5MB (without compression).

docker images --format="table {{.Repository}}\t{{.Tag}}\t{{ .Size }}"  | grep "REPOSITORY\|debian"
REPOSITORY    TAG             SIZE
debian        bullseye-slim   80.5MB

bison-test:1.0

First I make a simple Dockerfile and build it.

FROM debian:bullseye-slim

ENV BISON_VERSION v3.8.2
ENV AUTOCONF_VERSION 2.71

# install apt dependencies
RUN set -eux; \
    apt-get update; \
    apt-get install -y \
        automake \
        autopoint \
        ca-certificates \
        flex \
        gettext \
        gcc \
        git \
        gperf \
        graphviz \
        help2man \
        libc6-dev \
        m4 \
        make \
        texinfo \
        wget \
        xsltproc

# compile autoconf
RUN wget ftp://ftp.gnu.org/gnu/autoconf/autoconf-$AUTOCONF_VERSION.tar.gz
RUN tar -xvzf autoconf-$AUTOCONF_VERSION.tar.gz
WORKDIR /autoconf-$AUTOCONF_VERSION
RUN ./configure
RUN make
RUN make install
WORKDIR /

# compile bison
RUN git clone --branch=$BISON_VERSION --depth=1 https://github.com/akimd/bison.git /bison
WORKDIR /bison
RUN git submodule update --init --recursive
RUN ./bootstrap
RUN ./configure
RUN make
RUN make install
WORKDIR /

docker build -t bison-test:1.0 .

Ok. Image contains many layers

docker history bison-test:1.0 --format="table {{.CreatedBy }}\t{{ .Size }}" | grep -v 0B
CREATED BY                                      SIZE
RUN /bin/sh -c make install # buildkit          5.86MB
RUN /bin/sh -c make # buildkit                  22.3MB
RUN /bin/sh -c ./configure # buildkit           2.02MB
RUN /bin/sh -c ./bootstrap # buildkit           18.1MB
RUN /bin/sh -c git submodule update --init -…   137MB
RUN /bin/sh -c git clone --branch=$BISON_VER…   6.55MB
RUN /bin/sh -c make install # buildkit          3.46MB
RUN /bin/sh -c make # buildkit                  990kB
RUN /bin/sh -c ./configure # buildkit           127kB
RUN /bin/sh -c tar -xvzf autoconf-$AUTOCONF_…   6.88MB
RUN /bin/sh -c wget ftp://ftp.gnu.org/gnu/au…   2MB
RUN /bin/sh -c set -eux;     apt-get update;…   348MB
/bin/sh -c #(nop) ADD file:3ea7c69e4bfac2ebb…   80.5MB

and the total size is 633MB.

docker images --format="table {{.Repository}}\t{{.Tag}}\t{{ .Size }}"  | grep "REPOSITORY\|bison-test"
REPOSITORY    TAG             SIZE
bison-test    1.0             633MB

bison-test:2.0

Let's reduce layers.
Instead of creating many separate RUN commands, I wrote two scripts.

RUN set -eux; \
   wget ftp://ftp.gnu.org/gnu/autoconf/autoconf-$AUTOCONF_VERSION.tar.gz; \
   tar -xvzf autoconf-$AUTOCONF_VERSION.tar.gz; \
    cd /autoconf-$AUTOCONF_VERSION; \
   ./configure; \
   make; \
   make install

RUN set -eux; \
   git clone --branch=$BISON_VERSION --depth=1 https://github.com/akimd/bison.git /bison; \
   cd /bison; \
   git submodule update --init --recursive; \
   ./bootstrap; \
   ./configure; \
   make; \
   make install

The number of layers has decreased

docker history bison-test:2.0 --format="table {{.CreatedBy }}\t{{ .Size }}" | grep -v 0B
CREATED BY                                      SIZE
RUN /bin/sh -c set -eux;  git clone --branch…   188MB
RUN /bin/sh -c set -eux;  wget ftp://ftp.gnu…   13.5MB
RUN /bin/sh -c set -eux;     apt-get update;…   348MB
/bin/sh -c #(nop) ADD file:3ea7c69e4bfac2ebb…   80.5MB

but the total size is only 3 MB smaller.

docker images --format="table {{.Repository}}\t{{.Tag}}\t{{ .Size }}"  | grep "REPOSITORY\|bison-test"
REPOSITORY    TAG             SIZE
bison-test    2.0             630MB

bison-test:3.0

Now I'll try to remove all the source files and add another RUN command to remove the apt dependencies and the apt cache.

RUN set -eux; \
   wget ftp://ftp.gnu.org/gnu/autoconf/autoconf-$AUTOCONF_VERSION.tar.gz; \
   tar -xvzf autoconf-$AUTOCONF_VERSION.tar.gz; \
    cd /autoconf-$AUTOCONF_VERSION; \
   ./configure; \
   make; \
   make install; \
   rm -rf /autoconf-$AUTOCONF_VERSION.tar.gz; \ # remove unnecessary source files
    rm -rf /autoconf-$AUTOCONF_VERSION # remove unnecessary source files

RUN set -eux; \
   git clone --branch=$BISON_VERSION --depth=1 https://github.com/akimd/bison.git /bison; \
   cd /bison; \
   git submodule update --init --recursive; \
   ./bootstrap; \
   ./configure; \
   make; \
   make install; \
   rm -rf /bison # remove unnecessary source files

# remove apt dependencies and cache
RUN set -eux; \
    apt-mark auto '.*' > /dev/null; \
    apt-get purge -y --auto-remove -o APT::AutoRemove::RecommendsImportant=false; \
    rm -rf /var/lib/apt/lists/*

docker history bison-test:3.0 --format="table {{.CreatedBy }}\t{{ .Size }}" | grep -v 0B
CREATED BY                                      SIZE
RUN /bin/sh -c set -eux;     apt-mark auto '…   1.96MB
RUN /bin/sh -c set -eux;  git clone --branch…   5.83MB
RUN /bin/sh -c set -eux;  wget ftp://ftp.gnu…   3.46MB
RUN /bin/sh -c set -eux;     apt-get update;…   330MB
/bin/sh -c #(nop) ADD file:3ea7c69e4bfac2ebb…   80.5MB

The total size is 422MB. It's 211MB smaller than the first image bison-test:1.0

docker images --format="table {{.Repository}}\t{{.Tag}}\t{{ .Size }}"  | grep "REPOSITORY\|bison-test"
REPOSITORY    TAG             SIZE
bison-test    3.0             422MB

bison-test:4.0

The last image is smaller, but too large compared to the original debian:bullseye-slim image.
When you see the previous image layers, you may notice that the apt-install layer is very big and the last command does not reduce the size of the image.
I need to install dependencies, compile bison and remove dependencies inside one layer.
Let's do it.

FROM debian:bullseye-slim

ENV BISON_VERSION v3.8.2
ENV AUTOCONF_VERSION 2.71

RUN set -eux; \
    apt-get update; \
    apt-get install -y --no-install-recommends \
        automake \
        autopoint \
        ca-certificates \
        flex \
        gettext \
        gcc \
        git \
        gperf \
        graphviz \
        help2man \
        libc6-dev \
        m4 \
        make \
        texinfo \
        wget \
        xsltproc; \
    \
   wget ftp://ftp.gnu.org/gnu/autoconf/autoconf-$AUTOCONF_VERSION.tar.gz; \
   tar -xvzf autoconf-$AUTOCONF_VERSION.tar.gz; \
    cd /autoconf-$AUTOCONF_VERSION; \
   ./configure; \
   make; \
   make install; \
   rm -rf /autoconf-$AUTOCONF_VERSION.tar.gz; \
   rm -rf /autoconf-$AUTOCONF_VERSION; \
   cd /; \
    \
   git clone --branch=$BISON_VERSION --depth=1 https://github.com/akimd/bison.git /bison; \
   cd /bison; \
   git submodule update --init --recursive; \
   ./bootstrap; \
   ./configure; \
   make; \
   make install; \
   rm -rf /bison; \
   cd /; \
    \
    apt-mark auto '.*' > /dev/null; \
    apt-get purge -y --auto-remove -o APT::AutoRemove::RecommendsImportant=false; \
    rm -rf /var/lib/apt/lists/*

Great! The image has only two layers

docker history bison-test:4.0 --format="table {{.CreatedBy }}\t{{ .Size }}" | grep -v 0B
CREATED BY                                      SIZE
RUN /bin/sh -c set -eux;     apt-get update;…   11.3MB
/bin/sh -c #(nop) ADD file:3ea7c69e4bfac2ebb…   80.5MB

and the total size is 91.8 MB!

docker images --format="table {{.Repository}}\t{{.Tag}}\t{{ .Size }}"  | grep "REPOSITORY\|bison-test"
REPOSITORY    TAG             SIZE
bison-test    4.0             91.8MB

Now you know a few simple steps to make your image smaller:

reduce the number of layers
remove unnecessary files/dependencies inside the layer where you created it

You can see the original bison Dockerfile here.

How PHP engine builds AST

Anton Sukhachev — Mon, 05 Sep 2022 15:01:19 +0000

First let's look at the PHP codeflow:

Prior to version 7, PHP generated OPcodes right inside the parser. PHP 7 introduced a new code abstraction - AST.
Now we can separate parsing and compilation.

In this post I want to talk about the Lexer + Parser part.

PHP uses re2c to create a lexer and Bison to create a parser. If you don't know about these tools, I recommend reading this post.

Let's start with the lexer.
The main function of the lexer is to parse the code into tokens.

The PHP 8 tokenizer module provides us with the PhpToken class to parse code into tokens.
This is very similar to PHP's internal lexer.

Let's write lexer.php and use it to parse the test.php file.

lexer.php

<?php

$code = file_get_contents($argv[1]);

$tokens = PhpToken::tokenize($code);

foreach ($tokens as $token) {
    echo $token->getTokenName() . " ";
}

test.php

<?php

$a = 1;

echo $a;

lexer.php output:

php lexer.php test.php
T_OPEN_TAG 
T_WHITESPACE 
T_VARIABLE T_WHITESPACE = T_WHITESPACE T_LNUMBER ; 
T_WHITESPACE 
T_ECHO T_WHITESPACE T_VARIABLE ;

I put the contents of test.php and the output of lexer.php in the same place for a better comparison:

<?php    |   T_OPEN_TAG
         |   T_WHITESPACE
$a = 1;  |   T_VARIABLE T_WHITESPACE = T_WHITESPACE T_LNUMBER ;
         |   T_WHITESPACE
echo $a; |   T_ECHO T_WHITESPACE T_VARIABLE ;

How does the PHP lexer parse code into tokens?
re2c helps with this.
re2c is an open-source lexer generator. It uses regular expressions to recognize tokens.

The PHP lexer code is in zend_language_scanner.l
The main function that recognizes the code and returns the token is lex_scan:
zend_language_scanner.l

int ZEND_FASTCALL lex_scan(zval *zendlval, zend_parser_stack_elem *elem)
{

...

/*!re2c
re2c:yyfill:check = 0;
LNUM    [0-9]+(_[0-9]+)*
DNUM    ({LNUM}?"."{LNUM})|({LNUM}"."{LNUM}?)
EXPONENT_DNUM   (({LNUM}|{DNUM})[eE][+-]?{LNUM})
HNUM    "0x"[0-9a-fA-F]+(_[0-9a-fA-F]+)*
BNUM    "0b"[01]+(_[01]+)*
ONUM    "0o"[0-7]+(_[0-7]+)*

...

<ST_IN_SCRIPTING>"exit" {
    RETURN_TOKEN_WITH_IDENT(T_EXIT);
}

<ST_IN_SCRIPTING>"const" {
    RETURN_TOKEN_WITH_IDENT(T_CONST);
}

<ST_IN_SCRIPTING>"return" {
    RETURN_TOKEN_WITH_IDENT(T_RETURN);
}

...

*/

After the lexer we have tokens, but we need a parser to build AST.
Bison can help us with this.
Bison is an open-source context-free parser generator.
It can generate a parser from BNF.

Example of Bison BNF:

line:
  %empty
|  expr { printf("%d", $1); }
;

expr:
    TOK_NUMBER    { $$ = $1; }
|   expr '+' expr { $$ = $1 + $3; }
|   expr '-' expr { $$ = $1 - $3; }
;

The parser code is in zend_language_parser.y

For example, this part parses PHP attributes (#[Attribute])
zend_language_parser.y

attribute_decl:
        class_name
            { $$ = zend_ast_create(ZEND_AST_ATTRIBUTE, $1, NULL); }
    |   class_name argument_list
            { $$ = zend_ast_create(ZEND_AST_ATTRIBUTE, $1, $2); }
;

When the parser finds a PHP attribute, it calls zend_ast_create function.
zend_ast.c

ZEND_API zend_ast *zend_ast_create(zend_ast_kind kind, ...)

zend_ast_create is one of several functions that help create an AST node.

PHP represents the AST node as a _zend_ast structure for simple nodes, and several more complex structures for other nodes.
zend_ast.h

struct _zend_ast {
    zend_ast_kind kind; /* Type of the node (ZEND_AST_* enum constant) */
    zend_ast_attr attr; /* Additional attribute, use depending on node type */
    uint32_t lineno;    /* Line number */
    zend_ast *child[1]; /* Array of children (using struct hack) */
};

The main parser function is yyparse. You don't need to write it - Bison will generate it itself;
Each time yyparse needs to get the next token, it calls the yylex lexer function.
We already have the lexer function lex_scan.

How do parser and lexer work together?

Bison has parameter api.prefix:

zend_language_parser.y

%define api.prefix {zend}

This means that all function prefixes will be zend instead of yy:
yyparse -> zendparse
yylex -> zendlex

We have the zendlex function in
zend_compile.c

int ZEND_FASTCALL zendlex(zend_parser_stack_elem *elem)

it calls the already known lex_scan function from zend_language_scanner.l

And zendparse is called in the function zend_compile_string_to_ast
zend_language_scanner.l

ZEND_API zend_ast *zend_compile_string_to_ast(zend_string *code, zend_arena **ast_arena, zend_string *filename)

In the final, we have a chain of calls:

zend_compile_string_to_ast() -> zendparse() -> zendlex() -> lex_scan()

Now we can call the zend_compile_string_to_ast function and get the real PHP AST.
I wrote a get_ast function to get the AST from zend_compile_string_to_ast, parse it and store it in a simple structure _node_ast so we can easily export it to PHP using FFI.
mrsuh/ast.c

node_ast *get_ast(char *input)

mrsuh/ast.h

struct _node_ast {
    const char *kind;
    const char *attr;
    const char *value;
    int lineno;
    int children;
    node_ast *child[100];
};

After compilation, I included it in PHP
mrsuh/Parser.php

<?php

self::$libc = \FFI::cdef(
"
typedef struct _node_ast node_ast;

struct _node_ast {
    const char *kind;
    const char *attr;
    const char *value;
    int lineno;
    int children;
    node_ast *child[100];
};

node_ast *get_ast(char *input);
",
__DIR__ . "ast_linux.so");

and translated the C structure into a PHP Node class.
mrsuh/Node.php

<?php

namespace Mrsuh\PhpAst;

final class Node
{
    public string $kind   = "";
    public string $value  = "";
    public int    $lineno = 0;
    /** @var Node[] */
    public array $children = [];
}

Let's parse some code into AST:

mrsuh/parse.php

<?php

require __DIR__. '/vendor/autoload.php';

use Mrsuh\PhpAst\Parser;
use Mrsuh\PhpAst\Printer;

$code = <<<'CODE'
<?php

namespace App;

class Test
{
    public function test($foo)
    {
        var_dump($foo);
    }
}
CODE;

$node = Parser::parse($code);
Printer::print($node);

mrsuh/parse.php output:

php parse.php
[001] ZEND_AST_STMT_LIST
[003]   ZEND_AST_NAMESPACE
[003]     ZEND_AST_ZVAL "App"
[005]   ZEND_AST_CLASS "Test"
[006]     ZEND_AST_STMT_LIST
[007]       ZEND_AST_METHOD "test"
[007]         ZEND_AST_PARAM_LIST
[007]           ZEND_AST_PARAM
[007]             ZEND_AST_ZVAL "foo"
[008]         ZEND_AST_STMT_LIST
[009]           ZEND_AST_CALL
[009]             ZEND_AST_ZVAL "var_dump"
[009]             ZEND_AST_ARG_LIST
[009]               ZEND_AST_VAR
[009]                 ZEND_AST_ZVAL "foo"

The complete parser code is here.

Nikita Popov already has a php-ast parser that uses zend_compile_string_to_ast function and a php-parser that uses the PHP tokenizer module as a lexer and a PHP version of YACC as a parser generator.

Below I have shown the outputs of three libraries for this code:
test.php

<?php

$a = 1;

echo $a;

mrsuh/php-ast

[001] ZEND_AST_STMT_LIST
[003]   ZEND_AST_ASSIGN
[003]     ZEND_AST_VAR
[003]       ZEND_AST_ZVAL "a"
[003]     ZEND_AST_ZVAL "1"
[005]   ZEND_AST_STMT_LIST
[005]     ZEND_AST_ECHO
[005]       ZEND_AST_VAR
[005]         ZEND_AST_ZVAL "a"

nikic/php-ast

AST_STMT_LIST
    0: AST_ASSIGN
        var: AST_VAR
            name: "a"
        expr: 1
    1: AST_ECHO
        expr: AST_VAR
            name: "a"

nikic/PHP-Parser

array(
    0: Stmt_Expression(
        expr: Expr_Assign(
            var: Expr_Variable(
                name: a
            )
            expr: Scalar_LNumber(
                value: 1
            )
        )
    )
    1: Stmt_Echo(
        exprs: array(
            0: Expr_Variable(
                name: a
            )
        )
    )
)

As for me, it looks very similar.

There are additional resources if you want to know more:

Parsing with PHP, Bison and re2c

Anton Sukhachev — Fri, 26 Aug 2022 06:44:00 +0000

The PHP engine uses Bison and re2c to parse code into AST.
I'll show you how we can use these tools with and without PHP to parse any structured text.

re2c is an open-source lexer generator. It uses regular expressions to recognize tokens.

A simple lexer example:

lexer.l

#include <stdio.h>

const char *lex(const char *s)
{
    /*!re2c
        re2c:yyfill:enable = 0;
        re2c:define:YYCTYPE = char;
        re2c:define:YYCURSOR = s;

        [0-9]+ { return "TOK_NUMBER"; }
        *      { return "TOK_ANY"; }
    */

    return "";
}

int main(int argc, char *argv[])
{
    printf("%s\n", lex(argv[1]));

    return 0;
}

Lexer reads stdin, determines token using a regular expression and prints token.

The re2c replaces the /*!re2c ... */ block with actual code:

re2c lexer.l > lexer.c

Lexer code after re2c:
lexer.c

#line 1 "lexer.l"
#include <stdio.h>

const char *lex(const char *s)
{

#line 9 "<stdout>"
{
    char yych;
    yych = *s;
    switch (yych) {
        case '0':
        case '1':
        case '2':
        case '3':
        case '4':
        case '5':
        case '6':
        case '7':
        case '8':
        case '9': goto yy2;
        default: goto yy1;
    }
yy1:
    ++s;
#line 11 "lexer.l"
    { return "TOK_ANY"; }
#line 30 "<stdout>"
yy2:
    yych = *++s;
    switch (yych) {
        case '0':
        case '1':
        case '2':
        case '3':
        case '4':
        case '5':
        case '6':
        case '7':
        case '8':
        case '9': goto yy2;
        default: goto yy3;
    }
yy3:
#line 10 "lexer.l"
    { return "TOK_NUMBER"; }
#line 49 "<stdout>"
}
#line 12 "lexer.l"


    return "";
}

int main(int argc, char *argv[])
{
    printf("%s\n", lex(argv[1]));

    return 0;
}

Let's compile and test it:

gcc lexer.c -o lexer

./lexer 123
TOK_NUMBER

./lexer test
TOK_ANY

Not bad. Now we can recognize numbers.

The next part is parsing.

Bison is an open-source context-free parser generator.
It can generate a parser from BNF.

A simple Bison example:

parser.y

%code top {
  #include <ctype.h>  /* isdigit. */
  #include <stdio.h>  /* printf. */

  int yylex();
  void yyerror(char const *);
}

%define api.header.include {"parser.h"}

%define api.value.type {double}
%token TOK_NUMBER
%type  expr

%left '-' '+'

%% /* The grammar follows. */
input:
  %empty
| expr '\n'  { printf ("%.10g\n", $1); }
;

expr:
  TOK_NUMBER    { $$ = $1; }
| expr '+' expr { $$ = $1 + $3; }
| expr '-' expr { $$ = $1 - $3; }
;

%%

int yylex()
{
    int c;

    /* Ignore white space, get first nonwhite character.  */
    while ((c = getchar()) == ' ' || c == '\t')
    {
        continue;
    }

    if (c == EOF)
    {
        return YYEOF;
    }

    /* Char starts a number => parse the number. */
    if (c == '.' || isdigit(c))
    {
        ungetc(c, stdin);
        if (scanf("%lf", &yylval) != 1)
        {
            return YYUNDEF;
        }

        return TOK_NUMBER;
    }

    return c;
}

void yyerror(char const *s)
{
    fprintf(stderr, "%s\n", s);
}

int main()
{
    return yyparse();
}

The main parser function is yyparse. Bison generates it himself.
Each time the parser needs the next token it calls the yylex function.
The yylex function reads a word, recognizes the word's token, stores the word in yyval and returns the token.

We have changed the type of yyval to store a double number.

%define api.value.type {double}

Bison grammar says:

parse text with numbers and signs (for example 1 + 2 - 3);
math it;
print the result.

input:
  %empty
| expr '\n'  { printf ("%.10g\n", $1); }
;

expr:
  TOK_NUMBER    { $$ = $1 }
| expr '+' expr { $$ = $1 + $3; }
| expr '-' expr { $$ = $1 - $3; }
;

Generate a parser and compile it:

bison --header -o parser.c parser.y
gcc parser.c -o parser

./parser
1 + 7
8

It works!

Let's combine Bison and re2c to parse simple math expressions into an AST.

First we need an AST node structure and functions to create this structure:
ast.c

typedef struct parser_ast {
    const char* kind;
    const char* value;
    struct parser_ast* children[2];
} parser_ast;

parser_ast* create_ast(const char* kind, const char* value);

parser_ast* create_ast_operation(const char* kind, parser_ast* left, parser_ast* right);

We need a char* type for TOK_NUMBER and a parser_ast* type for AST.
The yyval type has become the parser_t structure:
ast.c

typedef union parser_t {
    char* number;
    parser_ast* ast;
} parser_t;

Let's rewrite parser.y with a new yyval type and AST functions:
parser.y

%require "3.8"

%code top {
  #include <stdio.h>  /* fprintf. */
  #include "ast.h"

  int yylex(char **content);
  void yyerror(char **content, char const *);
  parser_ast *ast = NULL;
}

%param {char **content}

%define api.header.include {"parser.h"}
%define api.value.type {parser_t}

%token <number> TOK_NUMBER
%type  <ast> expr

%left '-' '+'

%%

line:
  %empty
|  expr { ast = $1; }
;

expr:
    TOK_NUMBER    { $$ = create_ast("NUMBER", $1); }
|   expr '+' expr { $$ = create_ast_operation("OPERATION_PLUS", $1, $3); }
|   expr '-' expr { $$ = create_ast_operation("OPERATION_MINUS", $1, $3); }
;

%%

void yyerror (char **content, char const *s)
{
  fprintf (stderr, "%s\n", s);
}

parser_ast* parse(char *content) {

    yyparse(&content);

    return ast;
}

int main(int argc, char *argv[])
{
    ast = parse(argv[1]);
    if (ast == NULL) {
       return 1;
    }

    dump_ast(ast, 0);

    return 0;
}

The new grammar creates a parser_ast structure with AST functions:
parser.y

expr:
    TOK_NUMBER    { $$ = create_ast("NUMBER", $1); }
|   expr '+' expr { $$ = create_ast_operation("OPERATION_PLUS", $1, $3); }
|   expr '-' expr { $$ = create_ast_operation("OPERATION_MINUS", $1, $3); }

Let's rewrite the yylex function with re2c and a new yyval type:
lexer.l

#include "ast.h"
#include "parser.h"
#include <stdio.h> // sprintf
#include <stdlib.h> // malloc

int yylex(char **content)
{
    for(;;) {
        char *last = *content;
        /*!re2c
            re2c:define:YYCTYPE  = char;
            re2c:define:YYCURSOR = *content;
            re2c:yyfill:enable   = 0;
            [\+\-]                { return *(*content-1); }
            [0-9]+                {
                                    int size = *content-last;
                                    yylval.number = (char *)malloc(size);
                                    sprintf(yylval.number, "%.*s", size, last);
                                    return TOK_NUMBER;
                                  }
            [ \t]+                { continue; }
            [\x00]                { return YYEOF; }
        */
    }

    return YYUNDEF;
}

For dump AST we need help function:
ast.c

void dump_ast(parser_ast* ast, int indent) {
    for(int i = 0; i < indent; i++) {
        printf(" ");
    }

    printf("%s", ast->kind);

    if(ast->value != "") {
        printf(" \"%s\"", ast->value);
    }
    printf("\n");

    for(int i = 0; i < 2; i++) {
        if(ast->children[i] != NULL) {
            dump_ast(ast->children[i], indent + 2);
        }
    }
}

Now we can compile all files into one and test it:

bison --header -o parser.c parser.y
re2c lexer.l > lexer.c
gcc ast.c lexer.c parser.c -o parser

./parser "10 - 20 + 30"
OPERATION_PLUS
  OPERATION_MINUS
    NUMBER "10"
    NUMBER "20"
  NUMBER "30"

Cool. But I want to use it with PHP.
I need to compile a shared library:

gcc -fPIC -shared -I . -o library_linux.so ast.c lexer.c parser.c

It's time to include library_linux.so into PHP with FFI:
parse.php

<?php

$libc = \FFI::cdef('
typedef struct parser_ast {
    const char* kind;
    const char* value;
    struct parser_ast* children[2];
} parser_ast;
parser_ast* parse(char *content);
', __DIR__ . "/library_linux.so");

function dump($ast, int $indent = 0): void
{
    $node = $ast[0];
    printf("%s%s%s\n",
        (str_repeat(' ', $indent)),
        $node->kind,
        $node->value ? sprintf(" \"%s\"", $node->value) : ''
    );
    for ($i = 0; $i < 2; $i++) {
        if ($node->children[$i] !== null) {
            dump($node->children[$i], $indent + 2);
        }
    }
}

$ast = $libc->parse($argv[1]);
dump($ast);

php parse.php "10 - 20 + 30"
OPERATION_PLUS
  OPERATION_MINUS
    NUMBER "10"
    NUMBER "20"
  NUMBER "30"

And it works again!

I posted the source code on GitHub.

Hope it will be useful for you!

Comparing PHP Collections

Anton Sukhachev — Tue, 22 Mar 2022 08:04:38 +0000

Let's imagine that we want to store a collection of Item objects:

<?php

namespace App\Entity;

class Item {
    public string $name = '';
    public int $value = 0;
}

Working with this collection we want to:

PHP does a type checks to make sure collection only stores Item objects
IDE makes hints about the type of Item objects in a collection
static analyses tool can find type errors

I want to compare:

Usage

Let's first compare usage.

Array

<?php

/** @var Item[] $collection */
$collection = [];
$collection[] = new Item();

/**
 * @param Item[] $collection
 */
function test(array $collection): array {}

pros

easy to implement
IDE makes hints about the type of Item objects in collection
static analyses tool can find type errors

cons

PHP doesn't check types

Psalm annotations

<?php

/**
 * @template T
 */
class Collection implements \Iterator
{
    protected \ArrayIterator $iterator;

    public function __construct()
    {
        $this->iterator = new \ArrayIterator();
    }

    /** @param T $item */
    public function append($item): void
    {
        $this->iterator->append($item);
    }

    /** @return T|null */
    public function current(): mixed
    {
        return $this->iterator->current();
    }
...
}

<?php
/** @var Collection<Item> $collection */
$collection = new Collection();
$collection->append(new Item());

/**
 * @param Collection<Item> $data
 * @return Collection<Item>
 */
function test(Collection $data): Collection {}

pros

IDE makes hints about the type of Item objects in collection
static analyses tool can find type errors

cons

PHP doesn't check types

Monomorphic generics

<?php

class Collection<T> implements \Iterator
{
    protected \ArrayIterator $iterator;

    public function __construct()
    {
        $this->iterator = new \ArrayIterator();
    }

    public function append(T $item): void
    {
        $this->iterator->append($item);
    }

    public function current(): ?T
    {
        return $this->iterator->current();
    }
..
}

<?php

$collection = new Collection<Item>;
$collection->append(new Item());

function test(Collection<Item> $data): Collection<Item> {}

pros

PHP does a type checks to make sure collection only stores Item objects

cons

static analyses tool can't find type errors
IDE doesn't make hints about the type of Item objects in a collection

Type erased generics

<?php

class Collection<T> implements \Iterator
{
    protected \ArrayIterator $iterator;

    public function __construct()
    {
        $this->iterator = new \ArrayIterator();
    }

    public function append(T $item): void
    {
        $this->iterator->append($item);
    }

    public function current(): ?T
    {
        return $this->iterator->current();
    }
...
}

<?php

$collection = new Collection<Item>;
$collection->append(new Item());

function test(Collection<Item> $data): Collection<Item> {}

cons

PHP doesn't check types
static analyses tool can't find type errors
IDE doesn't make hints about the type of Item objects in a collection

Memory

Memory test is very simple.
It creates $collection and puts Item objects into it count times.
For measurement I use var_sizeof() and memory_get_usage().

Items in collection: 0

type	var_class_sizeof(bytes)	var_sizeof(bytes)	memory_get_usage(bytes)
array(count: 0)	0	336	0
psalm(count: 0)	1,510	544	240
monomorphic(count: 0)	1,528	544	240
type-erased(count: 0)	1,512	544	240

Items in collection: 100

type	var_class_sizeof(bytes)	var_sizeof(bytes)	memory_get_usage(bytes)
array(count: 100)	0	7,728	12,248
psalm(count: 100)	1,510	7,936	12,432
monomorphic(count: 100)	1,528	7,936	12,432
type-erased(count: 100)	1,512	7,936	12,432

Items in collection: 1000

type	var_class_sizeof(bytes)	var_sizeof(bytes)	memory_get_usage(bytes)
array(count: 1000)	0	72,464	76,920
psalm(count: 1000)	1,510	72,672	77,104
monomorphic(count: 1000)	1,528	72,672	77,104
type-erased(count: 1000)	1,512	72,672	77,104

Items in collection: 10000

type	var_class_sizeof(bytes)	var_sizeof(bytes)	memory_get_usage(bytes)
array(count: 10000)	0	822,224	1,051,320
psalm(count: 10000)	1,510	822,432	1,051,560
monomorphic(count: 10000)	1,528	822,432	1,051,560
type-erased(count: 10000)	1,512	822,432	1,051,560

It's not surprising an array requires the least amount of memory.
Other approaches have roughly the same internal structure and require the same amount of memory.

Performance

I used phpbench to measure performance.
I think one of the big differences between all the solutions is the type checking. So I decided to try measure it.
How much faster will code with/without type checking?

PHPBench (1.2.3) running benchmarks...
with configuration file: /app/phpbench.json
with PHP version 8.1.3, xdebug ❌, opcache ❌

\App\Tests\TypHintBench

    benchWithoutType........................R1 I6 - Mo240.713μs (±0.47%)
    benchWithArrayType......................R1 I70 - Mo247.663μs (±0.45%)
    benchWithMixedType......................R2 I59 - Mo249.293μs (±0.54%)
    benchWithClassType......................R1 I26 - Mo306.533μs (±0.48%)

Subjects: 4, Assertions: 0, Failures: 0, Errors: 0
+--------------+--------------------+-----+------+-----+-----------+-----------+--------+
| benchmark    | subject            | set | revs | its | mem_peak  | mode      | rstdev |
+--------------+--------------------+-----+------+-----+-----------+-----------+--------+
| TypHintBench | benchWithoutType   |     | 1000 | 100 | 674.272kb | 240.713μs | ±0.47% |
| TypHintBench | benchWithArrayType |     | 1000 | 100 | 674.272kb | 247.663μs | ±0.45% |
| TypHintBench | benchWithMixedType |     | 1000 | 100 | 674.272kb | 249.293μs | ±0.54% |
| TypHintBench | benchWithClassType |     | 1000 | 100 | 674.272kb | 306.533μs | ±0.48% |
+--------------+--------------------+-----+------+-----+-----------+-----------+--------+

If the tests are correct, the difference between a function argument with class type and a function argument without a type is ~20%.

Conclusions

I have drawn some charts so you can compare all measurements in percentage. The results may vary slightly on different machines, but the percentage result should be the same

If you are only using simple collections you can use array - it is very fast and requires little memory.
PHP doesn't support generic syntax and IDE can't make hints about the type of objects in a collection (yet),
but if you want PHP to do type checks at runtime you can test the php-generics library.

I think for now the best solution is a combination of array with annotations for simple collections and Psalm annotation templates for complex objects.

If you want to reproduce the tests result you can find the source code and instructions here.

Generics implementation approaches

Anton Sukhachev — Tue, 08 Feb 2022 11:39:05 +0000

I want to introduce you to generics implementation approaches with some simple examples everyone can understand.
The description of each approach includes key features without details.
Basic examples are written in PHP because I'm a PHP developer, but there are also Hack/Java/C++ examples.

Type erasure

This approach means generics arguments are dropped after compilation.

Before type erasure:

<?php

class Container<T> {

    private T $data; 

    public function __construct(T $data) {
        $this->data = $data;
    }  
}

$intContainer = new Container<int>(1);

After type erasure:

<?php

class Container {

    private $data; 

    public function __construct($data) {
        $this->data = $data;
    }  
}

$intContainer = new Container(1);

You can't do that because it doesn't make sense after type erasure:

<?php

class Container<T> {       

    public function foo($data) {
        $className = T::class;

        T::staticFunction();

        $newObject = new T();

        if($data instanceof T) {

        }
    }  
}

During static analysis and compile time generics types can be reflected and checked, but after type erasure at run time, this is not possible.
This approach has a small performance/memory effect and some generics types restrictions (see example above).

Type erasure generics visibility table for better understanding:

	static analysis time	compile time	runtime
type reflection	yes	yes	no*
type checking	yes	yes	no

no* - generics types of some languages like Java/Hack may be reflected and not used by VM at runtime.

I can assume the PHP Psalm annotations are a kind of type erasure generics, but there is no such thing in PHP as generic types at compile/run time.
PHP Psalm annotations visibility table:

	static analysis time	compile time	runtime
type reflection	yes	no	no
type checking	yes	no	no

Let's look at a real example of type erasure generics in Java:

test.java

class Container<T> {

  private T data;

  public void set(T data) {
      this.data = data;
  }
}

class Programm {
    public static void main(String[] args) {
        Container<Integer> intContainer = new Container<Integer>();
        intContainer.set(1);

        Container<String> stringContainer = new Container<String>();
        stringContainer.set("hello");
    }
}

Use these commands to compile and run the script above:

docker run -it --rm -v $PWD:/app -w /app openjdk:latest javac test.java
docker run -it --rm -v $PWD:/app -w /app openjdk:latest java Programm

If you try to pass string "hello" to intContainer.set() you will get a compile time error:

test.java:13: error: incompatible types: String cannot be converted to Integer
        intContainer.set("hello");
                         ^

Reification

Generic arguments are retained at compile/run time and can be reflected.

There is a real example of reified generics in Hack.
The keyword reify is very important to mark a generics as reified.

test.hack

class MyContainer<reify T> {
    private T $var;

    public function set(T $var): void {
        $this->var = $var;
    }
}

<<__EntryPoint>>
function main(): void {
  $intContainer = new MyContainer<int>();
  $intContainer->set(1);

  $stringContainer = new MyContainer<string>();
  $stringContainer->set("hello");
}

You can run the script above with command:

docker run -it --rm -v $PWD:/app -w /app hhvm/hhvm:latest hhvm test.hack

If you try to pass string "hello" to $intContainer->set() you will get a compile time error:

Fatal error: Uncaught TypeError: Argument 1 passed to MyContainer::set() must be an instance of int, string given in /app/test.hack:6

At runtime, there is only one class MyContainer with many generic types.
Let's look inside the $stringContainer variable by var_dump():

object(MyContainer) (2) {
  ["86reified_prop"]=>
  vec(1) {
    dict(1) {
      ["kind"]=>
      int(4)
    }
  }
  ["var":"MyContainer":private]=>
  string(5) "hello"
}

The example above describes the MyContainer class and the kind property.
I think kind => 4 is a constant for type string.
It means you can get the generics type at runtime.

This approach has a small performance/memory effect.
Nikita Popov already had an attempt to implement this type of generics in PHP.

Reified generics visibility table:

	static analysis time	compile time	runtime
type reflection	yes	yes	yes
type checking	yes	yes	yes

Monomorphization

A new class is generated for each generic argument combination.

Before monomorphization:

<?php

class Container<T> {

    private T $data; 

    public function __construct(T $data) {
        $this->data = $data;
    }  
}

$intContainer = new Container<int>(1);

After monomorphization:

<?php

class ContainerForInt {

    private int $data; 

    public function __construct(int $data) {
        $this->data = $data;
    }  
}

$intContainer = new ContainerForInt(1);

This approach has a big memory effect.
PHP doesn't support native generics, but you can test monomorphic generics with my library.

Monomorphic generics visibility table:

	static analysis time	compilation time	run time
type reflection	yes	yes	no
type checking	yes	yes	yes

C++ templates are a real example of monomorphization:

test.cpp

template <class T> class MyContainer
{
    private:
     T data;

    public:
     void set(T _data)  {
        data = _data;
     }
};

int main () {
  MyContainer<int> intContainer;
  intContainer.set(1);

  MyContainer<const char*> stringContainer;
  stringContainer.set("hello");

  return 0;
}

You can compile and run the script above with commands:

docker run -it --rm -v $PWD:/app -w /app gcc:latest g++ test.cpp -o test
docker run -it --rm -v $PWD:/app -w /app gcc:latest ./test

If you try to pass string "hello" to intContainer.set() you will get a compile time error:

test.cpp: In function 'int main()':
test.cpp:15:20: error: invalid conversion from 'const char*' to 'int' [-fpermissive]
   15 |   intContainer.set("hello");
      |                    ^~~~~~~
      |                    |
      |                    const char*
test.cpp:8:17: note:   initializing argument 1 of 'void MyContainer<T>::set(T) [with T = int]'
    8 |      void set(T _data) {
      |               ~~^~~~~

This approach increases compile time, but improves performance runtime.

I hope it was helpful to you.
Play around with the examples above - it's a really interesting process!
If you want to go further, read this great article about generics.

Have a nice day!