It returns two things, an identifier for the token it just read and possibly some sort of value for it.

We use flex for this. It takes multiple regex rules and for each regex it returns a token and its value.

For each rule, it matches tokens based on the Aho-Corasick algorithm. This is basically a preprocessing table for multiple words, similar to KMP algorithm.

vector<int> jump(const string &s) {
    int len = 0;
    vector<int> v(s.size());
    v[0] = 0;
    for (int i = 1; i < s.size(); i++) {
        if (s[len] == s[i]) {
          len++;
          v[i] = len;
        }
        else if (len != 0) {
          len = v[len - 1]; // check the previous smaller prefixes of the length 
                            // matched
          i--; // we don't want to incrememt without it matching
        } else {
          v[i] = 0; // Can't be matched, has to be zero
        }
    }
    return v;
}

vector<int> kmp(const string &text, const string &pattern) {
    vector<int> jumps = jump(pattern);
    vector<int> result;
    int text_idx = 0, pat_idx = 0;
    while (text.size() - text_idx >= pattern.size() - pat_idx) {
        if (text[text_idx] == pattern[pat_idx]) {
            pat_idx++; text_idx++;
        }
        if (pat_idx == pattern.size()) {
            result.push_back(text_idx - pat_idx + 1);
            pat_idx = jumps[pat_idx - 1];
        }
        else if (text_idx < text.size() && text[text_idx] != pattern[pat_idx]) {
            if (pat_idx) {
                pat_idx = jumps[pat_idx - 1];
            } else {
                text_idx++;
            }
        }
    }
    return result;
}

To show that it's linear time, if the increment does not happen for some k iterations, we have already matched the length of atleast k of the pattern and then moved to this spot in the pattern and text. Therefore, it can only do at most ~ 2k iterations for a segment of length k. Hence it is linear in time.

This matches a pattern in a text. We can extend this idea to a DFA for multiple words and transitions based on the input character to achieve what's called as the Aho Corasick automaton.

Usually the longest match is picked. This is also true in (f)lex. In case two of the regexes have the same length, the one above gets matched.

All of this was for theoretical discussion based on string matching. Actual matching is done based on regex rules. There is a conversion from the regex to a DFA using a syntax tree.

We first make the syntax tree of the regex followed by a meta symbol (in this case #).

We also assign a number to each of the leaves.

• firstpos is the set of positions where the current node's subtree would start. For * it will be the same as its child, for concat it'll be the lesser of the two. For or node it will be the union of the two. For concat if the first one can null then it's a union.
• lastpos is where they end. Rules are the same. For concat if the second one is nullable then it's a union.
• followpos is the number that would immediately follow the token represented by the current node. If a and b are concatenated, then firstpos of b is the followpos for lastpos of a. For star node it's the firstpos of the same node. For or node you need to go up.

Now the DFA transitions are as follows:

1. Take the root and mark its firstpos as the unmarked state
2. While there is an unmarked state s, mark the state s.
3. For each leaf symbol a (the input letter in the regex) in s, mark a transition from s to the union of followpos(p) where p are the leaf nodes corresponding to a. So if the state s has firstpos 123, with 1 and 3 being a, then transition on reading a to \(\bigcup followpos(p)\) where p is 1 and 3 in this case

There are many kinds of parsers. All of them are supposed to take a Context Free Grammar (or rather, a restriction on it) and recognise programs that conform to it.

A CFG has a set of terminals called tokens. These are what form the bottom rung of the CFG rules.

These compose in a certain way to form rules called productions. A non-terminal is any other token that is not a terminal (i.e. not returned by the lexer) and is a particular order of other terminals or non-terminals in a specified order.

list -> list + digit | list - digit | digit
digit -> 0 | 1 | 2 | ... | 9

A production is for a non-terminal if it is on the LHS of the rule, also known as the head. The RHS of the same rule is called the body of the production. A start-symbol is one which is where the parsing starts. A string is said to be derived from a grammar if we can make replacements in the start symbol many times by replacing a non-terminal with the body of the non-terminal's production.

A parse-tree is what is formed when you apply the production rule substitutions to derive a string. Needless to say, there can be multiple parse trees for a single string if the grammar allows it. Such grammars are called ambiguous.

• Do a DFS in the parse tree (preorder)
• Find the leftmost derivation at each instant
• Generally does recursive descent which backtracks

• Special case is LL(k) which does predictive parsing based on a parse table.

  for each production in \(A \rightarrow X_1...X_k\)

  1. for \(i = 1\) to \(k\)
     1. if \(X_i\) is a nonterminal call corresponding function
     2. else if \(X_i\) is the next symbol advance input
     3. else go back one token (yyless) and break
  2. if \(A\) matches break;
  3. else current input position is saved

• Parsing is aided by FIRST and FOLLOW sets which allow the parser to choose which production to apply.
• First \(\alpha\) is the set of terminals that begin strings when derived from \(\alpha\)
  • If \(\alpha \xrightarrow{\text{*}} \epsilon\) , that is also there in the first set
• Follow is the set of terminals that can appear to the right of \(\alpha\)
  • If \(S \xrightarrow{\text{*}} \alpha A \beta B\) then follow of \(A\) contains \(\beta\)
  • If \(S \xrightarrow{\text{*}} \alpha A B \beta\) then follow of \(A\) contains First \(B\)
    • If \(B\) also has \(\epsilon\) in its first, then follow of \(A\) also contains \(\beta\)
  • If \(S \xrightarrow{\text{*}} \alpha A\) then follow of \(A\) contains follow of \(S\)
    • \(S \xrightarrow{\text{*}} AB\) and \(B\) is nullable then follow of \(A\) contains follow of \(S\)

Reverse derivation happens from rightmost. Basically, we have the tokens and we combine or reduce them to non-terminals. Hence called LR parsing

A handle is a substring of the production that can be reduced into a non-terminal. This will always be at the top of the stack.

• Shift reduce conflicts appear when the handled can be reduced and another token shifted can also lead to a new reduction. Basically the tail of a production is also a reduction.
• Reduce reduce happens when two different lengths of the top can be reduced to something.

Shift and reduce, what else do I even say? Every token can be associated with a semantic value, which is like an action in Bison.

Shift reduce decisions are made by generating a set of states that keeps track of where we are in the rule.

This is how we start.

If [A → α . X β] is in itemset I, then GOTO(I, X) is the closure of the itemset [A → α X . β]. For instance, GOTO(I0, E) is {E' → E ., E → E . + T}.

Depending on what we will encounter next, the automaton transitions.

How is the actual parsing done? We start with the initial state I0. We encounter a terminal and then go to the corresponding state in the automaton. Over there we see that the next token we got from the lexer either has a rule going from the current state to another state (shift), or is in the FOLLOW of the topmost token currently. This is checked via the dot in the states.

Shift-reduce happens when there is a transition from one state on encountering a term and it is also there in the follow of the same term for that state.

Reduce-reduce happens when you can go back to different states while reducing and more than one of them contribute to the same token in the follow of the current state.

Parse with lookahead when creating the automaton. This allows for more precise parsing and lets you write more ambiguous grammar that lets you get better results and cleaner results or some shit like that.

Each attribute must either be:

• synthesized
• inherited
• For a production \(A \rightarrow X_1X_2...X_n\) with inherited attributes \(X_i.a\) computed by an action, the rule may use only
  • inherited attributes from \(A\)
  • either inherited or synthesized attributes \(X_j\) for \(j < i\)

This is mostly only used with a top-down parser.

These are used when doing bottom-up parsing. In fact, bottom-up parsing exclusively makes use of S-attributed SDTs. This is because it does not have the parent node at all. Midrule actions are basically resolved to empty non-terminals that allow the parser to treat it as a postfix SDT.