lex/yach - Page 1

Heu est il plus avantageux de dériver a gauche ou à droite? perso j'ai tout mis en derivation a droite quand je le pouvais (parce qu'en C/C++ quand on derive en fin de fonction c toujours plus optimisé), mais la je sais pas si je fais pas une boulette...

qqn connait un peu ces outils?

L'un des deux sens est catastrophique en performances et en occupation mémoire.
Me rappelle plus lequel.

je sais plus exactement ce que t'appelles dérivation a gauche / a droite, mais ca parait logique que :
L := plouf | (plop . M) | ...
soit bcp plus facile a parser [enfin, sauf qd on va de droite a gauche ] que
L := plouf | (M . plop) | ...
(la premiere c la dérivation a droite ?)

Apparement c'est une analyser LR (yacc & bison):
Analyseurs LR(k)...
■Definition
■Analyseur syntaxique ascendant
■L : Left To Right Scanning
■R : Rightmost derivation
■k : k symboles de prévision

donc il vaut mieux dériver à droite.
J'entend par dérivation:
Liste:
int Var Liste
| Var;

voilou si qqn peut confirmer

enfin c'est un LALR...

bon apparement j'ai tout faux
2.2 Optimisation de la récursivité
On reprend la grammaire de l’exercice précédent et on modifie les deux premières règles de la
grammaire comme ci-dessous :
S → AB
A → ABa | ε
On teste ensuite l’analyseur avec l’exemple bababcabd. Après avoir également reconstruit la
trace de l’analyse effectuée, on peut ensuite les comparer et comprendre pourquoi la récursivité à
gauche est préférable avec un analyseur comme Yacc

je viens de retrouver mon cours, ca aide

3.3.2 Analyse LR(k)
Il est possible, malgr ́e les apparences, de construire des analyseurs ascendants plus efficaces que les analyseurs
descendants, et acceptant une classe de langages plus large que la classe des langages trait ́es par ces derniers.
Le principal inconv ́enient de ces analyseurs est qu’ils n ́ecessitent des tables qu’il est extrˆemement difficile
de construire `a la main. Heureusement, des outils existent pour les construire automatiquement, `a partir de la
grammaire du langage ; la section 3.4 pr ́esente yacc, un des plus connus de ces outils.
Les analyseurs LR(k) lisent la chaˆıne d’entr ́ee de la gauche vers la droite (d’o`u le L), en construisant
l’inverse d’une d ́erivation droite (d’o`u le R) avec une vue sur la chaˆıne d’entr ́ee large de k symboles ; lorsqu’on
dit simplement LR on sous-entend k = 1, c’est le cas le plus fr ́equent.
Etant donn ́ee une grammaire G = (VT , VN , S0 , P ), un analyseur LR est constitu ́e par la donn ́ee d’un ensemble
d’ ́etats E, d’une fenˆetre `a symboles terminaux (c’est-`a-dire un analyseur lexical), d’une pile de doublets (s, e)
o`u s
∈ E et e ∈ VT et de deux tables Action et S uivant, qui repr ́esentent des fonctions :
Action : E
× VT → ({ decaler } × E) ∪ ({reduire} × P ) ∪ { succes, erreur }
S uivant : E
× VN → E

Tu confondais analyse ascendante/descendante et analyse de droite à gauche / de gauche à droite ?