Syntaxe

Grammaire

1. Un ensemble de symboles dits terminaux. Ces symboles représentent les unités lexicales du langage. En Basic, on y trouve les symboles opérateurs et de relations arithmétiques et logiques (+, &, <, <=, ..) ; les mots clés du langage (GOTO, PRINT, IF, THEN, ..) ; les entiers (unité entier) et les variables (unité variable).
2. Un ensemble de symboles dits non terminaux. Ces symboles représentent les composantes syntaxique du langage. Par exemple, un programme Basic est composé de lignes, on a donc la composante Ligne ; une ligne peut contenir une Expression, etc.
3. Un ensemble de règles dites de production. Elles décrivent comment s'articulent les symboles terminaux et ceux non terminaux pour produire une composante syntaxique. Une ligne en Basic, est formée de son numéro suivi d'une instruction. C'est le sens de la règle suivante :

   Ligne

   ::=

   entier Instruction

   Une même composante peut être produite de plusieurs façons. On sépare les alternatives par le symbole | comme dans

   Instruction	::=	LET variable = Expression
   	|	GOTO entier
   	|	PRINT Expression
   etc.

4. Enfin, parmi tous les non terminaux, on en distingue un que l'on appelle axiome. C'est sa règle de production qui dénote la règle de production du langage dans son entier.

Production et reconnaissance

Analyse descendante

Le cas simple

# let lexer s =
   let ll = Genlex.make_lexer ["+";"*"] 
   in  ll (Stream.of_string s) ;;
val lexer : string -> Genlex.token Stream.t = <fun>
# let rec stream_parse s = 
   match s with parser
     [<'Genlex.Ident x>] -> x
   | [<'Genlex.Int n>] -> string_of_int n
   | [<'Genlex.Kwd "+"; e1=stream_parse; e2=stream_parse>] -> "("^e1^"+"^e2^")"
   | [<'Genlex.Kwd "*"; e1=stream_parse; e2=stream_parse>] -> "("^e1^"*"^e2^")"
   | [<>] -> failwith "Parse error"
 ;;
val stream_parse : Genlex.token Stream.t -> string = <fun>
# let infix_of s = stream_parse (lexer s) ;; 
val infix_of : string -> string = <fun>
# infix_of "* +3 11 22";;
- : string = "((3+11)*22)"

# infix_of "*+3 11 22";;
- : string = "*+"

Un cas moins simple

1. Il ne doit pas y avoir de récursivité gauche dans les règles de grammaire. Une règle est récursive à gauche lorsque que le membre droit commence par le non-terminal qui est le membre gauche de la règle, comme dans Exp ::= Exp + Exp ;
2. Il ne doit pas y avoir deux règles commençant par la même expression.

# let rec suite = parser 
     [< 'Lsymbol "+"; e2 = atom >]  -> Some (PLUS,e2)
   | [< 'Lsymbol "-"; e2 = atom >]  -> Some (MOINS,e2)
   | [< 'Lsymbol "*"; e2 = atom >]  -> Some (MULT,e2)
   | [< 'Lsymbol "/"; e2 = atom >]  -> Some (DIV,e2)
   | [< >] -> None
 and atom = parser 
     [< 'Lint i >] -> ExpInt i
   | [< 'Lsymbol "("; e = expr ; 'Lsymbol ")" >] -> e
 and expr s =
   match s with parser
     [< e1 = atom >] ->  
       match suite s with
           None -> e1
         | Some (op,e2) -> ExpBin(e1,op,e2) ;;
val suite : lexeme Stream.t -> (op_bin * expression) option = <fun>
val atom : lexeme Stream.t -> expression = <fun>
val expr : lexeme Stream.t -> expression = <fun>

Analyse ascendante

Pour le meilleur

---

Action	Entrée	Pile
	12+3*4+$	[]
Avancer
	2+3*4+$	[1]
Réduire (R1)
	2+3*4+$	[Expr]
Avancer
	+3*4+$	[2Expr]
Réduire (R1)
	+3*4+$	[Expr Expr]
Avancer, Réduire (R2)
	3*4+$	[Expr]
Avancer, Réduire (R1)
	*4+$	[Expr Expr]
Avancer, Réduire (R3)
	4+$	[Expr]
Avancer, Réduire (R1)
	+$	[Expr Expr]
Avancer, Réduire (R2)
	$	[Expr]

Figure 11.2 : Exemple d'analyse ascendante

---

Pour le pire

L'outil ocamlyacc

Format général

Actions sémantiques

Axiomes

 %start non-terminal .. non-terminal

 %type <type-retour> non-terminal

Warning

Unités lexicales

 %token PLUS MOINS MULT DIV MOD

 %token <string> IDENT

Warning

expr : expr "+" expr   { ... }
     | expr "*" expr   { ... }
     | ...             
     ;

Priorité, associativité

 %left PLUS
 %left MULT

Options de la commande

• -b nom : les fichiers Objective CAML engendrés sont nom.ml et nom.mli;
• -v : crée un fichier d'extension .output contenant la numérotation des règles, les états de l'automate reconnaissant la grammaire et les sources de conflits.

Utilisation conjointe avec ocamllex

Grammaires contextuelles

# type token = A | B | C ;;

# let rec parse_w1 s =
   match s with parser
     [<'A; l = parse_w1  >] -> (parser [<'A >] -> "a")::l
   | [<'B; l = parse_w1  >] -> (parser [<'B >] -> "b")::l
   | [< >] -> [] ;;
val parse_w1 : token Stream.t -> (token Stream.t -> string) list = <fun>

# let rec parse_w2 l =
   match l with
     p::pl -> (parser [< x = p; l = (parse_w2 pl)  >] -> x^l)
   | [] -> parser [<>] -> "" ;;
val parse_w2 : ('a Stream.t -> string) list -> 'a Stream.t -> string = <fun>

# let parse_L = parser  [< l = parse_w1 ; 'C; r = (parse_w2 l) >] -> r ;;
val parse_L : token Stream.t -> string = <fun>

# parse_L [< 'A; 'B; 'B; 'C; 'A; 'B; 'B >];;
- : string = "abb"
# parse_L [< 'A; 'B; 'C; 'B; 'A >];;
Uncaught exception: Stream.Error("")