click below
click below
Normal Size Small Size show me how
*CS445History
Why Compilers A Brief History : Compiler Construction : Louden : CH1.1
Question | Answer |
---|---|
Define the term grammar | The rules specifying their (languages) structure |
Define the term Chomsky hierarchy | Consists of four levels of grammar , each of which is a specialization of its predecessor |
How many levels of grammar does the Chomsky hierarchy consist of | Four |
What are the names of Chomsky's grammar levels | Type 0, Type 1, Type 2 (Context Free), Type 3 |
What grammar from Chomsky's hierarchy proved to be the most useful for programming languages | Type 2 , Context Free |
What grammar is used as the standard way to represent the structure of programming languages | Type 2, Context Free |
What is the parsing problem | The determination of efficient algorithms for the recognition of context free languages |
When was the parsing problem pursued | 1960s-1970s |
Was the parsing problem solved | Led to a fairly complete solution of this problem which today has become a standard part of compiler theory |
What did the advent of the stored program computer do to programming | It became necessary to write sequences of codes, or programs, that would cause these computers to perform the desired computations |
Who pioneered the stored program computer | John Von Neumann |
When was the advent of the stored program computer pioneered | Late 1940s |
What were initial programs written in | Machine language |
What is machine language | Numeric codes that represented the actual machine operations to be performed |
Example of machine language for the instruction to move the number 2 into the location 0000 (in hexadecimal) on the Intel 8x86 processor (used in IBM PC) | C7 06 0000 0002 |
What are the downsides to writing code in machine language | Extremely time consuming and tedious |
What form of coding replaced coding in machine language | Coding in Assembly language |
What's a primary characteristic of assembly language | Instructions and memory locations are given symbolic forms |
Example of assembly language instruction representing the instruction to move the number 2 into the symbolic memory location X , where X is the memory location 0000 (in hexadecimal) | MOV X,2 |
What does an assembler do | Translates the symbolic codes and memory locations of assembly language into the corresponding numeric codes of machine language |
What is the tool that translates the symbolic codes and memory locations of assembly language into the corresponding numeric codes of machine language | Assembler |
How did assembly language improve program writing | It improved the speed and accuracy with which programs could be written |
When is assembly language used for modern applications | For projects where extreme speed or conciseness of code is needed |
What are the defects of assembly language | It is still not easy to write and it is difficult to read and understand. assembly language is also extremely dependent on the particular machine for which it was written (so code written for one machine must be completely rewritten for another machine) |
What are the implications of using a language that is extremely dependent on the particular machine for which it was written | Code written for one machine must be completely rewritten for another machine |
What were the goals of the next major step in programming technology after assembly language became a popular form of coding | Was 2 write the operations of a program in concise form more nearly resembling mathematical notation/natural language,in a way that was independent of any one particular machine and yet capable of itself being translated by a program into executable code |
For the assembly language code MOV X,2 , write the instruction in a concise machine independent form | X=2 |
What were the concerns regarding the development of machine independent forms of coding more nearly resembling mathematical notation/natural language | It was feared that this might not be possible or if it was then the object code would be so inefficient as to be useless |
What project developed the machine independent forms of coding resembling mathematical notation/natural language and showed that this task was possible and that the object code wasn't inefficient to the point of uselessness | Development of the FORTRAN language and its compiler |
Who built The FORTRAN language and its compiler | A team at IBM led by John Backus |
When was the FORTRAN language and its compiler developed | Between 1954-1957 |
What caused the development of the FORTRAN language and its compiler to be successful | A great deal of effort, since most of the processes involved in translating programming languages were not well understood at that time |
What did Noam Chomsky study | The structure of natural language |
When did Noam Chomsky began his study of the structure of natural language | About the same time the first compiler was under development so 1954-1957 |
What did Chomsky's findings, from his study of the structure of natural language, contribute to compiler development | Made the construction of compilers considerably easier and even capable of partial automation |
What did Chomsky's study produce | |
What did Chomsky's study produce? | Led to the classification of languages according to the complexity of their grammars (the rules specifying their structure) and the power of the algorithms needed to recognize them |
What are related to context free grammars | Finite automata and regular expressions |
What's related to context free grammars | Finite automata and regular expressions |
What Chomsky's grammar corresponds to finite automata and regular expressions | Chomsky's type 3 grammars |
What was gained by the study of finite automata and regular expressions | Led to symbolic methods for expressing the structure of the words, or tokens , of a programming language |
Define optimization techniques | The development of methods for generating efficient object |
Express the complexity of optimization techniques | More complex , began with the first compiler and continues to this day |
What is a better name for optimization techniques | Code improvement techniques |
Why is the term code improvement techniques more fitting than the term optimization techniques | They almost never result in truly optimal object code but only improve its efficiency |
Define parser generators | Programs that would automate the part of the compilation process involving the parsing problem |
What's another name for parser generators | Compiler compilers |
Why is compiler compilers programs more aptly referred to as parser generators | They only automate one part of the compilation process |
What is one of the best known parser generator programs | Yacc (Yet another compiler compiler) |
Who was Yacc written by | Steve Johnson |
What system was Yacc written for | UNIX |
Define scanner generator | Tool developed based on the study of finite automata |
When was Yacc developed | 1975 |
What is one of the best known scanner generators | Lex |
Who was Lex developed by | Mike Lesk |
When was Lex developed | About the same time as Yacc so ~1975 |
What system was Lex developed for | UNIX |
Describe the types of projects that were focused on in the late 1970s and early 1980s | Projects focused on automating the generation of other parts of compilation (besides scanning and parsing) including code generation |
How successful were the projects that focused on automating the generation of other parts of compilation (besides scanning and parsing) including code generation | Less successful |
Why were attempts at projects that focused on automating the generation of other parts of compilation (besides scanning and parsing ) including code generation , less successful ? | Possibly because of the complex nature of the operations and our less than perfect understanding of them |
What are more recent advances in compiler design ? | -compilers have included the application of more sophisticated algorithms for inferring &/or simplifying the information contained in a program - compilers have become more a part of window based IDEs |
What development helped make compilers that have included the application of more sophisticated algorithms for inferring $/or simplifying the information contained in a program | Development of more sophisticated programming languages that allow this kind of analysis |
What is an example of a more sophisticated algorithm for inferring $/or simplifying the information contained in a program | Unification algorithm of Hindley Milner type checking |
When is the unification algorithm of Hindley Milner type checking used | Used in the compilation of functional languages |
What is also included in IDEs besides compilers | Includes editors, linkers, debuggers, and project managers |
What does IDE stand for | Interactive development environment |
Explain the situation regarding standardization of IDEs | So far there has been little standardization of such IDEs but the development of standard windowing environments is leading in that direction |
The basics of compiler design have not changed in how many years | Book answer : ~20 |
What is a part of the standard core of computer science curriculum | Compiler design |