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 :
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.