[blog/seoc] Mostly finished the second section, and started on the third

1 files changed, 256 insertions, 61 deletions

diff --git a/src/blog/sane-explanation-of-compilers-and-lex-yacc/index.md b/src/blog/sane-explanation-of-compilers-and-lex-yacc/index.md
index 816e59f..fea71ee 100644
--- a/src/blog/sane-explanation-of-compilers-and-lex-yacc/index.md
+++ b/src/blog/sane-explanation-of-compilers-and-lex-yacc/index.md
@@ -50,8 +50,6 @@ There are three main layers to a compiler:
 
 ## 1. How do we understand code?
 
-The simplest programming languages would just assign names to different processor instructions, so writing "Store\_value\_from\_A\_into\_B" is actually instruction number 47, however this abstraction isn't high enough.
-
 Syntax in current programming languages can be quite sophisticated and ambiguous. A weird example (taken from [wikipedia](https://en.wikipedia.org/wiki/Most_vexing_parse)) with C++ would be:
 
 ```
@@ -65,10 +63,11 @@ since it could be interpreted either as a:
 1. declaration of variable `i`, which is initialized with the value of `int(d)` (which just casts `d` to an integer), or
 2. function declaration, since superfluous parenthesis around function parameter declarations are allowed (meaning it is treated as `int i(int d)`)
 
-Note that I'm talking about syntax, not semantics.
-Compiled programming languages are meant to associate specific templates of code to their corresponding machine instructions, there is no underlying meaning to code.
-In natural languages, you could construct a sentence which follows all gramatical rules, but is absolute nonsence, devoid of any meaning, like ["Colorless green ideas sleep furiously"](https://en.wikipedia.org/wiki/Colorless_green_ideas_sleep_furiously).
-The problem of semtantics, logical sense, is extremely difficult and isn't really "solved", however analyzing syntax is.
+Note that I'm talking about syntax, the valid selection and layouts of characters, and not semantics, the underlying meaning.
+Compiled programming languages associate specific templates of code (text) to their corresponding machine instructions, there isn't anything special you need to understand in a piece of code.
+In natural languages, you could construct a sentence which follows all gramatical rules, but is absolute nonsence, like ["Colorless green ideas sleep furiously"](https://en.wikipedia.org/wiki/Colorless_green_ideas_sleep_furiously).
+
+The problem of semtantics is extremely difficult, however in our case we only care about syntax.
 And this is where math comes into play.
 
 ### Math
@@ -80,7 +79,7 @@ There is a special field in mathematics that deals with syntactical analysis: [f
 Although learning even the basics merits a whole university course, I'll still try to roughly explain what's important.  
 This field works primarily with strings via the help of two (relevant for our purposes) instruments: regular expressions and grammars.
 
-#### Regex
+#### Regular expressions
 
 You might've heard or even already used regexes in a text editor.
 They're small text expressions which specify a text pattern.
@@ -123,7 +122,12 @@ At their very base, such a pattern is created with the following rules:
   + "ac**hievem**en**ts**".
 
 - [Kleene star](https://en.wikipedia.org/wiki/Kleene_star) - repeat the preceding letter or group, 0 or more times.  
-  Considering the name, this is specified with an asterisk, `accents*` will match
+  An asterisk is used to mark this operation (hence the name, "Kleen **star**").
+
+  ```regex
+  accents*
+  ```
+  will match
 
   + "accent"
   + "accent**s**
@@ -190,13 +194,17 @@ Let's say you want to be able to have math expressions in your language, you can
 - however `()3*3)-(2^3()+2` isn't valid
 
 Such a structure is recursive, because it can contain "itself", `1+2` can be a standalone math expression, but it can also be contained in another expression, like `(1+2)*3`, which itself could be inside another bigger expressions and so on.
-That is where grammars come into play, they allow us to define a structure which can "contain" itself.
+For this task we have a whole separate tool: grammars.
 
-The syntax is different from regexes: a grammar is divided into rules, each rule is named and specifies an expression.
-Expressions are a concatenation of strings and/or names.
-Names aren't strings that will appear in our matched strings, the idea is that a name will be replaced with it's expression, they're a bit like placeholders.
+The syntax is different from regexes: a grammar is divided into (production) rules, each rule is named and specifies an expression.
+Expressions are a concatenation of strings and/or names[^terminals-and-nonterminals].
+Names won't appear in our matched strings, the idea is that a name will be replaced with it's expression, kind of like a placeholders.
 Additionally, there can be multiple rules with the same name, meaning a rule can be replaced by different stuff at any point of the string generation.
-Generally we write rules in the form `Name -> Expression`.
+
+Always one name is chosen to be the starting point, and generation continues from there.
+In math literature, generally we write rules in the form `Name -> Expression`[^grammar-syntax], and often names are a single capital letter.
+Additionally, often the starting name is called `S`.
+Finally, in future examples, I'll use the thick arrow `🡆` to show derivations, how the generated string looks after one or two replacements of the name with one of it's expressions.
 
 For an example, with the grammar
 
@@ -205,7 +213,7 @@ S -> aSb
 S -> cc
 ```
 
-we can generate the string `aaaaccbbbb` (`🡆` shows every step, where a name is replaced):
+we can generate the string `aaaaccbbbb` (remember, our starting point is `S`):
 
 ```grammar+
 S 🡆 aSb 🡆 aaSbb 🡆 aaaSbbb 🡆 aaaaSbbbb 🡆 aaaaccbbbb
@@ -217,8 +225,9 @@ or `accb`:
 S 🡆 aSb 🡆 accb
 ```
 
-where a and b are just characters.
-To simplify our lives, usually rules with the same name are merged into one rule, separated by vertical bars (`S -> aSb | cc`), this is pretty much alternation but in a different context.
+where a, b and c are just english characters.
+To simplify our lives, often rules with the same name are merged into one rule, separated by vertical bars (`S -> aSb | cc`).
+This is practically alternation but in a different context.
 
 As for our math expressions, we could create something like this:
 
@@ -233,21 +242,21 @@ which will sucessfully be able to match (generate) `((3 * 3) - (2 ^ 3)) + 2`:
 E 🡆 E + E 🡆 (E) + N 🡆 (E - E) + 2 🡆 ((E) - (E)) + 2 🡆 ((E * E) - (E ^ E)) + 2 🡆 ((N * N) - (N ^ N)) + 2 🡆 ((3 * 3) - (2 ^ 3)) + 2
 ```
 
-but there are no expressions (and rules) that allow `()3+3()` or `)3(-6` to be "matched".
+but there are no expressions (rules) that allow `()3+3()` or `)3(-6` to be "matched".
 
-### Using regular expressions and grammars in the real world
+### Lexers and parsers
 
-You might've noticed that for `N` we use three dots and the note "all possible numbers" to signify that N can be any positive whole number.
-If we want to be more precise, we really should formally define the grammar:
+You might've noticed that for `N` I use three dots and the note "all possible numbers" to signify that N can be any positive whole number.
+In practice we need formally define that grammar:
 
 ```grammar
 N -> 0 | 1 | 2 | ... | 9 | 0N | 1N | 2N | ... | 9N
 ```
 
 With this you might've realised that grammars can do anything a regular expressions can: concatenation and alternation are "built-in", and the Kleene star can be done with another rule in the form `R -> strR | str`[^regular-grammars].
-The reason we use both is that grammars are a lot harder to implement, harder to work with and slower than regexes.
+The reason we use both is that grammars are significantly slower and more complicated in code than regexes.
 
-#### Practical problems with grammars
+#### Implementational difficulties with grammars
 
 Implementing (very roughly) the regular expression `acce(n | p)*t` is quite easy:
 
@@ -270,12 +279,14 @@ bool matchesp(string str) {
 }
 ```
 
-In brief, we loop over the given string and the regex at the same time, checking if character values match on every index.
-That is until we reach "\_", which I use to specify we're in the `(n | p)*` part of the regex.
-Here, we loop until we've matched all "n"s and "p"s, after which we skip over this part and continue checking for equal characters.
+In brief, for concatenated characters we do a simple comparison per character.
+When we reach "\_", which I use to specify we're in the `(n | p)*` part of the regex, we do comparisons with the characters n and p as much as we can, after which we continue as normal.
 
-Even a programming novice could implement something like this, and it's pretty quick, simple, doesn't use a lot of resources.
-Certain grammars have the same qualities too, `S -> aSb | cc` can be implemented with a very simple recursion:
+Of course, this version only supports one regular expressions, however a "proper" implementation would look conceptually similar: a couple of different loops and equality checks, with maybe an additional array or two.
+The huge benefit is that that loops and arrays are stupid fast, a (simple) C++ for loop could be translated into [a handful of processor instructions](https://godbolt.org/#g:!%28%28g:!%28%28g:!%28%28h:codeEditor,i:%28filename:'1',fontScale:14,fontUsePx:'0',j:1,lang:c%2B%2B,selection:%28endColumn:16,endLineNumber:6,positionColumn:16,positionLineNumber:6,selectionStartColumn:16,selectionStartLineNumber:6,startColumn:16,startLineNumber:6%29,source:'//+Type+your+code+here,+or+load+an+example.%0Aint+f%28int+num%29+%7B%0A++++for+%28int+i+%3D+1%3B+i+%3C+100%3B+i%2B%2B%29+%7B%0A++++++++num+*%3D+100%3B%0A++++%7D%0A++++return+num%3B%0A%7D'%29,l:'5',n:'0',o:'C%2B%2B+source+%231',t:'0'%29%29,k:50,l:'4',n:'0',o:'',s:0,t:'0'%29,%28g:!%28%28h:compiler,i:%28compiler:g122,deviceViewOpen:'1',filters:%28b:'0',binary:'1',binaryObject:'1',commentOnly:'0',demangle:'0',directives:'0',execute:'1',intel:'0',libraryCode:'0',trim:'1'%29,flagsViewOpen:'1',fontScale:14,fontUsePx:'0',j:1,lang:c%2B%2B,libs:!%28%29,options:'',selection:%28endColumn:1,endLineNumber:1,positionColumn:1,positionLineNumber:1,selectionStartColumn:1,selectionStartLineNumber:1,startColumn:1,startLineNumber:1%29,source:1%29,l:'5',n:'0',o:'+x86-64+gcc+12.2+%28Editor+%231%29',t:'0'%29%29,k:50,l:'4',n:'0',o:'',s:0,t:'0'%29%29,l:'2',n:'0',o:'',t:'0'%29%29,version:4).
+
+On the other hand, usually grammars are more complicated and resource-intensive.
+Certain ones are simple enough to implement, like `S -> aSb | cc`:
 
 ```cpp
 bool matchesp(string str) {
@@ -288,9 +299,7 @@ bool matchesp(string str) {
 }
 ```
 
-The only caveat here could be making sure the code is a tail recursion, as to not cause any stack overflow problems.
-
-However lets discuss the grammar `S -> aSbSa | cc`.
+However think about more complicated cases[^context-free-grammars], like `S -> aSbSa | cc`.
 Implementing this one is quite a bit more difficult, since we don't know where `b` is located on the first iteration, it could either be the 4th character `accb...a` or the 9th `aaccbccab...a`.
 Searching for it is also complicated, it could be the first, the last or any other `b` in the middle of the string.
 
@@ -304,73 +313,259 @@ how would it generate `n + n * n`?
 There are two completely valid ways to do so:
 
 ```grammar+
-E 🡆 E + E 🡆 E + E * E 🡆 n + n * n
+E 🡆 E + E 🡆 n + E * E 🡆 n + n * n
 ```
 
 ```grammar+
-E 🡆 E * E 🡆 E + E * E 🡆 n + n * n
+E 🡆 E * E 🡆 E + E * n 🡆 n + n * n
 ```
 
-#### A middle ground
+How exactly we deal with these problems comes later, for now the takeaway is that we have to try and use regular expressions wherever we can, and leave grammars as a bit of a last resort.
+
+#### Usage in the real world
+
+Let's think a bit more about what grammars are supposed to do: they're really good at handling structure, especially recursive structure, so it's best if we use them only for that.
+What I'm trying to say is, our math expression grammar (from [here](#grammars)) shouldn't really care if we're trying to sum integers or floats or chars[^static-typing], it's important how everything is layed out and that our operations are done with numbers.
+
+This is why we're going to separate and generalize the code into [tokens](https://en.wikipedia.org/wiki/Lexical_analysis#Token), basically into building blocks.
+As a rough example, we want `1 + (2 * 3)` to be transformed into `NUMBER + (NUMBER * NUMBER)`, `int var = 13;` into `TYPE NAME = NUMBER;` and so on, where "TYPE", "NUMBER" and "NAME" are tokens.
+Now we're reducing the amount of "objects" our grammars need to work on: from all characters to many (but significantly fewer) tokens and some really small amount of characters.
+Of course, each token will contain it's name (NUMBER, TYPE, ...) and it's value, since we aren't trying to change the code, but our grammars will work with the token names directly and just output the values at the very end.
+Usually we identify at least six token types:
+
+- identifiers: variable and function names for example
+- keywords: `if`, `while`, `for`, `return`, ...
+- separators: braces, `;`
+- operators: `+`, `-`, `<=`
+- literals: numbers, strings, characters
+- comments
+
+As you might've noticed, here we can use regular expressions, grouping consequtive characters is what regexes are good for.
+Additionally, we're going to be reading the file, a decently slow operation, only once and for a comparatively very little time.
+
+In the compiler front-end, the part that implementes our regular expressions is called the "lexer", and the part that implements our grammars - the "parser".
+In the last section we already talked about how easy implementing regexes (lexers) is and how difficult implementing grammars (parsers) is, but we didn't talk about actual impelementations of parsers.
+
+#### Parsing algorithms
+
+Proper algorithms that "implement" grammars are kind of complicated, and most can handle only specific types of grammars.
+Generally we categorize them into:
+
+- [top-down](https://en.wikipedia.org/wiki/Top-down_parsing) algorithms, which work in the way we've been talking about grammars: start with a name and replace it with it's expression, and continue replacements until we have no more names
+- [bottom-up](https://en.wikipedia.org/wiki/Bottom-up_parsing) algorithms, where we do the opposite: for each substring we find from which rule it could've come from, replace it with the corresponding name, and continue upwards like that, until we reach the starting name
+
+Furthermore, if our algorithms allow for ambiguity (meaning we can replace a name with any one of multiple expressions), we divide them into:
+
+- left-most derivation algirithms, where we choose the left-most valid expression
+- right-most derivation algorithms, where we chose the right-most valid expression
+
+The advantage and disadvantages of every type kind of depend on the exact algorithm and grammar.
+Looking at some of the more famous ones:
+
+1. [LL](https://en.wikipedia.org/wiki/LL_parser): top-down left-most derivations algorithm that can parse only specific types of grammars.
+   In these grammar, every expression is uniquely identifiable by just looking at the characters (tokens) in the very beginning.
+   If an LL(k) algorithm can parse the given grammar, we say the grammar is a "LL(k) grammar".
+   An "LL(k)" grammar, by extension, is any grammar where each expression is uniquely identifiable by just looking at the first k tokens.  
+   As an example, the grammar:
+
+   ```grammar
+   F -> a
+   S -> F | (S + F)
+   ```
+
+   is LL(1).
+   With the input `(a + a)`:
+
+   - we start with S, we peek one symbol forward, to the `(`, and we find we need to match with the second expression for S
+   - after matching the one symbol, we peek at `a`, we find that only the first expression for S works
+   - and so on
 
-#### How do we use them for compiling code
+   The grammar
 
+   ```grammar
+   B -> b
+   C -> c
+   S -> aaB | aaC
+   ```
+
+   is LL(3).
+   For the input `aab`, if we look at the first two "a"s, we still don't know which rule to use: `aaB` or `aaC`.
+   However if we look at the third symbol, "b", then we can determine that we need `aaB`.
+
+2. [LR](https://en.wikipedia.org/wiki/LR_parser): bottom-up right-most derivations algorithm.
+   It is slightly reminiscent to LL, parsing only specific grammars and needing to peek forward (lookahead; which also means LR(k) is similarly defined), but is significantly more powerful.
+   However, the "normal" LR parser requires a lot of memory, which spurred it's variations - the [SLR](https://en.wikipedia.org/wiki/Simple_LR_parser), [CLR](https://en.wikipedia.org/wiki/Canonical_LR_parser) and most importantly:
+
+3. [LALR](https://en.wikipedia.org/wiki/LALR_parser)  
+   These memory optimizations, however, came at a cost: lower grammar parsing power, though LALR can work with the most grammars out of all the alternatives and still beats LL.
 
 #### Abstract syntax tree
 
-I briefly mentionted that grammers require more resources than regexes, why is that?
-Well, 
+We already decided that the lexer will output tokens (and characters) to the parser, but we didn't talk about what the parser is supposed to output.
 
-### Lexers and parsers
+## Implementing a front-end
+
+If you want, you could implement your own lexer and parser manually, but few people do, there are already very well made tools for that.
+Furthermore, at the end of the day, we want our compiler to be a singular program, or at least every layer to be a singular program.
+[Compiler-compilers](https://en.wikipedia.org/wiki/Compiler-compiler) are tools that create parsers (and more) from their normal formal definition.
+
+The two popular ones from the old days are lex and yacc.
+lex is a lexer generator and yacc is a LALR parser generator, both of which generate a corresponding C implementation of the given regular expressions and grammars.
+
+### lex
+
+Lex is the original program, from 1975, in the modern day it's successor/implementation is the opensource [flex](https://github.com/westes/flex).
+
+A lex source file is divided into three parts:
+
+```
+%{
+// C code that will be put in the program verbatim
+%}
+
+/* Definitions */
+
+%%
+
+    /* Rules */
+
+%%
+
+// C code
+```
+
+where `%{%}` is used for includes and declarations, the rules are your regular expressions and the C code is the general logic of the lexer.
+Usually you wouldn't write anything in the C code section, the defaults are fine, but you'll probably need to do one or two includes in the `%{%}` section.
+
+Rules are in the form `regex { C_code }`.
+To simplify your life, you can write only the regex or a part of it inside the "definitions" part of the file, and give it a name to use later.
+Referencing those names in later regexes is done by surrounding them in curly braces. 
+Usually the `C_code` in the regex would be a return (more commonly called "emit") of a token, which will be available in a header file, but more on that later.
+
+#### Example 1
+
+Let's look at a very simple example program: every whole number is printed as "NUMBER", while everything else is printed as-is:
+
+```lex
+%{
+%}
+
+%%
+
+[0-9]+ { printf("NUMBER"); }
+[A-z]+ { printf("%s", yytext); }
+
+%%
+```
+
+The syntax `[0-9]` is the same as `(0 | 1 | ... | 9)`, it is available in all modern regexes.
+Note that inside every regex's "body" you have an assortment of variables already set, one of them being `yytext` which is just the whole match.
+Additionally lex matches the longest possible match, so if we had a rule `[0-z]`, only it will be matched.
+
+If this file is located in `lexer.l`, we can compile it into a working lexer like this:
+
+```bash
+flex lexer.l && gcc lex.yy.c -lfl
+```
+
+Of course, you can use your lex implementation or C compiler of choice.
+Now, if you run `./a.out` you would get a prompt, every line you write will be lexically analyzed and in our case, everything will be printed out.
+Entering
+
+```
+The number 10 changed to 8, 38, and 19 sequentially, before becoming 0.
+```
+
+will output
+
+```
+The number NUMBER changed to NUMBER, NUMBER, and NUMBER sequentially, before becoming NUMBER.
+```
+
+#### Example 2
 
-Now that we're armed with all of that math, we'll get to coding.
-The program/part of a compiler front-end that handles the regular expresions is called a lexer, and the one that handles grammars - parser.
-The job of the lexer is to split our code into strings the specify what it is (a string, a number, a type name, a function name, ...; those are called tokens) and then the grammar will use those strings in it's rules.
+Now let's try something more sophisticated, let's surround numbers and strings in HTML tags, the stuff that power webpages.
+We would want numbers to be in the format:
 
-So, our pipeline looks something like:
+```
+<span class="num">number</span>
+```
+
+and strings:
 
 ```
-code -> LEXER -> tokens -> PARSER -> abstract syntax tree
+<span class="str">string</span>
 ```
 
-#### lex
+We'll define numbers as both whole digits and floating point numbers (with sign) and strings can be surrounded in either single or double quotes.
 
-How do we handle regular expressions?
-The manual way is with a loop, we're going over the code and the regex at the same time.
-We read both character by character, comparing them, but when we hit something special in the regex (`(,),*,|`), we handle it.
-For example if we hit an opening brace, rather than compare it to the current character, we would read the regex forward until the closing brace, finding what our next possible character (string) could be, then comparing every option with the current character.
+```lex
+%{
+%}
+
+/* Only multiline comments are supported, not comments that start with // */
+/* This is a definition, it's in the format "NAME regex" */
+DIGIT [0-9]
 
-However nobody does that, and you shouldn't too.
-There is already a widely used tool called [lex](https://en.wikipedia.org/wiki/Lex_%28software%29), although usually [flex](https://en.wikipedia.org/wiki/Flex_%28lexical_analyser_generator%29) is used as an open-source alternative.
+%%
+    /* Comments in here have to be indented, otherwise you'll get an error */
+    /* ? means 0 or 1 of the preceding group*/
+    /* + means 1 or more of the preceding group*/
+    /* the backward slashes are used because . and + have special meaning in regexes*/
+[\+-]?{DIGIT}+(\.{DIGIT}+)?   { printf("<span class=\"num\">%s</span>", yytext); }
 
-A flex file is compiled into a C program, meaning if you want to change a regex you'll have to recompile.
-It is divided into three parts:
+    /* [^] is a group of characters, like [], however it specifies "all characters except the ones given"*/
+    /* this way if we have "This is a string with " three quotes" it's not going to match the whole thing*/
+\"[^"]*\"|'[^']*'             { printf("<span class=\"str\">%s</span>", yytext); }
 
+%%
+```
+
+With the input
+
+```
+John said 10 times "2 + 2 = 5" but '2 + 2 = 4'!
 ```
+
+we'll get
+
+```
+John said <span class="num">10</span> times <span class="str">"2 + 2 = 5"</span> but <span class="str">'2 + 2 = 4'</span>!
+```
+
+You've probably already noticed that the number inside the strings aren't matched, because the string rule results in a longer match.
+In programming languages this is fine, since strings are quite often "self-contained" objects, there isn't anything in them that you would need to match.
+
+### yacc
+
+Similarly to lex, yacc originates from 1975, and it's modern replacement is [GNU Bison](https://www.gnu.org/software/bison/).
+
+A yacc file looks very similar to a lex one:
+
+```yacc
 %{
 // C code that will be put in the program verbatim
 %}
 
-// Definitions
+/* Settings */
 
 %%
 
-    // Rules
+    /* Rules */
 
 %%
 
 // C code
 ```
 
-where `%{%}` is used for includes and declarations, the rules are your grammars and the C code is the general logic of the lexer.
-Usually you wouldn't write anything in the C code section, and do one or two includes in the `%{%}` section.
+[^how-did-we-get-here]: Though it's obvious, I would like to point out that modern compilers are most often written in languages that are themselves compiled. You might ask yourself "where did the first compiler come from?" The answer is simple: it was written with "numbers", with direct instructions to the processor, from the time when computers were simple enough that *all* programming was done with CPU instructions.
+
+[^terminals-and-nonterminals]: Formally, we call the rule "names" nonterminals, the idea being that all normal characters, that could appear in our string, are called terminals, since they would terminate replacement and string generation. For the purposes of this post, I won't use the formal names, with the hope that using less terminology will increase understandability.
 
-Rules are in the form `regex { C_code }`.
-To simplify your life, you can write a regex or a part of a regex inside the definitions part of the file, and give it a name to use later (you'll need to surround them in curly braces when wanting to reference them).
-Usually the `C_code` in the regex would be a return for a token (more on that in yacc), which will be available in a header file, that you'll need to have included in the flex file.
+[^grammar-syntax]: This is pretty much the mathematical notation, often in CS the Backus-Naur form is used, but I find that a bit harder to read. You might also make the argument that I should use a proper unicode arrow symbol, like `→`, but `->` is way more convinient.
 
-#### yacc
+[^regular-grammars]: Such grammars are called [regular grammars](https://en.wikipedia.org/wiki/Regular_grammar), more formally, every rule has to contain at most one name and that name must be at the start or end of the string characters.
 
-[^how-did-we-get-here]: Though it's obvious, I would like to point out that modern compilers are most often written in languages that are themselves compiled. You might ask yourself "where did the first compiler come from?" The answer is simple: it was written with "numbers", with direct instructions to the processor, from the time when computers were simple enough that *all* programming was done with CPU instructions.
+[^context-free-grammars]: Be careful about cases that are too complicated, the grammar I'm showing is "context-free", but that topic is way beyond the scope of this post.
 
-[^empty-string-isnt-a-number]: The Kleene star specifies that something can be repeated **0** or more times, so in the case of this regex, the empty string "" will also be a number. In math, usually a plus as a supscript is defined, so 5* means 0 or more 5s, while 5^+ is 1 or more 5s. In regexes we just put a + next to the repeated string.
+[^static-typing]: Yeah yeah, in a statically typed language you might not be able to do operations on doubles and integers at the same time, but you get the point.