Majeure 2
Langages et Compilation
Cours 3


Grammaires contex-free

jean-jacques.levy@inria.fr

2 février 1998

Les supports de cours sont en

http://www.polytechnique.fr/poly/edu/informatique/
http://www.polytechnique.fr/poly/~levy/

Livres:

Introduction

Expressions régulières dans Unix

awk, sed, ed, grep, sh
ont des expressions régulières dans leurs arguments. Pour le shell,

* répétition quelconque de caractères
? tout caractère
[az] union des caractères a ou b
[a-p] tous les caractères entre a et p

Exemples:

% ls *.c
% ls *[ab][0-2]*.ml
% ls ?emacs?
Expressions régulières dans sed

En sed, une expression e régulière est:

c caractère quelconque à matcher
^ au début pour le caractère nul début de ligne
$ à la fin pour le caractère nul fin de ligne
. pour tout caractère sauf le newline du bout
e'* pour répéter l'expression e'
[s] pour matcher tout caractère de la chaîne s
[^s] pour matcher tout caractère pas dans la chaîne s
e'e''  

Exemples:

% sed -e 's/aa*/a/g'
% sed -e '/Ca[^m]*ml/d'

Expression régulières dans awk

Interpréteur C guidé par des expressions régulières. Un programme est une suite de paires (expression régulière, programme C):

pattern1 {action1}
pattern2 {action2}
etc

Deux motifs spéciaux: BEGIN et END pour désigner le début et la fin du fichier.

En outre, la ligne est délimitée en plusieurs champs par \t (ou autre caractère donné en option), et les actions peuvent manipuler les champs par $1, $2, etc. Il y a aussi des tableaux associatifs accessibles par le contenu.

Awk >> Excel.

Exemple de programme Awk

awk -F: 'BEGIN { 
         code["Prog. L"] = "BD";  
         code["BdD"] = "CP";  
         code["Cal. Par."] = "PL";  
         code["Algo NP"] = "AP";  
      } {if (NF >= 13){
    num = $1; cie = $2; unknown = $8;
    nom = $3; prenom = $4; nom = nom "(" prenom ")";
    cp = $5; voie = $6; svoie = $7;
    maj1 = $9; maj2 = "info";
    choix1 = code[$11]; 
    choix2 = code[$12]; 
    choix3 = code[$13];
    printf ( "%-23s: %-11s:    %s: %s: %s: \n", \
              nom, \
                         maj1, \
                            choix1, \
                                choix2, \
                                   choix3);
     };}' maj2.txt

Expressions régulières en Perl

Perl est un shell avec des sous-programmes. Il a des tableaux associatifs et des expressions régulières (comme awk) qui peuvent intervenir dans les conditions booléennes, grâce à 2 opérateurs: m// pour matcher une expression, ou s// idem avec remplacement.

Perl n'est pas typé.

Perl est très utilisé dans les cgi-bin qui sont les programmes appelés par le Web pour les formulaires, etc.

Analyseurs lexicaux

Un compilateur commence par transformer le flux de caractères d'entrée en une suite d'entités plus abstraites: les lexèmes. Typiquement, il saute les blancs, les tabulations, les newline, et les commentaires. Les lexèmes sont par exemple les

identificateurs,
nombres,
chaînes de caractères,
opérateurs

Analyseurs lexicaux (2)

Chaque lexème a sa syntaxe donnée par une expression régulière:

identificateur = lettre (lettre ou chiffre)*
nombre = chiffre (chiffre)*
chaîne = "(caractère autre que ")*"
opérateur = symbole non alphanumérique

Il suffit donc d'un automate fini pour faire l'Analyse lexicale. Comment construire cet automate?

Lex

Lex (Lesk et Schmidt) est un utilitaire Unix qui prend des expressions régulières en entrée et qui produit les tables d'un automate fini déterministe qui reconnait le langage correspondant.

Un programme Lex a la forme suivante:

définitions
%%
pattern1 action1
pattern2 action2
...
%%
programmes de l'utilisateur

Lexer pour bc  levy/m2/bc/scan.l

%{
#include "bcdefs.h"
#include "y.tab.h"
#include "global.h"
#include "proto.h"
%}

DIGIT [0-9A-F]
LETTER [a-z]
%%
scale  return(Scale);
ibase  return(Ibase);
obase  return(Obase);
"+"|"-"|";"|"("|")"|"{"|"}"|"["|"]"|","|"^" { 
        yylval.c_value = yytext[0]; return((int)yytext[0]); }
&&    { return(AND); }
\|\|  { return(OR); }
"!"   { return(NOT); }
"*"|"/"|"%" { yylval.c_value = yytext[0]; return(MUL_OP); }
"="|\+=|-=|\*=|\/=|%=|\^=  {
        yylval.c_value = yytext[0]; return(ASSIGN_OP); }
=\+|=-|=\*|=\/|=%|=\^  { yylval.c_value = '='; yyless (1);
        return(ASSIGN_OP); }
[ \t]+ { /* ignore spaces and tabs */ }
[a-z][a-z0-9_]* { 
        yylval.s_value = strcopyof(yytext); return(NAME); }
\"[^\"]*\"  {
        char *look;
        yylval.s_value = strcopyof(yytext);
        for (look = yytext; *look != 0; look++)
            if (*look == '\n') line_no++;
        return(STRING);
        }
{DIGIT}({DIGIT}|\\\n)*
   ("."({DIGIT}|\\\n)*)?|"."(\\\n)*{DIGIT}({DIGIT}|\\\n)* {
...
            }
.       yyerror ("illegal character: %s",yytext);
%%

Camllex

La structure d'un lexer est identique à celle demandée par Lex.

{ header }
rule entrypoint =
  parse pattern_1 { action_1 }
      | ...
      | pattern_n { action_n }
and entrypoint =
  parse ...
and ...
;;

Quelques exemples de grammaires context-free

Grammaires contex-free

Ce sont les grammaires de type 2, dont les règles sont toutes de la forme $A \rightarrow\alpha$$\alpha \in V^*$, $V = \Sigma \cup V_N$.














Arbre syntaxique

Arbre dont la racine est étiqueté par l'axiome de la grammaire, les noeuds par des non-terminales et les feuilles par des terminales. Si $A \rightarrow\alpha$ est une règle de la grammaire, alors les lettres de $\alpha$ peuvent étiqueter les fils (dans l'ordre) des noeuds de A.

Tout mot w est accepté par la grammaire ssi il existe un arbre syntaxique dont les feuilles forment w. On vérifie facilement que cette condition équivaut à dire qu'il existe une dérivation à partir de l'axiome.

Plusieurs dérivations peuvent correspondre à un même arbre (qui représente en fait une classe de permutation de dérivations produisant une chaîne donnée).

Grammaires ambigues

Plusieurs arbres syntaxiques peuvent aboutir à la même chaîne. On dit alors que la grammaire est ambigue. Par exemple:

$S \rightarrow if \;\; C \;\; then \;\; S$
$S \rightarrow if\;\; C \;\; then \;\; S \;\;else \;\; S$

Si on considère le mot

$if\;\; C \;\; then\;\; S \;\; if \;\; C' \;\; then \;\; S' \;\; else \;\; S''$

a deux arbres syntaxiques différents.

L'exemple des expressions arithmétiques

$\begin{array}
{l@{\hspace{2em}}l@{\hspace{2em}}l}
E \rightarrow E + P & E \righ...
 ...arrow T \\ T \rightarrow id & T \rightarrow nb & T \rightarrow( E ) \end{array}$

L'arbre syntaxique de a * (b +1 ) est:












Syntaxe abstraite

L'arbre de syntaxe abstraite est un arbre d'opérateurs qui ne contient plus que la sémantique de l'expression. Pour a * (b +1 ) c'est:










Pratiquement tous les compilateurs construisent cet arbre avant de générer du code. Il permet de construire des interpréteurs et de faire les différentes analyses.

Yacc

Yacc (Johnson) est un utilitaire Unix qui prend des grammaires en entrée et qui produit les tables d'un analyseur syntaxique qui reconnait le langage correspondant.

Un programme Yacc a la forme suivante:

déclarations
%%
règle1 règle2 ...
%%
programmes de l'utilisateur

Parser pour bc  levy/m2/bc/scan.y

%{
#include "bcdefs.h"
#include "global.h"
#include "proto.h"
%}

%start program

%union {
        char     *s_value;
        char      c_value;
        int       i_value;
        arg_list *a_value;
       }
%token <i_value> NEWLINE AND OR NOT
%token <s_value> STRING NAME NUMBER
...
/* Types of all other things. */
%type <i_value> expression return_expression ...
%type <c_value> '+' '-' 
...
/* precedence */
%left OR
%left AND
%nonassoc NOT
...
%%
program      : ...
expression   :
               expression '+' expression
                 {
                   generate ("+");
                   $$ = $1 | $3;
                 }
               NUMBER
                 {
                   int len = strlen($1);
                   $$ = 1;
                   if (len == 1 && *$1 == '0')
                     generate ("0");
                   else if (len == 1 && *$1 == '1')
                     generate ("1");
                   else
                     {
                       generate ("K");
                       generate ($1);
                       generate (":");
                     }
                   free ($1);
                 }
               '(' expression ')'
                 { $$ = $2 | 1; }
...

Camlyacc

/* File parser.mly */
%token <int> INT
%token PLUS MINUS TIMES DIV
%token LPAREN RPAREN
%token EOL
%left PLUS MINUS        /* lowest precedence */
%left TIMES DIV         /* medium precedence */
%nonassoc UMINUS        /* highest precedence */
%start Main             /* the entry point */
%type <int> Main
%%
Main:
    Expr EOL                { $1 }
;
Expr:
    INT                     { $1 }
  | LPAREN Expr RPAREN      { $2 }
  | Expr PLUS Expr          { $1 + $3 }
  | Expr MINUS Expr         { $1 - $3 }
  | Expr TIMES Expr         { $1 * $3 }
  | Expr DIV Expr           { $1 / $3 }
  | MINUS Expr %prec UMINUS { - $2 }
;

Lexer correspondant

(* File lexer.mll *)
{
#open "parser";;(* The type token is defined in parser.mli *)
exception Eof;;
}
rule Token = parse
    [` ` `\t`]     { Token lexbuf }     (* skip blanks *)
  | [`\n` ]        { EOL }
  | [`0`-`9`]+     { INT(int_of_string (get_lexeme lexbuf)) }
  | `+`            { PLUS }
  | `-`            { MINUS }
  | `*`            { TIMES }
  | `/`            { DIV }
  | `(`            { LPAREN }
  | `)`            { RPAREN }
  | eof            { raise Eof }
;;
Programme principal

(* File calc.ml *)
try
  let lexbuf = lexing__create_lexer_channel std_in in
  while true do
    let result = parser__Main lexer__Token lexbuf in
      print_int result; print_newline(); flush std_out
  done
with Eof ->
  ()
;;

On compile le tout en tapant les ordres suivants au niveau shell.

camllex lexer.mll       # generates lexer.ml
camlyacc parser.mly     # generates parser.ml and parser.mli
camlc -c parser.mli
camlc -c lexer.ml
camlc -c parser.ml
camlc -c calc.ml
camlc -o calc lexer.zo parser.zo calc.zo
Les modules Camllex et Camlyacc

Dans l'exemple précédent:

lexing__create_lexer_channel crée un canal d'entrée attaché à stdin, sur le lexer lexer__Token décrit en camllex pourra fonctionner.

Le lexer retourne les valeurs EOL, INT, PLUS, etc qui sont les constructeurs d'un type token généré par camlyacc dans l'interface parser.mli. INT est un constructeur unaire qui prend un entier en argument.

En yacc, des expressions Caml sont attachées à chaque règle, et retournées comme valeur de la non-terminale membre gauche de la règle. Les valeurs associés aux lettres des parties droites sont notées $1, $2, etc en fonction de leur ordre d'apparition.

Formes normales de grammaires

Prop 1 Soit $G = (\Sigma, V_N, S, \mathcal{P})$ générant un langage non vide. Alors on peut trouver une grammaire équivalente G1 telle que pour toute non-terminale A de G1, il existe $w
\in \Sigma^*$ tel que $A \Rightarrow^* w$.

Prop 2 Soit L un langage context-free. Alors il existe une grammaire G générant L telle que pour toute non-terminale A de G, il existe une dérivation $S \Rightarrow^* w_1 A w_2 \Rightarrow^* w_1 w_2 w_3$w1, w2, w3 sont des chaines terminales.

Prop 3 Soit G une grammaire context-free. Si $G \Rightarrow^* w$,alors il existe une dérivation gauche (ie dérivant la non-terminale toujours la plus à gauche) donnant w.

Formes normales de grammaires (2)

Prop 4 Soit G une grammaire context-free, on peut trouver une grammaire équivalente sans aucune règle de la forme $A \rightarrow B$, où A et B sont deux non-terminales.

Forme normale de Chomsky Tout langage context-free peut être généré par une grammaire dont toutes les règles sont de la forme $A \rightarrow BC$ ou $A \rightarrow a$A, B sont non-terminales, et a est terminale.

Prop 5 Appelons A-règle toute règle dont A est le membre gauche. Si $A \rightarrow\alpha_1 B \alpha_2$ est une A-règle et $\{B \rightarrow
\beta_1, \cdots, B \rightarrow\beta_r\}$ est l'ensemble des B-règles. Alors la grammaire G1 obtenue en remplaçant la règle $A \rightarrow\alpha_1 B \alpha_2$ par $A \rightarrow\alpha_1 \beta_1 \alpha_2,
\cdots A \rightarrow\alpha_1 \beta_r \alpha_2$ est équivalente.

Formes normales de grammaires (3)

Prop 4 Soit G une grammaire context-free Soit $\{ A \rightarrow
A\alpha_1, \cdots A\alpha_r \}$ l'ensemble des A-règles dont A est le symbole le plus à gauche. Soit $A \rightarrow\beta_1$, $\cdots$ $A \rightarrow
\beta_s$ l'ensemble des A-règles restantes. Alors on peut trouver une grammaire équivalente, dont toutes les A-règles sont de la forme $A \rightarrow\beta_i$, $A \rightarrow\beta_i Z$, $Z \rightarrow\alpha_i$, $Z \rightarrow
\alpha_i Z$Z est un nouveau symbole non terminal.

Forme normale de Greibach Toute langage context-free peut être généré par une grammaire dont toute les règles sont de la forme $A \rightarrow a \alpha$a est une terminale et $\alpha \in V^*$, $V = \Sigma \cup V_N$.

Lemme de l'étoile pour les langages réguliers

Théorème Soit L un langage régulier. Il existe p ne dépendant que de L tel que pour tout mot z de L dont la longueur |z| excède p, il existe une décomposition z = uvw
avec $\vert v\vert \leq p$, $\vert v\vert \neq 0$, et pour tout n, uvnw est dans L.


Exercice Montrer que le langage suivants n'est pas régulier

$L_0 = \{a^n b^n \}$

Lemme de la pompe pour les langages context-free

Théorème Soit L un langage context-free. Il existe p et q dépendant de L tel que pour tout mot z de L dont la longueur |z| excède p, il existe une décomposition z = uvwxy
avec $\vert vwx\vert \leq q$, $\vert vx\vert \neq 0$, et pour tout n, uvnwxny est dans L.


Exercice Montrer que les langages suivants ne sont pas context-free

$L_1 = \{a^n b^n c^n \}$
$L_2 = \{ww \}$
$L_2 = \{a^n \mid n \; \mbox{premier} \}$

Montrer que tout langage context-free sur un alphabet à une lettre est régulier.

Exercices



2/1/1998