{"id":813,"date":"2019-03-09T20:23:00","date_gmt":"2019-03-09T19:23:00","guid":{"rendered":"http:\/\/blogperso.union31.fr\/?p=813"},"modified":"2019-03-10T20:18:35","modified_gmt":"2019-03-10T19:18:35","slug":"analyse-syntaxique","status":"publish","type":"post","link":"https:\/\/blogperso.union31.fr\/?p=813","title":{"rendered":"Analyse syntaxique"},"content":{"rendered":"\n<div id=\"ez-toc-container\" class=\"ez-toc-v2_0_82_2 counter-hierarchy ez-toc-counter ez-toc-grey ez-toc-container-direction\">\n<div class=\"ez-toc-title-container\">\n<p class=\"ez-toc-title\" style=\"cursor:inherit\">Sommaire<\/p>\n<span class=\"ez-toc-title-toggle\"><a href=\"#\" class=\"ez-toc-pull-right ez-toc-btn ez-toc-btn-xs ez-toc-btn-default ez-toc-toggle\" aria-label=\"Toggle Table of Content\"><span class=\"ez-toc-js-icon-con\"><span class=\"\"><span class=\"eztoc-hide\" style=\"display:none;\">Toggle<\/span><span class=\"ez-toc-icon-toggle-span\"><svg style=\"fill: #999;color:#999\" xmlns=\"http:\/\/www.w3.org\/2000\/svg\" class=\"list-377408\" width=\"20px\" height=\"20px\" viewBox=\"0 0 24 24\" fill=\"none\"><path d=\"M6 6H4v2h2V6zm14 0H8v2h12V6zM4 11h2v2H4v-2zm16 0H8v2h12v-2zM4 16h2v2H4v-2zm16 0H8v2h12v-2z\" fill=\"currentColor\"><\/path><\/svg><svg style=\"fill: #999;color:#999\" class=\"arrow-unsorted-368013\" xmlns=\"http:\/\/www.w3.org\/2000\/svg\" width=\"10px\" height=\"10px\" viewBox=\"0 0 24 24\" version=\"1.2\" baseProfile=\"tiny\"><path d=\"M18.2 9.3l-6.2-6.3-6.2 6.3c-.2.2-.3.4-.3.7s.1.5.3.7c.2.2.4.3.7.3h11c.3 0 .5-.1.7-.3.2-.2.3-.5.3-.7s-.1-.5-.3-.7zM5.8 14.7l6.2 6.3 6.2-6.3c.2-.2.3-.5.3-.7s-.1-.5-.3-.7c-.2-.2-.4-.3-.7-.3h-11c-.3 0-.5.1-.7.3-.2.2-.3.5-.3.7s.1.5.3.7z\"\/><\/svg><\/span><\/span><\/span><\/a><\/span><\/div>\n<nav><ul class='ez-toc-list ez-toc-list-level-1 ' ><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-1\" href=\"https:\/\/blogperso.union31.fr\/?p=813\/#I_Introduction\" >I Introduction<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-2\" href=\"https:\/\/blogperso.union31.fr\/?p=813\/#II_Grammaire\" >II Grammaire<\/a><ul class='ez-toc-list-level-3' ><li class='ez-toc-heading-level-3'><a class=\"ez-toc-link ez-toc-heading-3\" href=\"https:\/\/blogperso.union31.fr\/?p=813\/#II1_differents_type_de_grammaires_%E2%80%A6\" >II.1 diff\u00e9rents type de grammaires &#8230;<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-3'><a class=\"ez-toc-link ez-toc-heading-4\" href=\"https:\/\/blogperso.union31.fr\/?p=813\/#II2_Grammaire_algebrique%E2%80%A6\" >II.2 Grammaire alg\u00e9brique&#8230;<\/a><ul class='ez-toc-list-level-4' ><li class='ez-toc-heading-level-4'><a class=\"ez-toc-link ez-toc-heading-5\" href=\"https:\/\/blogperso.union31.fr\/?p=813\/#II21_Regles_generales\" >II.2.1 R\u00e8gles g\u00e9n\u00e9rales<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-4'><a class=\"ez-toc-link ez-toc-heading-6\" href=\"https:\/\/blogperso.union31.fr\/?p=813\/#II22_Un_peu_dexplications\" >II.2.2 Un peu d&rsquo;explications<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-4'><a class=\"ez-toc-link ez-toc-heading-7\" href=\"https:\/\/blogperso.union31.fr\/?p=813\/#II23_Methodes_danalyse_syntaxique\" >II.2.3 M\u00e9thodes d&rsquo;analyse syntaxique<\/a><\/li><\/ul><\/li><\/ul><\/li><\/ul><\/nav><\/div>\n<h2 class=\"wp-block-heading\"><span class=\"ez-toc-section\" id=\"I_Introduction\"><\/span>I Introduction<span class=\"ez-toc-section-end\"><\/span><\/h2>\n\n\n\n<p>Apr\u00e8s l&rsquo;analyse lexicale qui v\u00e9rifie que chaque \u00ab\u00a0mot\/valeur\u00a0\u00bb utilis\u00e9 soit correct il faut maintenant aborder <strong>l&rsquo;analyse syntaxique<\/strong> qui va principalement v\u00e9rifier que la \u00ab\u00a0<strong>grammaire<\/strong>\u00a0\u00bb  corresponde \u00e0 ce que l&rsquo;on attend.<\/p>\n\n\n\n<p>La \u00ab\u00a0grammaire\u00a0\u00bb va ainsi d\u00e9finir la combinaison des mots \u00e0 respecter.  Par Exemple un \u00ab\u00a0IF\u00a0\u00bb doit \u00eatre suivi d&rsquo;une condition puis d&rsquo;un \u00ab\u00a0THEN\u00a0\u00bb : IF (condition) THEN. <\/p>\n\n\n\n<p>L&rsquo;analyse syntaxique permet \u00e9galement de faire d&rsquo;autres op\u00e9rations. Pour r\u00e9sumer ces op\u00e9rations seront les suivantes :<\/p>\n\n\n\n<ul class=\"wp-block-list\"><li>v\u00e9rifier que la grammaire soit correcte ;<\/li><li>traduire le programme sous forme d&rsquo;un arbre. Ce qui permettra par la suite de transformer cet arbre en code ou op\u00e9rations ;<\/li><li>produire du code interm\u00e9diaire.<\/li><\/ul>\n\n\n\n<h2 class=\"wp-block-heading\"><span class=\"ez-toc-section\" id=\"II_Grammaire\"><\/span>II Grammaire<span class=\"ez-toc-section-end\"><\/span><\/h2>\n\n\n\n<h3 class=\"wp-block-heading\"><span class=\"ez-toc-section\" id=\"II1_differents_type_de_grammaires_%E2%80%A6\"><\/span>II.1 diff\u00e9rents type de grammaires &#8230;<span class=\"ez-toc-section-end\"><\/span><\/h3>\n\n\n\n<p>En informatique, il est souvent fait mention de la hi\u00e9rarchie de Chomsky qui classifie les langages formels en plusieurs classifications.<\/p>\n\n\n\n<div class=\"wp-block-image\"><figure class=\"aligncenter is-resized\"><img loading=\"lazy\" decoding=\"async\" src=\"http:\/\/blogperso.union31.fr\/wp-content\/uploads\/2019\/03\/Hierarchie_chomsky.svg_.png\" alt=\"\" class=\"wp-image-820\" width=\"230\" height=\"253\" srcset=\"https:\/\/blogperso.union31.fr\/wp-content\/uploads\/2019\/03\/Hierarchie_chomsky.svg_.png 800w, https:\/\/blogperso.union31.fr\/wp-content\/uploads\/2019\/03\/Hierarchie_chomsky.svg_-273x300.png 273w, https:\/\/blogperso.union31.fr\/wp-content\/uploads\/2019\/03\/Hierarchie_chomsky.svg_-768x845.png 768w\" sizes=\"auto, (max-width: 230px) 100vw, 230px\" \/><figcaption> <br><em>hi\u00e9rarchie de Chomsky <\/em><\/figcaption><\/figure><\/div>\n\n\n\n<p>Ces diff\u00e9rentes grammaires sont les suivantes :<\/p>\n\n\n\n<ul class=\"wp-block-list\"><li>de type 0 : grammaires g\u00e9n\u00e9rales<\/li><li>de type 1 : grammaires contextuelles<\/li><li>de type 2 : grammaires alg\u00e9briques, g\u00e9n\u00e9ralement utilis\u00e9es par des <strong>analyseurs syntaxiques<\/strong><\/li><li>de type 4 : grammaires r\u00e9guli\u00e8res, domaine ou l&rsquo;on utilise des expressions r\u00e9guli\u00e8res. Souvent utilis\u00e9 par des <strong>analyseurs lexicaux<\/strong><\/li><\/ul>\n\n\n\n<p>Pour notre part nous allons donc nous concentrer sur la grammaire alg\u00e9briques.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\"><span class=\"ez-toc-section\" id=\"II2_Grammaire_algebrique%E2%80%A6\"><\/span>II.2 Grammaire alg\u00e9brique&#8230;<span class=\"ez-toc-section-end\"><\/span><\/h3>\n\n\n\n<h4 class=\"wp-block-heading\"><span class=\"ez-toc-section\" id=\"II21_Regles_generales\"><\/span>II.2.1 R\u00e8gles g\u00e9n\u00e9rales<span class=\"ez-toc-section-end\"><\/span><\/h4>\n\n\n\n<p>La notion de grammaire formelle va \u00eatre utilis\u00e9e. Cette grammaire est constitu\u00e9e des 4 \u00e9l\u00e9ments :<\/p>\n\n\n\n<ul class=\"wp-block-list\"><li>un ensemble de symboles dit <strong>terminaux<\/strong> ;<\/li><li>un ensemble de symbole dit <strong>non terminaux<\/strong> ; <\/li><li><u>un \u00e9l\u00e9ment<\/u> de l&rsquo;ensemble des non terminaux, appel\u00e9 axiome et souvent not\u00e9 S ;<\/li><li>un ensemble de <strong>r\u00e8gles de production<\/strong> compos\u00e9 d&rsquo;un non terminal, de suite de terminaux et de non terminaux ;<\/li><\/ul>\n\n\n\n<h4 class=\"wp-block-heading\" id=\"mce_31\"><span class=\"ez-toc-section\" id=\"II22_Un_peu_dexplications\"><\/span>II.2.2 Un peu d&rsquo;explications<span class=\"ez-toc-section-end\"><\/span><\/h4>\n\n\n\n<p>Un \u00e9l\u00e9ment terminal peut \u00eatre un chiffre, une lettre ou un op\u00e9rateur (+, -, =).  Lorsque on attend aucun \u00e9l\u00e9ment (une cha\u00eene vide), il est souvent utilis\u00e9 le symbole \u0404<\/p>\n\n\n\n<p>Un \u00e9l\u00e9ment non terminal est compos\u00e9 d&rsquo;\u00e9l\u00e9ments terminaux. Par exemple un nombre (\u00e9l\u00e9ment non terminal) et compos\u00e9 de plusieurs chiffres (\u00e9l\u00e9ments terminaux).<\/p>\n\n\n\n<p>Une r\u00e8gle de production est une r\u00e8gle d&rsquo;\u00e9criture qui permet de d\u00e9finir toutes les chaines correctes.<\/p>\n\n\n\n<p><u>Exemple :<\/u><\/p>\n\n\n\n<table class=\"wp-block-table\"><tbody><tr><td>R\u00e8gle de grammaire                                                                                 <\/td><td>Commentaire<\/td><\/tr><tr><td> <strong>S<\/strong> -&gt; lettre<strong>S<\/strong> <\/td><td>R\u00e8gle de production S compos\u00e9 d&rsquo;\u00e9l\u00e9ments non terminaux (lettre) et d&rsquo;une r\u00e8gle de production<\/td><\/tr><tr><td> <strong>S<\/strong>-&gt; lettre | \u0404  <\/td><td>R\u00e8gle de production compos\u00e9 d&rsquo;un \u00e9l\u00e9ment non terminal (lettre) ou d&rsquo;un \u00e9l\u00e9ment terminal ( \u0404 )<\/td><\/tr><tr><td> lettre -&gt; a|b <\/td><td>Une lettre est un \u00e9l\u00e9ment nom terminal qui peut \u00eatre compos\u00e9 d&rsquo;\u00e9l\u00e9ments terminaux (soit un \u00ab\u00a0a\u00a0\u00bb ou un \u00ab\u00a0b\u00a0\u00bb)<\/td><\/tr><\/tbody><\/table>\n\n\n\n<p>Ainsi les exemples ci-dessous sont accept\u00e9s par la grammaire ci-dessus :<\/p>\n\n\n\n<ul class=\"wp-block-list\"><li>\u00ab\u00a0a\u00a0\u00bb, \u00ab\u00a0aa\u00a0\u00bb, \u00ab\u00a0aaa\u00a0\u00bb, &#8230;<\/li><li>\u00ab\u00a0b\u00a0\u00bb, \u00ab\u00a0bb\u00a0\u00bb,\u00a0\u00bbbbb\u00a0\u00bb, &#8230;<\/li><li>\u00ab\u00a0ba\u00a0\u00bb, \u00ab\u00a0ab\u00a0\u00bb, \u00ab\u00a0aaaaab\u00a0\u00bb, &#8230;<\/li><\/ul>\n\n\n\n<p><u>Autre exemple :<\/u><\/p>\n\n\n\n<p>Soit la grammaire pour d\u00e9finir une op\u00e9ration prenant en compte la multiplication et l&rsquo;addition de variables<\/p>\n\n\n\n<p>E \u2192 E + T | T<br>T \u2192 T \u00d7 F | F<br>F \u2192 ( E ) | id<\/p>\n\n\n\n<p>E, T et F sont des non terminaux.  +, \u00d7, (,) et id sont des terminaux. <\/p>\n\n\n\n<p>Le symbole \u00a0\u00bb | \u00a0\u00bb indique \u00ab\u00a0ou\u00a0\u00bb. Exemple : <strong>E \u2192  A | B<\/strong> . Ainsi  E peut \u00eatre A ou B.<\/p>\n\n\n\n<p>Nous allons voir si <strong>id + id<\/strong> est correct ?<\/p>\n\n\n\n<table class=\"wp-block-table\"><tbody><tr><td>\u00e9tape <\/td><td>Op\u00e9ration : <br>id + id<\/td><td>Grammaire :<br>E \u2192 E + T | T<br>T \u2192 T \u00d7 F | F<br>F \u2192 ( E ) | id <\/td><\/tr><tr><td>1<\/td><td>id <\/td><td> F \u2192 ( E ) | <strong>id<\/strong>  <br><\/td><\/tr><tr><td>2<\/td><td>id +<\/td><td>correspond  \u00e0  E \u2192 E + T <br>mais la r\u00e8gle  F \u2192 ( E ) impose que E soit entre parenth\u00e8ses<br>donc &#8211;&gt; erreur ou ne correspond pas \u00e0 la grammaire<\/td><\/tr><\/tbody><\/table>\n\n\n\n<p> Nous allons voir si <strong>(id*id)<\/strong> est correct ?<\/p>\n\n\n\n<table class=\"wp-block-table\"><tbody><tr><td>\u00e9tape <\/td><td>(id*id) <\/td><td>E \u2192 E + T | T<br>T \u2192 T \u00d7 F | F<br>F \u2192 ( E ) | id <\/td><\/tr><tr><td>1<\/td><td>(<\/td><td><strong> F \u2192 ( <\/strong>E ) | id  <br><\/td><\/tr><tr><td>2<\/td><td>(id <\/td><td> <strong>F \u2192 ( E<\/strong> ) | id  <br> <strong>E<\/strong> \u2192 E + T | <strong>T<\/strong> <br> <strong>T<\/strong> \u2192 T \u00d7 F | <strong>F<\/strong> <br> <strong>F<\/strong> \u2192 ( E ) | <strong>id<\/strong>  <br><\/td><\/tr><tr><td>3<\/td><td>(id*<\/td><td> <strong>F \u2192 ( E<\/strong> ) | id <br> <strong>E<\/strong> \u2192 E + T | <strong>T<\/strong> <br> <strong>T<\/strong> \u2192 <strong>T \u00d7<\/strong> F | F <br><\/td><\/tr><tr><td>4<\/td><td> (id*id <\/td><td> <strong>F \u2192 ( E<\/strong> ) | id <br> <strong>E<\/strong> \u2192 E + T | <strong>T<\/strong> <br> <strong>T<\/strong> \u2192 <strong>T \u00d7<\/strong> <strong>F<\/strong> | F <br><strong>F<\/strong> \u2192 ( E ) | <strong>id<\/strong> <\/td><\/tr><tr><td>5<\/td><td> (id*id) <\/td><td> <strong>F \u2192 ( E<\/strong> <strong>)<\/strong> | id <br> <strong>E<\/strong> \u2192 E + T | <strong>T<\/strong> <br> <strong>T<\/strong> \u2192 <strong>T \u00d7<\/strong> <strong>F<\/strong> | F <br><strong> F<\/strong> \u2192 <strong>( E )<\/strong> | id  <\/td><\/tr><\/tbody><\/table>\n\n\n\n<p>Toutes les conditions ont \u00e9t\u00e9 satisfaites &#8230; (id*id) correspond \u00e0 la grammaire attendue.<\/p>\n\n\n\n<h4 class=\"wp-block-heading\" id=\"mce_32\"><span class=\"ez-toc-section\" id=\"II23_Methodes_danalyse_syntaxique\"><\/span>II.2.3 M\u00e9thodes d&rsquo;analyse syntaxique<span class=\"ez-toc-section-end\"><\/span><\/h4>\n\n\n\n<p>La plupart des m\u00e9thodes d&rsquo;analyses sont class\u00e9es en 2 cat\u00e9gories :<\/p>\n\n\n\n<ul class=\"wp-block-list\"><li>les m\u00e9thodes d&rsquo;analyse descendantes (top-down parsing). M\u00e9thodes les plus simples car elles sont facilement utilisables \u00e0 la main,<\/li><li>les m\u00e9thodes d&rsquo;analyse ascendantes (bottom-up parsing). M\u00e9thodes les plus performantes, notamment utilis\u00e9es par l&rsquo;analyseur yacc.<\/li><\/ul>\n\n\n\n<p>Ici nous allons nous concentrer sur les m\u00e9thodes d&rsquo;analyses descendantes. <\/p>\n\n\n\n<p>Le type d&rsquo;analyse <u>descendante<\/u> porte les noms suivant :<\/p>\n\n\n\n<ul class=\"wp-block-list\"><li>LL  (pour <strong>L<\/strong>eft to right, <strong>L<\/strong>eftmost derivation en anglais). Cet analyseur lit de gauche \u00e0 droite et produit une d\u00e9rivation \u00e0 gauche. L&rsquo;analyse se fait en une seule passe sur le mot d&rsquo;entr\u00e9e. Ce type d&rsquo;analyse est aussi appel\u00e9 LL(k) lorsque elle utilise une fen\u00eatre de k lex\u00e8mes.<\/li><\/ul>\n\n\n\n<p><\/p>\n\n\n\n<p>Exemple de type d&rsquo;analyse <u>ascendante<\/u> :<\/p>\n\n\n\n<ul class=\"wp-block-list\"><li>LR (pour <strong>L<\/strong>eft to right, <strong>R<\/strong>ightmost derivation en anglais). Cet analyseur lit  de gauche \u00e0 droite et produit une d\u00e9rivation \u00e0 droite. On parle \u00e9galement d&rsquo;analyseur de type LR(k) o\u00f9 k repr\u00e9sente le nombre de symbole non consomm\u00e9.<\/li><li>SLR ou LR simple.<\/li><li>LLAR (<strong>L<\/strong>ook-<strong>A<\/strong>head <strong>L<\/strong>eft-to-right <strong>R<\/strong>ightmost derivation) qui est une am\u00e9lioration du type LR.<\/li><\/ul>\n\n\n\n<p>Pour ces analyseurs, n&rsquo;importe quelle grammaire n&rsquo;est pas applicable. Elle doit \u00eatre de type \u00ab\u00a0non ambigu\u00eb\u00a0\u00bb et avoir certaines sp\u00e9cifi\u00e9s comme la factorisation \u00e0 gauche par exemple. Un analyseur descendant et d\u00e9terministe est dit pr\u00e9dictif.<\/p>\n\n\n\n<p>analyse par descente r\u00e9cursive<\/p>\n\n\n\n<p>analyse pr\u00e9dictive par descente non-recursive<\/p>\n\n\n\n<p><\/p>\n\n\n\n<p><\/p>\n\n\n\n<p><\/p>\n\n\n\n<p>Pour aller plus loin :<\/p>\n\n\n\n<ul class=\"wp-block-list\"><li><a href=\"https:\/\/fr.wikipedia.org\/wiki\/Grammaire_formelle\">https:\/\/fr.wikipedia.org\/wiki\/Grammaire_formelle<\/a><\/li><li><a href=\"https:\/\/fr.wikipedia.org\/wiki\/Symboles_terminaux_et_non_terminaux\">https:\/\/fr.wikipedia.org\/wiki\/Symboles_terminaux_et_non_terminaux<\/a><\/li><li><a href=\"https:\/\/henri-garreta.developpez.com\/tutoriels\/techniques-outils-compilation\/?page=page_3#LIII-A-1\">https:\/\/henri-garreta.developpez.com\/tutoriels\/techniques-outils-compilation\/?page=page_3#LIII-A-1<\/a><\/li><\/ul>\n\n\n\n<p><\/p>\n","protected":false},"excerpt":{"rendered":"<p>I Introduction Apr\u00e8s l&rsquo;analyse lexicale qui v\u00e9rifie que chaque \u00ab\u00a0mot\/valeur\u00a0\u00bb utilis\u00e9 soit correct il faut maintenant aborder l&rsquo;analyse syntaxique qui va principalement v\u00e9rifier que la \u00ab\u00a0grammaire\u00a0\u00bb corresponde \u00e0 ce que l&rsquo;on attend. La \u00ab\u00a0grammaire\u00a0\u00bb va ainsi d\u00e9finir la combinaison des<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[2],"tags":[],"class_list":["post-813","post","type-post","status-publish","format-standard","hentry","category-_dev"],"_links":{"self":[{"href":"https:\/\/blogperso.union31.fr\/index.php?rest_route=\/wp\/v2\/posts\/813","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/blogperso.union31.fr\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/blogperso.union31.fr\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/blogperso.union31.fr\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/blogperso.union31.fr\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=813"}],"version-history":[{"count":22,"href":"https:\/\/blogperso.union31.fr\/index.php?rest_route=\/wp\/v2\/posts\/813\/revisions"}],"predecessor-version":[{"id":846,"href":"https:\/\/blogperso.union31.fr\/index.php?rest_route=\/wp\/v2\/posts\/813\/revisions\/846"}],"wp:attachment":[{"href":"https:\/\/blogperso.union31.fr\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=813"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/blogperso.union31.fr\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=813"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/blogperso.union31.fr\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=813"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}