diff options
| author | Adam <adam.moloney.stuck@gmail.com> | 2022-04-23 19:15:16 +0200 |
|---|---|---|
| committer | Adam <adam.moloney.stuck@gmail.com> | 2022-04-23 19:15:16 +0200 |
| commit | 0ed4646ee7f469352762771d5e04d931c27ce5ad (patch) | |
| tree | cd09a97630ffaec95e7d4e0098c172679e0fbc0a /dst/SPO notes.html | |
Populating repo
Diffstat (limited to 'dst/SPO notes.html')
| -rw-r--r-- | dst/SPO notes.html | 670 |
1 files changed, 670 insertions, 0 deletions
diff --git a/dst/SPO notes.html b/dst/SPO notes.html new file mode 100644 index 0000000..178a9cb --- /dev/null +++ b/dst/SPO notes.html @@ -0,0 +1,670 @@ +<!DOCTYPE html> +<html> +<meta charset="UTF-8"> +<meta name="viewport" content="width=device-width, initial-scale=1.0"> + +<title>Exam — adamski.wtf</title> +<link rel="icon" type="image/png" href="favicon.png"> +<link rel="stylesheet" href="styles/style.css"> + +<p class="header"><a href="/">adamski.wtf</a></p> +<h1 id="Exam">Exam</h1> + +<ul> +<li>15 minute video presentation</li> +<li>1 hour to record</li> +<li>Chosen subject appears on digital exam</li> +</ul> + +<h1 id="Language%20processors">Language processors</h1> + +<p>Most important problem in computing : increasing programmer productivity +to improve speed of software release.</p> + +<p>This can be improved with:</p> + +<ul> +<li>Software process (eg: AGIL) about 20% increase</li> +<li>Good tools 10%</li> +<li>Better programming language design immense increase</li> +</ul> + +<p>Example: + Quicksort is twice as much code in C than Haskell</p> + +<p>This can be more readable</p> + +<p>You can gain deeper understanding of programming through learning about compilers.</p> + +<h2 id="Programming%20languages">Programming languages</h2> + +<ul> +<li>Set of rules to tell a computer what operations to perform</li> +<li>For communicating an algorithm</li> +<li>Linguistic framework</li> +<li>Symbols, words, rules of grammar, rules of semantics</li> +</ul> + +<h3 id="Why%20are%20there%20so%20many%20programming%20languages?">Why are there so many programming languages?</h3> + +<p>Programming has evolved over time because different programming languages can be desinged for different types of programs.</p> + +<h3 id="Types%20of%20programming%20languages">Types of programming languages</h3> + +<ul> +<li>Low level - high level 1st-2nd gen</li> +<li>Paradigms + +<ul> +<li>Imperative / object oriented 3rd gen</li> +<li>Logic / declarative (database languages) 4th gen</li> +<li>Functional / logical 5th gen</li> +<li>Reactive programming possible 6th gen?</li> +</ul></li> +</ul> + +<p>We are in the “multi-paradigm era”, Anders Hejlsberg says languages in of the future will be a mix of all existing paradigms.</p> + +<h3 id="What%20is%20a%20good%20language?">What is a good language?</h3> + +<ul> +<li>Formerly: run-time performance</li> +<li>Now: Lifecycle (ease of designing, coding, debugging, maintainance, reusability)</li> +<li>Fads</li> +</ul> + +<p>Programming language characterstics can be broken down into readibility, writability and reliability.</p> + +<p>Static / dynamic typed languages end up with the same amount of time spent debugging. The only difference is where that time is spent.</p> + +<p>Programming languages are languages with no ambiguitity and vagueness. Everything is exact. A sentence means one thing or it means nothing.</p> + +<p>Programming languages require specification. Example: C# docs. Syntax needs to be specified, scope rules, type rules, semantics (or runtime semantics).</p> + +<p>Types of specification: +- Formal: Precise, mathematical +- Informal: description in English +- Usually both</p> + +<p>Language specification consists of: +- Syntax, usually formal +- Contextual constraits + - Scope rules (English / formal) + - Type rules + - Semantics</p> + +<h3 id="Does%20syntax%20matter?">Does syntax matter?</h3> + +<p>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.</p> + +<p>Yes. Syntax matters. </p> + +<h2 id="Language%20Processors">Language Processors</h2> + +<ul> +<li>Text Editors / IDEs</li> +<li>Translators + +<ul> +<li>Compiler, assembler, disassembler, etc</li> +</ul></li> +<li>Interpreters</li> +</ul> + +<h3 id="Interpreters">Interpreters</h3> + +<p>Take source code and input and produces output. For example, web browser.</p> + +<h3 id="Compilation">Compilation</h3> + +<p>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.</p> + +<p>Phases: +- Syntax analysis -> Error reports | AST +- Contextual analysis -> Error reports | DAST +- Code generation (Semantics) -> Object code</p> + +<p>Symbol tables can be accessed from several phases.</p> + +<h3 id="Compiler%20design">Compiler design</h3> + +<p>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.</p> + +<p>There are tools to help write compilers (compiler generators/ compiler compiler)</p> + +<ul> +<li>Scanner generators + +<ul> +<li>JLex</li> +</ul></li> +<li>Parser generators + +<ul> +<li>JavaCUP, Yacc</li> +</ul></li> +<li>Front-end generator + +<ul> +<li>SableCC, JavaCC, ANTLR</li> +</ul></li> +<li>Code-generation tools</li> +</ul> + +<h1 id="Programming%20language%20evolution%20and%20tombstone%20diagrams">Programming language evolution and tombstone diagrams</h1> + +<p>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.</p> + +<h2 id="Programming%20language%20design">Programming language design</h2> + +<ol> +<li>Create ideas + +<ul> +<li>Do a problem analysis (what is the purpose?, who is this for?)</li> +<li>Take inspiration from existing languages</li> +<li>Create some example programs</li> +</ul></li> +<li>Describe/define (SS)</li> +<li>Implement (SPO)</li> +<li>Evaluate</li> +<li>Repeat until satisfied</li> +</ol> + +<p>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. </p> + +<h2 id="Programming%20language%20history">Programming language history</h2> + +<p>40-50s: Assembly languages made programming more readable more usable. Came with a compiler that could translate assembly to machine operations.</p> + +<p>50s: Fortran was invented, first high-level language. Now programs could be developed machine independant.</p> + +<p>60s: Programming paradigms started taking over. Structured programming. Pascale: No GOTO, Types. OOP.</p> + +<p>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.</p> + +<p>80s: OOP really takes over. C++ invented (thought of as C with classes). More discussion about functional programming.</p> + +<p>00s: Distributed systems. C# + .Net CLR (common language runtime system).</p> + +<p>10s: Multi-paradigm (OO + FP)</p> + +<h2 id="Tombstone%20diagrams%20-%20gravstens%20diagramer">Tombstone diagrams - gravstens diagramer</h2> + +<p>A notation consisting of puzzle pieces that can be used to reason about language processors and programs.</p> + +<ul> +<li>Program P implemented in language L (tombstone)</li> +<li>Translator implemented in language L (square tombstone)</li> +<li>Machine implemented in hardware M (shield)</li> +<li>Language interpreter in L (square box)</li> +</ul> + +<p>These can be combined to give a general diagram of some source to target language scenario.</p> + +<ul> +<li>Cross compilation: a compiler that runs on one machine, that emits code for another machine.</li> +<li>Two-stage compilation: a composition of two translators. Output of first translator is provided as input to the second. Mainly IL but can be any language.</li> +<li>Interpreters: provide better platform indepedence. Useful for testing and debugging. Typically slower than compilers.</li> +</ul> + +<p>Bootstrapping can be used as a way to generate more efficient compilers.</p> + +<h1 id="The%20ac%20language%20and%20compiler">The ac language and compiler</h1> + +<h2 id="Phases%20of%20a%20compiler">Phases of a compiler</h2> + +<p>Phases: +- Syntax analysis -> Error reports | AST +- Contextual analysis -> Error reports | DAST +- Code generation (Semantics) -> Object code</p> + +<p>The phases can be seen as the transformation steps for transforming some source code into object code.</p> + +<ul> +<li>Syntax analysis <-> Syntax + +<ul> +<li>Lexical analysis <-> Regular Expressions</li> +<li>Parsing <-> CFG</li> +</ul></li> +<li>Contextual analysis <-> Contextual constraints + +<ul> +<li>Scope checking <-> Scope rules (static semantics)</li> +<li>Type checking <-> Type rules (static semantics)</li> +</ul></li> +<li>Code generation <-> Semantics (dynamic semantics)</li> +</ul> + +<p>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.</p> + +<h2 id="Phases%20of%20a%20simple%20compiler">Phases of a simple compiler</h2> + +<ul> +<li>Syntax analysis + +<ul> +<li>Scanner/Lexer -> tokens</li> +<li>Parser: tokens -> AST</li> +</ul></li> +<li>Contextual analysis + +<ul> +<li>Symbol table: AST -> symbol table</li> +<li>Semantic analysis -> DAST</li> +</ul></li> +<li>Code generation + +<ul> +<li>Translation</li> +</ul></li> +</ul> + +<p>Scanner/Lexer phase takes input source code and produces a stream of tokens. Tokens have and type and value.</p> + +<p>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.</p> + +<p>Contextual analysis for checking the semantics. A symbol table is used to process declarations and to check for type consistency.</p> + +<p>Symbol table is generally just a key-value list.</p> + +<p>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.</p> + +<p>Code generation: formulation of target-machine instructions that represent the semantics of the source program.</p> + +<h2 id="The%20ac%20language%20(adding%20calculator)">The ac language (adding calculator)</h2> + +<p>A simple language for arithmetic. Monolithic scope, meaning a variable can only be declared once. Target of translation: dc (desk calculator)</p> + +<p>Example ac program:</p> + +<pre><code>f b // float b +i a // int a +a = 5 +b = a + 3.2 +p b // print b +</code></pre> + +<h3 id="Formal%20definition%20of%20ac">Formal definition of ac</h3> + +<ul> +<li>Syntax specification + +<ul> +<li>Context free grammar (CFG)</li> +</ul></li> +<li>Token specification + +<ul> +<li>Regular expressions (RE)</li> +</ul></li> +</ul> + +<h2 id="Context%20free%20grammar%20(CFG)">Context free grammar (CFG)</h2> + +<p>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).</p> + +<p>A syntax tree / parse tree can be used to show the production rules of some source code in a tree structure.</p> + +<h2 id="Regular%20expressions%20(RE)">Regular expressions (RE)</h2> + +<p>For specifying tokens. For example: id, num, “+”, “-”, etc.</p> + +<h1 id="Language%20specifications">Language specifications</h1> + +<p>A communication device between people who need a common understanding of the programming language or PL. For example, the language desinger, implementor, user, etc.</p> + +<p>What should be specified? Syntax, contextual constraints or static semantics (scope/type rules), semantics (runtime semantics).</p> + +<p>How is a language specified? +- Formal: Precise, mathematical +- Informal: description in English +- Usually both</p> + +<p>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</p> + +<h2 id="Syntax%20terminology">Syntax terminology</h2> + +<ul> +<li>Sentence: string of characters over some alphabet</li> +<li>Language: set of sentences</li> +<li>Lexeme: lowest level syntatic unit of a language</li> +<li>Token: a category of lexemes (e.g. identifier)</li> +</ul> + +<h2 id="Formal%20definition%20of%20languages">Formal definition of languages</h2> + +<ul> +<li>Generators: a device that generates senteces of a language.</li> +<li>Recognizer: reads input strings over the alphabet and decides whether the input strings belong to the language.</li> +</ul> + +<h2 id="Syntax%20specification">Syntax specification</h2> + +<p>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</p> + +<p>Usually CFG are written in BNF notation. Example:</p> + +<pre><code>N ::= a +N ::= a | B | ... +</code></pre> + +<p>Note: non-terminals are often enclosed with angle brackets. Example:</p> + +<pre><code><N> ::= a | <B> | ... +<B> ::= ... +</code></pre> + +<p>In BNF, syntactic lists are described using recursion.</p> + +<h2 id="Derivations">Derivations</h2> + +<p>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.</p> + +<p>Leftmost derivation (from left to right) and rightmost derivation (from right to left).</p> + +<p>Leftmost derivation always choses the leftmost possible non-terminal and vice-versa for rightmost derivation.</p> + +<h2 id="Ambiguity%20in%20grammars">Ambiguity in grammars</h2> + +<p>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.</p> + +<p>A ‘dangling-else’ problem can be a sign of ambiguity in a language.</p> + +<ul> +<li>Sometimes obvious, sometimes difficult to spot.</li> +<li>Ambiguity in grammars is an undecidable property.</li> +</ul> + +<h2 id="EBNF">EBNF</h2> + +<p>A non-standardised extension to BNF notation.</p> + +<ul> +<li>Optional parts are placed in brackets <a href="sometimes%20question%20mark"></a></li> +<li>Alternatives can be expressed in-line using parentheses ()</li> +<li>Reptitions (0 or more) are placed inside curly braces {} (sometimes parentheses asterisk ()* )</li> +</ul> + +<p>EBNF can also be rewritten to standard BNF fairly easily.</p> + +<h1 id="Context%20free%20grammars">Context free grammars</h1> + +<h2 id="Properties%20of%20grammars%20(non-terminals)">Properties of grammars (non-terminals)</h2> + +<ul> +<li>Left-recursive: <code>N ::= N ...</code></li> +<li>Right-recursive: <code>N ::= ... N</code></li> +<li>Nullable: <code>expression ::= λ</code></li> +<li>Useless: if a non-terminal can never produce a string of terminal symbols.</li> +</ul> + +<h2 id="Grammar%20transformations">Grammar transformations</h2> + +<ul> +<li>Left factorization: <code>X Y | X Z</code> is transformed to <code>X (Y | Z)</code></li> +<li>Elimination of left-recursion: <code>N ::= X | N Y</code> becomes <code>N ::= X Y*</code></li> +<li>Substitution of non-terminals: for clearer CFGs </li> +</ul> + +<h2 id="From%20tokens%20to%20parse%20tree">From tokens to parse tree</h2> + +<p>Parsing is finding the structure in a stream of tokens. This is done by the parser.</p> + +<p>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.</p> + +<h2 id="First%20sets">First sets</h2> + +<p>The set of all terminal symbols, in order, derived from a sentence S. The empty string λ is never included.</p> + +<h2 id="Follow%20sets">Follow sets</h2> + +<p>The set of terminals that can follow a non-terminal A, where the EOF symbol is $.</p> + +<h2 id="LL(1)%20grammars">LL(1) grammars</h2> + +<ul> +<li>Cannot be left-recursive.</li> +<li>Cannot contain ambiguity.</li> +<li>Some languages have no LL(1) grammar.</li> +<li>λ-free grammars are very easy as you only need to check for the first set.</li> +</ul> + +<h2 id="LR%20grammars">LR grammars</h2> + +<ul> +<li>Can be parsed using an LR algorithm.</li> +<li>Harder to implement parsers for LR than LL.</li> +<li>Can recognize a bigger class of grammars than LL.</li> +<li>LR parsing methods are the most commonly used for automatic tools today.</li> +</ul> + +<h1 id="Lexical%20analysis">Lexical analysis</h1> + +<h2 id="Developing%20a%20scanner">Developing a scanner</h2> + +<p>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. </p> + +<p>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.</p> + +<p>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.</p> + +<h3 id="Lexical%20elements">Lexical elements</h3> + +<ul> +<li>Character set (ASCII vs Unicode)</li> +<li>Identifiers</li> +<li>Operators</li> +<li>Keywords</li> +<li>Elementary data</li> +<li>Noise words</li> +<li>Blank space</li> +<li>Layout</li> +<li>Comments</li> +<li>Delimiters</li> +</ul> + +<p>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.</p> + +<p>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. </p> + +<h3 id="Regular%20grammars&#47;expressions">Regular grammars/expressions</h3> + +<p>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. </p> + +<h3 id="Implement%20a%20scanner%20based%20on%20RE%20by%20hand">Implement a scanner based on RE by hand</h3> + +<ol> +<li><p>Express the ‘lexical’ grammar as RE. Sometimes it is easier to start with (E)BNF and do the necessary transformations.</p></li> +<li><p>For each variant use a switch on the first character by peeking the input stream.</p></li> +<li><p>For each repetition (..)* use a while loop that keeps going as look as the peeking input yields an expected character.</p></li> +<li><p>If there are multiple REs then use a switch to determine which rule is being recognized before following steps 2-3. </p></li> +</ol> + +<ul> +<li>Hand-made scanners are easy for simple token arguments but can be hard and error prone for more complicated grammars.</li> +<li>The task can be automated.</li> +<li>Most compilers are developed using a generated scanner.</li> +</ul> + +<h2 id="Generating%20scanners">Generating scanners</h2> + +<p>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.</p> + +<p>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.</p> + +<h2 id="Performance%20considerations">Performance considerations</h2> + +<p>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.</p> + +<h1 id="Top%20down%20parsing">Top down parsing</h1> + +<p>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.</p> + +<p>Top down parsing example of “Micro English”. This is always done with left derivation.</p> + +<pre><code>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 +</code></pre> + +<p>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. </p> + +<h2 id="Recursive%20decent%20parsing">Recursive decent parsing</h2> + +<p>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.</p> + +<pre><code>private void parseSentence() { + parseSubject(); + parseVerb(); + parseObject(); + accept('.'); +} +</code></pre> + +<p>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.</p> + +<h2 id="Algo%20to%20convert%20EBNF%20into%20a%20RD%20parser">Algo to convert EBNF into a RD parser</h2> + +<p>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. </p> + +<p>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. </p> + +<p>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).</p> + +<h2 id="The%20visitor%20pattern%20(briefly)">The visitor pattern (briefly)</h2> + +<p>For OOP the visitor pattern enbales the definition of a new operator on an object structure without changing classes of the objects.</p> + +<h2 id="LL(1)%20grammars-2">LL(1) grammars</h2> + +<p>A grammar which can be parsed with a top-down parse with a lookahead (in the input stream of tokens) of one token.</p> + +<p>Lecture 7 @ 32:00 for formal definition of LL(1) grammar.</p> + +<h3 id="Table-driven%20LL(1)%20parsers">Table-driven LL(1) parsers</h3> + +<p>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.</p> + +<h1 id="Bottom%20up%20parsing">Bottom up parsing</h1> + +<p>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.</p> + +<ul> +<li>LR(0): The simplest algorithm.</li> +<li>SLR(1): An improved LR(0).</li> +<li>LR(1): LR(0) with extra lookahead token.</li> +<li>LR(k): for k>0 tokens </li> +<li>LALR: “watered down” version of LR(1)</li> +</ul> + +<p>Read through every construction and recognize it at the end. 13:00 Lecture 8.</p> + +<p>There are tools that can automate generating the bottom up parser. 50:00 Lecture 8.</p> + +<h2 id="Terminology%2015:00%20Lecture%208">Terminology 15:00 Lecture 8</h2> + +<ul> +<li>A reduction transforms <code>uwv to uAv</code> if <code>A -> w</code> is a production.</li> +<li>Right sentenial form.</li> +<li>Handle (informally: a production than can be used in reverse without getting stuck).</li> +</ul> + +<h2 id="The%20shift%20reduce%20process%2018:00%20Lecture%208">The shift reduce process 18:00 Lecture 8</h2> + +<p>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.</p> + +<p>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.</p> + +<p>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.</p> + +<p>How is the parse table built? The table is coded as a DFA (28:00 Lecture 8).</p> + +<h3 id="LR(0)%20conflicts">LR(0) conflicts</h3> + +<p>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.</p> + +<h3 id="The%20shift-reduce%20problem">The shift-reduce problem</h3> + +<p>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.</p> + +<h2 id="LR(0)%20vs%20SLR(1)">LR(0) vs SLR(1)</h2> + +<p>SLR(1) looks at the symbol after the handle (follow set). This means fewer reduce-actoins and therefore removes a lot of potential conflicts.</p> + +<h2 id="LR(1)">LR(1)</h2> + +<p>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).</p> + +<h2 id="LALR(1)">LALR(1)</h2> + +<p>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).</p> + +<h2 id="Parser%20conflict%20resolution">Parser conflict resolution</h2> + +<p>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).</p> + +<p>Parsing conflicts must be fixed. You cannot rely on the resolution rule.</p> + +<h1 id="Abstract%20syntax%20trees%20(AST)">Abstract syntax trees (AST)</h1> + +<p>Like a parse tree but with some details omitted.</p> + +<p>Semantic actions and values 5:00 Lecture 9. +Synthesized and inherited attributes.</p> + +<p>AST must be concise and sufficiently flexible. AST is typically constructed bottom up. Lists of siblings are typically generated by recursive rules.</p> + +<p>It should be possible to unparse an AST (reconstruct the source from an AST).</p> + +<h2 id="Single-pass%20vs%20multi-pass%20compilers">Single-pass vs multi-pass compilers</h2> + +<p>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.</p> + +<p>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.</p> + +<h2 id="Visitor%20pattern">Visitor pattern</h2> + +<p>35:00 Lecture 9. </p> + +<h2 id="Contextual%20analysis">Contextual analysis</h2> + +<p>Identification and type checking are combined into a depth-first traversal of the AST.</p> +<p class="footer"><a href="/">adamski.wtf</a></p> +</html> |