Retour sur un succès indéniable de la théorie des langagesPour les langages de programmation, la BNF et les analyseurs LALR (Yacc/Lex) ont résolu le problème de manière satisfaisante. Le cadre général d'analyse des langages algébriques déterministes a été torché par Knuth avec les LR(k). Mais d'une part ça ne rend pas compte des aspects de sémantique statique plus dépendants du contexte que sont les règles de liaison et de typage. Et d'autre part (ou plutôt comme extension de ce problème de fond) ça ne suffit pas pour la langue naturelle, qui est inhéremment non-déterministe à cause des ambiguités.Bien sûr, on peut prendre la classe de tous les langages algébrqiues ou hors-contexte, et obtenir des analyseurs en n3 (Earley). Et même ajouter l'adjonction, avec les TAGs (n6). Et même considérer la classe des grammaires à concaténation d'intervalle (RCG, Boullier), analysable en temps polynomiale, et ayant de bonnes propriétés de fermeture (complément, intersection). En fait le cadre décidable est trop restrictif. Il faut peut-être viser la complétude au sens de Turing, qui exprime qu'on a à notre disposition toute la puissance d'un langage de programmation universel. Par contre, ne pas coder sous forme de règles de grammaires syntagmatiques les restrictions contextuelles (accord, etc), et plutôt considérer un mécanisme orthogonal de résolution de contraintes. The quest for a perfect parsing framework within controlled complexity bounds is a wild goose chase.
|