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 toskeletonfile -
-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:
Top comments (0)