Alphabets, Strings and Languages; Automata and Grammars, Finite automata (FA), DFA -Formal definition & simplified notations (state transition diagram, transition table), NFA -Formal definition, Language of an NFA, Removing, epsilon-transitions. Equivalence of DFAs and NFAs, Regular grammars and FA, Context-free Grammars (CFGs) -Formal definition, sentential forms, leftmost and rightmost derivations. Derivation tree or Parse tree -Definition, Relationship between parse trees and derivations. Parsing and ambiguity, Ambiguity in grammars and Languages Pushdown Automata (PDA) - The language of PDA (acceptance by final state and empty stack). Definition of simple language that has less than 100 tokens. Removing Left Recursion. Applied study for recognition of the syntax of the toy language. Course will be supported with bi-weekly labs & project
Prerequisite(s)
N/A
Corequisite(s)
N/A
Special Requisite(s)
The minimum qualifications that are expected from the students who want to attend the course.(Examples: Foreign language level, attendance, known theoretical pre-qualifications, etc.)
1- Alfred Aho, Ravi Sethi & Jeffrey D. Ullman ; Compilers : Principles, Techniques & Tools ; 1986 Bell Labs or Addison wesley march 1988 corrected edition, ISBN 0-201-10088-6 (main text )
2- Dr. Rafa E. Al-Qutaish; Compiler Construction: With Software Measurement Capability ; Publisher: LAP LAMBERT Academic Publishing (February 4, 2011); Paperback: 156 pages; ISBN-10: 3844306382; ISBN-13: 978-3844306385
3- F.L.Bauer, J.Eickel (editors) ; Compiler Construction : An advanced Course ; Spinger verlag 1976, ISNB 0-540-08046-5 OR 0-387-08046-0 (for T-diagrams, also you may find them in various web cites)
4- Peter H. Salus (series editor) ; handbook of programming languages, vol III : Little Languages & Tools; MacMillan Technical Publishing 1998; ISBN 1-57870-010-8 (for defining course projects )
5- D. Grune, H. Bal, C. Jacobs, K. Langendoen ; Modern Compiler Design ; John Wiley & Sons; 2000; ISBN: 0471976970 ; Paperback: 754 pages Amazon Sales Rank : #67,370
6- Y.N.Srikant, Priti Shankar; The Compiler Design Handbook: Optimizations & Machine Code Generation ; CRC Press; 2002, ISBN: 084931240X, 928 pages , Amazon Sales Rank : #171,350
7- Steven S. Muchnick ; Advanced Compiler Design and Implementation ; Morgan Kaufmann; 1997) ; ISBN: 1558603204, Hardcover: 856 pages Amazon Sales Rank : #73,574
8- Kenneth C. Louden ; Compiler Construction: Principles and Practice; Publ.: Course Technology; 1997 ; ISBN: 0534939724, Hardcover: 592 pages Amazon Sales Rank : #107,877
9- William M. Waite, Lief H. Carter, Lynn R. Carter ; Compiler Construction: Principles and Practice ; Addison-Wesley 1997 , ISBN:0673398226 ? ISBN:0534939724
10- Randy Allen, Ken Kennedy ; Optimizing Compilers for Modern Architectures: A Dependence-based Approach; Morgan Kaufmann; 2001 , ISBN: 1558602860, Amazon Sales Rank : #141,027
11- Randy M. Kaplan ; Constructing Language Processors for Little Languages ; Wiley; 1 edition (August 9, 1994) , ISBN: 0471597538, paperback: 464 pages , Amazon Sales Rank : #359,401
12- Evelyn Duesterwald (Editor), Compiler Construction ; Springer Verlag 2004, ISBN: 3540212973, Paperback: 313 pages , $68.00
13- Gorel Hedin (editor), Compiler Construction: 12th International Conference, 2003 Held As Part of the Joint European Conferences on Theory and Practice of Software, Lecture Notes in Computer Science, 2622, Springer-Verlag 2003, ISBN: 3540009043, $56.00 Paperback: 334 pages
14- R. Nigel Horspool (editor) ; Compiler Construction: 11th International Conference, 2002 Held As Part of the Joint European Conferences on Theory and Practice of Software, Springer-Verlag 2002, ISBN: 3540433694 (Lecture Notes in Computer Science, 2304), $69.95, Paperback: 341 pages, Amazon Sales Rank : #2,207,810
15- R. Wilhelm (editor), Compiler Construction: 10th International Conference, Held As Part of the Joint European Conferences on Theory and Practiceof Software, Springer-Verlag 2001, ISBN: 354041861X (Lecture Notes in Computer Science, 2027 Amazon Sales Rank : #1,726,483
16- William M. Waite, Lynn R. Carter ; An Introduction to Compiler Construction; Publ. Harpercollins College Div 1993 , ISBN: 0673398226, Paperback: 438 pages , Amazon Sales Rank : #1,473,648
17- Thomas W Parsons ; Introduction to Compiler Construction ; Publ. W. H. Freeman, 1992, ISBN: 0716782618, Hardcover: 359 pages , Amazon Sales Rank : #51,114
18 -Robert Morgan; Building an Optimizing Compiler; Digital Press, 1998); ISBN: 155558179X paperback: 450 pages, Amazon Sales Rank : #746,423
NFA -Formal definition, Language of an NFA, Removing, epsilon-transitions. Equivalence of DFAs and NFAs,
4. Week
Regular grammars and FA, Context-free Grammars (CFGs) -Formal definition, sentential forms, leftmost and rightmost derivations. Derivation tree or Parse tree -
5. Week
Definition, Relationship between parse trees and derivations. Parsing and ambiguity,
6. Week
Ambiguity in grammars and Languages Pushdown Automata (PDA) - The language of PDA (acceptance by final state and empty stack).
7. Week
Definition of simple language that has less than 100 tokens ( definition of toy language for the semester).
8. Week
Tentative midterm time
9. Week
Removing Left Recursion.
10. Week
Applied study for recognition of the syntax of the toy language. –Lex -YACC
11. Week
Applied study for recognition of the syntax of the toy language. Syntax directed compiling and integration of Semantic Anaysis Modules
12. Week
Semantic Anaysis examples on the toy language
13. Week
Generation of quadruples for code generation
14. Week
Course will be supported with bi-weekly labs & project. This week is reserved for presentation and evaluation of the projects
15. Week
16. Week
17. Week
Assessments
Evaluation tools
Quantity
Weight(%)
Midterm(s)
1
27
Attendance
1
6
Laboratory
1
27
Final Exam
1
40
Program Outcomes
PO-1
an ability to apply knowledge from undergraduate and graduate engineering and other disciplines to identify, formulate, and solve novel and complex electrical/computer engineering problems that require advanced knowledge within the field
PO-2
knowledge of advanced topics within at least two subdisciplines of computer engineering
PO-3
the ability to understand and integrate new knowledge within the field;
PO-4
the ability to apply advanced technical knowledge in multiple contexts
PO-5
a recognition of the need for, and an ability to engage in, life-long learning
PO-6
the ability to plan and conduct an organized and systematic study on a significant topic within the field
PO-7
an ability to convey technical material through formal written reports which satisfy accepted standards for writing style
PO-8
the ability to analyze and use existing literature
PO-9
the ability to demonstrate effective oral communication skills
PO-10
the ability to stay abreast of advancements in the area of computer engineering
Learning Outcomes
LO-1
Will understand capabilities of three types of Formal Languages
LO-2
Will define reasonable token structure and develop scanner.
LO-3
Understand capabilities of top down and bottomup syntax analysis method
LO-4
Understand the necessity of eliminating left recursion in the grammer while using top down methods
LO-5
Design a triple or quadruple structure that a syntax analysis will produce
to develop pre processor, scanner and syntax analysis phases is emphasized
LO-6
Ability to use Compiler Development tool utilization,