Jakie przedmioty informatyczne są wymagane, aby przejść kurs wprowadzający w kompilatorach? [Zamknięte]

10

Nie jestem studentem informatyki i pracuję jako programista stron internetowych (Java, Python, AS3 itp.) Jako profesjonalista. Biorę 1 kurs na semestr na moim lokalnym uniwersytecie. W zeszłym semestrze wziąłem Sztuczną Inteligencję (obejmującą logikę, gramatykę bezkontekstową, parsowanie CYK, wstępne NLP, łańcuchy Markowa, HMM itp.).

Planuję wziąć udział w kursie wprowadzającym do kompilatorów w nadchodzącym semestrze, który obejmuje następujący program:

Analiza leksykalna, analiza składniowa, analiza semantyczna, środowisko wykonawcze, reprezentacje pośrednie, generowanie kodu, przydzielanie rejestrów, wybór i harmonogramowanie instrukcji, wprowadzenie do optymalizacji kodu lokalnego i globalnego, analiza przepływu danych

Moje pytanie brzmi: czy są jakieś przedmioty informatyczne, które powinienem znać przed rozpoczęciem tego kursu? Jeśli tak, byłoby wspaniale, gdybyś mógł wymienić te kursy.

Stress_geek
źródło
1
Zależy od twojej szkoły. Mój nie był tak trudny, więc niezbędne były podstawowe struktury danych i podstawowe algorytmy - to wszystko. Niestety uczyniły one kompilatory opcjonalnymi, więc odrzuciłem je i nie wzięłem tego.
Job

Odpowiedzi:

8

Prawdopodobnie powinieneś mieć proste zrozumienie następujących tematów:

  • Dyskretna matematyka (zbiory, relacje, drzewa, wykresy, macierze, teoria liczb)
  • Struktury danych (w bardziej stosowanym sensie, jak działają drzewa, listy, stosy, kolejki i łańcuchy)
  • Podstawowe algorytmy (podstawowe pojęcia, sortowanie, wyszukiwanie, notacja Big-O itp.)
  • Architektura komputerów (logika cyfrowa, operacje bitowe, mikrokomponenty, pamięć podręczna, pamięć, programowanie asemblacyjne)
  • Różne (wyrażenia regularne, języki bezkontekstowe, automaty skończone / pushdown, maszyny i obliczenia Turinga, narzędzia leksykalne i parsujące)

Opcjonalnie i prawdopodobnie bardzo pomoże:

  • Projektowanie systemu operacyjnego (zarządzanie procesami, projektowanie jądra, synchronizacja, planowanie, zdarzenia, blokady, wątki i stos kontra stos)
Pewpewarrows
źródło
4

Cóż, trochę popracowałem nad pisaniem własnych kompilatorów i powiedziałbym, że głównym warunkiem jest solidne zrozumienie rzeczy, które dostaniesz w klasie struktur danych. W szczególności, jeśli nie rozumiesz tabel rekurencyjnych, drzew i map / skrótów, bardzo szybko się zgubisz, próbując nauczyć się budować kompilator.

Mason Wheeler
źródło
3

Będziesz potrzebować podstawowego doświadczenia w architekturze komputera (rejestry, pamięć, rejestry specjalnego przeznaczenia itp.) I wcześniej widziałeś kod asemblera. Byłoby jeszcze lepiej, gdybyś napisał wcześniej jakiś kod asemblera, więc dobrze rozumiesz, jak działa język maszynowy.

W zależności od poziomu kursu można oczekiwać, że wiesz trochę o przetwarzaniu superskalarnym i tym podobnych.

Peter Smith
źródło
1
Jest to prawdą tylko wtedy, gdy założymy, że dany kompilator generuje kod maszynowy, a nie jakiś kod bajtowy.
Mason Wheeler,
3

Jeśli jest to coś w rodzaju klasy kompilatorów, którą wziąłem z powrotem pod koniec kredy (ok. 1988 r.), Jedynymi prawdziwymi warunkami byłyby struktury danych (zwłaszcza drzewa i tabele skrótów), ewentualnie język asemblera (dla wygenerowanego kodu), być może pewna architektura komputerowa i jakakolwiek klasa uczyłaby takich rzeczy, jak wyrażenia regularne, automaty skończone, maszyny Turinga itp., chociaż mogą one być omówione w ramach samego kursu kompilatora (FWIW, moje nie). Musisz także upewnić się, że rozumiesz rekurencję.

John Bode
źródło
2

Prawdopodobnie będziesz musiał wziąć udział w kursie na temat formalnych modeli i języków. Wszystko, co obejmuje podstawową hierarchię Chompsky'ego, byłoby w porządku: Zwykłe języki + wolne języki kontekstowe. Jest tak, ponieważ ważne jest, aby zrozumieć matematyczne podstawy analizy składniowej, aby analizator składni był czysty, wydajny i poprawny. Myślę, że dobra klasa kompilatorów często będzie obejmować zarówno wyrażenia regularne, jak i parsery LALR / LL (k) i teorię, która się za nimi kryje.

Mark Pauley
źródło
0

Ponieważ mówią o optymalizacji kodu, możliwe jest, że będzie tam trochę kodowania języka asemblera. Więc może warto mieć przynajmniej przejściową znajomość. Zależy to od struktury tego konkretnego kursu. W przeciwnym razie posiadanie silnego zestawu umiejętności programistycznych powinno wystarczyć do wprowadzenia do klasy kompilatorów. To będzie bardzo cenna klasa.

Grandmaster B.
źródło
0

Zależy od twojego uniwersytetu, ale większość wymaga następujących warunków wstępnych:

=> 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
źródło