Applications Generation and Software Development
Translators, the stages of compilation, linkers and loaders, libraries, and every software development methodology with its strengths and weaknesses.
Translators and the stages of compilation
The three translators
- Assembler. Translates assembly language to machine code, essentially one to one.
- Compiler. Translates the entire source into machine code before execution, producing an executable. All errors are reported after the attempt. The executable runs fast and the source stays private, but a separate build is needed for each platform.
- Interpreter. Translates and executes one statement at a time, every time the program runs. It stops at the first error, which makes development much easier, but execution is slower and both the source and the interpreter are needed to run.
The stages of compilation
1. Lexical analysis. The source is read character by character and grouped into tokens. Whitespace and comments are removed. Identifiers and constants are entered into the symbol table.
2. Syntax analysis. The token stream is parsed against the grammar of the language to build an abstract syntax tree. Anything that does not fit produces a syntax error. Semantic checks such as type compatibility and use of undeclared variables also happen here.
3. Code generation. The abstract syntax tree is converted into machine code or object code.
4. Optimisation. The code is improved to run faster or use less memory: removing redundant instructions, moving invariant calculations out of loops, reusing registers efficiently. Optimisation takes compilation time and can make debugging harder because the generated code no longer maps neatly onto the source.
Linkers, loaders and libraries
- A library is a collection of pre-compiled, pre-tested subroutines that can be reused. It saves development time and the code is generally more reliable than a fresh implementation.
- A linker combines the compiled object code with the library code the program uses.
- Static linking copies the library code into the executable. The file is larger but self contained, and it is unaffected by later library changes.
- Dynamic linking stores only a reference, and the library is loaded at run time. The executable is smaller and a library update benefits every program using it, but a missing or incompatible library breaks the program.
- A loader copies the executable into memory and prepares it to run, resolving addresses.
Static gives reliability and independence at the cost of size and duplication. Dynamic gives smaller files and shared updates at the cost of a run time dependency.
- Compiler: translates everything first, then the program runs fast and the source stays private.
- Interpreter: translates and runs one line at a time, so it is easy to test and stops at the first error.
- Assembler: turns assembly into machine code, one line for one instruction.
- Lexical analysis: group the characters into tokens and record the names in the symbol table.
- Syntax analysis: check the grammar and build the abstract syntax tree.
- Code generation: produce machine or object code.
- Optimisation: make the code faster or smaller.
- Static linking copies library code into the executable.
- Dynamic linking keeps a reference to a shared library, loaded when the program runs.
- The loader copies the executable into memory and prepares it to run.
Development methodologies
Waterfall
Sequential stages: analysis, design, implementation, testing, evaluation, maintenance. Each is completed before the next begins.
- Clear structure with well defined documentation at every stage, so progress is easy to manage
- Suits projects where the requirements are fully known and stable, such as safety critical systems
- Very inflexible: changing a requirement late means revisiting earlier stages at great expense
- The client sees nothing working until very late
Agile
An umbrella term for iterative approaches delivering working software in short cycles, with continuous customer involvement.
- Responds well to changing requirements
- The customer sees working software early and often, so misunderstandings surface quickly
- Requires close, continuous customer availability
- Documentation is lighter, which can cause problems for long term maintenance
- Harder to predict a final cost and completion date
Extreme programming, a form of agile
- Pair programming: two developers at one machine, one writing and one reviewing continuously
- Test driven development: tests written before the code
- Very frequent small releases and constant refactoring
- Produces high quality code, but is expensive in developer time and demands high discipline
Spiral
Repeated cycles, each containing determining objectives, risk analysis, development and planning the next cycle. Risk is assessed explicitly at every turn.
- Excellent for large, high risk projects
- Expensive, and requires genuine risk assessment expertise
Rapid application development
Prototypes are built quickly and refined through user feedback.
- Very fast, with strong user involvement, so usability is usually good
- Risk of a poorly structured final system if prototypes are patched rather than rebuilt
- Not suitable for large systems with complex integration
Choosing one
| Situation | Methodology |
|---|---|
| Requirements fixed and safety critical | Waterfall |
| Requirements likely to change, customer available | Agile |
| Large project with significant risk | Spiral |
| Interface heavy with uncertain user needs | Rapid application development |
| Code quality is paramount and budget allows | Extreme programming |
The marks are for linking the choice to something specific in the question, such as an unavailable client, a regulatory requirement or requirements that are certain to change.
- Waterfall: each stage is finished before the next begins. Clear, but inflexible.
- Agile: short cycles with working software each time. Flexible, but needs the customer.
- Extreme programming: pair programming, tests first and tiny releases.
- Spiral: repeated turns with risk analysis each time. Good for large, risky projects.
Key terms you must be able to define
- Lexical analysis
- The first stage of compilation, converting source characters into tokens and building the symbol table.
- Token
- A categorised unit of source code such as a keyword, identifier or operator.
- Symbol table
- A structure holding identifiers and their attributes, built during compilation.
- Syntax analysis
- Parsing tokens against the grammar of the language to build an abstract syntax tree.
- Abstract syntax tree
- A tree representing the structure of a program, produced by syntax analysis.
- Code generation
- Converting the abstract syntax tree into machine or object code.
- Optimisation
- Improving generated code so it runs faster or uses less memory.
- Linker
- Software combining compiled object code with the library code the program requires.
- Static linking
- Copying library code into the executable at compile time.
- Dynamic linking
- Storing a reference so the library is loaded at run time.
- Loader
- Software that copies an executable into memory and prepares it for execution.
- Waterfall
- A sequential development methodology completing each stage before the next begins.
- Agile
- Iterative development delivering working software in short cycles with continuous customer involvement.
- Spiral
- An iterative methodology with explicit risk analysis in every cycle.
Flashcards
Say the definition out loud before you flip the card. Retrieving it from memory is what builds recall, reading it again is not.
Reach the top grade on this topic
- Name all four stages of compilation in order and say what each produces
- Explain the symbol table as built during lexical analysis and used throughout
- Compare static and dynamic linking on file size, updates and dependency
- Justify a methodology against something specific in the scenario, not in general
- Give both a strength and a weakness for every methodology you name
Mistakes that cost marks here
- Giving compilation stages out of order, or omitting optimisation.
- Saying agile has no documentation. It has less, which is a genuine maintenance trade off.
- Saying waterfall is simply outdated. It remains correct where requirements are fixed and must be documented, as in regulated industries.
- Confusing the linker with the loader. The linker combines code, the loader puts it into memory.
- Recommending a methodology without referring to anything in the scenario.
A compiler makes several complete passes over your source code before producing anything. Lexical analysis, syntax analysis, semantic analysis, optimisation and code generation each look at the whole program in a different way.
Knowledge check
Exam-style questions
Five written questions in the style of the real paper. Write a full answer, then let the marker check it against the mark scheme.
- LLexical analysis groups characters into tokens
- LWhitespace and comments are removed and the symbol table is created
- LSyntax analysis parses tokens against the grammar of the language
- LAn abstract syntax tree is produced and syntax errors are reported
- LCode generation converts the tree into machine or object code
- LOptimisation improves the code so it runs faster or uses less memory
Compilation begins with lexical analysis, in which the source is read character by character and grouped into tokens representing keywords, identifiers, operators and constants. Whitespace and comments are discarded because they have no meaning to the compiler, and identifiers and constants are recorded in the symbol table along with attributes such as type and scope. Syntax analysis then parses the stream of tokens against the formal grammar of the language, building an abstract syntax tree that represents the structure of the program, and reporting a syntax error for anything that cannot be fitted to the grammar. Semantic checks such as type compatibility and the use of undeclared identifiers are also carried out at this point. Code generation then walks the abstract syntax tree and produces the equivalent machine code or object code. Finally the optimisation stage improves that code, for example by removing instructions whose results are never used, moving calculations that do not change out of loops, and allocating registers more efficiently, so that the finished program runs faster or occupies less memory.
- LStatic linking copies the library code into the executable at compile time
- LThe executable is larger but self contained
- LDynamic linking stores only a reference and loads the library at run time
- LThe executable is smaller and library updates apply automatically, but a missing library breaks it
Static linking copies the machine code of every library subroutine the program uses directly into the executable file at compile time. The result is a larger file, and identical library code is duplicated across every program that uses it, but the executable is entirely self contained: it will run wherever it is placed and cannot be broken by a later change to the library. Dynamic linking instead stores only a reference to the library, which is located and loaded into memory when the program runs. Executables are therefore much smaller, one copy of the library serves every program on the system, and a security fix or improvement to that library benefits all of them without any of them being rebuilt. The trade off is a run time dependency: if the library is missing, or has been replaced by an incompatible version, the program will fail to start or behave unpredictably.
- LRecommends the waterfall methodology
- LThe requirements are fixed and fully known in advance
- LWaterfall completes each stage fully before the next begins
- LIt produces thorough documentation at every stage, which regulation demands
- LIts inflexibility is not a problem because the requirements cannot change
- LNotes that a methodology such as agile would produce insufficient documentation for approval
The company should use the waterfall methodology. Its central weakness, inflexibility in the face of changing requirements, does not apply here because the requirements are fixed by regulation and cannot change during development, so the risk of an expensive late revision is minimal. Waterfall's sequential structure, completing analysis, design, implementation, testing and evaluation fully in turn, produces a formal signed off deliverable at the end of each stage, and this is precisely what a regulator needs: a complete audit trail demonstrating that every requirement was specified, designed for, implemented and tested. In a medical device context this documentation is not overhead, it is a legal necessity, and its absence would prevent approval regardless of how good the software actually was. An agile approach would be a poor fit here even though it is often preferable elsewhere. Agile deliberately produces lighter documentation and expects requirements to evolve through customer feedback, neither of which is appropriate when the specification is externally imposed and immutable. Its strength, responding rapidly to change, has no value in this project. The one adjustment worth making is to include rigorous verification within each waterfall stage rather than leaving all testing to the end, since defects found late in a safety critical system are extremely expensive to correct.
- LDevelopment time is reduced because the code does not have to be written
- LThe developer can concentrate on the parts specific to their application
- LLibrary code is widely used and tested, so it is more reliable
- LSpecialist areas such as cryptography are extremely difficult to implement correctly
The first advantage is development speed. A library provides subroutines for common tasks such as sorting, mathematical functions, file compression or network communication, so the developer does not have to write, debug and document that functionality themselves and can concentrate on the parts of the system that are specific to their own application. The second advantage is reliability. Library code has typically been used by very large numbers of developers over a long period, so defects have been found and corrected in a way that newly written code cannot match. This matters most in specialist areas such as cryptography, where a subtly incorrect implementation may appear to work perfectly while being completely insecure, and where writing it yourself is almost always the wrong decision.
- LWaterfall is sequential with each stage completed before the next
- LAgile is iterative, delivering working software in short repeated cycles
- LWaterfall produces extensive documentation at every stage
- LAgile involves the customer continuously and adapts to changing requirements
- LWaterfall handles change poorly and shows the client nothing working until late
- LAgile can be harder to cost and schedule and produces lighter documentation
Waterfall is a sequential methodology in which analysis, design, implementation, testing and evaluation are each completed and signed off before the next begins, producing a full set of documentation at every stage. Agile is iterative: the project is divided into short cycles, each of which delivers a working increment of the software, and the customer reviews that increment and influences what is built next. This produces two very different profiles. Waterfall gives strong control and a complete audit trail, which suits projects where the requirements are fixed and where regulators or contracts demand documented evidence, but it handles change extremely badly, because altering a requirement after design is complete means revisiting earlier stages at considerable cost, and the client sees nothing that actually runs until very late in the project. Agile handles change as a normal part of the process rather than an exception, and because working software is delivered early and frequently, misunderstandings about requirements surface within weeks rather than months. Its costs are that it demands continuous customer availability, which many organisations cannot provide, that the final cost and delivery date are much harder to predict at the outset, and that its lighter documentation can make the system more difficult to maintain years later when the original developers have moved on.