Extended lexical analysis

1 files changed, 87 insertions, 5 deletions

diff --git a/website/content/slides/02_lexical_analysis/_index.md b/website/content/slides/02_lexical_analysis/_index.md
index 6a0513a..bc7c1f8 100644
--- a/website/content/slides/02_lexical_analysis/_index.md
+++ b/website/content/slides/02_lexical_analysis/_index.md
@@ -26,9 +26,25 @@ DFA to recognize the tokens.
 - *a* matches a
 - *ab* matches ab
 - *a|b* matches a or b
-- *a\** matches a zero or more times
+- `a*` matches a zero or more times
 - *a?* matches a or *empty*
 - *[0-9]* matches any digit
+- *a{m,n}* matches between *m* and *n* *a*s
+
+---
+### What we can do with regular expressions
+
+- We can define regular language.
+- We can recognize words from regular language.
+- We can find patterns in sequence of characters.
+
+---
+### What we can't do with regular expressions
+
+- We can't recognize a{n}b{2n}
+- We can't recognize if something is valid HTML
+- We can't recognize if something is valid (place here almost every programing
+  language)
 
 ---
 ## Token
@@ -57,7 +73,7 @@ Typical tokens are:
 > looking at the first character
 
 ---
-## How to implement a token
+## How to implement a token?
 
 ---
 ### What goes into a token
@@ -119,6 +135,13 @@ regexes that define the language.
 
 - generate it with a tool
 - write one by hand
+- for an existing language
+    - search in google: "Lexical grammar for *language you prefer*"
+    - it might be in a format ready for some tool
+- for a custom language write down on paper the lexical grammar
+    - define your keywords
+    - rules for identifiers, numbers, strings, ...
+    - ...
 
 ---
 #### Generate a lexer
@@ -134,6 +157,7 @@ be stored.
 - *re2c* - generates code for the automaton in *C*
     - claims easier debuggability, but still the generated code is pretty
       complex
+- some parser generators have built-in lexer as well
 
 ---
 ### Flex
@@ -173,15 +197,68 @@ be stored.
     {ID}        printf("An identifier:%s\n", yytext);
 
 ---
-# TODO: Link to input
+### Input
+
+https://github.com/SofiaCPP/IPL/blob/master/demo/flex/JavaScript.flex
+
+---
+### Output
+
+https://github.com/SofiaCPP/IPL/blob/master/demo/flex/lex.yy.c
+
+---
+### Disclaimer
+
+> Default options used!
+
+`flex` is quite customizable, either by options, or by defines for the file.
+We have used the default options for simplicity.
+
+---
+### Debugging tool generated code
+
+- pretty much impossible in the generated code
+- the tool is created to allow defining the lexer in high-level language
+
+> Debug the high-level language definition, not the generated code
 
 ---
-# TODO: Link to output
+## Writing a lexer by hand
+
+1. Start with the lexical grammar
+2. Read input symbol by symbol, for each symbol follow rules that are still
+   possible
+3. Continue reading until no more input is possible -> emit the last possible
+   token
 
 ---
 ## Writing a lexer by hand
 
-# TODO: EXPAND
+For our sample lexical grammar:
+
+    while (c != '\0') {
+        if (isdigit(c)) {
+            emit_number();
+        }
+        else if (c >= 'a' && c <= 'z') {
+            auto word = read_word();
+            if (keyword(word)) {
+                emit_keyword(word);
+            } else {
+                emit_identifier(word);
+            }
+        }
+        else { error(); }
+    }
+
+---
+### Keyword vs identifier
+
+> The set of keywords is fixed and finite.
+
+- it is possible to create a perfect hash
+    - gperf is a tool for that
+- use a good data-structure that will allow for very fast look-up
 
 ---
 ### Note
@@ -193,5 +270,10 @@ Some languages do not have/need grammar for compilation
 - Forth
 
 ---
+### Homework
+
+Create a xxx2html syntax highlighter for a language of your choice.
+
+---
 # ?