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.