Quelques rappels

Qu'est-ce qu'un langage ?

Un langage est un ensemble de mots dont les enchainements respectent une structure. Chaque mot est une séquence de symboles appartenant à un alphabet.

Qu'est-ce qu'un langage ?

Autrement dit : langage = notation conventionnelle destinée à formuler des idées.

Classes de langages/grammaires

• Grammaires régulières : expressions régulières
• Grammaires non-contextuelles (algébriques) : la plupart des langages de programmation

Lien entre langage et grammaire

• Ensemble de conventions ⇒ grammaire
• Convention ⇒ règle
• Mot ⇒ lexème/token

Let's write our own SQL parser!

SQL?

Yeah, sure.

Our SQL

SELECT name FROM person
SELECT name, age FROM person
SELECT p.name, age FROM person AS p
SELECT p.name, age, j.title AS job FROM person AS p, job j

Tokens

// keywords
%token select       SELECT
%token from         FROM
%token as           AS

// identifiers
%token identifier   [a-zA-Z][a-zA-Z0-9_]*

// rest
%token comma        ,
%token dot          .

Rules

#TableIdentifier:
    <identifier> (::as::? <identifier>)?
#ColumnIdentifier:
        <identifier>
    |   TableIdentifier() ::dot:: <identifier>

#SelectExpression:
    ColumnIdentifier() (::as::? <identifier>)?

#SelectClause:
    ::select:: SelectExpression() (::comma:: SelectExpression())*

#FromClause:
    ::from:: TableIdentifier() (::comma:: TableIdentifier())*

#SelectQuery:
    SelectClause() FromClause()

Hoa\Compiler \o/

SELECT name, age FROM person

 # namespace     token name           token value  offset
----------------------------------------------------------
 0 default       select               SELECT        0
 1 default       identifier           name          7
 2 default       comma                ,            11
 3 default       identifier           age          13
 4 default       from                 FROM         17
 5 default       identifier           person       22
 6 default       EOF                               28

>  #SelectQuery
>  >  #SelectClause
>  >  >  #SelectExpression
>  >  >  >  #ColumnIdentifier
>  >  >  >  >  token(identifier, name)
>  >  >  #SelectExpression
>  >  >  >  #ColumnIdentifier
>  >  >  >  >  token(identifier, age)
>  >  #FromClause
>  >  >  #TableIdentifier
>  >  >  >  token(identifier, person)

Utilisation de l'AST

class PrettyPrinter implements Hoa\Visitor\Visit {
  public function visit(Hoa\Visitor\Element $element, &$handle = null, $eldnah = null) {
    switch ($element->getId()) {
      case '#SelectClause':
        $selectedExpressions = array();
        foreach ($element->getChildren() as $child)
          $selectedExpressions[] = $child->accept($this, $handle, $eldnah);
        return 'SELECT ' . implode(', ', $selectedExpressions);
      case '#FromClause':
        $tables = array();
        foreach ($element->getChildren() as $child)
          $tables[] = $child->accept($this, $handle, $eldnah);
        return "\n" . 'FROM '. implode(', ', $tables);
      // ...
    }
  }
}

Bonus

Génération automatique

$sampler = new Hoa\Compiler\Llk\Sampler\Coverage(
    // Grammar.
    Hoa\Compiler\Llk\Llk::load(new Hoa\File\Read('sql_sample.pp')),
    // Token sampler.
    new Hoa\Regex\Visitor\Isotropic(new Hoa\Math\Sampler\Random()),
    // Length.
    6
);

foreach ($sampler as $i => $data)
    echo $i, ' => ', $data, "\n";

0 => SELECT v28__ AS Js32_B0 , w FROM T4 AS FO4Z0_ , y__ b3x_n , t3
1 => SELECT wZ_ AS i0E_6 , Od , zl82Q_ FROM e_bNTB AS I8_d___u , X AS yl2
2 => SELECT lBp FROM xV_v93Y AS j2a4991_

Technique utilisée dans le cadre du Grammar-Based testing