Grammaire G0 | ||
---|---|---|
E | → | E+T | T |
T | → | T*F | F |
F | → | (E) | id | cte |
Cette grammaire est récursive à gauche. Pour la dérécursiver, nous observons que
Ainsi, on redéfinit
Pour mémoire, les conventions de la notation BNF incluent:
{ … } | 0 à n fois successives |
[ … ] | 0 ou 1 fois |
( … ) | groupe d'options |
| | ou |
On écrira cette grammaire sous la forme BNF, qui est utilisé pour l'analyseur (yacc/bison) :
Notre grammaire dérécursivée sera exprimée : E:: T({+T} | e) ??
Dans l'analyseur, l'on écrit une fonction par règle : que faire pour prendre en compte chaque lecture d'UL. Ainsi, nous aurons des fonctions read_E(), read_T(), read_F(), read_id(), read_cte(), qui détecte d'éventuelles erreurs et construisent
expr read_E(){ expr result, other; result = read_T(); if (result!=NULL){ while (read_char('+') ){ other = read_T(); if (other==NULL) error(1); result = new Add(result,other); } } return result; }
expr read_T(){ expr result, other; result = read_F(); if (result!=NULL) { while (read_char('*')){ other = read_F(); if (other==NULL) error(1); result = new Mult(result, other); } } return result; } expr read_F(){ expr result; if (read_char('(')){ result = read_E(); if (result==NULL) error(1); if (!read_char(')')) error; } else if (read_id()) result = new Id(last_id); else if (read_cte()) result = new Cte(last_int); return result; }
read_char()
est une fonction booléenne qui consomme un caractère de yylex() et le compare à son argument.read_id()
lit l'UL suivante et, s'il s'agit bien d'un identifiant, il l'ajout à une table de strings (var globale), augmente le compteur de strings last_id, et répond True
; répond False
sinon.read_cte()
lit l'UL suivante et, s'il s'agit bien d'un integer, il l'ajout à une table (ou liste) de integers (var globale), augmente le compteur de integers last_integer, et répond True
; répond False
sinon.typedef expr
ni le fonctionnement de new Id(last_id)
et new Cte(last_int)
.Construire un analyseur LL(1) pour des structures de contrôle d'un pseudo Pascal de la formeif … then …endif
,if…then…else…endif
,while…do…endot
, etid = E
, dans lesquelles une liste d'instructions est composée d'instructions séparées par un point-virgule. Pour ne pas surcharger la grammaire, on considère dans la suite que les symboles E pour les expressions arithmétiques et C pour les expressions conditionnelles sont des symboles terminaux.
I → “if” C “then” B “endif” |
B → id = E | I | J | W |
J → “if” C “then” B “else” B “endif” |
W → “while” C “do” B “endo” |
E -> E u T | T T -> TF | F F -> G'*' | G G -> (E) | 'a' | 'b' | 'c'
Règle | Production |
---|---|
1 | E → T E' |
2 | E' → u T E' |
3 | E' → e |
4 | T → F T' |
5 | T' → F T' |
6 | T' → e |
7 | F → G F' |
8 | F' → '*' |
9 | F' → e |
10 | G → (E) |
11 | G → a |
12 | G → b |
13 | G → c |
De là nous construisons les First et Follow :
X | First(X) | Follow(X) | Explication |
---|---|---|---|
E | { (, a, b, c } | { $, ) } | |
E' | { u, e } | {$, ) } | |
T | { (, a, b, c } | { u, $, ) } | First(E')+Follow(E) |
T' | { (, a, b, c } | { u, $, ) } | Follow(T) |
F | { (, a, b, c } | { (, a, b, c, u, $ } | First(T') & ? |
F' | { *, e } | { (, a, b, c, u, $, ) } | |
G | { (, a, b, c } | { *, (, a, b, c, u, $ ) } |