Cours Compilation Chapitre 3 [PDF]

Zitiervorschau

Ministre de l’Enseignement supérieur et de la Recherche Scientifique Université Abderrahmane Mira Bejaia Faculté des sciences exactes Département d’informatique

Licence académique 3ème année

Cours compilation Chapitre 3 : Analyse syntaxique

1

Licence 3

Cours compilation

Chapitre 3

3.1. Introduction Tout langage de programmation possède des règles qui indiquent si un programme est bien formé. L’analyseur syntaxique reçoit une suite d’unités lexicales de la part de l’analyseur lexical, et doit vérifier que cette suite peut être engendrée par une grammaire du langage. Le problème est donc : -

Étant donné une grammaire G ; Étant donné un mot m (programme) ;

Est-ce que le mot (m) appartient au langage généré par G.

3.2. Principe Le principe est d’essayer de construire un arbre de dérivation. Les grammaires les plus adaptées à l’analyse syntaxique sont les grammaires de type 2 (non contextuelle).

3.2.1. Grammaire de type 2 Les grammaires de type 2 sont des grammaires dont les règles sont sous la forme suivante :

𝐴 → 𝛼 𝑡𝑒𝑙 𝑞𝑢𝑒 𝐴 ∈ 𝑁, 𝛼 ∈ (𝑇 ∪ 𝑁)∗ 3.2.2. Classification des analyseurs syntaxiques Le schéma suivant représente la classification des analyseurs syntaxiques. Analyseur syntaxique

Méthode indéterministe

Méthode déterministe

Méthode descendante

Méthode ascendante

Figure 1 : Classification des analyseurs syntaxiques

2

Licence 3

Cours compilation

Chapitre 3

3.2.2.1. Analyse descendante Nous définissons l’analyse descendante par un processus d’analyse qui cherche à attendre le programme source à analyser en commençant par l’axiome, cette analyse est nommée « Top – Down ».

3.2.2.2. Analyse ascendante Nous définissons l’analyse ascendante par un processus d’analyse qui cherche à attendre l’axiome en commençant par le programme source, cette analyse est nommée « Bottom-Down ».

3.3. Condition d’analyse syntaxique descendante Afin de réaliser l’analyse syntaxique descendante, il faut que la grammaire soit de type 2, factorisée, et non récursive à gauche. La dernière condition permet de limiter les retours arrière et les boucles.

3.3.1. Récursivité directe La grammaire G est récursive à gauche, si elle s’écrit sous la forme suivante : 𝐴 → 𝐴𝛼 𝑡𝑒𝑙 𝑞𝑢𝑒 𝐴 ∈ 𝑁, 𝛼 ∈ (𝑇 ∪ 𝑁)∗ Il est possible de transformer une grammaire récursive à gauche, en une grammaire non récursive à gauche.

3.3.1.1. Transformation de la grammaire Soit la règle de production suivante 𝐴 → 𝐴𝛼1 ⁄𝐴𝛼2 / … /𝐴𝛼𝑛 / 𝛽1⁄𝛽2 / … /𝛽𝑚 𝑡𝑒𝑙 𝑞𝑢𝑒 𝐴 ∈ 𝑁, 𝛼_ ∈ (𝑇𝑠 ∪ 𝑁)∗ On remarque qu’il y a une récursivité à gauche, afin d’éliminer la récursivité à gauche, la grammaire doit être transformée comme suit : {

𝐴 → 𝛽1⁄𝛽2 / … /𝛽𝑚 / 𝛽1 𝐴′ ⁄𝛽2 𝐴′ / … /𝛽𝑚 𝐴′ 𝐴′ → 𝛼1 ⁄𝛼2 / … /𝛼𝑛 / 𝛼1 𝐴′⁄𝛼2 𝐴′ / … /𝛼𝑛 𝐴′

Exemple : 𝐺1 = {

𝑆 → 𝑎𝑆⁄𝑏 /𝐴𝑐 𝐴 → 𝐴𝑎⁄𝑐

3

Licence 3

Cours compilation

Chapitre 3

En transformant la grammaire, le résultat est comme suit : 𝑆 → 𝑎𝑆⁄𝑏 /𝐴𝑐 𝐺1 = { 𝐴 → 𝑐 ⁄𝑐𝐴′ 𝐴′ → 𝑎⁄𝑎𝐴′

3.3.2. Récursivité indirecte Une grammaire G est récursive indirecte à gauche, si elle s’écrit sous la forme suivante :

𝐴 → 𝐵𝛼1 ⁄𝛽1 { 𝐵 → 𝐴𝛼2 ⁄𝛽2 Pour transformer une grammaire récursive à gauche directe indirecte, on utilise la « substitution ».

𝐴 → 𝐵𝛼1 ⁄𝛽1 𝐵 → 𝐴𝛼2 ⁄𝛽2

On a {

On substitue B dans A, ce qui donne : 𝐴 → 𝐴𝛼2 𝛼1 ⁄𝛽2 𝛼1 /𝛽1 On substitue A dans B, ce qui donne : 𝐵 → 𝐵𝛼1 𝛼2 ⁄𝛽1 𝛼2 /𝛽2 La grammaire après substitution : {

𝐴 → 𝐴𝛼2 𝛼1 ⁄𝛽2 𝛼1 /𝛽1 𝐵 → 𝐵𝛼1 𝛼2 ⁄𝛽1 𝛼2 /𝛽2

On aura une grammaire récursive à gauche directe, après transformation on obtient : 𝐴 → 𝛽1⁄𝛽1 𝐴′ 𝐴′ → 𝛼2 𝛼1 ⁄𝛼1 𝛼2 𝐴′ 𝐵 → 𝛽2⁄𝛽2 𝐵 ′ { 𝐵′ → 𝛼1 𝛼2 ⁄𝛼1 𝛼2 𝐵′

3.3.2. Factorisation d’une grammaire Une des conditions permettant de faire une analyse syntaxique descendante déterministe est la factorisation. Une grammaire G n’est pas factorisée, s’il existe dans P production sous la forme : 𝐴 → 𝛼𝑥⁄𝛼𝑦/𝛼𝑧/ 𝛾/𝛽 𝑎𝑣𝑒𝑐 𝛼, 𝑥, 𝑦, 𝑧 ∈ (𝑇 ∪ 𝑁)+ 𝑒𝑡 𝛽, 𝛾 ∈ (𝑇 ∪ 𝑁)∗

4

Licence 3

Cours compilation

Chapitre 3

Cette règle devient :

𝐴 → 𝛼𝐵/𝛾/𝛽 { 𝐵 → 𝑥/𝑦/𝑧 Exemple :

𝑆 → 𝑎𝑆/𝑏𝐴 𝑆 → 𝑎𝑆/𝑏𝐴 𝐺2 = { ⇔ 𝐺 ′ = {𝐴 → 𝑎𝐵/𝑐 𝐴 → 𝑎𝑏/𝑎𝐴/𝑐 𝐵 → 𝑏/𝐴 3.4. Grammaire 𝜺 − 𝑳𝒊𝒃𝒓𝒆 Une grammaire est 𝜺 − 𝒍𝒊𝒃𝒓𝒆 si et seulement si : Il n’existe pas dans P des productions de la forme : 𝐴 → 𝜀 ou bien 𝑆 → 𝜀 (Axiome), et il n’existe pas de membre droit de production de la forme 𝐴 → 𝜀 pour 𝐴 ≠ 𝑆. Une grammaire peut être transformée en une grammaire équivalente.

3.4.1. Transformation d’une grammaire en une grammaire 𝜺 − 𝒍𝒊𝒃𝒓𝒆 Soit l’algorithme suivant : 1. 𝑝𝑜𝑢𝑟 𝑐ℎ𝑎𝑞𝑢𝑒 𝑟è𝑔𝑙𝑒 𝑑𝑒 𝑙𝑎 𝑓𝑜𝑟𝑚 𝐴 → 𝜀 𝑎𝑣𝑒𝑐 𝐴 ≠ 𝑆 𝑓𝑎𝑖𝑟𝑒 𝑃𝑜𝑢𝑟 𝑐ℎ𝑎𝑞𝑢𝑒 𝑟è𝑔𝑙𝑒 𝑑𝑒 𝑙𝑎 𝑓𝑜𝑟𝑚 𝐵 → 𝛼𝐴𝛽 𝑓𝑎𝑖𝑟𝑒 𝐴𝑗𝑜𝑢𝑡𝑒𝑟 𝑙𝑎 𝑝𝑟𝑜𝑑𝑢𝑡𝑖𝑜𝑛 𝐵 → 𝛼𝛽 𝑓𝑎𝑖𝑡 𝐸𝑙𝑖𝑚𝑖𝑛𝑒𝑟 𝑙𝑎 𝑟è𝑔𝑙𝑒 𝐴 → 𝜀 𝑓𝑎𝑖𝑡 2. 𝑠𝑖 𝑆 → 𝜀 𝑒𝑡 ∃ 𝑀𝐷𝑃 𝑑𝑒 𝑙𝑎 𝑓𝑜𝑟𝑚𝑒 𝛼𝑆𝛽 𝐴𝑙𝑜𝑟𝑠 𝐼𝑛𝑡𝑟𝑜𝑑𝑢𝑖𝑟𝑒 𝑢𝑛 𝑛𝑜𝑛 − 𝑡𝑒𝑟𝑚𝑖𝑛𝑎𝑙 𝑆 ′ , 𝑛𝑜𝑢𝑣𝑒𝑙 𝑎𝑥𝑖𝑜𝑚 𝑑𝑒 𝑙𝑎 𝑔𝑟𝑎𝑚𝑚𝑎𝑖𝑟𝑒 𝑆 ′ → 𝑆/𝜀 𝑟𝑒𝑓𝑎𝑖𝑟𝑒 𝑙 ′ é𝑡𝑎𝑝𝑒1 𝑎𝑣𝑒𝑐 𝑆 → 𝜀

Exemple :

𝑆 → 𝑎/𝐴 𝐺3 = { 𝐴 → 𝐴𝐵/𝜀 𝐵 → 𝑎𝐴𝑏𝐵/𝑏

⇔

𝑆 → 𝑎/𝐴 {𝐴 → 𝐴𝐵/𝐵 𝐵 → 𝑎𝐴𝑏𝐵/𝑏/𝑎𝑏𝐵

3.5. Conditions d’analyse syntaxique ascendante Afin de réaliser l’analyse syntaxique ascendante, il faut que la grammaire soit de type 2, soit non ambiguë.

5

Licence 3

Cours compilation

Chapitre 3

Une grammaire est ambiguë, s’il existe une séquence de symboles terminaux qui admet plusieurs dérivations.

Exemple Soit 𝐺 = {𝐸 → 𝐸 + 𝐸/𝐸 ∗ 𝐸/𝑖𝑑} La grammaire G est ambiguë, car la séquence (id + id*id) admet deux arbres de dérivation distincte. E

E

E

+

E

E

*

E

+

E

id

ou id

E

id

*

E

E

id

id

id

Figure 2 : Arbre syntaxique d’une grammaire ambiguë

3.6. Méthodes d’analyse descendante non déterministe 3.6.1. Analyse descendante parallèle La technique d’analyse syntaxique descendante parallèle est une technique dont le processus fonctionne en parallèle de tel sort à construire un ensemble d’arbres en même temps, elle suit les étapes suivantes : 1. Initialement, la première cible contient l’axiome suivi d’un #; 2. Si le sommet de la cible est un non-terminal, alors Remplacer le non-terminal par toutes les alternatives (autant de cible que d’alternatives) ; 3. Si le sommet de la cible est un terminal, alors comparer le terme courant du programme avec le sommet de la cible : a. Avancer dans la cible et dans la chaine dans le cas où ils sont égaux ; b. Abandonner dans le cas contraire ; 4. Si le sommet de la cible est égal à # et la chaine à analyser est égale à #, alors la chaine est correcte et abandonner les autres cibles, sinon Échec.

6

Licence 3

Cours compilation

Chapitre 3

Exemple : Soit la grammaire 𝐺2 suivante :

< 𝑝𝑟𝑜𝑔 >→ 𝑏𝑒𝑔𝑖𝑛 < 𝐿𝐷 >; < 𝐿𝐼 > 𝑒𝑛𝑑 𝐺4 = { < 𝐿𝐷 >→ 𝑑; < 𝐿𝐷 >/ 𝑑 < 𝐿𝐼 > → 𝑖; < 𝐿𝐼 >/ 𝑖 Analyser la chaine suivante : Begin d ; d ; i end # Cible Chaine begin d ; d ; i end # < 𝑝𝑟𝑜𝑔 > 𝑒𝑛𝑑# begin d ; d ; i end # 𝑏𝑒𝑔𝑖𝑛 < 𝐿𝐷 >; < 𝐿𝐼 > 𝑒𝑛𝑑# d ; d ; i end # < 𝐿𝐷 >; < 𝐿𝐼 > 𝑒𝑛𝑑# d ; d ; i end # 𝑑; < 𝐿𝐷 >; < 𝐿𝐼 > 𝑒𝑛𝑑# d ; d ; i end # 𝑑; < 𝐿𝐼 > 𝑒𝑛𝑑# ; d ; i end # ; < 𝐿𝐷 >; < 𝐿𝐼 > 𝑒𝑛𝑑# ; d ; i end # ; < 𝐿𝐼 > 𝑒𝑛𝑑# d ; i end # < 𝐿𝐷 >; < 𝐿𝐼 > 𝑒𝑛𝑑# d ; i end # < 𝐿𝐼 > 𝑒𝑛𝑑# d ; i end # 𝑑; < 𝐿𝐷 >; < 𝐿𝐼 > 𝑒𝑛𝑑# d ; i end # 𝑑; < 𝐿𝐼 > 𝑒𝑛𝑑# d ; i end # 𝑖; < 𝐿𝐼 >; < 𝐿𝐼 > 𝑒𝑛𝑑# d ; i end # 𝑖; < 𝐿𝐼 > 𝑒𝑛𝑑# ; i end # ; < 𝐿𝐷 >; < 𝐿𝐼 > 𝑒𝑛𝑑# ; i end # ; < 𝐿𝐼 > 𝑒𝑛𝑑# i end # < 𝐿𝐷 >; < 𝐿𝐼 > 𝑒𝑛𝑑# i end # < 𝐿𝐼 > 𝑒𝑛𝑑# i end # 𝑑; < 𝐿𝐷 >; < 𝐿𝐼 > 𝑒𝑛𝑑# i end # 𝑑; < 𝐿𝐼 > 𝑒𝑛𝑑# i end # 𝑖; < 𝐿𝐼 >< 𝐿𝐼 > 𝑒𝑛𝑑# i end # 𝑖 < 𝐿𝐼 > 𝑒𝑛𝑑# i end # 𝑖; < 𝐿𝐼 >; < 𝐿𝐼 > 𝑒𝑛𝑑# i end # 𝑖; < 𝐿𝐼 > 𝑒𝑛𝑑# i end # ; < 𝐿𝐼 >; < 𝐿𝐼 > 𝑒𝑛𝑑# i end # < 𝐿𝐼 > 𝑒𝑛𝑑# i end # 𝑖; < 𝐿𝐼 > 𝑒𝑛𝑑# i end # 𝑖 𝑒𝑛𝑑# end # ; < 𝐿𝐼 > 𝑒𝑛𝑑# end # 𝑒𝑛𝑑# # #

7

Action Remplacer < prog > par les MDP 𝐷é𝑝𝑖𝑙𝑒𝑟 𝑒𝑡 𝑎𝑣𝑎𝑛𝑐𝑒𝑟 𝑑𝑎𝑛𝑠 𝑙𝑎 𝑐ℎ𝑎𝑖𝑛𝑒 Remplacer < LD > par les MDP 𝐷é𝑝𝑖𝑙𝑒𝑟 𝑒𝑡 𝑎𝑣𝑎𝑛𝑐𝑒𝑟 𝑑𝑎𝑛𝑠 𝑙𝑎 𝑐ℎ𝑎𝑖𝑛𝑒 𝐷é𝑝𝑖𝑙𝑒𝑟 𝑒𝑡 𝑎𝑣𝑎𝑛𝑐𝑒𝑟 𝑑𝑎𝑛𝑠 𝑙𝑎 𝑐ℎ𝑎𝑖𝑛𝑒 𝐷é𝑝𝑖𝑙𝑒𝑟 𝑒𝑡 𝑎𝑣𝑎𝑛𝑐𝑒𝑟 𝑑𝑎𝑛𝑠 𝑙𝑎 𝑐ℎ𝑎𝑖𝑛𝑒 𝐷é𝑝𝑖𝑙𝑒𝑟 𝑒𝑡 𝑎𝑣𝑎𝑛𝑐𝑒𝑟 𝑑𝑎𝑛𝑠 𝑙𝑎 𝑐ℎ𝑎𝑖𝑛𝑒 Remplacer < LD > par les MDP Remplacer < LI > par les MDP 𝐷é𝑝𝑖𝑙𝑒𝑟 𝑒𝑡 𝑎𝑣𝑎𝑛𝑐𝑒𝑟 𝑑𝑎𝑛𝑠 𝑙𝑎 𝑐ℎ𝑎𝑖𝑛𝑒 𝐷é𝑝𝑖𝑙𝑒𝑟 𝑒𝑡 𝑎𝑣𝑎𝑛𝑐𝑒𝑟 𝑑𝑎𝑛𝑠 𝑙𝑎 𝑐ℎ𝑎𝑖𝑛𝑒 𝐸𝑐ℎ𝑒𝑐 𝐸𝑐ℎ𝑒𝑐 𝐷é𝑝𝑖𝑙𝑒𝑟 𝑒𝑡 𝑎𝑣𝑎𝑛𝑐𝑒𝑟 𝑑𝑎𝑛𝑠 𝑙𝑎 𝑐ℎ𝑎𝑖𝑛𝑒 𝐷é𝑝𝑖𝑙𝑒𝑟 𝑒𝑡 𝑎𝑣𝑎𝑛𝑐𝑒𝑟 𝑑𝑎𝑛𝑠 𝑙𝑎 𝑐ℎ𝑎𝑖𝑛𝑒 Remplacer < LD > par les MDP Remplacer < LI > par les MDP 𝐸𝑐ℎ𝑒𝑐 𝐸𝑐ℎ𝑒𝑐 𝐷é𝑝𝑖𝑙𝑒𝑟 𝑒𝑡 𝑎𝑣𝑎𝑛𝑐𝑒𝑟 𝑑𝑎𝑛𝑠 𝑙𝑎 𝑐ℎ𝑎𝑖𝑛𝑒 𝐷é𝑝𝑖𝑙𝑒𝑟 𝑒𝑡 𝑎𝑣𝑎𝑛𝑐𝑒𝑟 𝑑𝑎𝑛𝑠 𝑙𝑎 𝑐ℎ𝑎𝑖𝑛𝑒 𝐷é𝑝𝑖𝑙𝑒𝑟 𝑒𝑡 𝑎𝑣𝑎𝑛𝑐𝑒𝑟 𝑑𝑎𝑛𝑠 𝑙𝑎 𝑐ℎ𝑎𝑖𝑛𝑒 𝐷é𝑝𝑖𝑙𝑒𝑟 𝑒𝑡 𝑎𝑣𝑎𝑛𝑐𝑒𝑟 𝑑𝑎𝑛𝑠 𝑙𝑎 𝑐ℎ𝑎𝑖𝑛𝑒 𝐸𝑐ℎ𝑒𝑐 Remplacer < LI > par les MDP 𝐷é𝑝𝑖𝑙𝑒𝑟 𝑒𝑡 𝑎𝑣𝑎𝑛𝑐𝑒𝑟 𝑑𝑎𝑛𝑠 𝑙𝑎 𝑐ℎ𝑎𝑖𝑛𝑒 𝐷é𝑝𝑖𝑙𝑒𝑟 𝑒𝑡 𝑎𝑣𝑎𝑛𝑐𝑒𝑟 𝑑𝑎𝑛𝑠 𝑙𝑎 𝑐ℎ𝑎𝑖𝑛𝑒 𝐸𝑐ℎ𝑒𝑐 𝐷é𝑝𝑖𝑙𝑒𝑟 𝑒𝑡 𝑎𝑣𝑎𝑛𝑐𝑒𝑟 𝑑𝑎𝑛𝑠 𝑙𝑎 𝑐ℎ𝑎𝑖𝑛𝑒 𝐶ℎ𝑎𝑖𝑛𝑒 𝑎𝑐𝑐𝑒𝑝𝑡é𝑒

Licence 3

Cours compilation

Chapitre 3

Remarque 1. Cette technique n’est pas efficace, car elle nécessite l’examinassions de plusieurs arbres de dérivation en parallèle, ce qui est couteux en temps et en espace mémoire. 2. Pour appliquer cette méthode, il faut que la grammaire soit non récursive à gauche.

3.6.2. Analyse descendante prédictive avec retour arrière La technique d’analyse prédictive avec retour arrière est une technique dont le processus fonctionne séquentiellement, de tels sorts à réduire l’espace mémoire. Elle se base sur le concept de l’arbre syntaxique. Nous utilisons une pile afin de sauvegarder les informations nécessaires pour permettre le retour arrière. Une structure est associée à chaque règle de la grammaire : (Numéro de la règle, numéro de l’alternative, nombre d’alternatives, Position dans la chaine) L’analyse suit les étapes suivantes : 1. Initialement la pile contient l’axiome ; 2. Si le sommet de la pile est un non-terminal, alors empiler la structure définie précédemment, et remplacer le non-terminal par l’alternative ; 3. Si le sommet de la pile est un terminal, alors comparer le sommet de la pile avec le terme courant de la chaine à analyser. a. Si le sommet de la pile et le terme courant sont égaux, alors avancer dans la chaine et dépiler le sommet de la pile ; b. Sinon faire un retour arrière et essayer une autre alternative, 4. répéter le processus, jusqu’à ce que le programme soit correcte syntaxiquement ou échec. Exemple

< 𝑝𝑟𝑜𝑔 >→ 𝑏𝑒𝑔𝑖𝑛 < 𝐿𝐷 >; < 𝐿𝐼 > 𝑒𝑛𝑑 𝐺4 = { < 𝐿𝐷 >→ 𝑑; < 𝐿𝐷 >/ 𝑑 < 𝐿𝐼 > → 𝑖; < 𝐿𝐼 >/ 𝑖

Analyser la chaine 𝒃𝒆𝒈𝒊𝒏 𝒅; 𝒊 𝒆𝒏𝒅#

8

Licence 3

Cours compilation

Chapitre 3

< 𝑝𝑟𝑜𝑔 > (1, 1, 1, 1)

(𝐴𝑣𝑎𝑛𝑐𝑒𝑟) 𝑏𝑒𝑔𝑖𝑛

(2,1,1,2)
(𝐴𝑣𝑎𝑛𝑐𝑒𝑟) ;

(3,1,2,4)


(𝐴𝑣𝑎𝑛𝑐𝑒𝑟)𝑒𝑛𝑑 4 𝑅𝑒𝑡𝑟𝑜𝑢𝑟 𝐴𝑟𝑟𝑖è𝑟𝑒 𝐴𝑟𝑟𝑖è𝑟𝑒

< 𝐿𝐷 > (𝐴𝑣𝑎𝑛𝑐𝑒𝑟)𝑖 (𝐸𝑐ℎ𝑒𝑐) ;

1 𝑅𝑒𝑡𝑟𝑜𝑢𝑟 𝐴𝑟𝑟𝑖è𝑟𝑒 𝐴𝑟𝑟𝑖è𝑟𝑒

(3,2,2,4) 𝐸𝑐ℎ𝑒𝑐 𝑑

;

< 𝐿𝐷 >

2 𝑅𝑒𝑡𝑟𝑜𝑢𝑟 𝐴𝑟𝑟𝑖è𝑟𝑒

(𝐴𝑣𝑎𝑛𝑐𝑒𝑟)𝑖

(2,2,2,4)

(𝐸𝑐ℎ𝑒𝑐)𝑑 (2,2,2,2)

(𝐴𝑣𝑎𝑛𝑐𝑒𝑟)𝑑

Figure 3 : arbre syntaxique

9

< 𝐿𝐼 >

Licence 3

Cours compilation

Chapitre 3

Table d’analyse N° 1 2 3 4

Pile

Chaine

5 6 7

d ; (2,1,2,2) ;