Analyse syntaxique

Grammaires algébriques

Le cours est l'occasion de quelques rappels sur les langages formels, les systèmes de réécriture, les grammaires syntagmatiques et les machines formelles. La démarche pose trois prérequis à l'analyse syntaxique d'un texte :

  1. une formalisation de la syntaxe permet de décider ce qui est syntaxiquement correct ou non ;
  2. la formalisation doit exhiber la structure de la syntaxe pour permettre le raisonnement sémantique ;
  3. la formalisation doit permettre de dériver automatiquement un analyseur syntaxique correct.
On vérifie ces trois prérequis dans le cas des grammaires algébriques.

Fichiers du cours

Bibliographie

Les articles [BBG+60, Can62, Cho56, Ear70, GR62, Par66] peuvent m'être demandés.

[Bac59]
John W. Backus. The syntax and semantics of the proposed international algebraic language of the Zürich ACM-GAMM Conference. In IFIP Congress, pages 125–131, 1959.
[BBG+60]
John W. Backus, Friedrich L. Bauer, Julien Green, C. Katz, John McCarthy, Alan J. Perlis, Heinz Rutishauser, Klaus Samelson, Bernard Vauquois, Joseph Henry Wegstein, Adriaan van Wijngaarden, and Michael Woodger. Report on the algorithmic language ALGOL 60. Communications of the ACM, 3(5):299–314, 1960.
[Can62]
David G. Cantor. On the ambiguity problem of Backus systems. Journal of the ACM, 9(4):477–479, 1962.
[Cho56]
Noam Chomsky. Three models for the description of language. IEEE Transactions on Information Theory, 2:113–124, 1956.
[Cho59]
Noam Chomsky. On certain formal properties of grammars. Information and Control, 2(2):137–167, 1959.
[CS63]
Noam Chomsky and Marcel Paul Schützenberger. The Algebraic Theory of Context-free Languages. Computer Programming and Formal Systems. North-Holland Publishing Co., Amsterdam, 1963.
[Ear70]
Jay Earley. An efficient context-free parsing algorithm. Communications of the ACM, 13(2):94–102, 1970.
[GR62]
Seymour Ginsburg and H. Gordon Rice. Two families of languages related to ALGOL. Journal of the ACM, 9(3):350–371, 1962.
[Kle56]
Stephen C. Kleene. Representation of events in nerve nets and finite automata. In C. E. Shannon and J. McCarthy, editors, Automata Studies, pages 3–40. Princeton University Press, Princeton, NJ, 1956.
[Par66]
Rohit J. Parikh. On context-free languages. Journal of the ACM, 13(4):570–581, 1966.