There are no universal notations, methods or techniques for software engineering. -This is because different types of software require different approaches.
- -There are cases where software projects or software can fail.
- -As new software technology helps us to build bigger, more complicated systems, the requirements change.
- -Systems need to be developed and delivered faster meaning more complicated systems are required. -This means more requirements for the systems.
- -It is easy to develop programs without using software engineering techniques… BUT -This can result in more expensive software development and less reliable, readable systems. -To solve this issue, more education and training is required on these techniques.
- -This is where the clients and the developers define the software that should be produced. -This is where the software is limited in terms of what is should be.
- -This is where the software is designed and programmed.
- -This step ensures that the software does what the client requested.
- -When software is modified to meet client’s or the market’s new requirements.
- -A software process model is a set or related activities that leads to a software product. -An abstract descriptions of high level software processes. -These can be used to explain different approaches to software development. -These can be interpreted as frameworks that can be expanded and personalized to create more specific software engineering processes.
- -The model takes the fundamental software process activities. -Seperate process phases: -- Requirement specification -- Software design -- Implementation -- Test
- -This approach combines the activities with specification, development and validation. -The system is developed in a series of versions (increments) -Each version adds some functionality on top of the previous version.
- -This approach depends on the availability of reusable components or systems. -The systemdevelopment process focuses on configuring these components to be used in new contexts and integrate them with the system. -This lets you reuse code from previous projects and save time and money.
- -Activities are done in a sequence. -Handover of workproducts between phases and milestones are used to monitor progress. -Waterfall model is an example of a plan-driven process. -You are supposed to have all of the process activities and phases planned out before you start development. -The phases in the model directly reflect the fundamental development activities.
- -The systems services, limits and goal and made concrete through consulting with the users. -They are then defined in detail and are used as the system specification.
- -The overall system architecture is established in this phase. -Identify and describe the fundamental system abstractions and their relations (UML)
- -The design is implemented in the indivivual program parts. -The design is tested to verify that it meets the specification.
- -The individual program parts are integrated and the whole system it tested. -The software is delivered to the client.
- -The system is now installed and in use. -The system is maintained to any issuse that weren’t found earlier. -The system is improved over time.
- -For software that needs to be flexible while it is being developed.
- -The software must interface with hardware. -In this case the hardware is not flexible, thus the software must be.
- -When total security is a requirement of the specification and design. -These systems must have finite specifications and design documents.
- -Part of a larger system being developed by several parties. -This makes finite specifications extremely necessary.
- -When one phase ends another begins. -Steps come ordered and don’t allow for going back and redoing parts. (waterfall flows only down) -When the requirements are mostly unchanging.
- -Activities in sequence versus all activities at the same time. -Agile development is very flexible and the requirements may be constantly changing.
- -You can iterate within increments and the increments can be planned. -You work within fixed time slots and update the project backlog continuously. -Incremental is an agile process, where you end with multiple versions that you can show the clients as the project progresses. -This allows for the client to come with feedback along the way.
- -Development risk is reduced by reuse but there is the risk of not being able to make the desired changes at all or in the time frame. -Most projects have some level of code reuse. -This is often informal. -This reuse requires looking for the existing code, changing them to meet the requirements and integrating them with the new code.
- -The incremental development is based on the idea that: -1. Develop in prototypes. -2. Get feedback from the users and others. -3. Develop over multiple versions until the required system is produced.
- -Incremental development is the most common approach to developing applications and software.
- -Yes, it can be either one or a mix of both.
- -Identify the system increments in advance. -A predictable waterfall plan is split into parts.
- -The early increments are identified. -The later increments depend on progress and the clients priorities. -You work in fixed timeframes and update the full project backlog as you go.
- -Focus on the individuals and teamwork rather than the processes and tools. -Good software comes before comprehensive documentation. -Work with the client instead of using contract work. -Deal with changes instead of sticking to the plan.
- -Development costs are reduced -The amount of analysis and documentation that has to be redone is much less than waterfall.
It is easier to get client feedback -The clients can comment on demonstrations of the different versions and see the progress.
Earlier delivery of new software -New features can be made available even if they are not fully completed.
The project is not visible -Managers can have difficulty measuring progress. -It would be a waste of resources to produce documents that reflect the different versions.
The system structure can get messy over time -Changes lead to messy code. -It gets increasingly difficult to add new functions to a system. -Large, complex systems with large teams struggle with incremental for this reason. -Large systems need a stable architecture. -Responsibility of the different teams needs to be clear with respect to this architecture. -This has to be done in advance.
The inital requirements are suggested -They don’t need to be developed in more detail. -They should include short descriptions of important requirements and desired functionality.
- -With the overview of the requirements, components are searched for that provide the necessary functionality.
- -The requirements are polished with the knowledge of the reusable components that were found.
- -If an application that meets the requirements is available, it is configured for use in the new system.
- -This model reduces the amount of software that must be developed. -This in turn, reduces the costs and risks.
- -You usually don’t have control of the software that is being reused. -This can include for example how and when new version are released and how the functionality is changed.
- -Plandriven means the desired result can be predicted. -Plandriven = waterfall. -Plandriven is an approach where the development process is planned in detail. -A project plan is created that registers the work that needs to done, who should do it the development plan and the work tools. -Managers use this plan to support project decisions and as a way to measure progress. -This is a traditional approach to software development.
- -Agile expects changes and frequent user inspection to get the best results. -Agile = Iterative, more detailed Scrum and XP -Agile methods are iterative, the software is developed and delivered in stages. -These versions are not planned in advance but are chosen underway. -Decisions on what should be included in a version depend on the clients priorities.
- -Goal: to handle changes in the project. -Small teams. -Environment is turbulent and fast-paced, project focused.
- -Goal: predictability, stability and security. -Larger teams and projects. -Environment: stable, few changes, organisation focused.
- -Customer relations: dedicated clients on site, focused on prioritised changes -Planning and control: qualitative control. Who and how doensn’t matter as long as it gets done. -Communications: Tacit knowledge. People do things without needing much explanation or discussion.
- -Customer relations: More formal and infrequent. Focused on contract decisions. -Planning and control: Documented plans, quantitative control. It is important to know who does what. -Communications: Explicit. Plans must be discussed and verbalized and shared with the others.
- -Requirements: can withstand unpredictability. -Development: simple design, small increments, refactoring is assumed to be cheap. -Test: Test cases define the requirements.
- -Requirements: Formal project, user interface, quality, predictable requirements. -Development: Comprehensive design, larger intervals, refactoring is costly. -Test: Documented testplans and procedures.
- -Cockburn characteristics can describe a programmers personality. -One type may be more favourable than another depending on agile/plan-driven approach.
- -As soon as the work on a task is complete, it is integrated into the whole system. -After such integration, all the unit tests must pass. -Continuous integration uses tools to automate the process. -Depends on unit tests. -Does NOT remove the need for tests.
- -Openness of all work. -Respect each other. -Focus on the common goal. -Courage for difficult decisions. -Duty to the common goal.
- -3 roles. -5 events. -3 artifacts.
- -Transparency: Everyone knows what needs to be done and who is doing what. -Inspect: Keep an eye on where we are heading (daily meetings). -Adapt: Change if it is necessary.
- -Commitment: to reach the sprint goal. -Focus: on what needs to be done in the sprint. -Openness: Communication is key, don’t hide issuse. -Respect: for each other -Courage: to do the right thing
- -Scrum master is a manager. -No communication with the client. -New tasks are added to the sprint backlog in the middle of a sprint.
- -Inspect progress towards the sprint goal. -Adjust the backlog accordingly. -Update (how far are we?) -Short meeting (15 min) -Tell the others if you need help.
- -Work together with the whole SCRUM team for sprints. -Look in the backlog. -Make a sprint backlog. (this can’t be changed from the outside)
- -Check development status. -Sprint review max 4 hours with sprints of 4 weeks. -The client participates along with the team. -Only talk about what has been done. -Dialogue, no presentation. -Update the backlog.
- -For increasing quality and effictivity. -What went well/bad? -How can this be improved for the future?
- -Stakeholder contact -Updates/prioritises the product backlog -Can be a person dedicated to the client -The goal is the maximise product value -Can delegate but is responsible
- -Ensure everyone is keeping in-line with SCRUM -Not the management leader -Ensure the team is effective -Deal with the teams blockages
- -They own the backlog -Programmers, UI, UX and so on
- -An agile, incremental development method with focus on: -- Collaboration -- Quick and early software creation -- Skillfull development practices -XP takes all the ‘good things’ the extreme. (testing, pair programming).
- -The customre should be available full time for the use of the XP team. -In XP, the customer is a member of the dev team and is responsible for bringing requirements.
- -Pair programming: developers work in pairs, checking each other’s work to ensure quality.
- -Pair-programming. -Writing unittests before the code (with the help of TDD). -Partners often have to integrate their code (use continuous integration). -Refactor as often as possible. -Collective ownership of code. -Customer on-site, user stories, planning game, …
- -Work should be done incrementally/iteratively. -Teamwork, transparency, communication and prioritisation are crucial. -Requirements are broken down into bite-size pieces. -There is overlap with the roles. (XP client and SCRUM’s product owner)
- -Communication, simplicity, feedback, courage.
- -Pair programming -Customer on-site -Acceptance test -Daily standup (short meetings)
- -Teams implement exactly what was asked for. Nothing more. -Strive for simple designs and quality code.
- -Early and frequent feedback is crucial. -Feedback can come from unittests, team members and the client. -Continuous integration. -Acceptance test that the client performs. -Short sprints.
- -Developers should be honest. -Don’t make excuses for issuse. -Don’t be afraid to make big changes.
- -E.g. If tests are good, do them all the time. -Takes all good things, and places them at the core of the process.
- -Unit test, pair review, customer on-site, continuous integration, testing, early test, unit test, TDD.
- -Brief feature request, a promise for conversation. -Written on a card with criteria for confirmation on the back.
- -To see the bigger picture of the user stories. -To understand how things are now and to imagine how they could be. -Visualize the stories you tell about your software.
- -Story maps consist of: -* User - - a card that tells a story about a type of person, doing something to reach a goal. -* Activities - - Jobs done by similar people to reach a time -* Backbone - - Activies and jobs on a higher goal tier, give the user story structure. - - This is a big goal, that the little goals are attached to. -* User tasks - - Short, concise sentences that explain the goal. -* Sub-tasks - - Break down more complicated goals. -* Release slices - - Identify tasks. The smallest number of tasks that allow specific users to reach their goal.
- -Story map process has 4 levels
- -“As a
Exploration, planning, iterations to first release, productionizing, maintenance.
- -Iteration
- -Elicitation and analysis of needs. -Specification of requirements. -Validation of requirements.
- -There are two fundamental approaches to Requirement Elicitation: -1. Interview, where people talk about what they are doing. -2. Observation or etnography, where you observe how people do their work and which technologies they use and so on.
- -Use a mix of interview and observation to gather information. -This can be used to find the requirements that form the basis of further discussion.
- -Is a process in which you write down user and system requirements into a document. -Ideally, these requirements should be clear, consistent, complete and easy to understand. -User requirements should be written in natural language and supplemented with dialogue and tables in the document. -System requirements can also be written in natural language, but other notations, graphs, maths, etc can also be used. (state machines, automata)
- -Is the process of controlling of ensuring that the system requirements will are really what the client wants. -There are different checks that can be used to validate the requirements.
- -Validity checks: -Check if the requirements reflect the users real needs. -User needs can change over time, so this is an important thing to keep track of.
Consistency checks: -Requirements should not conflict with others.
Completeness checks: -The requirement specification should be comprehensive for every function and the limits that the client wants.
Realism checks: -Using knowledge on existing systems, control the requirements to ensure that they fit within the budget and time-frame.
Verifiability: -You should be able to create tests that verify whether or not a requirement is met.
Requirement reviews -Requirements are analyzed systematically by a team of judges, to check for mistakes or conflicts.
Prototyping -Develop executable models of the system and verify with the client that it meets their expectations.
Test-case generation -Tests can be designed along with requirements instead of after the fact. -If it is difficult to design tests for a requirement, that can mean the requirement is unrealistic.
Discovery & Classification -This is the process of interacting with the stakeholders to find their requirements.
Categorization -Take the unstructured list of requirements and group related requirements together.
Prioritization & Negotiation -Conflicts can arise when there are multiple stakeholders. -Prioritize the most important requirements, through negotiation, discussions, compromises and meetings.
Documentation -Here the requirements are documented.
Many stakeholders with conflicting needs. -Stakeholders speak their own “language”. -Lack of communication because things are assumed to be “obvious”.
- -Stories, Scenarios.
- -Waterfall: Verify the requirement specificatino with strict change management. -SCRUM: Product vision and product backlog, are discussed and updated every sprint. -Product Planning: Product vision, release plans and/or product roadmaps. -XP: User Stories.
- -Waterfall: Be up front in the requirements phase - state it now or it will be difficult later on. -SCRUM: Ongoing refinement of product backlog with stakeholders, say what is most important now, we will continue. -XP: Customer on-site.
- -User personas are a useful technique to describe users of your product. -A fictional character with a name, picture, relevant characteristics, behavior, opinions and a goal. -Different people can have different goals. -Understand a personas goal is useful for creating a product that is meaningful to the users.
- -Short description on a type of user, a goal and a reason.
- -Product Feature: Corresponds to an Epic. -Epic: A collection of related user stories. -User story: Breakdown of an Epic.
- -The experiences a person has, when interacting with the software.
- -This is to do list of items a SCRUM team must tackle. -- Software requirements. -- User stories. -- Descriptions of supplementary tasks that are needed, such as architecture definition or user documentation.
- -A risk is a potential problem. -The possibility of loss or damage. -Risk Management: project leaders must evaluate the risks that can affect a project, monitor them, and handle them when problems arrise.
- -Risks that threaten the project plan. -Time will be wasted and costs will rise.
- -Architectural design. -Arrises because problems can be harder to solve than expected. -Vagueness in the specification. -Project gets older and starts to decay.
- -Market risk. What if no one uses the product? -Strategic risk. We don’t need that new component after all. -Sales risk. How the fuck do we sell this?! -Management risk. The top management don’t support the project anymore. -Budget risks. Budget or personnel is lost.
- -Risk analysis and management are actions, that help a software team understand and handle uncertainty. -It is a good idea to identify risks. -Evaluate the probability of risks. -Estimate the impact of a risk and form a reaction plan for if the risk actually happens.
- -Risk exposure = probability * loss, describe consequence. -Probability < 100%. If p = 100% then it’s an issue.
- -Prioritize according to risk exposure, establish cut-line. -Deal with the risks above the line, accept the ones below.
- -Establish for each risk above the cut-line (RMMM: Risk Mitigation, monitor, management)
- -We want to prevent the risk from becoming an issue. -We can reduce the probability. -Or try to reduce the associated loss. -Risk exposure = probability * loss.
- -For when a risk has become a loss, try to minimize the loss. -This assumes the mitigation activity was unsuccessful. -This is done by the project leader.
- -Observe how risks change over time. -How the probabilities, loss, or the environment, change over time.
- -Risk and risk plans are part of the plans in project management. -Development of others plans to contribute to identification of risk. -It is planned.
- -Daily SCRUM: Do you have any impediments? -Sprint review: Inspects risk related to product and stakeholder. -Sprint retrospective: Adresses risks related to how the team works.
- -Personal shortcomings, unrealistic schedule, wrong function…
- -Safety, security, reliability, complexity, adaptability, testability, understandability, efficiency, usability, etc…
- -Quality is evaluated aesthetically, symbolically and functionally -Quality can be either objective or subjective. -Quality may not always be obvious.
- -Quality is a reflection of one or more peoples evaluation of the compliance of a product or service with their expectations. -Quality can be broken into three types of categories: -1. Product quality. -2. Process quality. -3. Quality of expectations.
- -Quality tradeoffs are unavoidable. -Quality consists of: -- Quality assurance: plan or design processes to prevent bad quality. -- Quality control: track that work products meet quality standards.
- -Cost of not doing it is bad quality - fixing errors.
- -Direct cost of error correction: -- Loss. (effort) -- Wasted work. (for users of the program) -- Maintenance usually has larger costs than development.
- -Indirect cost of error correction -- Follows from poor quality (unsatisfied users) -- Has potentially severe consequences (losing customers)
- -Quality Management reduces these costs significantly.
- -Are we building a system that is fit for use? -Compliance with the users expectations and experiences?
- -Do we pass all tests and requirements? -Are we building a system with all the requirements implemented? -Unit/integration tests
- -Testing: of programmes and prototypes. -Review: of specifications, documentation and programs.
- -A user must participate in order to validate. -Verification focuses on the compliance to the specifications and a client usually doensn’t participate.
- -Tests are a set of practices that support verification and validation. -The purpose is to ensure a program does what it is supposed to, and to discover errors before delivery. -This is done by making sure the progrm meets the requirements and by finding incorrect or undesirable behaviour. -Verification: Unit test, component test. -Validation: prototype test, user acceptance test.
- -Evaluation of work of one or more people with similar skills (peers). -Mostly in the form of documents but can also be analysis of code.
- -Review is static, and there is no interaction between errors found in review. -Tests are dynamic and errors can come as side-affects of an initial errors. -Reviews (inspections) and tests are complementary to quality techniques. -Both should be used under the verification and validation process. -Inspections can control compliance with a specifications but not with the clients or users actual requirements. -(Unless the user participates in the review. Prototypes are preferred for user participation) -Inspecions cannot control non-functional properties such as performance, usability, etc.
- -For documents, designs, architectures, plans, etc.
- -For functionality and dynamic use of the program.
- -A model that shows the connection between tests at different levels and primary activities that drive the tests.
- -Unit test, component test, integration test, system test, user acceptance test.
- -Unit test: confirm valid and invalid input. -Integration test: confirm that interfaces are compatible and work as expected. -Acceptance test: validate fit for use, exploratory test.
- -Plan driven: in the end (often a dedicated test-team aspart of QA) -Agile: all the time (test competence on the team, accept criteria on story, automated test, TDD)
- -DevOps is a method for both development and operation. -DevOps is a development method for IT systems that connects different activities in projects. -DevOps is a culture, that focuses on the entire software productions life cycle. -The goal is to remove barriers between development and operation teams, to be able to react quickly to the users needs. -It is also defined by The Three Ways: -1. Flow. -2. Feedback. -3. Continuous Learning.
- -When the code is checked, it is automatically integrated with the system. -Speed up the rate of delivery and run tests constantly. -Bsed on tools to automate the process. -Depends on a suite of unit tests. -Does NOT eliminate the need for testers.
- -Continuous Testing in DevOps is a type of software test that involves testing at all stages of a develoments lifecycle. -The goal is the continuously evaluate the quality of the software.
- -Ensure that code can be implemented securely. -Ensure that the business and service application function as expected and deliver every change to production.
- -Ensure that tests are automated and that every change is automatically implemented in production. -Makes the development and release process faster and more robust.
- -Automated access to well defined environments. -Tools like Docker for containerization or Virtual Machines.
- - - - - - diff --git a/dst/game.html b/dst/game.html deleted file mode 100644 index be81007..0000000 --- a/dst/game.html +++ /dev/null @@ -1,64 +0,0 @@ - - - - - - - --- -7th May 2021 — hello world!
-
Aftershock (working title) is a multiplayer old-school arena shooter being made in Unity. It’s a hobby project that I have been working on since 2016. It started as a warmup project before jumping into developing an MMO, but I have since learned how much work goes into making just a multiplayer fps. Especially as a solo project.
- -At it’s core, Aftershock is supposed to be my attempt at recreating a mix of Quake 3 / Quake Live along with whatever else I decide to add.
- -Main features (so far):
- -I’m in the process of rewriting a lot of systems in the game at the moment because I’m switching from janky p2p multiplayer to an authoritative server setup with client-side prediction (more).
- -➤ Gameplay clips
-➤ Follow my progress
Hello there!
- -My name is Adam and I am a computer nerd studying at Aalborg University. I am interested in space, game dev, sailing and the outdoors.
- -I’m currently working as a student developer at E-Komplet and I work on my multiplayer old-school arena shooter in my free time. I occasionally post videos of my game along with other stuff here.
- -Most important problem in computing : increasing programmer productivity -to improve speed of software release.
- -This can be improved with:
- -Example: - Quicksort is twice as much code in C than Haskell
- -This can be more readable
- -You can gain deeper understanding of programming through learning about compilers.
- -Programming has evolved over time because different programming languages can be desinged for different types of programs.
- -We are in the “multi-paradigm era”, Anders Hejlsberg says languages in of the future will be a mix of all existing paradigms.
- -Programming language characterstics can be broken down into readibility, writability and reliability.
- -Static / dynamic typed languages end up with the same amount of time spent debugging. The only difference is where that time is spent.
- -Programming languages are languages with no ambiguitity and vagueness. Everything is exact. A sentence means one thing or it means nothing.
- -Programming languages require specification. Example: C# docs. Syntax needs to be specified, scope rules, type rules, semantics (or runtime semantics).
- -Types of specification: -- Formal: Precise, mathematical -- Informal: description in English -- Usually both
- -Language specification consists of: -- Syntax, usually formal -- Contextual constraits - - Scope rules (English / formal) - - Type rules - - Semantics
- -Syntax is the visible part of the language. The paradigm is the next most visible. Most invisible part is the language semantics. But clear semantics usually means simple and efficient implementations.
- -Yes. Syntax matters.
- -Take source code and input and produces output. For example, web browser.
- -A 2-step process. Source program is inputted to compiler and a new program target program is outputted from the compiler. However this is much more complicated. Lexical-, syntax-, semantic analysis, code generation (IL)?. Sometimes you may generate high-level code. For example, taking source and converting it to C code.
- -Phases: -- Syntax analysis -> Error reports | AST -- Contextual analysis -> Error reports | DAST -- Code generation (Semantics) -> Object code
- -Symbol tables can be accessed from several phases.
- -Compiler design is strong affected and strong affects programming language design. Advantages of good compiler: easier to learn, read, understand. Fewer bugs. More reliable. More diagnostic messages and tools.
- -There are tools to help write compilers (compiler generators/ compiler compiler)
- -Most new languages are invented out of frustration. When a new language is created it tends to be because it would be an improvement over some existing language. For example, Fortran was invented to improve programmer productivity.
- -The programming language critera table can be used to generate ideas for or evaluate a language’s design. Reusability and relocatability of code has become a more and more important criteria over time.
- -40-50s: Assembly languages made programming more readable more usable. Came with a compiler that could translate assembly to machine operations.
- -50s: Fortran was invented, first high-level language. Now programs could be developed machine independant.
- -60s: Programming paradigms started taking over. Structured programming. Pascale: No GOTO, Types. OOP.
- -70s: C invented for high-level programming with low-level power. Ada invented as a means to avoid using hundreds of different programming languages. Functional programming starts off.
- -80s: OOP really takes over. C++ invented (thought of as C with classes). More discussion about functional programming.
- -00s: Distributed systems. C# + .Net CLR (common language runtime system).
- -10s: Multi-paradigm (OO + FP)
- -A notation consisting of puzzle pieces that can be used to reason about language processors and programs.
- -These can be combined to give a general diagram of some source to target language scenario.
- -Bootstrapping can be used as a way to generate more efficient compilers.
- -Phases: -- Syntax analysis -> Error reports | AST -- Contextual analysis -> Error reports | DAST -- Code generation (Semantics) -> Object code
- -The phases can be seen as the transformation steps for transforming some source code into object code.
- -Modern compilers all make use of symbol tables. This can generally be used in any phase of compilation but it is now best practice to only access it from type checker / contextual analysis.
- -Scanner/Lexer phase takes input source code and produces a stream of tokens. Tokens have and type and value.
- -Parsing phase is used to determine if the stream of tokens conforms to the languages grammar specification. This phase either produces an AST or returns errors.
- -Contextual analysis for checking the semantics. A symbol table is used to process declarations and to check for type consistency.
- -Symbol table is generally just a key-value list.
- -Type checking: check each node and ensure child nodes are consistent with their types. For example adding an int to a float. The compiler must specificy what to do in this case.
- -Code generation: formulation of target-machine instructions that represent the semantics of the source program.
- -A simple language for arithmetic. Monolithic scope, meaning a variable can only be declared once. Target of translation: dc (desk calculator)
- -Example ac program:
- -f b // float b
-i a // int a
-a = 5
-b = a + 3.2
-p b // print b
-A set of production rules for a language. Two types of symbols: terminals and non-terminals. Terminals cannot be rewritten (id, num, etc). Non-terminals are rules like (prog, scope, etc).
- -A syntax tree / parse tree can be used to show the production rules of some source code in a tree structure.
- -For specifying tokens. For example: id, num, “+”, “-”, etc.
- -A communication device between people who need a common understanding of the programming language or PL. For example, the language desinger, implementor, user, etc.
- -What should be specified? Syntax, contextual constraints or static semantics (scope/type rules), semantics (runtime semantics).
- -How is a language specified? -- Formal: Precise, mathematical -- Informal: description in English -- Usually both
- -A language specification needs to address: -- Syntax - - Token grammar: Regular expressions - - Context free grammar: BNF EBNF -- Contextual constraints - - Scope rules (static semantics) - - Often informal - - Type rules (static semantics) - - Informal or formal -- Semantics (dynamic semantics) - - Informal or formal
- -Syntax is specified suing a CFG. - - a finite set of terminals (tokens) - - a finite set of non-terminals - - a start symbol - - a finite set of production rules
- -Usually CFG are written in BNF notation. Example:
- -N ::= a
-N ::= a | B | ...
-Note: non-terminals are often enclosed with angle brackets. Example:
- -<N> ::= a | <B> | ...
-<B> ::= ...
-In BNF, syntactic lists are described using recursion.
- -This is where you take some source code and you step through the CFG with it to see which rules are rewritten to deeper rules, until you get the end result. This can also be represented as a parse tree.
- -Leftmost derivation (from left to right) and rightmost derivation (from right to left).
- -Leftmost derivation always choses the leftmost possible non-terminal and vice-versa for rightmost derivation.
- -A grammar is ambiguous if a string (sentence) can be defined by more than one different parse trees. Ususally ambiguity is undesirable and CFGs are rewritten to disallow this behaviour. This rewritting process can be done systematically.
- -A ‘dangling-else’ problem can be a sign of ambiguity in a language.
- -A non-standardised extension to BNF notation.
- -EBNF can also be rewritten to standard BNF fairly easily.
- -N ::= N ...N ::= ... Nexpression ::= λX Y | X Z is transformed to X (Y | Z)N ::= X | N Y becomes N ::= X Y*Parsing is finding the structure in a stream of tokens. This is done by the parser.
- -Two well known ways to parse: -- top-down (Leftmost derivation / LL), constructed in pre-order. -- bottom-up (Rightmost derivation in reverse / LR), constructed in post-order.
- -The set of all terminal symbols, in order, derived from a sentence S. The empty string λ is never included.
- -The set of terminals that can follow a non-terminal A, where the EOF symbol is $.
- -The scanner/lexer is what reads through source code character by character and divides them into lexemes and tokens. This includes whitespace which can have meaning for languages like Python.
- -A Java implementation of a scanner will normally return instances of a Token class, containing a ‘kind’ and ‘spelling’. Some tokens, like floats, ints, etc, have one single spelling so in some cases spelling can be left blank.
- -How do we know how to implement a scanner? Read the language specification. Included in the specification is typically tokens/lexemes as regular expressions and reserved words.
- -Lexem structure can be more detailed for example allowing escaping characters in strings or allowing a null string. Another example would be 0.1 vs 00.1 or .1, 10. vs 1..10 and so on.
- -The audience of your PL matters for lexical design, for example if target audience are C programmers they will prefer curly braces over begin-end keywords. It is a good idea to keep your design simple though.
- -It is generally better to use regular expressions instead of production rules where possible. Regular expressions are typically easy to implement. REs can be implemented by finite state machines (FSM). These automatas can then be easily implemented in code and as such make the job of implementing a scanner/lexer a little easier.
- -Express the ‘lexical’ grammar as RE. Sometimes it is easier to start with (E)BNF and do the necessary transformations.
For each variant use a switch on the first character by peeking the input stream.
For each repetition (..)* use a while loop that keeps going as look as the peeking input yields an expected character.
If there are multiple REs then use a switch to determine which rule is being recognized before following steps 2-3.
Something about REs and the different types of FAs are equivalent. -There is an algorithm for transforming NDFA with epsilon into DFAs. DFAs are easily implementable by computers.
- -A scanner generator a program that takes tokens as REs and will generate a scanner based on a FAs in whatever language. JLex/Lex/CSharpLex are tools for generating a scanner that recognizes tokens.
- -Performance of scanners is important for production compilers. Size of scanner sometimes matters. Note: modern scanners use explicit control, not table, because bigger tables may perform worse on modern architectures.
- -The job of the syntax analysis, is to read to source text and determine it’s phase structure. -This can be used to construct the AST. The input to the scanner is the stream of characters which output a stream of tokens to the parser or reports errors. The parser produces the AST or reports errors again.
- -Top down parsing example of “Micro English”. This is always done with left derivation.
- -Sentence Verb Object .
-The Noun Verb Object .
-The cat Verb Object .
-The cat sees a Object .
-The cat sees a Noun .
-The cat sees a rat
-This is equivalent to the parse tree that would be produced from the sentence. So Top down is a straight-forward parsing algorithm. The parse structure corresponds to the set of procedures.
- -Each non-terminal will have a parse method. There will also need to be a method that asks for the next token. This function will either return the this token or give an error in the event of an unexepected token.
- -private void parseSentence() {
- parseSubject();
- parseVerb();
- parseObject();
- accept('.');
-}
-This is a little more involved when there are alternatives. This can be implemented using if-elseif or a switch structure that checks for the alternatives.
- -Foreach non-terminal in the grammar, create a parse method. Parsing a terminal just uses the ‘accept’ method. Parsing of non-terminals is just method calls to those non-terminal’s parse methods in order. If there are repetitions, (0 .. more) you use a while loop. As long as the current token is in the first set, you keep parsing it. Use a switch case of if-else for alternatives.
- -For systematic development of a RD parser: 17:36 in video 7. This process is so mechanical that there are tools for doing this. These are known as parser generators. One tool JavaCC is based on LL(k) grammars so you can specify how many symbols it should look at at once. This allows for fine control when parsing.
- -If we want the parser to return an AST each of the parse methods should return their little bit of the AST instead of void. (Think of our visitor methods).
- -For OOP the visitor pattern enbales the definition of a new operator on an object structure without changing classes of the objects.
- -A grammar which can be parsed with a top-down parse with a lookahead (in the input stream of tokens) of one token.
- -Lecture 7 @ 32:00 for formal definition of LL(1) grammar.
- -A table is generated that simulates the way the regular parser’s stack works. This presumably doesn’t consume as much memory as a traditional parser’s stack. The table is constructed with non-terminals and the lookahead terminals. The table tells which rule to use in the grammar. 49:00 Lecture 7. ANTLR an example of a Java parser generator, that allows LL(*) grammars and is table-driven.
- -LR languages are more powerful than LL. -- LR(0), SLR(1), LALR(1), LR(k) grammars. -- Can handle left recursion. -- Usually more convenient because less need to rewrite gramamr. -- Most commonly used for parsing methods in automatic tools today.
- -Read through every construction and recognize it at the end. 13:00 Lecture 8.
- -There are tools that can automate generating the bottom up parser. 50:00 Lecture 8.
- -uwv to uAv if A -> w is a production.This is how bottom up parser work. They have a stack and a table of operations. This can also be represented as a knitting game.
- -All bottom up parsers have a similar algorithm: 22:00 Lecture 8 -- A loop with these parts: - - Try to find the leftmost parse tree which has not yet been constructed but all whose children have been constructed. - - This sequence of children is called a handle. - - This sequence of children is built or shifting elements on a stack - - Construct a new parse tree node. - - This is called reducing.
- -The only difference in the bottom up algorithms is how they find a handle. -If there is an empty state in the lookup table, we know we have an error.
- -How is the parse table built? The table is coded as a DFA (28:00 Lecture 8).
- -This algo doesn’t always work. A LR(0) conflict is a situation (DFA state) in which there is more than one possible action for the algo. There are two kinds of conflicts: -- Shift-reduce: can’t decide between shift or reduce. -- Reduce-reduce: can’t decide between two or more reductions for different grammar rules.
- -This is when you can either shift or reduce. This is a sign that the grammar is not LR(0). -There are tools that can be used to input a grammar and output what kind of grammar it is.
- -SLR(1) looks at the symbol after the handle (follow set). This means fewer reduce-actoins and therefore removes a lot of potential conflicts.
- -While SLR just uses the follow set for each production. LR(1) looks at the follow set for each handle. This gives even more reductions. LR(1) parse tables are very big. Expensive but almost all common languages are LR(1).
- -A variant of LR(1) that gives smaller parse tables. This is done by combining some states in the parse tree. In practice most practical languages are LALR(1).
- -Parsing conflicts are commonly caused by ambiguous grammars. In practice, these ambiguities are solved using a resolution rule however this may or may not do what you want (fx: dangling-else).
- -Parsing conflicts must be fixed. You cannot rely on the resolution rule.
- -Like a parse tree but with some details omitted.
- -Semantic actions and values 5:00 Lecture 9. -Synthesized and inherited attributes.
- -AST must be concise and sufficiently flexible. AST is typically constructed bottom up. Lists of siblings are typically generated by recursive rules.
- -It should be possible to unparse an AST (reconstruct the source from an AST).
- -Single-pass makes a single pass over source text, parsing, analyzing, and generating code all at once. This means that the contextual analyzer and code generator are called from the parser implementation.
- -Multi-pass makes several passes over the program. This is the modern approach. The output of a preceeding phase is stored in a data structure and used by subsequent phases. This is more readable and maintainable as the code is more broken down into independant modules.
- -35:00 Lecture 9.
- -Identification and type checking are combined into a depth-first traversal of the AST.
- - - - - - diff --git a/dst/styles/style.css b/dst/styles/style.css deleted file mode 100644 index e0bac34..0000000 --- a/dst/styles/style.css +++ /dev/null @@ -1,113 +0,0 @@ -:root { - --bg: #f3f3f3; - --fg: #181a1b; - --link: #006697; - --code: #e8e8e8; - --footer: #828997; - --home-link: #c02c38; - --quote-border: #c678dd; - --theme-toggle: #4078f2; -} - -.dark-mode { - --bg: #282c34; - --fg: #c8ceda; - --link: #56b6c2; - --code: #363a45; - --footer: #828997; - --home-link: #e06c75; - --quote-border: #c678dd; - --theme-toggle: #f9e2af; -} - -body { - background-color: var(--bg); - color: var(--fg); - font: 1em/1.8 'Open Sans', sans-serif; - margin: 0 auto; - max-width: 50em; - padding: 0em 1em; -} - -header { - overflow:hidden; - margin-top: 1em; - font-size: 2em; - color: var(--footer); -} - -.nav-left { - float:left; -} - -.nav-right { - float:right; -} - -footer { - margin-top: 3em; - margin-bottom: 1.5em; - text-align: center; - font-size: 0.95em; - color: var(--footer); -} - -a { - color: var(--link); - text-decoration: none; -} - -a:hover { - text-decoration: underline; -} - -pre > code { - display: block; - padding: 10px 15px; - white-space: pre-wrap; - line-height: 1.4em; -} - -pre, code { - font-family: 'Fira Code', monospace; - font-size: 0.98em; - /* color: var(--fg); */ - background-color: var(--code); - border-radius: 5px; -} - -code { - padding: 3px 5px; - white-space: nowrap; -} - -p img, table { - max-width: 100%; -} - -img { - display: block; - margin-left: auto; - margin-right: auto; -} - -blockquote { - background-color: var(--code); - border-left: 5px solid var(--quote-border); - border-radius: 5px; - margin: 0em 1em; - padding-left: 1em; -} - -.homepage-link { - color: var(--home-link); -} - -#darkmodetoggle { - color: var(--theme-toggle); -} - -#darkmodetoggle:hover { - cursor: pointer; - text-decoration: none; -} -- cgit v1.2.3-70-g09d2