1. Stéphane GALLAND
  2. lo46-lessons

Commits

Stéphane GALLAND  committed bcaeb32

Initial commit.

  • Participants
  • Branches master

Comments (0)

Files changed (18)

File .autolatex_project.cfg

View file
  • Ignore whitespace
+; Config::Simple 4.59
+; Fri Dec 27 17:46:26 2013
+
+[generation]
+main file=LO46.tex
+generate images=true
+image directory=imgs/chapter0:imgs/chapter1:imgs/appendix
+
+

File .gitignore

View file
  • Ignore whitespace
+.autolatex_stamp
+*.aux
+*.log
+*.nav
+*.out
+*.pdf
+*.snm
+*.synctex
+*.synctex.gz
+*.toc
+imgs/*/*.pdf
+

File LO46.tex

View file
  • Ignore whitespace
+\documentclass[english,partsectioncirclenumberstyle,eventbelowauthors]{irtesbeamer}
+
+\usepackage[utf8]{inputenc}
+\usepackage{autolatex}
+\usepackage{tabularx}
+
+\graphicspath{{./imgs/chapter0/},{./imgs/chapter1/},{./imgs/appendix/}}
+
+\title{Compilation and Language Theory}
+
+\addauthor[S.~Galland]{St\'ephane~GALLAND}
+
+\event[LO46]{Module LO46}
+
+\instituteurl{http://www.multiagent.fr}
+
+\institute[Computer Science Department -- UTBM]{
+	\textbf{IRTES-SeT, UTBM} \\[0cm]
+	90010 Belfort cedex, France \\[0cm]
+	\texttt{stephane.galland@utbm.fr} -- \insertinstituteurl
+}
+
+%\useheaderlinewithsections
+
+\newcommand{\animatedslide}[4][1-]{%
+	\begin{frame}<#1>[c]{#2}%
+		\begin{center}
+		\includeanimatedfigure[#4]{#3}%
+		\end{center}
+	\end{frame}%
+}
+
+\let\code\texttt
+\let\id\code
+\newcommand{\kw}[1]{\underline{\code{#1}}}
+
+\begin{document}
+
+\input{chapters/chapter0}
+
+\input{chapters/chapter1}
+
+\input{chapters/appendix}
+
+\end{document}

File chapters/appendix.tex

View file
  • Ignore whitespace
+\appendix
+
+\section{Document License}
+\begin{frame}{Creative Common License CC-BY-NC-SA 3.0}
+	\begin{center}\footnotesize
+	``\inserttitle'' by \insertauthor\ is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 3.0 Unported License.
+	\end{center}
+	\begin{block}{\footnotesize You are free}\scriptsize
+		\begin{tabularx}{\linewidth}{m{.04\linewidth}@{\hspace{.5em}}lX}
+		\raisebox{-.5\height}{\includegraphics[width=\linewidth]{creative_toshare}} &
+		\Emph{To Share} & to copy, distribute and transmit the work \\
+		\raisebox{-.5\height}{\includegraphics[width=\linewidth]{creative_toremix}} &
+		\Emph{To Remix} & to adapt the work \\
+		\end{tabularx}
+	\end{block}
+	\begin{block}{\footnotesize Under the following conditions}\scriptsize
+		\begin{tabularx}{\linewidth}{m{.04\linewidth}@{\hspace{.5em}}lX}
+		\raisebox{-.5\height}{\includegraphics[width=\linewidth]{creative_attribution}} &
+		\Emph{Attribution} & You must attribute the work in the manner specified by the author or licensor (but not in any way that suggests that they endorse you or your use of the work). \\
+		\raisebox{-.5\height}{\includegraphics[width=\linewidth]{creative_noncommercial}} &
+		\Emph{Noncommercial} & You may not use this work for commercial purposes. \\
+		\raisebox{-.5\height}{\includegraphics[width=\linewidth]{creative_sharealike}} &
+		\Emph{Share alike} & If you alter, transform, or build upon this work, you may distribute the resulting work only under the same or similar license to this one. \\
+		\end{tabularx}
+	\end{block}
+\end{frame}
+
+\section{Authors}
+\begin{frame}{Author of this Document:\\Dr.habil. St\'ephane GALLAND}
+	\begin{minipage}[t]{.75\linewidth}
+	\begin{raggedright}
+	\vspace{1em}
+	{\scriptsize Systems and Transport Laboratory \\
+	Institut de Recherche sur les Transports, l'\'Energie et la Soci\'et\'e \\
+	Universit\'e de Technologie de Belfort-Montb\'eliard, France} \\[.5cm]
+	\textbf{Topics: Multiagent systems, Agent-based simulation, Agent-oriented software engineering} \\[.5cm]
+	\end{raggedright}
+	\end{minipage}%
+	\hfill%
+	\raisebox{-\height}{\includegraphics[width=2cm]{sgalland}} \\[.5cm]%
+	\begin{raggedright}
+	\scriptsize \begin{tabularx}{\linewidth}{@{}lX@{}}
+	Web page: & \url{http://www.multiagent.fr/People:Galland_stephane} \\
+	Email: & \href{mailto:stephane.galland@utbm.fr}{stephane.galland@utbm.fr} \\
+	\end{tabularx} \\[.5cm]
+	\scriptsize Open-source contributions:\begin{itemize}
+	\item \url{http://www.janus-project.org}
+	\item \url{http://www.arakhne.org}
+	\end{itemize}
+	\end{raggedright}
+\end{frame}
+
+\section{Bibliography}
+\bibliography{biblio}
+

File chapters/chapter0.tex

View file
  • Ignore whitespace
+\begin{frame}{Another Yet English Course}
+	\begin{itemize}
+	\item Seminars and Lectures in English.
+	\item Supervised tutorials in French or English.
+	\item Laboratory Works mainly in French.
+	\end{itemize}
+	\includegraphics[width=\linewidth]{in_english}
+\end{frame}
+
+\begin{frame}{Goals of this Lecture}
+	\begin{enumerate}
+	\item Study models, techniques and algorithms that permit to analyze a text-based language.
+	\item Study models, techniques and algorithms that permit to generate and execute code.
+	\item Study the techniques for the optimization of executable codes.
+	\end{enumerate}
+\end{frame}
+
+\begin{frame}{Recommended Prerequisites}
+	To follow LO46 with the best results, you should have the following prerequisites:
+	\begin{itemize}
+	\item You should be familiar with one of the following languages, and may have encountered other languages as well: C, C++, C\#, or Java.
+	\item You should have already experienced CLI compilation.
+	\item You must have a good level in algorithmic.
+	\end{itemize}
+\end{frame}
+
+\tableofcontentslide[onlyparts]
+
+\begin{frame}{Tools}
+	\begin{description}
+	\item[Languages] \begin{itemize}
+		\item Java (tutorials and projects)
+		\item C/C++ (projects)
+		\item C\# (projects)
+		\end{itemize}
+	\item[Integrated Development Environment] \begin{itemize}
+		\item Eclipse (tutorials and projects)
+		\item NetBean (projects)
+		\item Visual Studio (projects)
+		\end{itemize}
+	\item[Compilation Tools] \begin{itemize}
+		\item javacc (tutorials, projects)
+		\item jlex (projects)
+		\item lex, flex (projects)
+		\item yacc, bison (projects)
+		\end{itemize}
+	\end{description}
+\end{frame}
+
+\begin{frame}{Evaluation of the Students}
+	\begin{description}
+	\item[Project] 30\% of the final score. \begin{itemize}
+		\item 2 to 4 students per group
+		\item subjects and guidelines will be detailled during the second lecture session.
+		\end{itemize}
+	\item[Mid-term Exam] 25\% of the final score.
+	\item[Final Exam] 25\% of the final score.
+	\item[Laboratory Works] 20\% of the final score. \begin{itemize}
+		\item Several practice sessions will be selected, and your works evaluated by teachers.
+		\item How many sessions? When? You will discover the answers at the beginning of each session.
+		\end{itemize}
+	\end{description}
+\end{frame}
+
+\begin{frame}{My Recommendations}
+	\begin{enumerate}
+	\item Download the PDF files of the slides before the lecture.
+	\item Do not read \emph{each word} of the slides during the lectures.
+	\item Listen carefully the teachers and takes notes on the side of the slides.
+	\item Ask questions \dots Ask questions \dots Ask questions.
+	\item You must read the slides at home as soon as possible, not few hours before the exams.
+	\end{enumerate}
+\end{frame}
+
+\libraryslide[frametitle={Books},subtitle={2nd edition}]{book1}{Compilers --- Principles, Techniques and Tools
+Second Edition}{Alfred V. AHO, Monica S. LAM, Ravi SETHI and Jeffrey D. ULLMAN}{Pearson \& Addison Wesley, 2007}{0-321-48681-1}
+
+\libraryslide[frametitle={Books}]{book2}{Parsing Techniques --- A Practical Guide}{Dick Grune and Ceriel J.H. Jacobs}{Springer Verlag New York, 2007}{0-387-20248-X}
+
+\libraryslide[frametitle={Books}]{book3}{Calculabilité, Complexité et Approximation}{Jean-François REY}{Vuibert, France, 2004}{2-7117-4808-1}
+

File chapters/chapter1.tex

View file
  • Ignore whitespace
+\part[author={Stéphane GALLAND}]{Introduction to and Overview of the Compilation Theory}
+
+\tableofcontentslide
+
+\section{Introduction}
+
+\begin{frame}{Introduction}
+	\begin{description}
+	\item Programming languages are notations for describing computations to people and to machines.
+	\item All the software running on all the computers was written in some programming language.
+	\item Before a program can be run, it first must be translated into a form in which it can be executed by a computer.
+	\item The software systems that do this translation are called compilers.
+	\item[Goal of this chapter] give an overview of a typical simple compiler.
+	\end{description}
+\end{frame}
+
+\section{Programming Languages}
+
+\tableofcontentslide[sectionstyle={show/shaded},subsectionstyle={show/show/hide},subsubsectionstyle={hide/hide/hide/hide}]
+
+\subsection{Brief history}
+\begin{frame}{A Brief History of Programming Languages}
+	\begin{description}
+	\item[1940's] machine language, sequences of 0's and 1's.
+	\item[1950's] mnemonic assembly languages.
+	\item[Later in 1950's] Fortran for scientific computation, Cobol for business data processing, Lisp for symbolic computation. ALGOL (ALGOrithmic Language) is the ancestor of the modern languages such as B, Pascal, Simula and C.
+	\item[1960's and 1970's] Refinements in the 3GL \begin{itemize}
+		\item APL: array programming and functional programming
+		\item PL/I: merging the best concepts from Fortan and Cobol.
+		\item Simula: first OO language, followed by Smalltalk
+		\item C: operating system programming
+		\item Prolog: first logic programming language
+		\item ML: polymorphic type system on top of Lisp
+		\end{itemize}
+	\end{description}
+\end{frame}
+
+\sidenote{Figure by Matthew Hancock --- Complete figure on \url{moodle.utbm.fr}}
+\figureslide[scale=1]{A Brief History of Programming Languages}{brief_history_of_languages}
+
+\subsection{Classifications and Types of Programming Languages}
+\begin{frame}{Generations of Programming Languages}
+	\begin{description}
+	\item[1st Generation -- 1GL] Machine languages.
+	\item[2nd Generation -- 2GL] Assembly languages.
+	\item[3rd Generation -- 3GL] High-level languages (Fortran, Cobol, Lisp, C, C++, C\#, Java\dots)
+	\item[4th Generation -- 4GL] languages designed for specific applications, like Nomad for report generation, SQL for database, Postscript for text formatting.
+	\item[5th Generation -- 5GL] languages based on logic and constraints, like Prolog and OPS5.
+	\end{description}
+\end{frame}
+
+\begin{frame}{Imperative or Declarative Language}
+	\begin{block}{Imperative Languages}
+	\begin{itemize}
+	\item Imperative programs are specifying how a computation is to be done.
+	\item Notion of program state and statements that change the state.
+	\item \inlineexamples{C, C++, C\#, Java}.
+	\end{itemize}
+	\end{block}
+	\begin{block}{Declarative Languages}
+	\begin{itemize}
+	\item Declarative programs are specifying what computation is to be done.
+	\item Functional and logic-based languages.
+	\item \inlineexamples{ML, Haskell, Prolog}.
+	\end{itemize}
+	\end{block}
+\end{frame}
+
+\begin{frame}{Object-oriented Language}
+	\begin{itemize}
+	\item \emph{Supports object-oriented programming.}
+	\vfill
+	\item Consists in building programs from a collection of objects that interact with one another.
+	\end{itemize}
+	\vfill
+	\begin{examples}\begin{itemize}
+		\item Simula 67, Smalltalk (the earliest major OO languages)
+		\item C++, C\#, Java, Ruby\dots.
+		\end{itemize}
+	\end{examples}
+\end{frame}
+
+\begin{frame}{Scripting Language}
+	\begin{itemize}
+	\item \emph{Interpreted languages with high-level operators designed for ``gluing together'' computations.}
+	\vfill
+	\item Programs are much shorter than equivalent program written in other languages.
+	\end{itemize}
+	\vfill
+	\begin{examples}
+		Awk, Basic, JavaScript, Perl, PHP, Python, Ruby, Tcl, \dots
+	\end{examples}
+\end{frame}
+
+\subsection{Basics of Programming Languages}
+
+\tableofcontentslide[currentsection,currentsubsection]
+
+\subsubsection{Definitions}
+\begin{frame}[allowframebreaks]{Definitions}
+	\begin{description}
+	\item[Name] a string of characters that refers to a thing in the program.
+	\item[Identifier] a string of characters that refers to an entity (data object, procedure, class, type). \begin{itemize}
+		\item All identifiers are names; but not all names are identifiers
+		\item \id{x.y} is a name but not an identifier, and \id{x} and \id{y} are identifiers.
+		\end{itemize}
+	\item[Variable] a particular location of the store of the values at run-time. A variable is denoted by a name. Each declaration of an identifier introduces a new variable.
+	\item[Keyword] an identifier that has a particular meaning to the programming language.
+	\end{description}
+	%
+	\pagebreak
+	%
+	\begin{description}
+	\item[Procedure] a subprogram that may be called.
+	\item[Function] a procedure that may return a value of some type (the``return type'').
+	\item[Method] a procedure or a function inside a class in object-oriented languages.
+	\end{description}
+	\begin{alertblock}{Caution}
+	In the C-family languages, all the subprograms are functions; and a function is enabled to return nothing (\kw{void}).
+	\end{alertblock}
+	%
+	\pagebreak
+	%
+	\begin{description}
+	\item[Declaration] tells us about the type of a thing. \begin{itemize}
+		\item \inlineexample{\code{\kw{int} i;}}
+		\end{itemize}
+	\item[Definition] tells us about the value of a thing. \begin{itemize}
+		\item \inlineexample{\code{i = 1;}}
+		\end{itemize}
+	\item[Signature of a procedure] the declaration of the procedure. It is composed of a return type, an identifier, and a collection of parameter declarations.
+	\end{description}
+	\begin{example}\smaller In C++: \begin{itemize}
+		\item a method is declared in a \code{.hpp} file.
+		\item a method is defined in a \code{.cpp} file.
+		\end{itemize}
+	\end{example}
+\end{frame}
+
+\subsubsection{Environment and State}
+\begin{frame}{Definitions}
+	The association of names with locations in memory (the store) and then with values is described by two mappings:
+	\begin{description}
+	\item[Environment] mapping from names to locations in the store.
+	\item[State] mapping from locations in store to their values.
+	\end{description}
+	\vfill
+	\begin{center}
+	\includegraphics[width=.75\linewidth]{environment_state}
+	\end{center}
+\end{frame}
+
+\subsubsection{Static and Dynamic Languages}
+\begin{frame}{Static or Dynamic Policy}
+	\alertbox{One of the most important issues when designing a compiler is what decisions can the compiler make about the program.}
+	\begin{block}{Static Policy}
+	A program uses a policy that enables the compiler to decide an issue; \emph{the decision could be decided at compile time.}
+	\end{block}
+	\begin{block}{Dynamic Policy}
+	The decision can be made when we execute the program; \emph{the decision is required at run time.}
+	\end{block}
+\end{frame}
+
+\begin{frame}{Example of the Scope of the Declarations}
+	\begin{itemize}
+	\item A language uses a static scope if it is possible to determine the scope of a declaration by looking only at the program (C, Java\dots)
+	\vfill
+	\item With dynamic scope, as the program runs, the same use of a variable x could refer to any of several different declarations of x (Perl, PHP\dots).
+	\end{itemize}
+\end{frame}
+
+\begin{frame}{Example of the use of the term ``static'' in Java}
+	\begin{center}
+		\code{\kw{public} \kw{static} \kw{int} x = 1;}
+	\end{center}
+	\vfill
+	\begin{itemize}
+	\item Here \kw{static} refers not to the scope of the variable, but rather to the ability of the compiler to determine the location in memory.
+	\vfill
+	\item If \kw{static} is omitted each object has this variable and the compiler cannot determine where it is in advance.
+	\end{itemize}
+\end{frame}
+
+\subsubsection{Static Scope and Block Structure}
+\subsubsection{Dynamic Scope}
+\subsubsection{Parameter-Passing Mechanisms}
+\subsubsection{Aliasing Mechanism}
+
+\section{What is a Language Processor?}
+
+\section{Structure of a Compiler}
+
+\section{Simple Syntax Directed Translator}
+
+\section{Conclusion}
+

File imgs/appendix/creative_attribution.svg

View file
  • Ignore whitespace
Added
New image

File imgs/appendix/creative_noncommercial.svg

View file
  • Ignore whitespace
Added
New image

File imgs/appendix/creative_sharealike.svg

View file
  • Ignore whitespace
Added
New image

File imgs/appendix/creative_toremix.svg

View file
  • Ignore whitespace
Added
New image

File imgs/appendix/creative_toshare.svg

View file
  • Ignore whitespace
Added
New image

File imgs/appendix/sgalland.jpg

  • Ignore whitespace
Added
New image

File imgs/chapter0/book1.png

  • Ignore whitespace
Added
New image

File imgs/chapter0/book2.png

  • Ignore whitespace
Added
New image

File imgs/chapter0/book3.png

  • Ignore whitespace
Added
New image

File imgs/chapter0/in_english.png

  • Ignore whitespace
Added
New image

File imgs/chapter1/brief_history_of_languages.svg

View file
  • Ignore whitespace
Added
New image