Quels sujets d'informatique sont nécessaires pour suivre un cours d'introduction aux compilateurs? [fermé]

10

Je ne suis pas étudiant en informatique et je travaille en tant que développeur web (java, python, AS3, etc.) en tant que professionnel. Je prends 1 cours par semestre dans mon université locale. J'avais pris l'intelligence artificielle (comprenant la logique, la grammaire sans contexte, l'analyse CYK, la PNL d'introduction, les chaînes de Markov, HMM, etc.) le semestre dernier.

Je prévois de suivre un cours d'introduction aux compilateurs dans le prochain semestre qui couvre le programme suivant:

Analyse lexicale, analyse syntaxique, analyse sémantique, environnement d'exécution, représentations intermédiaires, génération de code, allocation de registre, sélection et planification d'instructions, introduction aux optimisations de code local et global, analyse du flux de données

Ma question est la suivante: y a-t-il des sujets informatiques que je devrais connaître avant de suivre ce cours? Si oui, ce serait bien si vous pouviez énumérer ces cours.

education computer-science compiler souligné_geek
la source
1
Cela dépend de votre école. La mienne n'était pas si difficile, donc les conditions préalables étaient des structures de données de base et des algorithmes de base - c'est tout. Malheureusement, ils ont rendu les compilateurs facultatifs et je me suis débattu et je ne les ai pas pris.
Job du

Réponses:

8

Vous devriez probablement avoir une compréhension simple des sujets suivants:

  • Maths discrets (ensembles, relations, arbres, graphiques, matrices, théorie des nombres)
  • Structures de données (dans un sens plus appliqué, comment fonctionnent les arbres, les listes, les piles, les files d'attente et les chaînes)
  • Algorithmes de base (concepts de base, tri, recherche, notation Big-O, etc.)
  • Architecture informatique (logique numérique, opérations binaires, micro-composants, cache, mémoire, programmation d'assemblage)
  • Divers (expressions régulières, langages sans contexte, automates à états finis / pushdown, machines de Turing et calculabilité, outils lexicaux et d'analyse)

Facultatif, et aidera probablement beaucoup:

  • Conception du système d'exploitation (gestion des processus, conception du noyau, synchronisation, planification, événements, verrous, threads et pile vs tas)
Pewpewarrows
la source
4

Eh bien, j'ai fait un peu de travail pour écrire mes propres compilateurs, et je dirais que la principale condition préalable est une bonne compréhension des choses que vous obtiendrez dans une classe Data Structures. Plus précisément, si vous ne comprenez pas la récursivité, les arbres et les cartes / tables de hachage, vous allez vous perdre très rapidement en essayant d'apprendre à construire un compilateur.

Mason Wheeler
la source
3

Vous allez avoir besoin de quelques informations de base sur l'architecture informatique (registres, mémoire, registres spéciaux, etc.) et vous avez déjà vu du code d'assemblage. Ce serait encore mieux si vous avez déjà écrit du code d'assemblage, vous avez donc une bonne compréhension du fonctionnement du langage machine.

Selon le niveau du cours, vous pouvez vous attendre à en savoir un peu plus sur le traitement superscalaire et similaires.

Peter Smith
la source
1
Cela n'est vrai que si nous supposons que le compilateur en question génère du code machine et non une sorte de bytecode.
Mason Wheeler
3

Si cela ressemble à la classe de compilateurs que j'ai reprise à la fin du Crétacé (vers 1988), les seules véritables conditions préalables seraient les structures de données (arbres et tables de hachage en particulier), un langage d'assemblage (pour le code généré), peut-être une certaine architecture informatique, et quelle que soit la classe enseignerait des choses comme les expressions régulières, les automates finis, les machines de Turing, etc. bien que ceux-ci puissent être couverts dans le cadre du cours de compilation lui-même (FWIW, pas le mien). Vous devez également vous assurer que vous comprenez la récursivité.

John Bode
la source
2

Vous devrez probablement suivre également un cours sur les modèles formels et les langues. Tout ce qui couvre la hiérarchie Chompsky de base serait bien: Langues régulières + Langues sans contexte. En effet, il est important de comprendre les fondements mathématiques de l'analyse afin que votre analyseur soit propre, performant et correct. Je pense qu'une bonne classe de compilateurs couvrira souvent les expressions régulières et les analyseurs LALR / LL (k) et la théorie qui les sous-tend.

Mark Pauley
la source
0

Puisqu'ils parlent d'optimisation de code, il est possible qu'il y ait un certain codage de langage d'assemblage. Il serait donc peut-être bon d'avoir au moins une familiarité passagère avec cela. Cela dépend de la façon dont ce cours spécifique est structuré. Sinon, le simple fait d'avoir un solide ensemble de compétences en programmation devrait suffire pour une introduction à la classe des compilateurs, je pense. Ce sera une classe très précieuse.

GrandmasterB
la source
0

Dépend de votre université mais la plupart nécessitent ces pré-requis:

=> Discrete Mathematics
Should include: propositional logic, predicate logic, set theory etc etc 

=> General Concepts of Programming (In any language of choice would be okay)
=> Algorithms and Data Structures
Should include: data structures, abstract data types, recursive algorithms
rrazd
la source