Algorithmes d'analyse syntaxique - Historique des versions

Porteries le 27 mai 2018 à 09:12

2018-05-27T09:12:28Z

@@ Ligne 485 : / Ligne 485 : @@
 Pour mettre en application les algorithmes d'analyse syntaxique, un programme à été écrit avec le support de l'analyse descendante et ascendante simple.
-Ce programme est disponible dans le dépot : https://github.com/panzergame/analyseur_cmi
+Ce programme est disponible dans le dépôt : https://github.com/panzergame/analyseur_cmi
 Un fois compilé, l'exécutable build/analyzer prend quatre arguments :
@@ Ligne 494 : / Ligne 494 : @@
 		<li>regex_file : Fichier de description des règles lexicales et des séparateurs.</li>
 		<li>method : La méthode d'analyse, naive pour LL récursif, stack pour LL avec pile et slr pour SLR.</li>
-		<li>Résultat~: un historique de l'analyse en console et un arbre de dérivation au format .dot : derivation_tree.dot.</li>
+		<li>Résultat : un historique de l'analyse en console et un arbre de dérivation au format .dot : derivation_tree.dot.</li>
 </ul>

Porteries le 27 mai 2018 à 08:56

2018-05-27T08:56:13Z

Voir les modifications

Porteries le 26 mai 2018 à 17:45

2018-05-26T17:45:47Z

@@ Ligne 207 : / Ligne 207 : @@
 Dans le cas contraire non-deterministe, l'algorithme pourrait autoriser de revenir en arrière dans l'analyse lors d'erreur et d'appliquer les productions restantes jusqu'à ne plus avoir de production et donc signaler une véritable erreur.
-==== Analyseur à symbole de prévision ====
+==== Les analyseurs à symbole de prévision ====
 Un analyseur à symbole de prévision, nommé LL(k) ou k est le nombre de symboles, lors d'une dérivation va lire k symboles au début de la chaine d'entrée pour déterminer la production à dériver contenant ces k symboles en préfixe. La plupart des analyseurs se contentent de 1 symbole de prévision.
@@ Ligne 355 : / Ligne 355 : @@
 Les réductions valide sont nommées manche, ils dépendent de l'état de la pile.
-==== Table d'analyse ====
+==== Les tables d'analyse ====
 La table d'analyse représente les différents états de l'automate à pile formant l'analyseur, ces états sont calculé en se basant sur la notion d'item de production.
@@ Ligne 417 : / Ligne 417 : @@
 </ul>

Porteries le 24 mai 2018 à 17:26

2018-05-24T17:26:46Z

@@ Ligne 377 : / Ligne 377 : @@
 <math>Fermeture(X)</math> prend en argument un ensemble d'item.
-Soit un item <math>N \rightarrow \alpha\gamma</math>, si <math>\alpha</math> est un terminal alors ajouter cet item dans le résultat, sinon si <math>\alpha</math> est un non-terminal alors ajouter au résultat <math>Fermeture(Y)</math> où <math>Y</math> et l'ensemble de toutes les items des productions de <math>\alpha</math> avec le point en première position : <math>\{\alpha \rightarrow \bullet \beta, \alpha \rightarrow \bullet \delta, ...\}</math>
+Soit un item <math>N \rightarrow \gamma \bullet \alpha</math> de <math>X</math>, si <math>\alpha</math> est un terminal alors ajouter cet item dans le résultat, sinon si <math>\alpha</math> est un non-terminal alors concaténer au résultat <math>Fermeture(Y)</math> où <math>Y</math> et l'ensemble de toutes les items des productions de <math>\alpha</math> avec le point en première position : <math>\{\alpha \rightarrow \bullet \beta, \alpha \rightarrow \bullet \delta, ...\}</math>
 === Arbre abstrait de syntaxe ===

Porteries le 24 mai 2018 à 16:57

2018-05-24T16:57:24Z

Voir les modifications

Porteries le 23 mai 2018 à 12:42

2018-05-23T12:42:26Z

@@ Ligne 248 : / Ligne 248 : @@
 |-
 ! Non-terminal
 ! Production
 |-
@@ Ligne 282 : / Ligne 282 : @@
 Le non-terminal associé à la production <math>decl' \rightarrow \epsilon </math> et utilisé seulement dans <math>decl \rightarrow type\,id\,decl'\,;</math> et le symbole suivant <math>delc'</math> est ";". <math>decl' \rightarrow \epsilon </math> et donc associé à ";" dans la table comme pour la grammaire précédente sans productions utilisant <math>\epsilon</math>.
 === Les analyseurs ascendants ===

Porteries le 23 mai 2018 à 12:40

2018-05-23T12:40:11Z

Voir les modifications

Porteries le 17 mai 2018 à 09:13

2018-05-17T09:13:33Z

@@ Ligne 30 : / Ligne 30 : @@
 Le niveau le plus faible est attribué aux grammaires régulières. Ces grammaires sont d'une forme linéaire, chaque non-terminal peut être associé à une composition de terminaux et un non-terminal en préfixe ou suffixe seulement.
 Les grammaires algébrique (ou non-contextuelles) offrent une plus grande liberté en autorisant d'associer à un non-terminal n'importe quelle combinaison de terminaux et non-terminaux.
 Les grammaires contextuelles sont semblables aux grammaires algébrique mise à part l'ajout d'un contexte autour des productions en partie gauche et partie droite.
 Les grammaires régulières rendent possible l'association de n'importe quelle composition de non-terminaux et terminaux vers une autre composition.
-=== Grammaire non-contextuelles ===
+=== Les grammaire non-contextuelles ===
 Les grammaires non-contextuelles sont définits de la forme G = (V, A, S, P).
@@ Ligne 47 : / Ligne 50 : @@
 Plus formellement, soit \omega le mot d'entrée : S -*> \omega

Porteries le 16 mai 2018 à 09:46

2018-05-16T09:46:24Z

← Version précédente		Version du 16 mai 2018 à 09:46
Ligne 1 :		Ligne 1 :
	Un algorithme d'analyse syntaxique est un algorithme permettant de reconnaître l'existence d'un mot selon un langage, en cas général il est appliqué pour les langages informatiques et valide ou non un code source pour la syntaxe d'un langage informatique. Mais la plupart des analyseurs syntaxiques ne se contentent pas de seulement valider l'entrée, ils extraient aussi la construction de cette entrée sous la forme d'un arbre abstrait de syntaxe ~~composé~~ des opérateurs et ~~des~~ opérandes.		Un algorithme d'analyse syntaxique est un algorithme permettant de reconnaître l'existence d'un mot selon un langage, en cas général il est appliqué pour les langages informatiques et valide ou non un code source pour la syntaxe d'un langage informatique. Mais la plupart des analyseurs syntaxiques ne se contentent pas de seulement valider l'entrée, ils extraient aussi la construction de cette entrée sous la forme d'un arbre abstrait de syntaxe, par exemple pour des expressions mathématiques composé d'opérateurs et d'opérandes.

			== Les grammaires ==

			=== Les symboles de grammaire ===

			Toutes les grammaires sont composées de symboles regroupé sous deux catégories, les terminaux et le non-terminaux.

			Les terminaux sont les symboles les plus petits ne pouvant être subdivisé, il forme essentiellement la chaine d'entrée. Dans l'exemple d'une expression mathématique simple ces symboles sont tous les chiffres, tous les opérateurs et ponctuations : +-*/().

			Les non-terminaux sont des symboles pouvant être subdivisé, il servent à regrouper d'autre symboles. Par exemple une grammaire pourrait définir le non-terminal expr qui englobe toutes le expressions mathématique soit toutes les compositions valide de chiffres, opérateurs et ponctuations.

			TODO exemple production 5 + 2 - 3

			=== Les productions de grammaires ===

			Les productions décrivent les subdivisions de non-terminaux, dans le cas d'une grammaire non-contextuelle toutes les productions sont de la forme~:

			A --> \gamma

			A : un non-terminal.
			\gamma : une composition de terminaux et non-terminaux.

			Un non-terminal peut être dérivé par une des productions associée, cette opération mène à une proto-phrase, cette proto-phrase est une phrase si elle est constituée seulement de terminaux.
			De même il est possible de réduire une proto-phrase en un non-terminal.

			=== La hiérachie de Chomsky ===

			La hiérachie de Chomsky définit quatre classes de grammaires, chacune pouvant décrire toutes les régles des grammaires de hiérachie plus faible, les grammaires générales couvrent toutes les grammaires possibles.

			Le niveau le plus faible est attribué aux grammaires régulières. Ces grammaires sont d'une forme linéaire, chaque non-terminal peut être associé à une composition de terminaux et un non-terminal en préfixe ou suffixe seulement.
			Les grammaires algébrique (ou non-contextuelles) offrent une plus grande liberté en autorisant d'associer à un non-terminal n'importe quelle combinaison de terminaux et non-terminaux.
			Les grammaires contextuelles sont semblables aux grammaires algébrique mise à part l'ajout d'un contexte autour des productions en partie gauche et partie droite.
			Les grammaires régulières rendent possible l'association de n'importe quelle composition de non-terminaux et terminaux vers une autre composition.

			=== Grammaire non-contextuelles ===

			Les grammaires non-contextuelles sont définits de la forme G = (V, A, S, P).

			V : l'ensemble des non-terminaux de la grammaires.
			A : l'ensemble des terminaux.
			S : le non-terminal axiome.
			P: l'ensemble des productions associant un non-terminal à une composition de non-terminaux et terminaux.

			Dans un contexte plus technique il suffit de préciser l'axiome et les productions car ces dernières listent tout les non-terminaux et terminaux existant.
			L'axiome joue un rôle important dans la validation d'un mot par une grammaire, si des dérivations successives partant de l'axiome mènent à une phrase correspondant au mot d'entrée alors l'entrée est validé. De même si la phrase correspondante au mot d'entrée et réduite jusqu'à obtenir l'axiome.

			Plus formellement, soit \omega le mot d'entrée : S -*> \omega

Porteries le 15 mai 2018 à 19:57

2018-05-15T19:57:20Z

← Version précédente		Version du 15 mai 2018 à 19:57
Ligne 1 :		Ligne 1 :
	Un algorithme d'analyse syntaxique est un algorithme permettant de reconnaître l'existence d'un mot selon un langage, en cas général il est appliqué pour les langages ~~informatique~~ et valide ou non un code source pour la syntaxe d'un langage informatique.		Un algorithme d'analyse syntaxique est un algorithme permettant de reconnaître l'existence d'un mot selon un langage, en cas général il est appliqué pour les langages informatiques et valide ou non un code source pour la syntaxe d'un langage informatique. Mais la plupart des analyseurs syntaxiques ne se contentent pas de seulement valider l'entrée, ils extraient aussi la construction de cette entrée sous la forme d'un arbre abstrait de syntaxe composé des opérateurs et des opérandes.